C++實(shí)現(xiàn)LeetCode數(shù)組練習(xí)題
1、存在重復(fù)元素
排序數(shù)組,之后遍歷是否有重復(fù)的元素
public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); for(int i=1;i<nums.length;i++){ if(nums[i-1]==nums[i]){ return true; } } return false; }
不排序,利用set去重,判斷長(zhǎng)度
public boolean containsDuplicate(int[] nums) { HashSet <Integer> set=new HashSet<>(); for(int i=0;i<nums.length;i++){ set.add(nums[i]); } if(set.size()==nums.length){ return false; } return true; }
2、最大子序和
這道題最經(jīng)典的思路就是動(dòng)態(tài)規(guī)劃,取當(dāng)前數(shù)組值和當(dāng)前數(shù)組值加上前一個(gè)數(shù)組值中取最大值
public int maxSubArray(int[] nums) { int res=nums[0]; for(int i=1;i<nums.length;i++){ nums[i]=Math.max(nums[i]+nums[i-1],nums[i]); res=Math.max(nums[i],res); } return res; }
還有一種就是記錄前i項(xiàng)子序列和小于0就重新賦值為下一個(gè)
public int maxSubArray(int[] nums) { int count=nums[0]; int res=nums[0]; for(int i=1;i<nums.length;i++){ if(count<=0){ count=nums[i]; }else{ count+=nums[i]; } res=Math.max(res,count); } return res; }
3、兩數(shù)之和
利用map,來(lái)存儲(chǔ)數(shù)組值和當(dāng)前位置,來(lái)判斷
public int[] twoSum(int[] nums, int target) { HashMap<Integer,Integer> map=new HashMap<>(); for(int i=0;i<nums.length;i++){ map.put(nums[i],i); } for(int i=0;i<nums.length;i++){ int num=target-nums[i]; if(map.containsKey(num)&&i!=map.get(num)){ return new int[]{i,map.get(num)}; } } return null; }
4、合并兩個(gè)有序數(shù)組
定義變量,遍歷比較
public void merge(int[] nums1, int m, int[] nums2, int n) { int i=m-1; int j=n-1; int k=m+n-1; while(i>=0&&j>=0){ if(nums1[i]>nums2[j]){ nums1[k--]=nums1[i--]; }else{ nums1[k--]=nums2[j--]; } } while(j>=0){//即nums2元素還沒(méi)放完 nums1[k--]=nums2[j--]; } }
5、兩個(gè)數(shù)組的交集II
1.排序,定義指針來(lái)判斷
public int[] intersect(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int left=0; int right=0; List<Integer> list=new ArrayList<>(); while(left<nums1.length&&right<nums2.length){ if(nums1[left]==nums2[right]){ list.add(nums1[left]); left++; right++; }else if(nums1[left]<nums2[right]){ left++; }else{ right++; } } int []arr=new int[list.size()]; for(int i=0;i<list.size();i++){ arr[i]=list.get(i); } return arr; }
6、買賣股票的最佳時(shí)機(jī)
股票問(wèn)題就是保存數(shù)組中最小值,之后用當(dāng)前數(shù)組值減去最小值保留最大的,如果max是負(fù)數(shù),就返回0
public int maxProfit(int[] prices) { int max=Integer.MIN_VALUE; int min=prices[0]; for(int i=1;i<prices.length;i++){ max=Math.max(max,prices[i]-min); min=Math.min(prices[i],min); } if(max<0){ return 0; } return max; }
7、楊輝三角
判斷特殊情況,第一列和i=j列都是1,其他的都上面的值加上面左邊的值,定義二維數(shù)組進(jìn)行幫助
public List<List<Integer>> generate(int numRows) { List<List<Integer>> list=new ArrayList<>(); int [][]array=new int[numRows][numRows]; for(int i=0;i<numRows;i++){ List<Integer> res=new ArrayList<>(); for(int j=0;j<=i;j++){ 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); } return list; }
8、重塑矩陣
找到其規(guī)律進(jìn)行賦值即可
public int[][] matrixReshape(int[][] mat, int r, int c) { int n=mat.length;//行數(shù) int m=mat[0].length;//列數(shù) if(m*n!=r*c){ return mat; } int [][]arr=new int[r][c]; for(int i=0;i<r*c;i++){ arr[i/c][i%c]=mat[i/m][i%m]; } return arr; }
9、有效的數(shù)獨(dú)
定義二維數(shù)組來(lái)判斷,將存在的數(shù)字置為true,判斷是否該位置為true,返回false.
public boolean isValidSudoku(char[][] board) { boolean [][] row=new boolean[9][9];//行數(shù) boolean [][] col=new boolean[9][9];//列數(shù) boolean [][] box=new boolean[9][9];//格子內(nèi) for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ char ch=board[i][j]; if(ch=='.') continue; int curIndex=ch-'1';//計(jì)算在哪個(gè)位置 int boxIndex=i/3*3+j/3;// 計(jì)算在哪個(gè)格子里面 if(row[i][curIndex]||col[j][curIndex]||box[boxIndex][curIndex]) return false; row[i][curIndex]=true; col[j][curIndex]=true; box[boxIndex][curIndex]=true; } } return true; }
10、矩陣置零
先檢查第一行和第一列是否有0,定義boolean 變量標(biāo)記
再利用第一行和第一列作為標(biāo)記列,遍歷整個(gè)數(shù)組,將中間元素為0的第一行和第一列置為0,
之后遍歷整個(gè)數(shù)組將第一行和第一列的為0的元素的中間元素置為0,之后判斷第一行和第一列是否含0,改為0即可
class Solution { public void setZeroes(int[][] matrix) { boolean row=false;//標(biāo)記第一行 boolean col=false;//標(biāo)記第一列 int m=matrix.length;//行數(shù) int n=matrix[0].length;//列數(shù) //檢查第一行是否有0 標(biāo)記 for(int i=0;i<n;i++){ if(matrix[0][i]==0){ row=true; break ; } } //檢查第一列是否有0 標(biāo)記 for(int i=0;i<m;i++){ if(matrix[i][0]==0){ col=true; break ; } } //遍歷中間元素 把第一行和第一列置為0 for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ if(matrix[i][j]==0){ matrix[i][0]=0; matrix[0][j]=0; } } } //根據(jù)第一行第一列的結(jié)果 把中間元素置為0 for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ if(matrix[i][0]==0||matrix[0][j]==0){ matrix[i][j]=0; } } } //檢查第一行是否有最開(kāi)始為0的 if(row){ for(int i=0;i<n;i++){ matrix[0][i]=0; } } //檢查第一列是否有最開(kāi)始為0的 if(col){ for(int i=0;i<m;i++){ matrix[i][0]=0; } } } }
總結(jié)
本篇文章就到這里了,希望能給你帶來(lái)幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
基于C++ cin、cin.get()、cin.getline()、getline()、gets()函數(shù)的使用詳解
學(xué)C++的時(shí)候,這幾個(gè)輸入函數(shù)弄的有點(diǎn)迷糊;這里做個(gè)小結(jié)2013-05-05C++中的不規(guī)則二維數(shù)組實(shí)現(xiàn)代碼
本文介紹了一個(gè)在C++中保存不定長(zhǎng)二維數(shù)組的數(shù)據(jù)結(jié)構(gòu),在這個(gè)結(jié)構(gòu)中,我們使用了一個(gè)含有指針和數(shù)組長(zhǎng)度的結(jié)構(gòu)體,用這樣的一個(gè)結(jié)構(gòu)體構(gòu)造一個(gè)結(jié)構(gòu)體數(shù)組,用于存儲(chǔ)每一個(gè)不定長(zhǎng)的數(shù)組,感興趣的朋友一起看看吧2024-03-03C++類和對(duì)象實(shí)戰(zhàn)之Date類的實(shí)現(xiàn)方法
C++ 標(biāo)準(zhǔn)庫(kù)沒(méi)有提供所謂的日期類型,C++ 繼承了C語(yǔ)言用于日期和時(shí)間操作的結(jié)構(gòu)和函數(shù),這篇文章主要給大家介紹了C++類和對(duì)象實(shí)戰(zhàn)之Date類的實(shí)現(xiàn)方法,需要的朋友可以參考下2021-12-12C語(yǔ)言通過(guò)深度優(yōu)先搜索來(lái)解電梯問(wèn)題和N皇后問(wèn)題的示例
深度優(yōu)先搜索即是對(duì)一個(gè)新發(fā)現(xiàn)的節(jié)點(diǎn)上如果還關(guān)聯(lián)未探測(cè)到的邊,就沿此邊探測(cè)下去,直到發(fā)現(xiàn)從原點(diǎn)可達(dá)的所有點(diǎn)為止,這里我們就來(lái)展示C語(yǔ)言通過(guò)深度優(yōu)先搜索來(lái)解電梯問(wèn)題和N皇后問(wèn)題的示例2016-06-06COLORREF,COLOR,RGB,CString的轉(zhuǎn)化總結(jié)分析
實(shí)際的軟件開(kāi)發(fā)過(guò)程中,常需要用到非.net平臺(tái)的代碼。這時(shí)候就可能碰到ColorRef(也就是以int類型代表的顏色值或是以DWORD值表示的顏色)。這跟.net平臺(tái)下的顏色的相互轉(zhuǎn)換MS并沒(méi)有直接實(shí)現(xiàn)2013-09-09Visual?Studio?2022下載及配置OpenCV4.5.5的詳細(xì)過(guò)程
這篇文章主要介紹了Visual?Studio?2022下載及配置OpenCV4.5.5的詳細(xì)過(guò)程,在這里注意下Win10的64位操作系統(tǒng),在OpenCV官網(wǎng)下載OpenCV4.5.5,安裝的是Win?pack,本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì),需要的朋友可以參考下2022-05-05Matlab利用隨機(jī)森林(RF)算法實(shí)現(xiàn)回歸預(yù)測(cè)詳解
這篇文章主要為大家詳細(xì)介紹了Matlab如何利用隨機(jī)森林(RF)算法實(shí)現(xiàn)回歸預(yù)測(cè),以及自變量重要性排序的操作,感興趣的小伙伴可以了解一下2023-02-02關(guān)于C++智能指針shared_ptr和unique_ptr能否互轉(zhuǎn)問(wèn)題
C++中的智能指針最常用的是shared_ptr和unique_ptr,C++新手最常問(wèn)的問(wèn)題是我從一個(gè)函數(shù)中拿到unique_ptr,但要轉(zhuǎn)成shared_ptr才能使用,要怎么轉(zhuǎn)換?同理是否能將shared_ptr轉(zhuǎn)換成unique_ptr,面對(duì)這些問(wèn)題,跟隨小編一起看看吧2022-05-05