这篇文章主要介绍了C++实现LeetCode的几道数组练习题,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下
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 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 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 list=new ArrayList(<span style="color:transparent">来源gaodai#ma#com搞*!代#%^码$网</span>); 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> generate(int numRows) { List<List> list=new ArrayList(); int [][]array=new int[numRows][numRows]; for(int i=0;i<numRows;i++){ List 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]||c
以上就是C++实现LeetCode数组练习题的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C++实现LeetCode数组练习题 
