hot100之数组

最大子数组和(053)

先看代码

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int subSum = 0;
        int res = nums[0];
        for (int i = 0; i < n; i++){
            subSum = Math.max(nums[i], subSum+nums[i]);
            res = Math.max(res, subSum);
        }
        return res;
    }
}

• 分析

贪心+动态规划

判断前子数组是否对 subSum 产生负影响, 产生影响则放弃前子数组, 重新开始新的子数组

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

• 感悟

因为前值会对后值产生影响 , 让人自然想到动态规划

由于后值只需要前一个状态的值 我们可以用 subSum作滚动计算 ,优化空间复杂度

合并区间(056)

先看代码

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (p, q)-> p[0] - q[0]);
        List<int []> res = new ArrayList<>();
        for(int[] p : intervals){
            int m = res.size();
            if (m > 0 && p[0] <= res.get(m-1)[1]){
                res.get(m-1)[1] = Math.max(res.get(m-1)[1], p[1]);
            }else res.add(p);
        }
        return res.toArray(new int[res.size()][]);
    }
}

• 分析

利用左端点进行排序, 再组合

• 感悟

左端点排序可以不破坏p[k-1]与 p[k]一致, 递增

轮转数组(189)

先看代码

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, n-1);
    }

    private void reverse(int[] nums, int lef, int rig){
        while (lef < rig){
            int temp = nums[lef];
            nums[lef++] = nums[rig];
            nums[rig--] = temp; 
        }
        
    }
}

• 分析

先对整体数组翻转, 在以k为节点 左右各自翻转

• 感悟

数学 真神奇吧

除自身以外数的乘积(238)

先看代码

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] preSum = new int[n];
        preSum[0] = 1;
        int[] sufSum = new int[n];
        sufSum[n-1] = 1;
        for(int i = 1; i < n ; i++){
            preSum[i] = preSum[i-1] * nums[i-1]; 
        }
        for(int i = n-2; i >= 0; i--){
            sufSum[i] = sufSum[i+1] * nums[i+1];
        }
        int[] res = new int[n];

        for(int i = 0; i < n; i++){
            res[i] = preSum[i] * sufSum[i];
        }
        return res;
    }
}

• 分析

分别计算数组的前缀积与后缀积

用 i之前的前缀积 * i之和的后缀积

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

• 感悟

分解数据的前后缀再求解

缺失的第一个正数(041)

先看代码

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++){
            while(0 < nums[i] && nums[i] <= n && nums[i] != nums[nums[i] - 1]){
                int j = nums[i] - 1;
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; i++){
            if (nums[i] != i+1){
                return i+1;
            }
        }
        return n+1;
    }
}

• 分析

还是分座位, 如果i号座位上坐的人不是i , 让出座位给i

• 感悟

将理论问题生活化. 生活中的一个直觉, 背后可能有丰富的理论