day 28 第八章 贪心算法 part02

第一题：122.买卖股票的最佳时机II

解题思路

本题要求根据给定的股票每日价格数组 prices，找出能获得的最大利润，解题思路主要基于贪心算法，核心思想是只要相邻两天存在价格差（后一天价格高于前一天价格）就能获得利润，我们就抓住这些机会进行买卖操作，以下是详细说明：

1. 整体思路：
   贪心算法在这里的体现是，我们不考虑整体的买卖策略规划，而是着眼于每一天的价格变化情况，只要发现第二天的股价比第一天高，那我们就在第一天买入，第二天卖出，这样就能获取这两天之间的差价利润，通过不断累积这些差价利润，最终就能得到总的最大利润。即使价格有波动下降的情况，我们也不用去管它，只关注上涨能带来的利润机会就好。

2. 初始化变量：
   定义 result 变量用于记录最终能获得的最大利润，初始值设为 0，因为一开始还没有进行任何交易，利润为 0。

3. 遍历数组计算利润：
   通过 for 循环从数组的第二个元素开始遍历（索引为 i，循环条件是 i < prices.length，因为要通过 i - 1 去比较相邻元素，所以从 1 开始），在循环中计算当天价格 prices[i] 与前一天价格 prices[i - 1] 的差值（即 prices[i] - prices[i - 1]），然后取这个差值和 0 中的最大值（通过 Math.max(prices[i] - prices[i - 1], 0)）。这样做的原因是，如果差值大于 0，说明股价上涨了，能获得利润，这个差值就是这一次 “买卖” 操作可获得的利润，要累加到 result 中；而如果差值小于等于 0，说明股价没涨或者下跌了，此时不进行买卖操作，利润就是 0，不会对总的利润有正向贡献，也就不累加了。

4. 最终结果返回：
   当循环遍历完整个 prices 数组后，result 中记录的就是通过抓住所有股价上涨的机会进行买卖操作所能获得的最大利润，直接返回 result 即可。

代码

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跳跃游戏 

解题思路

本题要求判断在给定的非负整数数组 nums 中，从第一个下标出发是否能够到达最后一个下标，解题思路主要基于贪心算法，核心思想是不断更新所能覆盖的最远距离，看是否能够覆盖到数组的最后一个位置，以下是详细说明：

1. 整体思路：
   贪心算法在这里的体现是，我们不需要去穷举所有可能的跳跃路径，而是每一步都尽可能地去扩大自己能够到达的最远距离（也就是覆盖范围），只要在遍历过程中发现这个覆盖范围能够达到或者超过最后一个下标位置，那就说明可以到达最后一个下标，返回 true；反之，如果遍历完所有能到达的位置后，还是没能覆盖到最后一个下标，那就返回 false。

2. 边界情况处理：
   首先判断如果输入的 nums 数组长度为 1，那意味着只有一个位置，初始就位于这个唯一的下标位置，所以直接返回 true 即可。

3. 初始化变量：
   定义 coverRange 变量，用于记录当前所能覆盖到的最远距离，初始值设为 0，因为一开始还没有开始跳跃，所能到达的范围就是起始位置（下标为 0 的位置），对应距离为 0。

4. 遍历数组更新覆盖范围并判断：
   通过 for 循环从数组的第一个元素开始遍历（索引为 i，循环条件是 i <= coverRange，这意味着只遍历当前所能覆盖到的位置范围，超出这个范围的位置暂时还到不了，不用去考虑）。在循环中，更新 coverRange 的值，更新方式是取当前的 coverRange 和 i + nums[i]（也就是当前位置 i 加上在这个位置可以跳跃的最大长度）中的最大值（通过 Math.max(coverRange, i + nums[i])），这样 coverRange 始终记录着到当前位置为止所能跳到的最远位置。然后判断如果 coverRange 已经大于等于 nums.length - 1，说明已经能够覆盖到数组的最后一个下标了，直接返回 true。

5. 最终结果返回：
   如果循环结束后（也就是遍历完了所有能到达的位置，但是还是没有覆盖到最后一个下标），那就返回 false，表示无法到达最后一个下标。

代码

class Solution {public boolean canJump(int[] nums) {if(nums.length == 1){return true;}int coverRange = 0;for(int i = 0;i <= coverRange;i++){coverRange = Math.max(coverRange,i + nums[i]);if(coverRange >= nums.length - 1){return true;}}return false;}
}

第三题：跳跃游戏II

 

解题思路

本题要求给定一个整数数组 nums，返回从起始位置到达数组最后一个位置 nums[n - 1] 的最小跳跃次数，解题思路基于贪心算法，核心在于每次都选择能让覆盖范围尽可能扩大的跳跃策略，以下是详细说明：

1. 整体思路：
   贪心算法的体现是，我们不尝试去枚举所有可能的跳跃组合方式来找到最小跳跃次数，而是在每一步跳跃中，都尽可能选择能拓展更远覆盖范围的位置进行跳跃，通过不断更新覆盖范围以及记录跳跃次数，最终得到到达终点的最小跳跃次数。

2. 边界情况处理：
   首先判断如果输入的 nums 数组为 null 或者长度为 0 或者长度为 1。如果数组为 null 或者长度为 0，那自然不存在跳跃一说，直接返回 0；如果长度为 1，意味着一开始就已经在终点位置了，同样不需要跳跃，也返回 0。

3. 变量初始化：

   • count：用于记录跳跃的次数，初始值设为 0，因为还没开始跳跃，次数自然是 0。
   • curDistance：表示当前的覆盖区域，也就是当前这一跳所能到达的最远距离边界，初始化为 0，因为刚开始还没进行任何跳跃操作，能到达的范围就是起始位置（下标为 0 的位置）。
   • maxDistance：代表最大的覆盖区域，用于在当前可覆盖的范围内去寻找下一步能拓展到的最远位置，初始也设为 0，同样是基于起始位置还没开始拓展的初始状态来设定的。

4. 遍历数组并更新相关状态：
   通过 for 循环从数组的第一个元素开始依次遍历（索引为 i）。在循环中有以下几个关键操作：

   • 更新最大覆盖区域：
     计算当前位置 i 加上其能跳跃的最大长度 nums[i]（即 i + nums[i]），然后取它和当前的 maxDistance 中的最大值来更新 maxDistance（通过 Math.max(maxDistance, i + nums[i])），这样 maxDistance 始终记录着从当前已走过的位置出发，下一步可能跳到的最远位置范围，这个范围是不断动态更新的，只要还在当前的可覆盖区域内（也就是 i 还没超出当前能到达的范围），就要持续更新这个最远可到达范围。
   • 判断是否接近终点：
     如果 maxDistance 大于等于 nums.length - 1，说明通过当前的覆盖范围已经能够到达或者超过数组的最后一个位置了，那此时只需要再跳一次就可以到达终点，所以将 count 加 1 后直接通过 break 跳出循环，因为已经找到了到达终点的最小跳跃次数了。
   • 更新当前覆盖区域与跳跃次数：
     当 i 等于 curDistance 时，意味着已经走到了当前这一跳所能覆盖区域的边界位置了，此时需要进行下一步跳跃，那么就把 curDistance 更新为 maxDistance，也就是把下一步跳跃的起始位置所能覆盖的范围更新为之前找到的最大覆盖范围，同时将 count（跳跃次数）加 1，表示进行了一次新的跳跃操作，然后继续循环去寻找下一次跳跃后能拓展到的更远范围等情况。

5. 最终结果返回：
   当循环结束（正常结束或者通过 break 跳出循环）后，count 中记录的就是到达数组最后一个位置所需要的最小跳跃次数，直接返回 count 即可。

代码

class Solution {public int jump(int[] nums) {if(nums == null || nums.length == 0 || nums.length == 1){return 0;}//记录跳跃的次数int count = 0;//当前的覆盖区域int curDistance = 0;//最大的覆盖区域int maxDistance = 0;for(int i = 0;i < nums.length;i++){//在可覆盖区域内更新最大的覆盖区域maxDistance = Math.max(maxDistance,i + nums[i]);//说明当前一步，再跳一步就到达了末尾if(maxDistance >= nums.length - 1){count++;break;}//走到当前覆盖的最大区域时，更新下一步可达的最大区域if(i == curDistance){curDistance = maxDistance;count++;}}return count;}
}

 第四题：1005.K次取反后最大化的数组和

解题思路

本题要求对给定的整数数组 nums 进行 k 次取反操作，使得最终数组的和最大，整体解题思路可以分为以下几步，且运用了贪心算法的思想，即每一步都做出当下能使结果更优的选择：

1. 整体策略：
   为了让数组和最大，优先把负数变为正数会使和增大，所以要尽量先对负数进行取反操作。如果 k 次操作完负数都取反完了还有剩余操作次数，那就考虑对最小的非负数值进行取反（因为取反后对总和的影响最小），以此来得到最大的数组和。

2. 数组排序预处理：
   首先通过 IntStream.of(nums).boxed().sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray(); 这一系列操作对数组 nums 进行处理。这里是将数组先转换为流，再转换为 boxed（包装类型），然后按照元素绝对值从大到小进行排序（通过自定义的比较器 Math.abs(o2) - Math.abs(o1)），最后再转换回 int 类型数组。这样排序的目的是，后续遍历数组时，能优先处理绝对值大的负数（将其取反能让总和增加得更多），以及方便后续处理剩余取反次数时找到数值最小的元素（绝对值小的元素排在后面）。

3. 遍历数组处理负数取反：
   通过 for 循环从数组的第一个元素开始遍历（索引为 i），在循环中判断如果当前元素 nums[i] 是负数并且 k 大于 0，那就说明还有取反次数可用，且当前遇到了可以使总和增大的负数，此时将这个负数取反（通过 nums[i] = -nums[i]），同时把 k 的值减 1，表示已经用掉了一次取反操作。

4. 处理剩余取反次数：
   当遍历完数组或者 k 变为 0 后，可能存在 k 还有剩余的情况（也就是还有取反次数没用完）。此时判断如果 k 是奇数（通过 k % 2 == 1 判断），那就说明还需要再进行一次取反操作，为了让总和尽量大，选择数组中数值最小的元素进行取反，在已经排好序的数组中，数值最小的元素就是最后一个元素 nums[len - 1]（因为是按照绝对值从大到小排序的，绝对值小的元素在后面），所以将 nums[len - 1] 取反（通过 nums[len - 1] = -nums[len - 1]），把这最后一次取反操作用完。

5. 计算并返回最终数组和：
   最后通过 Arrays.stream(nums).sum(); 计算经过上述取反操作后的数组所有元素的总和，这个总和就是经过 k 次取反后能得到的最大数组和，直接将其返回即可。

代码

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();int len = nums.length;for(int i = 0;i < len;i++){//从前向后遍历，遇到负数就将其变为正数，同时k--if(nums[i] < 0 && k > 0){nums[i] = -nums[i];k--;}}//如果k还大于0，那么反复转变数值最小的元素，将k用完if(k % 2 == 1){nums[len - 1] = -nums[len - 1];}return Arrays.stream(nums).sum();}
}