马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
第一题：122.生意业务股票的最佳时机II
解题思绪
本题要求根据给定的股票逐日代价数组 prices，找出能获得的最大利润，解题思绪主要基于贪心算法，焦点思想是只要相邻两天存在代价差（后一天代价高于前一天代价）就能获得利润，我们就抓住这些时机进行生意业务操作，以下是详细阐明：
- 整体思绪：
贪心算法在这里的表现是，我们不考虑整体的生意业务策略规划，而是着眼于每一天的代价变化情况，只要发现第二天的股价比第一天高，那我们就在第一天买入，第二天卖出，这样就能获取这两天之间的差价利润，通过不断累积这些差价利润，终极就能得到总的最大利润。即使代价有波动下降的情况，我们也不用去管它，只关注上涨能带来的利润时机就好。
- 初始化变量：
定义 result 变量用于记录终极能获得的最大利润，初始值设为 0，因为一开始还没有进行任何生意业务，利润为 0。
- 遍历数组计算利润：
通过 for 循环从数组的第二个元素开始遍历（索引为 i，循环条件是 i < prices.length，因为要通过 i - 1 去比力相邻元素，所以从 1 开始），在循环中计算当天代价 prices 与前一天代价 prices[i - 1] 的差值（即 prices - prices[i - 1]），然后取这个差值和 0 中的最大值（通过 Math.max(prices - prices[i - 1], 0)）。这样做的原因是，如果差值大于 0，阐明股价上涨了，能获得利润，这个差值就是这一次 “生意业务” 操作可获得的利润，要累加到 result 中；而如果差值小于等于 0，阐明股价没涨大概下跌了，此时不进行生意业务操作，利润就是 0，不会对总的利润有正向贡献，也就不累加了。
- 最闭幕果返回：
当循环遍历完备个 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;
- }
- }
解题思绪
本题要求判定在给定的非负整数数组 nums 中，从第一个下标出发是否能够到达末了一个下标，解题思绪主要基于贪心算法，焦点思想是不断更新所能覆盖的最远距离，看是否能够覆盖到数组的末了一个位置，以下是详细阐明：
- 整体思绪：
贪心算法在这里的表现是，我们不必要去穷举所有大概的跳跃路径，而是每一步都尽大概地去扩大自己能够到达的最远距离（也就是覆盖范围），只要在遍历过程中发现这个覆盖范围能够达到大概超过末了一个下标位置，那就阐明可以到达末了一个下标，返回 true；反之，如果遍历完所有能到达的位置后，还是没能覆盖到末了一个下标，那就返回 false。
- 界限情况处理：
起首判定如果输入的 nums 数组长度为 1，那意味着只有一个位置，初始就位于这个唯一的下标位置，所以直接返回 true 即可。
- 初始化变量：
定义 coverRange 变量，用于记录当前所能覆盖到的最远距离，初始值设为 0，因为一开始还没有开始跳跃，所能到达的范围就是起始位置（下标为 0 的位置），对应距离为 0。
- 遍历数组更新覆盖范围并判定：
通过 for 循环从数组的第一个元素开始遍历（索引为 i，循环条件是 i <= coverRange，这意味着只遍历当前所能覆盖到的位置范围，超出这个范围的位置暂时还到不了，不用去考虑）。在循环中，更新 coverRange 的值，更新方式是取当前的 coverRange 和 i + nums（也就是当前位置 i 加上在这个位置可以跳跃的最大长度）中的最大值（通过 Math.max(coverRange, i + nums)），这样 coverRange 始终记录着到当前位置为止所能跳到的最远位置。然后判定如果 coverRange 已经大于等于 nums.length - 1，阐明已经能够覆盖到数组的末了一个下标了，直接返回 true。
- 最闭幕果返回：
如果循环竣过后（也就是遍历完了所有能到达的位置，但是还是没有覆盖到末了一个下标），那就返回 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;
- }
- }
解题思绪
本题要求给定一个整数数组 nums，返回从起始位置到达数组末了一个位置 nums[n - 1] 的最小跳跃次数，解题思绪基于贪心算法，焦点在于每次都选择能让覆盖范围尽大概扩大的跳跃策略，以下是详细阐明：
- 整体思绪：
贪心算法的表现是，我们不尝试去罗列所有大概的跳跃组合方式来找到最小跳跃次数，而是在每一步跳跃中，都尽大概选择能拓展更远覆盖范围的位置进行跳跃，通过不断更新覆盖范围以及记录跳跃次数，终极得到到达尽头的最小跳跃次数。
- 界限情况处理：
起首判定如果输入的 nums 数组为 null 大概长度为 0 大概长度为 1。如果数组为 null 大概长度为 0，那天然不存在跳跃一说，直接返回 0；如果长度为 1，意味着一开始就已经在尽头位置了，同样不必要跳跃，也返回 0。
- 变量初始化：
- count：用于记录跳跃的次数，初始值设为 0，因为还没开始跳跃，次数天然是 0。
- curDistance：表示当前的覆盖区域，也就是当前这一跳所能到达的最远距离界限，初始化为 0，因为刚开始还没进行任何跳跃操作，能到达的范围就是起始位置（下标为 0 的位置）。
- maxDistance：代表最大的覆盖区域，用于在当前可覆盖的范围内去寻找下一步能拓展到的最远位置，初始也设为 0，同样是基于起始位置还没开始拓展的初始状态来设定的。
- 遍历数组并更新相关状态：
通过 for 循环从数组的第一个元素开始依次遍历（索引为 i）。在循环中有以下几个关键操作：
- 更新最大覆盖区域：
计算当前位置 i 加上其能跳跃的最大长度 nums（即 i + nums），然后取它和当前的 maxDistance 中的最大值来更新 maxDistance（通过 Math.max(maxDistance, i + nums)），这样 maxDistance 始终记录着从当前已走过的位置出发，下一步大概跳到的最远位置范围，这个范围是不断动态更新的，只要还在当前的可覆盖区域内（也就是 i 还没超出当前能到达的范围），就要持续更新这个最远可到达范围。
- 判定是否接近尽头：
如果 maxDistance 大于等于 nums.length - 1，阐明通过当前的覆盖范围已经能够到达大概超过数组的末了一个位置了，那此时只必要再跳一次就可以到达尽头，所以将 count 加 1 后直接通过 break 跳出循环，因为已经找到了到达尽头的最小跳跃次数了。
- 更新当前覆盖区域与跳跃次数：
当 i 等于 curDistance 时，意味着已经走到了当前这一跳所能覆盖区域的界限位置了，此时必要进行下一步跳跃，那么就把 curDistance 更新为 maxDistance，也就是把下一步跳跃的起始位置所能覆盖的范围更新为之前找到的最大覆盖范围，同时将 count（跳跃次数）加 1，表示进行了一次新的跳跃操作，然后继承循环去寻找下一次跳跃后能拓展到的更远范围等情况。
- 最闭幕果返回：
当循环竣事（正常竣事大概通过 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;
- }
- }
解题思绪
本题要求对给定的整数数组 nums 进行 k 次取反操作，使得终极数组的和最大，整体解题思绪可以分为以下几步，且运用了贪心算法的思想，即每一步都做出当下能使结果更优的选择：
- 整体策略：
为了让数组和最大，优先把负数变为正数会使和增大，所以要尽量先对负数进行取反操作。如果 k 次操作完负数都取反完了还有剩余操作次数，那就考虑对最小的非负数值进行取反（因为取反后对总和的影响最小），以此来得到最大的数组和。
- 数组排序预处理：
起首通过 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 类型数组。这样排序的目标是，后续遍历数组时，能优先处理绝对值大的负数（将其取反能让总和增加得更多），以及方便后续处理剩余取反次数时找到数值最小的元素（绝对值小的元素排在反面）。
- 遍历数组处理负数取反：
通过 for 循环从数组的第一个元素开始遍历（索引为 i），在循环中判定如果当前元素 nums 是负数并且 k 大于 0，那就阐明还有取反次数可用，且当前遇到了可以使总和增大的负数，此时将这个负数取反（通过 nums = -nums），同时把 k 的值减 1，表示已经用掉了一次取反操作。
- 处理剩余取反次数：
当遍历完数组大概 k 变为 0 后，大概存在 k 还有剩余的情况（也就是还有取反次数没用完）。此时判定如果 k 是奇数（通过 k % 2 == 1 判定），那就阐明还必要再进行一次取反操作，为了让总和尽量大，选择数组中数值最小的元素进行取反，在已经排好序的数组中，数值最小的元素就是末了一个元素 nums[len - 1]（因为是按照绝对值从大到小排序的，绝对值小的元素在反面），所以将 nums[len - 1] 取反（通过 nums[len - 1] = -nums[len - 1]），把这末了一次取反操作用完。
- 计算并返回终极数组和：
末了通过 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();
- }
- }
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
