hot100之数组

最大子数组和(053)

先看代码

1. class Solution {
2.     public int maxSubArray(int[] nums) {
3.         int n = nums.length;
4.         int subSum = 0;
5.         int res = nums[0];
6.         for (int i = 0; i < n; i++){
7.             subSum = Math.max(nums[i], subSum+nums[i]);
8.             res = Math.max(res, subSum);
9.         }
10.         return res;
11.     }
12. }

复制代码

• 分析
  

贪心+动态规划
判断前子数组是否对 subSum 产生负影响, 产生影响则放弃前子数组, 重新开始新的子数组
动态规划体现在计算当前的子数组和时，需要考虑前面的子数组和是否对当前有贡献。贪心体现在如果前面的子数组和为负数，就直接舍弃重新开始计算。这道题的关键在于理解subSum代表以当前元素结尾的最大子数组和。

• 感悟
  

因为前值会对后值产生影响 , 让人自然想到动态规划
由于后值只需要前一个状态的值 我们可以用 subSum作滚动计算  ,优化空间复杂度
合并区间(056)

先看代码

1. class Solution {
2.     public int[][] merge(int[][] intervals) {
3.         Arrays.sort(intervals, (p, q)-> p[0] - q[0]);
4.         List<int []> res = new ArrayList<>();
5.         for(int[] p : intervals){
6.             int m = res.size();
7.             if (m > 0 && p[0] <= res.get(m-1)[1]){
8.                 res.get(m-1)[1] = Math.max(res.get(m-1)[1], p[1]);
9.             }else res.add(p);
10.         }
11.         return res.toArray(new int[res.size()][]);
12.     }
13. }

复制代码

• 分析
  

分别计算数组的前缀积与后缀积
用 i之前的前缀积 *  i之和的后缀积

res = preSum * sufSum
preSum[0] = 1   sufSum[n-1] = 1
可知 preSum 为 num[0] * …. * num[i-1]
同理 sufSum 为 num[n-1] * …. * num[i+1]
可知preSum * sufSum 不包含 num

• 感悟
  

分解数据的前后缀再求解
缺失的第一个正数(041)

先看代码
[code]class Solution {    public int firstMissingPositive(int[] nums) {        int n = nums.length;        for (int i = 0; i < n; i++){            while(0 < nums && nums