普通数组专题文章目录普通数组专题53. 最大子数组和贪心动态规划56. 合并区间189. 轮转数组53. 最大子数组和53. 最大子数组和贪心若指针所指当前元素之前的和小于0则丢弃当前元素之前的数列classSolution{publicintmaxSubArray(int[]nums){intpre0,ansnums[0];for(intx:nums){if(pre0){prex;}else{prex;}ansMath.max(pre,ans);}returnans;}}动态规划考虑nums[i] 单独成为一段还是加入f(i−1) 对应的那一段这取决于nums[i] 和f(i−1)nums[i] 的大小classSolution{publicintmaxSubArray(int[]nums){intpre0,maxAnsnums[0];for(intx:nums){preMath.max(prex,x);maxAnsMath.max(maxAns,pre);}returnmaxAns;}}56. 合并区间56. 合并区间一开始想到三种区间关系覆盖重叠相离不知道怎么把合并的区间添加到ans中其实不用分出三种区间关系直接判断能否合并就行即前一个的right和后一个left的关系q_left p_right 可以合并q_left p_right 不可以合并对于最后将合并好的区间添加的ans里也可以简单化可合并添加前一个区间p进ans 修改p_right为q_right如果q_right更大的话不可合并直接将该区间加入classSolution{publicint[][]merge(int[][]intervals){Arrays.sort(intervals,(p,q)-p[0]-q[0]);// 按照左端点从小到大排序Listint[]ansnewArrayList();//不知道最后结果大小 没法用二维数组for(int[]p:intervals){intmans.size();if(m0p[0]ans.get(m-1)[1]){// 可以合并ans.get(m-1)[1]Math.max(ans.get(m-1)[1],p[1]);// 更新右端点最大值}else{// 不相交无法合并ans.add(p);}}returnans.toArray(newint[ans.size()][]);}}return ans.toArray(new int[ans.size()][]);作用是将Listint[]转换为int[][]二维数组并返回。为什么要写这一行函数的返回类型是int[][]二维数组但我们使用Listint[]来动态存储合并后的区间因为List可以随时add而数组大小固定所以在最后必须把List转成int[][]才能返回。189. 轮转数组189. 轮转数组把A B变成B A先反转整个数组再分别反转A和BclassSolution{publicvoidrotate(int[]nums,intk){intnnums.length;k%n;// 轮转 k 次等于轮转 k % n 次reverse(nums,0,n-1);reverse(nums,0,k-1);reverse(nums,k,n-1);}privatevoidreverse(int[]nums,inti,intj){while(ij){inttempnums[i];nums[i]nums[j];nums[j--]temp;}}}
