第八章 贪心算法 part02
122.买卖股票的最佳时机II
本题解法很巧妙，本题大家可以先自己思考一下然后再看题解，会有惊喜！
文章讲解
思路
- 把利润分解为每天的维度，只收集正利润
class Solution {
public int maxProfit(int[] prices) {
int result = 0;
for(int i = 1; i < prices.length; i++){
result += Math.max(prices[i]-prices[i-1], 0);
}
return result;
}
}
55. 跳跃游戏
本题如果没接触过，很难想到，所以不要自己憋时间太久，读题思考一会，没思路立刻看题解
文章讲解
思路
- 判断跳跃范围能不能覆盖到终点
class Solution {
public boolean canJump(int[] nums) {
int cover = 0;
if(nums.length == 1) return true;
for(int i = 0; i <= cover; i++){
cover = Math.max(i + nums[i], cover);
if(cover >= nums.length-1) return true;
}
return false;
}
}
45.跳跃游戏II
本题同样不容易想出来。贪心就是这样，有的时候 会感觉简单到离谱，有时候，难的不行，主要是不容易想到。
文章讲解
思路
- 尽可能跳最大值，但是写代码时不能这样实现。
- 比如 [2,3,1,1,4]，在最开始的位置不能跳两步，而是应该先跳到3的位置
- 依然是用尽量少的步数来增加更多覆盖范围。只记录下一步最大的覆盖范围。
class Solution {
public int jump(int[] nums) {
if (nums.length == 1) return 0;
int curDistance = 0; // 当前覆盖最远距离下标
int nextDistance = 0; // 下一步覆盖最远距离下标
int result = 0; // 记录走的最大步数
for(int i = 0; i < nums.length; i++){ //开始遍历数组，收集下一步能跳多远
nextDistance = Math.max(nums[i] + i, nextDistance); //只记录最远的记录
if(i == curDistance){ //i移动到了当前的覆盖范围之后，发现也没有到终点，要再走一步到终点
if(curDistance < nums.length-1){ // 当前的范围小于数组长度，必须要再走一步增加覆盖范围
result++;
curDistance = nextDistance;
// 如果当前覆盖范围已经到达或超过数组的最后一个元素，退出循环
if (curDistance >= nums.length - 1) {
break;
}
}
}
}
return result;
}
}
但实际上代码随想录的少一个if
1005.K次取反后最大化的数组和
本题简单一些，估计大家不用想着贪心 ，用自己直觉也会有思路。
文章讲解
思路
第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
第二步：从前向后遍历，遇到负数将其变为正数，同时K--
第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
第四步：求和
- 注意一下Lambda表达式
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
// 对数组按绝对值从大到小排序
//nums = Arrays.sort(nums, (a, b) -> Integer.compare(Math.abs(b), Math.abs(a))); 不能这样写
nums = IntStream.of(nums)
.boxed()
.sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
.mapToInt(Integer::intValue)
.toArray();
//绝对值从大到小排列 因为
// Integer.compare(x, y) 方法比较两个整数 x 和 y：如果 x < y，返回负数（表示 a 应该排在 b 前面）。如果 x == y，返回 0（表示 a 和 b 的顺序不变）。如果 x > y，返回正数（表示 b 应该排在 a 前面）。
// 依次将负数变为正数，优先处理绝对值最大的
for(int i = 0; i < nums.length && k > 0; i++){ // 注意这里还有K>0
if(nums[i] < 0){
nums[i] = - nums[i];
k--;
}
}
// 如果K还大于0，且K是奇数，转变数值最小的元素, 因为如果k是偶数，正负转换结果不变
if(k % 2 == 1) nums[nums.length - 1] = -nums[nums.length - 1];
//计算结果 将数组 nums 转换为一个 IntStream 对象再求sum
int sum = Arrays.stream(nums).sum();
return sum;
}
}
