算法训练营（day34）
贪心算法理论基础
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
举个例子，在规定次数内从一堆钞票里怎么拿面额最大的钞票，根据贪心算法的思想：每次拿最大的就好（够贪就行O(∩_∩)O）
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
总而言之，贪心算法的本质其实就是 找到局部最优解，再比较所有的局部最优，得到全局最优。
1005. K 次取反后最大化的数组和
题目链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
- 选择某个下标
i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。以这种方式修改数组后，返回数组 可能的最大和 。
解题思路
解题过程：
思路一：贪心算法
排序
局部最优
当有负数时，优先取反 绝对值较大的 负数
没有负数时，优先取反 绝对值较小 的值
累加
详细代码
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) {
if(nums.length == 1){
return k % 2 == 0 ? nums[0] : nums[1];
}
Arrays.sort(nums);
int sum = 0;
int index = 0;
for(int i = 0; i < k; i++){
if(i < nums.length - 1 && nums[index] < 0){
nums[index] = -nums[index];
if(nums[index] >= Math.abs(nums[index + 1])){
index++;
}
continue;
}
nums[index] = -nums[index];
}
for(int num : nums){
sum += num;
}
return sum;
}
}
|
134. 加油站
题目链接：https://leetcode.cn/problems/gas-station/description/
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
解题思路
解题过程：
思路一：贪心
- 统计总汽油量
totalSum，如果它小于0，必不可能走一圈，返回 -1
- 计算每一段路程的耗油量
curSum，找到 不小于 0 的下标，返回
思路二：贪心
- 统计总汽油量
sum，如果它小于0，必不可能走一圈，返回 -1
- 计算每天剩下的油
min，从 0 开始 判断，如果一圈下来 min 没有出现负数，则说明可以从 下标0 出发
- 如果
min 出现 负数，则说明不能从当前下标出发，从后往前 计算第一个不为负数的节点，即为起始点（说明从这个点出发，油会有剩余，可以补齐后面所需）
详细代码
思路一：贪心
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int totalSum = 0;
int curSum = 0;
int index = 0;
for(int i = 0; i < gas.length; i++){
curSum += (gas[i] - cost[i]);
totalSum += (gas[i] - cost[i]);
if(curSum < 0){
index = (i + 1) % gas.length;
curSum = 0;
}
}
if(totalSum < 0){
return -1;
}
return index;
}
}
|
思路二：贪心
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 sum = 0;
int min = 0;
for(int i = 0; i < gas.length; i++){
sum += gas[i] - cost[i];
min = Math.min(sum, min);
}
if(sum < 0){
return -1;
}
if(min >= 0){
return 0;
}
for(int i = gas.length - 1; i >= 0; i--){
min += (gas[i] - cost[i]);
if(min >= 0){
return i;
}
}
return -1;
}
}
|
135. 分发糖果
题目链接：https://leetcode.cn/problems/candy/description/
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1 个糖果。
- 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
解题思路
解题过程：
局部最优：
- 从左往右：右边比左边大，则右边比左边多一个
- 从右往左：左边比右边大，则判断当前 左边糖果数量 是否比右边糖果数量多，多就不变，少就变成 右边糖果数量 + 1
全局最优：累加，返回
详细代码
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 candy(int[] ratings) {
int len = ratings.length;
int[] candyVec = new int[len];
candyVec[0] = 1;
for(int i = 1; i < len; i++){
candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
}
for(int i = len - 2; i >= 0; i--){
if(ratings[i] > ratings[i + 1]){
candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
}
}
int ans = 0;
for(int num : candyVec){
ans += num;
}
return ans;
}
}
|
