代码随想录第三十二天

Posted on In

复习

贪心算法 没有套路只有思路，从局部最优解找到全局最优解

455 分发饼干

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int indexC = 0;
        int indexG = 0;
        int count = 0;
        while (indexC < s.length){
            if (s[indexC] >= g[indexG]){
                count++;
                indexC++;
                indexG++;
            } else {
                indexC++;
            }
            if (count == g.length) return count;
        }
        return count;
    }
}

376 摆动序列

在更新preDiff的时候需要注意时机，只有在更新count的时候才更新prediff 即在摆动时更新，就不会在单调区间时出问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 1) return 0;

        int count = 1;
        int index = 1;
        int curDiff = 0;
        int preDiff = 0;
        for (index = 1; index < nums.length; index++){
            curDiff = nums[index] - nums[index - 1];
            if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)){
                count++;
                preDiff = curDiff;
            }
            
        }

        return count;
    }
}

53 最大子序和

具体逻辑，就是不停累加数组里面的数，遇到负数，就清空sum，即舍弃前面所有的总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
            maxSum = Math.max(maxSum, sum);
            if (sum < 0) sum = 0;
        }

        return maxSum;
    }
}

122 买卖股票的最佳时机II

此题即将所有两个值的区间为正值的数加在一起，负值舍弃，在贪心算法中，每一天如果买进，第二天卖出则所有正值就是最大值
最终利润可以分解， 所以可以用贪心算出每一天的收益

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 1) return 0;
        int sum = 0;
        for (int i = 1; i < prices.length; i++){
            int curDiff = prices[i] - prices[i - 1];
            if (curDiff > 0) sum += curDiff;
        }

        return sum;
    }
}

55 跳跃游戏

这道题本质是累加nums[i]之后的数字，找到是不是>=数组长度

此题的难点是在于for loop 之中的判断条件是累加的，是变化的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) return true;

        int coverage = 0;

        for (int i = 0; i <= coverage; i++){
            coverage = Math.max(coverage, i + nums[i]);
            if (coverage >= nums.length - 1){
                return true;
            }
        }

        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length <= 1) return true;

        int maxDistance = 0;

        for (int i = 0; i < nums.length; i++){
            maxDistance = Math.max(maxDistance, i+ nums[i]);
            if (maxDistance >= nums.length - 1) return true;
            if (maxDistance == i && nums[i] == 0) return false;
        }

        return true;
        
    }
}

45 跳跃游戏II

思路：
解题要从覆盖范围出发，不管怎么跳，覆盖范围一定可以跳到，最小步数增加覆盖范围，一旦覆盖了终点就是最小步数
利用current distance 记录走的步数，如果i == curdistance， 就相当于走到了现在的max的最终，需要count++；

也就是如果i走到超过当前可覆盖的最大范围，则count就需要加一了，这之后覆盖记录的这一count之中最大范围值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1 || nums == null) return 0;
        
        int count = 0;
        int curDistance = 0;
        int maxDistance = 0;

        for (int i = 0; i < nums.length; i++){
            maxDistance = Math.max(maxDistance, i + nums[i]);
            if (maxDistance >= nums.length - 1){
                count++;
                break;
            }

            if (i == curDistance){
                curDistance = maxDistance;
                count++;
            }
        }
        return count++;
    }
}

解法需要温习

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int jump(int[] nums) {
        int result = 0;
        int end = 0;
        int temp = 0;
        for (int i = 0; i <= end && end < nums.length - 1; i++){
            temp = Math.max(temp, i + nums[i]);
            if (i == end) {
                end = temp;
                result++;
            }
        }

        return result;
    }
}