代码随想录第三十八天

Posted on In

贪心总复习

455 分发饼干

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int indexG = 0;
        int indexS = 0;

        int count = 0;

        while (indexS < s.length){
            if (s[indexS] >= g[indexG]){
                indexS++;
                indexG++;
                count++;
            } else {
                indexS++;
            }

            if (indexG > g.length - 1) return count; 
        }
        return count;
    }
}

376 摆动序列

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

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

        return count;
    }
}

53 最大子序和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0 || nums == null) return 0;

        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
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;

        int profit = 0;
        int curDiff = 0;

        for (int i = 1; i < prices.length; i++){
            curDiff = prices[i] - prices[i - 1];
            if (curDiff > 0){
                profit += curDiff;
            }
        }

        return profit;
    }
}

55 跳跃游戏

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

        int maxLen = 0;

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

        return false;
    }
}

45 跳跃游戏II

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

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

            if (i == curLen){
                curLen = maxLen;
                count++;
            }
        }

        return count;
    }
}

1005 K次取反后最大化的数组和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        if (nums.length == 0 || nums == null) return 0;

        Arrays.sort(nums);
        int minVal = Integer.MAX_VALUE;
        int index = 0;
        for (int i = 0; i < nums.length; i++){
            if (minVal > Math.abs(nums[i])){
                minVal = Math.abs(nums[i]);
                index = i;
            }
            if (k > 0 && nums[i] < 0) {
                k--;
                nums[i] = -nums[i];
            }
        }

        if (k % 2 == 1) nums[index] = -nums[index];
        int sum = 0;
        for (int i : nums){
            sum += i;
        }
        return sum;
        
    }
}

134 加油站

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curRest = 0;
        int curSum = 0;
        int totalSum = 0;
        int index = 0;
        for (int i = 0; i < gas.length; i++){
            curRest = gas[i] - cost[i];
            curSum += curRest;
            totalSum += curRest;

            if (curSum < 0){
                curSum = 0;
                index = i + 1;
            }
        }

        if (totalSum < 0) return -1;
        
        return index;
    }
}

135 分发糖果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        int[] candies = new int[ratings.length];

        for (int i = 1; i < ratings.length; i++){
            if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
        }

        for (int i = ratings.length - 2; i >= 0; i--){
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) candies[i] = candies[i + 1] + 1; 
        }
        int sum = ratings.length;
        for (int i : candies){
            sum += i;
        }
        return sum;
    }
}

860 柠檬水找零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        for (int i : bills){
            if (i == 5) five++;
            else if (i == 10){
                if (five < 1) return false;
                five--;
                ten++;
            }

            else if (i == 20){
                if (ten > 0 && five > 0){
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five = five - 3;
                } else return false;
            }
        }

        return true;
    }
}

406 根据身高重建队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });

        LinkedList<int[]> result = new LinkedList<>();
        for (int[] i : people){
            result.add(i[1], i);
        }

        return result.toArray(new int[result.size()][]);
    }
}

452 用最少数量的箭引爆气球

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));

        int count = 1;
        for (int i = 1; i < points.length; i++){
            if (points[i][0] > points[i - 1][1]) {
                count++;
            } else {
                points[i][1] = Math.min(points[i][1], points[i-1][1]);
            }
        }

        return count;
    }
}

435 无重叠区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0],b[0]));

        int count = 1;
        for (int i = 1; i < intervals.length; i++){
            if (intervals[i][0] >= intervals[i - 1][1]){
                count++;
            } else {
                intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);
            }
        }

        return intervals.length - count;
    }
}

763 划分字母区间

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 List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        int[] index = new int[26];
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++){
            index[chars[i] - 'a'] = i; 
        }

        int maxLen = Integer.MIN_VALUE;
        int last = -1;
        for (int i = 0; i < chars.length; i++){
            maxLen = Math.max(maxLen, index[chars[i] - 'a']);

            if (i == maxLen){
                result.add(i - last);
                last = i;
            }
        }

        return result;
    }
}

56 合并区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> result = new ArrayList<>();
        int[] path = new int[2];
        path = intervals[0];
        for (int i = 1; i < intervals.length; i++){
            if (path[1] >= intervals[i][0]){
                path[1] = Math.max(path[1], intervals[i][1]);
            } else {
                result.add(path);
                path = intervals[i];
            }
        }

        result.add(path);

        return result.toArray(new int[result.size()][]);
    }
}

738 单调递增的数字

更新index时要变成i+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int index = chars.length;
        for (int i = chars.length - 2; i >= 0; i--){
            if (chars[i] > chars[i + 1]) {
                chars[i]--;
                index = i + 1;
            }
        }

        for (int i = index; i < chars.length; i++){
            chars[i] = '9';
        }

        return Integer.valueOf(String.valueOf(chars));
    }
}

968 监控二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    int result = 0;
    public int minCameraCover(TreeNode root) {
        if (backTraversal(root) == 0) result++;
        return result;
    }

    /*
        0. no cover
        1. have cam
        2. cover
    */  
    private int backTraversal(TreeNode root){
        if (root == null) return 2;

        int left = backTraversal(root.left);
        int right = backTraversal(root.right);

        if (left == 2 && right == 2) {
            return 0;
        }
        else if (left == 0 || right == 0) {
            result++;
            return 1;
        }
        else return 2;
    }
}

动态规划基础理论

一个问题有很多重叠的子问题
动态规划中的每一状态一定是由上一个状态推导出来的

动态规划五步法：

1.
确定dp数组（dp table）以及下标的含义
2.
确定递推公式
3.
dp数组如何初始化
4.
确定遍历顺序
5.
举例推导dp数组

写代码之前一定要把状态转移在dp数组上具体情况模拟一遍

509 斐波那契数

五部曲：

  1. dp[i] 就是 第i个数的斐波那契数值
  2. 递推公式 dp[i] = dp[i - 1] + dp[i - 2]
  3. dp初始化 dp[0] = 0 dp[1] = 1
  4. 遍历顺序，从前往后遍历
  5. 0 1 1 2 3 5 8 13 模拟过程
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i < dp.length; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[dp.length - 1];
    }
}

70 爬楼梯

五部曲：

  1. dp[i] 就是 爬到i层楼梯有dp[i]种方法

  2. 递推公式
    从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。
    首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，再一步跳一个台阶就是dp[i]。
    还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，再一步跳两个台阶就是dp[i]。
    所以dp[i] = dp[i - 1] + dp[i - 2]
    即斐波那契数列，只是初始化不一样

  3. dp初始化 dp[1] = 1 dp[2] = 2

  4. 遍历顺序，从前往后遍历

  5. 0 1 2 3 5 8 13 模拟过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i < dp.length; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[dp.length - 1];
    }
}

746 使用最小花费爬楼梯

五部曲：

  1. dp[i] 就是 爬到i层楼梯使用的dp[i]体力就是最小的

  2. 递推公式
    dp[i] 要么是dp[i - 1] + cost[i - 1]
    或者是dp[i-2] + cost[i - 2];

  3. dp初始化 dp[0] = 0 dp[1] = 0

  4. 遍历顺序，从前往后遍历

  5. 0 1 2 3 5 8 13 模拟过程

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i < dp.length; i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[dp.length - 1];
    }
}

每日一题： 1291 Sequential Digits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i<= 9; i++){
            int num = i;
            int nextDigit = i + 1;
            while (num <= high && nextDigit <= 9){
                num = num * 10 + nextDigit;
                if (low <= num && num <= high){
                    result.add(num);
                }
                nextDigit++;
            }

            
        }

        result.sort(null);
        return result;
    }
}