第C++實現(xiàn)LeetCode數(shù)組練習(xí)題目錄1、存在重復(fù)元素2、最大子序和3、兩數(shù)之和4、合并兩個有序數(shù)組5、兩個數(shù)組的交集II6、買賣股票的最佳時機7、楊輝三角8、重塑矩陣9、有效的數(shù)獨10、矩陣置零總結(jié)

1、存在重復(fù)元素

排序數(shù)組，之后遍歷是否有重復(fù)的元素

publicbooleancontainsDuplicate(int[]nums){

Arrays.sort(nums);

for(inti=1;inums.length;i++){

if(nums[i-1]==nums[i]){

returntrue;

returnfalse;

不排序，利用set去重，判斷長度

publicbooleancontainsDuplicate(int[]nums){

HashSetIntegerset=newHashSet();

for(inti=0;inums.length;i++){

set.add(nums[i]);

if(set.size()==nums.length){

returnfalse;

returntrue;

2、最大子序和

這道題最經(jīng)典的思路就是動態(tài)規(guī)劃，取當(dāng)前數(shù)組值和當(dāng)前數(shù)組值加上前一個數(shù)組值中取最大值

publicintmaxSubArray(int[]nums){

intres=nums[0];

for(inti=1;inums.length;i++){

nums[i]=Math.max(nums[i]+nums[i-1],nums[i]);

res=Math.max(nums[i],res);

returnres;

還有一種就是記錄前i項子序列和小于0就重新賦值為下一個

publicintmaxSubArray(int[]nums){

intcount=nums[0];

intres=nums[0];

for(inti=1;inums.length;i++){

if(count=0){

count=nums[i];

}else{

count+=nums[i];

res=Math.max(res,count);

returnres;

3、兩數(shù)之和

利用map,來存儲數(shù)組值和當(dāng)前位置，來判斷

publicint[]twoSum(int[]nums,inttarget){

HashMapInteger,Integermap=newHashMap();

for(inti=0;inums.length;i++){

map.put(nums[i],i);

for(inti=0;inums.length;i++){

intnum=target-nums[i];

if(map.containsKey(num)i!=map.get(num)){

returnnewint[]{i,map.get(num)};

returnnull;

4、合并兩個有序數(shù)組

定義變量，遍歷比較

publicvoidmerge(int[]nums1,intm,int[]nums2,intn){

inti=m-1;

intj=n-1;

intk=m+n-1;

while(i=0j=0){

if(nums1[i]nums2[j]){

nums1[k--]=nums1[i--];

}else{

nums1[k--]=nums2[j--];

while(j=0){//即nums2元素還沒放完

nums1[k--]=nums2[j--];

5、兩個數(shù)組的交集II

1.排序，定義指針來判斷

publicint[]intersect(int[]nums1,int[]nums2){

Arrays.sort(nums1);

Arrays.sort(nums2);

intleft=0;

intright=0;

ListIntegerlist=newArrayList();

while(leftnums1.lengthrightnums2.length){

if(nums1[left]==nums2[right]){

list.add(nums1[left]);

left++;

right++;

}elseif(nums1[left]nums2[right]){

left++;

}else{

right++;

int[]arr=newint[list.size()];

for(inti=0;ilist.size();i++){

arr[i]=list.get(i);

returnarr;

6、買賣股票的最佳時機

股票問題就是保存數(shù)組中最小值，之后用當(dāng)前數(shù)組值減去最小值保留最大的，如果max是負(fù)數(shù)，就返回0

publicintmaxProfit(int[]prices){

intmax=Integer.MIN_VALUE;

intmin=prices[0];

for(inti=1;iprices.length;i++){

max=Math.max(max,prices[i]-min);

min=Math.min(prices[i],min);

if(max0){

return0;

returnmax;

7、楊輝三角

判斷特殊情況，第一列和i=j列都是1，其他的都上面的值加上面左邊的值，定義二維數(shù)組進行幫助

publicListListIntegergenerate(intnumRows){

ListListIntegerlist=newArrayList();

int[][]array=newint[numRows][numRows];

for(inti=0;inumRows;i++){

ListIntegerres=newArrayList();

for(intj=0;jj++){

if(j==0||i==j){

array[i][j]=1;

}else{

array[i][j]=array[i-1][j-1]+array[i-1][j];

res.add(array[i][j]);

list.add(res);

returnlist;

8、重塑矩陣

找到其規(guī)律進行賦值即可

publicint[][]matrixReshape(int[][]mat,intr,intc){

intn=mat.length;//行數(shù)

intm=mat[0].length;//列數(shù)

if(m*n!=r*c){

returnmat;

int[][]arr=newint[r][c];

for(inti=0;ii++){

arr[i/c][i%c]=mat[i/m][i%m];

returnarr;

9、有效的數(shù)獨

定義二維數(shù)組來判斷，將存在的數(shù)字置為true，判斷是否該位置為true，返回false.

publicbooleanisValidSudoku(char[][]board){

boolean[][]row=newboolean[9][9];//行數(shù)

boolean[][]col=newboolean[9][9];//列數(shù)

boolean[][]box=newboolean[9][9];//格子內(nèi)

for(inti=0;ii++){

for(intj=0;jj++){

charch=board[i][j];

if(ch=='.')continue;

intcurIndex=ch-'1';//計算在哪個位置

intboxIndex=i/3*3+j/3;//計算在哪個格子里面

if(row[i][curIndex]||col[j][curIndex]||box[boxIndex][curIndex])returnfalse;

row[i][curIndex]=true;

col[j][curIndex]=true;

box[boxIndex][curIndex]=true;

returntrue;

10、矩陣置零

先檢查第一行和第一列是否有0，定義boolean變量標(biāo)記

再利用第一行和第一列作為標(biāo)記列，遍歷整個數(shù)組，將中間元素為0的第一行和第一列置為0，

之后遍歷整個數(shù)組將第一行和第一列的為0的元素的中間元素置為0，之后判斷第一行和第一列是否含0，改為0即可

classSolution{

publicvoidsetZeroes(int[][]matrix){

booleanrow=false;//標(biāo)記第一行

booleancol=false;//標(biāo)記第一列

intm=matrix.length;//行數(shù)

intn=matrix[0].length;//列數(shù)

//檢查第一行是否有0標(biāo)記

for(inti=0;ii++){

if(matrix[0][i]==0){

row=true;

break;

//檢查第一列是否有0標(biāo)記

for(inti=0;ii++){

if(matrix[i][0]==0){

col=true;

break;

//遍歷中間元素把第一行和第一列置為0

for(inti=1;ii++){

for(intj=1;jj++){

if(matrix[i][j]==0){

matrix[i][0]=0;

matrix[0][j]=0;

//根據(jù)第一行第一列的結(jié)果把中間元素置為0

for(inti=1;ii++){

for(intj=1;jj++){

if(matrix[i][0