C++实现LeetCode数组练习题

C++实现LeetCode数组练习题，久久派带你了解更多相关信息。

目录

• 1、存在重复元素
• 2、最大子序和
• 3、两数之和
• 4、合并两个有序数组
• 5、两个数组的交集II
• 6、买卖股票的最佳时机
• 7、杨辉三角
• 8、重塑矩阵
• 9、有效的数独
• 10、矩阵置零
• 总结

1、存在重复元素

排序数组，之后遍历是否有重复的元素

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、最大子序和

这道题最经典的思路就是动态规划，取当前数组值和当前数组值加上前一个数组值中取最大值

 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、两数之和

利用map,来存储数组值和当前位置，来判断

 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、合并两个有序数组

定义变量，遍历比较

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、两个数组的交集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、买卖股票的最佳时机

股票问题就是保存数组中最小值，之后用当前数组值减去最小值保留最大的，如果max是负数，就返回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，其他的都上面的值加上面左边的值，定义二维数组进行帮助

 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、重塑矩阵

找到其规律进行赋值即可

public int[][] matrixReshape(int[][] mat, int r, int c) {        int n=mat.length;//行数        int m=mat[0].length;//列数        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、有效的数独

定义二维数组来判断，将存在的数字置为true，判断是否该位置为true，返回false.

 public boolean isValidSudoku(char[][] board) {        boolean [][] row=new boolean[9][9];//行数        boolean [][] col=new boolean[9][9];//列数        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 变量标记
再利用第一行和第一列作为标记列，遍历整个数组，将中间元素为0的第一行和第一列置为0，
之后遍历整个数组将第一行和第一列的为0的元素的中间元素置为0，之后判断第一行和第一列是否含0，改为0即可

class Solution {    public void setZeroes(int[][] matrix) {        boolean row=false;//标记第一行        boolean col=false;//标记第一列        int m=matrix.length;//行数        int n=matrix[0].length;//列数       //检查第一行是否有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;                }            }        }        //根据第一行第一列的结果 把中间元素置为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;            }        }    }}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注趣讯吧的更多内容！