C++實現(xiàn)LeetCode數(shù)組練習題
更新時間：2021年08月16日 10:39:34 作者：caiyec
這篇文章主要介紹了C++實現(xiàn)LeetCode的幾道數(shù)組練習題,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
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、最大子序和
這道題最經典的思路就是動態(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];//格子內
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;
}
}
}
}
總結
本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關注腳本之家的更多內容！
相關文章
c++中的內聯(lián)函數(shù)inline用法實例
在本篇文章里小編給大家整理的是關于c++中的內聯(lián)函數(shù)inline用法實例以及相關知識點，有需要的朋友們學習下。2019-09-09
Visual?Studio2022配置ReSharper?C++?常用設置方法
這篇文章主要介紹了Visual?Studio2022配置ReSharper?C++?常用設置,本文通過圖文并茂的形式給大家介紹的非常詳細,文中介紹了卸載Resharper的方法及Resharper激活碼,感興趣的朋友參考下吧2024-01-01
C語言提供了豐富的字符串處理函數(shù),可以對字符串進行輸入、輸出、合并、修改、比較、轉換、復制、搜索等操作,下面這篇文章主要給大家介紹了關于C語言進階教程之字符函數(shù)&字符串函數(shù)的相關資料,需要的朋友可以參考下2022-03-03
很多時候需要用到項目重命名,本文主要介紹了visualstudio2022工程重命名的圖文步驟,具有一定的參考價值,感興趣的可以了解一下2024-06-06
這篇文章主要為大家詳細介紹了C語言版三子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要介紹了詳解C++中賦值和輸入輸出語句的用法,是C++入門學習中的基礎知識,需要的朋友可以參考下2015-09-09
這篇文章主要介紹了C++ STL list 遍歷刪除出錯解決方案的相關資料,這里對出錯進行分析，并給出正確的解決方法，需要的朋友可以參考下2016-12-12
下面小編就為大家?guī)硪黄狢++之類和對象課后習題簡單實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-07-07
以下是對c語言中static函數(shù)的用法進行了詳細的分析介紹，需要的朋友可以過來參考下2013-08-08
這篇文章主要介紹了C++采用ring3讀取MBR實例,可實現(xiàn)對硬盤的主引導記錄的讀取,非常具有實用價值,需要的朋友可以參考下2014-10-10