【算法刷题day34】Leetcode：1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果

草稿图网站
java的Deque

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

题目：1005. K 次取反后最大化的数组和
解析：代码随想录解析

解题思路

使用绝对值大小来排序，可以避免找哪个是最小的不必要的判断

代码

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // Arrays.sort(nums);
        nums = IntStream.of(nums)//将传入的整型数组 nums 转换为一个原始类型流（IntStream）
                        .boxed()//IntStream 装箱为 Stream<Integer>，以便后续可以使用泛型方法操作流中的元素。
                        .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))//传入一个比较器（Comparator）
                        .mapToInt(Integer::intValue).toArray();//将装箱后的流中的元素转换为整型。//返回一个包含流中所有元素的数组。

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

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

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

总结

数组求和方式Arrays.stream(nums).sum();

Leetcode 134. 加油站

题目：134. 加油站
解析：代码随想录解析

解题思路

若当前和<0，总和>=0，则当前和的下一个元素可以成为起点

代码

//暴力，以每个站点为起点走一轮
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for (int i = 0; i < gas.length; i++) {
            int res = gas[i] - cost[i];
            int index = (i + 1) % gas.length;
            while (res > 0 && index != i) {
                res += gas[index] - cost[index];
                index = (index + 1) % gas.length;
            }
            if (res >= 0 && index == i)
                return i;
        }
        return -1;
    }
}

//贪心
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = -1;
        for (int i = 0; i < gas.length; i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {
                start = i + 1;
                curSum = 0;
            }
        }
        if (totalSum < 0) return -1;
        return start;
    }
}

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
29
30
31
32
33
34
35
36

总结

暂无

Leetcode 135. 分发糖果

题目：135. 分发糖果
解析：代码随想录解析

解题思路

先给每人一颗，然后从左到右加一轮，从右到左加一轮（这一轮加的时候要取原来的糖果数和加的糖果数的最大值）。

代码

class Solution {
    public int candy(int[] ratings) {
        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] = Math.max(candies[i], candies[i+1] + 1);
        }
        return Arrays.stream(candies).sum();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

总结

从右到左的时候，刚开始使用的是candies[i] =candies[i+1] + 1;而不是candies[i] = Math.max(candies[i], candies[i+1] + 1);这导致可能破坏从左到右的规则。