代码随想录第三十七天

Posted on In

复习

455 分发饼干

while loop 判断s的停止
在while loop里面判断g的停止

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 findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int indexS = 0;
        int indexG = 0;
        int count = 0;

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

        return count;
    }
}

376 摆动序列

确定边界

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 wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return 1;

        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)){
                count++;
                preDiff = curDiff;
            }
        }

        return count;
    }
}

53 最大子序和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) 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
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || 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 跳跃游戏

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 maxLen = 0;

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

            if (i == maxLen && nums[i] == 0) return false;
        }

        return true;
    }
}

45 跳跃游戏II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1|| nums == null) return 0;
        int count = 0;
        int maxLen = 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){
                count++;
                curLen = maxLen;
            }
        }

        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
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int minVal = Integer.MAX_VALUE;
        int index = 0;
        for (int i = 0; i < nums.length; i++){
            if (Math.abs(nums[i]) < minVal){
                index = i;
                minVal = Math.abs(nums[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
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int index = 0;
        int curSum = 0;
        int totalSum = 0;
        int rest = 0;
        for (int i = 0; i < gas.length; i++){
            rest = gas[i] - cost[i];
            curSum += rest;
            totalSum += rest;

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

        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
20
21
22
23
24
class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;

        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);

        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 = 0;

        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
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;
                ten++;
                five--;
            } else {
                if (ten > 0 && five > 0){
                    ten--;
                    five--;
                } else if (five > 2){
                    five = five - 3;
                } else return false;
            }
        }

        return true;
    }
}

406 根据身高重建队列

Integer.compare 用法

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[people.length][]);
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] index = new int[26];
        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++){
            index[chars[i] - 'a'] = i; 
        }
        List<Integer> result = new ArrayList<>();
        int maxLen = 0;
        int k = -1;
        for (int i = 0; i < chars.length; i++){
            maxLen = Math.max(maxLen, index[chars[i] - 'a']);
            if (i == maxLen){
                result.add(i - k); 
                k = i;
            }
        }

        return result;
    }
}

56 合并区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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]){
                result.add(path);
                path = intervals[i];
            } else {
                path[1] = Math.max(intervals[i][1], path[1]);
            }
        }
        result.add(path);
        return result.toArray(new int[result.size()][]);
    }
}

738 单调递增的数字

把int 换成 String 再换成char Array

再对比数字，设置start，start之后全是9

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 start = chars.length;
        for (int i = s.length() - 2; i >= 0; i--){
            if (chars[i] > chars[i + 1]){
                chars[i]--;
                start = i + 1;
            }
        }

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

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

23 监控二叉树

局部最优是：叶子节点的父节点放摄像头
全局最优: 全摄像头使用最少

从低向上遍历 利用后序遍历
更新状态：

  1. 节点无覆盖
  2. 节点有摄像头
  3. 节点有覆盖

关系：

  1. 左右节点都有覆盖，中间节点就是无覆盖
  2. 左右节点至少有一个无覆盖， 则中间节点放摄像头
  3. 左右节点至少有一个摄像头， 则父节点就是覆盖的状态
  4. 头节点没有覆盖，则判断是否需要放摄像头
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
class Solution {
    int result = 0;
    public int minCameraCover(TreeNode root) {
        if (backTraversal(root) == 0){
            result++;
        }

        return result;
    }

    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;
        }
    }

}

每日一题 2966 Divide Arrays Into Arrays With Max Difference

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[][] divideArray(int[] nums, int k) {
        int size = nums.length;
        if (size % 3 != 0) return new int[0][];
        Arrays.sort(nums);
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i += 3){
            if (i + 2 < size && nums[i + 2] - nums[i] <= k){
                result.add(new int[]{nums[i], nums[i + 1], nums[i + 2]});
            } else {
                return new int[0][];
            }
        }

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