代码随想录第三十六天

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

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

376 摆动序列

count从1开始

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

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

        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int i: nums){
            sum += i;
            max = Math.max(max, sum);
            if (sum < 0){
                sum = 0;
            }
        }

        return max;
    }
}

122 买卖股票的最佳时机II

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

        int sum = 0;
        int curDiff = 0;

        for (int i = 1; i < prices.length; i++){
            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
class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length <= 1 || nums == null) return true;

        int maxLen = 0;

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

        return false;
    }
}

45 跳跃游戏II

判断maxLen超过最后的时间返回count

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

        int maxLen = Integer.MIN_VALUE;
        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){
                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
26
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);

        int min = Integer.MAX_VALUE;
        int indexMin = 0;
        for (int i  = 0; i < nums.length; i++){
            if (Math.abs(nums[i]) < min) {
                min = Math.abs(nums[i]);
                indexMin = i;
            }

            if (k > 0 && nums[i] < 0){
                k--;
                nums[i] = -nums[i];
            }
        }

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

134 加油站

找到curSum最后一个大于0的值

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 canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int index = 0;

        for(int i = 0; i < gas.length; i++){
            int 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
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]) 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 + 1;
        }

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

        return true;
    }
}

406 根据身高重建队列

a - b 是顺序 小到大
b - a 是倒序 大到小
或者利用Integer.compare();
利用LinkedList在index插入

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 Integer.compare(a[1], b[1]);
            return Integer.compare(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][2]);
    }
}

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 无重叠区间

气球的题求的是非交叉区间的数量，此题求的是交叉区间数量，就是length - 非交叉区间数量
判断边界时，要注意

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][1], intervals[i][1]);
            }
        }

        return intervals.length - count;
    }
}

763 划分字母区间

遍历过程中找每个字母的边界，找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点。
统计每个字符最后出现的位置

idx表示最远边界，找到最远边界，更新

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 List<Integer> partitionLabels(String s) {
        List<Integer> result = new LinkedList<>();

        int[] edge = new int[26];
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++){
            edge[chars[i] - 'a'] = i;
        }

        int idx = 0;
        int last = -1;

        for (int i = 0; i < chars.length; i++){
            idx = Math.max(idx, edge[chars[i] - 'a']);
            if (i == idx){
                result.add(i - last);
                last = i;
            }
        }

        return result;
    }
}

56 合并区间

利用path合并所需区间

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[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> Integer.compare(a[0],b[0]));

        List<int[]> result = new LinkedList<>();
        int[] path = new int[2];
        path = intervals[0];
        int count = 1;

        for (int i = 1; i < intervals.length; i++){
            if (intervals[i][0] <= path[1]){
                path[1] = Math.max(intervals[i][1], path[1]);
            } else {
                result.add(path);
                count++;
                path = intervals[i];
            }
        }
        result.add(path);
        return result.toArray(new int[count][]);
    }
}