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、两个数组的交集II1.排序，定义指针来判断
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.
【C++实现LeetCode数组练习题】 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 变量标记

C++实现LeetCode数组练习题

推荐阅读

圆肩驼背形成的原因有什么

聚焦的演员介绍

条形码下面的是快递单号吗

钟表之国是哪个国家?

gre高效记忆词汇是什么 GRE高效记忆词汇要明确3个常见误区

优化盒子如何卸载

校园欺凌未成年判多久

春晓写的是什么时候的情景春晓写的是什么时间的情景

孕妈必知怀孕前有些事不能做

怎么登录别人抖音号