最大子数组和(053)

先看代码

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int subSum = 0;
        int res = nums[0];
        for (int i = 0; i 

• 分析

贪心+动态规划

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

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

• 感悟

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

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

合并区间(056)

先看代码

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (p, q)-> p[0] - q[0]);
        List res = new ArrayList();
        for(int[] p : intervals){
            int m = res.size();
            if (m > 0 && p[0] 

• 分析

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

• 感悟

左端点排序可以不破坏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 

• 分析

先对整体数组翻转, 在以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 = 0; i--){
            sufSum[i] = sufSum[i+1] * nums[i+1];
        }
        int[] res = new int[n];

        for(int i = 0; i 

• 分析

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

用 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 

• 分析

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

• 感悟

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

广告