C++實現(xiàn)LeetCode數(shù)組練習題
更新時間：2021年08月16日 10:39:34 作者：caiyec
這篇文章主要介紹了C++實現(xiàn)LeetCode的幾道數(shù)組練習題,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下
1、存在重復元素
排序數(shù)組，之后遍歷是否有重復的元素
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去重，判斷長度
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)典的思路就是動態(tài)規(guī)劃，取當前數(shù)組值和當前數(shù)組值加上前一個數(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項子序列和小于0就重新賦值為下一個
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,來存儲數(shù)組值和當前位置，來判斷
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、合并兩個有序數(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元素還沒放完
nums1[k--]=nums2[j--];
}
}
5、兩個數(shù)組的交集II
1.排序，定義指針來判斷
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ù)組中最小值，之后用當前數(shù)組值減去最小值保留最大的，如果max是負數(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ù)組進行幫助
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ī)律進行賦值即可
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ù)獨
定義二維數(shù)組來判斷，將存在的數(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';//計算在哪個位置
int boxIndex=i/3*3+j/3;// 計算在哪個格子里面
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 變量標記
再利用第一行和第一列作為標記列，遍歷整個數(shù)組，將中間元素為0的第一行和第一列置為0，
之后遍歷整個數(shù)組將第一行和第一列的為0的元素的中間元素置為0，之后判斷第一行和第一列是否含0，改為0即可
class Solution {
public void setZeroes(int[][] matrix) {
boolean row=false;//標記第一行
boolean col=false;//標記第一列
int m=matrix.length;//行數(shù)
int n=matrix[0].length;//列數(shù)
//檢查第一行是否有0 標記
for(int i=0;i<n;i++){
if(matrix[0][i]==0){
row=true;
break ;
}
}
//檢查第一列是否有0 標記
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ù)第一行第一列的結果 把中間元素置為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;
}
}
}
//檢查第一行是否有最開始為0的
if(row){
for(int i=0;i<n;i++){
matrix[0][i]=0;
}
}
//檢查第一列是否有最開始為0的
if(col){
for(int i=0;i<m;i++){
matrix[i][0]=0;
}
}
}
}
總結
本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關注腳本之家的更多內(nèi)容！
相關文章
基于C++ cin、cin.get()、cin.getline()、getline()、gets()函數(shù)的使用詳解
學C++的時候，這幾個輸入函數(shù)弄的有點迷糊；這里做個小結2013-05-05
C++中的不規(guī)則二維數(shù)組實現(xiàn)代碼
本文介紹了一個在C++中保存不定長二維數(shù)組的數(shù)據(jù)結構,在這個結構中,我們使用了一個含有指針和數(shù)組長度的結構體,用這樣的一個結構體構造一個結構體數(shù)組,用于存儲每一個不定長的數(shù)組,感興趣的朋友一起看看吧2024-03-03
迭代器是一種檢查容器內(nèi)元素并遍歷元素的數(shù)據(jù)類型。迭代器是一個變量，提供對一個容器中的對象的（間接）訪問方法，并且定義了容器中對象的范圍。迭代器可以指向容器中的某個元素，通過迭代器就可以對非數(shù)組（存儲空間不連續(xù)）的數(shù)據(jù)結構進行遍歷2022-10-10
C++類和對象實戰(zhàn)之Date類的實現(xiàn)方法
C++ 標準庫沒有提供所謂的日期類型,C++ 繼承了C語言用于日期和時間操作的結構和函數(shù),這篇文章主要給大家介紹了C++類和對象實戰(zhàn)之Date類的實現(xiàn)方法,需要的朋友可以參考下2021-12-12
C語言通過深度優(yōu)先搜索來解電梯問題和N皇后問題的示例
深度優(yōu)先搜索即是對一個新發(fā)現(xiàn)的節(jié)點上如果還關聯(lián)未探測到的邊,就沿此邊探測下去,直到發(fā)現(xiàn)從原點可達的所有點為止,這里我們就來展示C語言通過深度優(yōu)先搜索來解電梯問題和N皇后問題的示例2016-06-06
std::flush是C++標準庫中的一個操作符,用于刷新輸出流,本文主要介紹了C++庫std::flush的具體使用,具有一定的參考價值,感興趣的可以了解一下2024-02-02
COLORREF,COLOR,RGB,CString的轉化總結分析
實際的軟件開發(fā)過程中,常需要用到非.net平臺的代碼。這時候就可能碰到ColorRef(也就是以int類型代表的顏色值或是以DWORD值表示的顏色)。這跟.net平臺下的顏色的相互轉換MS并沒有直接實現(xiàn)2013-09-09
Visual?Studio?2022下載及配置OpenCV4.5.5的詳細過程
這篇文章主要介紹了Visual?Studio?2022下載及配置OpenCV4.5.5的詳細過程，在這里注意下Win10的64位操作系統(tǒng)，在OpenCV官網(wǎng)下載OpenCV4.5.5，安裝的是Win?pack,本文通過圖文并茂的形式給大家介紹的非常詳細，需要的朋友可以參考下2022-05-05
Matlab利用隨機森林(RF)算法實現(xiàn)回歸預測詳解
這篇文章主要為大家詳細介紹了Matlab如何利用隨機森林（RF）算法實現(xiàn)回歸預測，以及自變量重要性排序的操作，感興趣的小伙伴可以了解一下2023-02-02
關于C++智能指針shared_ptr和unique_ptr能否互轉問題
C++中的智能指針最常用的是shared_ptr和unique_ptr，C++新手最常問的問題是我從一個函數(shù)中拿到unique_ptr，但要轉成shared_ptr才能使用，要怎么轉換？同理是否能將shared_ptr轉換成unique_ptr，面對這些問題，跟隨小編一起看看吧2022-05-05