代码随想录第三十四天

Posted on Edited 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 (indexG < g.length){
                if (s[indexS] >= g[indexG]){
                    count++;
                    indexG++;
                }
                indexS++;
            } else {
                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.length == 0 || nums == null) 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
15
16
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(sum, maxSum);
            if (sum < 0){
                sum = 0;
            }
        }

        return maxSum;
    }
}

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
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 < nums.length; 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
20
21
22
23
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次取反后最大化的数组和

贪心思路
把绝对值最大的负数变成正数，之后反复变换最小值

具体解法把数组通过绝对值由大到小排列，之后找到负数把他变成正数，如果K值还剩单数，则变换绝对值最小的数

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 largestSumAfterKNegations(int[] nums, int k) {
        nums = IntStream.of(nums)
		     .boxed()
		     .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
		     .mapToInt(Integer::intValue).toArray();

        for (int i = 0; i < nums.length; i++){
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        if (k % 2 == 1){
            nums[nums.length - 1] = -nums[nums.length - 1];
        }

        return Arrays.stream(nums).sum();
    }
}

直接sortArray， 如果有负数，负数的绝对值最大的数就会排在前面，变换负数，记录最小的值，在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) {
        Arrays.sort(nums);
        int min = Integer.MAX_VALUE;
        int index = 0;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }

            if (Math.abs(nums[i]) < min){
                min = Math.abs(nums[i]);
                index = i;
            }
        }

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

134 加油站

暴力解法就是模拟每一个点都是起点，没有就退出

贪心 方法一：

  1. 如果gas总和小于cost总和，一定不行
  2. 利用剩下的油，从0累加到最后一站，没有负数，就是从0出发的
  3. 如果累加的最小值是负数，从后向前，看哪个节点能把负数填平
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 canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < gas.length; i++){
            int rest = gas[i] - cost[i];
            curSum += rest;
            if (curSum < min){
                min = curSum;
            }
        }

        if (curSum < 0) return -1;
        if (min >= 0) return 0;

        for (int i = gas.length - 1; i >= 0; i--){
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) return i;
        }

        return -1;
    }
}

贪心二：

  1. gas总和小于cost总和一定不行
  2. 剩下的油如果累加时出现负值，更新index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int index = 0;
        int sum = 0;
        for (int i = 0; i < gas.length; i++){
            int rest = gas[i] - cost[i];
            curSum += rest;
            sum += rest;
            if (curSum < 0){
                index = i + 1;
                curSum = 0;
            }
        }
        
        if (sum < 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;
        if (ratings.length == 1) return 1;
        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] > 0 && candies[i] <= candies[i + 1]){
                candies[i] = candies[i + 1] + 1;
            }
        }
        int sum = 0;
        for (int i : candies){
            sum += i;
        }
        return sum;
    }
}