代码随想录算法训练营第二十八天-122买卖股票的最佳时机II、55 跳跃游戏、45跳跃游戏II、1005K次取反后最大化的数组和

前言
状态：122AC，55 看了题解 AC，45AC，题解代码更简单一点
更新

1	24-06-14 初始记录

初步题解

122 买卖股票的最佳时机 II

题目链接：(https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii)

画图很简单

/**  
 * 就是算所有增区间的值  
 * @param prices 列表  
 * @return 股票金额  
 */  
public int maxProfit(int[] prices) {  
    int sum = 0;  
  
    for (int i = 1; i < prices.length; i++) {  
        if (prices[i] >= prices[i - 1]) {  
            sum +=prices[i] - prices[i - 1];  
        }  
    }  
  
    return sum;  
}

55 跳跃游戏

题目链接：(https://leetcode.cn/problems/jump-game/)

没有思路。看了部分题解，说是求覆盖最大的范围。

public static boolean canJump(int[] nums) {  
    int maxIndex = 0;  
  
    for (int i = 0; i < nums.length; i++) {  
        if (i > maxIndex) {  
            return false;  
        }  

		// 这里看了题解优化了一下
        maxIndex = Math.max(nums[i] + i, maxIndex);  
        if (maxIndex >= nums.length - 1){  
            return true;  
        }  
    }  
    return false;  
}

45 跳跃游戏 II

题目链接：(https://leetcode.cn/problems/jump-game-ii/)

/**  
 * 假设每次都跳跃区间内最远的距离  
 * @param nums 数组  
 * @return 结果  
 */  
public static int jump(int[] nums) {  
    int maxIndex = 0;  
    int maxJ = 0;  
    int count = 0;  
  
    if (nums.length == 1) {  
        return count;  
    }  
  
    for (int i = 0; i < nums.length;) {  
        if (i + nums[i] >= nums.length - 1) {  
            count++;  
            return count;  
        }  
  
        for (int j = i + 1; j <= i + nums[i] && j < nums.length; j++) {  
  
            if (j + nums[j] >= maxIndex) {  
                maxIndex = j + nums[j];  
                maxJ = j;  
            }  
        }  
        count++;  
        i = maxJ;  
    }  
  
    return count;  
}

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

题目链接：(https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations)

/**  
 * 思路：可以多次选择同一个数字，返回最大和，说明可以先排序  
 * 1. 从小到大排列， 把所有负数变正  
 * 2. 还有次数剩余。奇数次剩余，就把绝对值最小的翻转一次。  
 *  
 * @param nums 数组  
 * @param k 翻转次数  
 * @return 结果  
 */  
public static int largestSumAfterKNegations(int[] nums, int k) {  
    Arrays.sort(nums);  
    int minAbs = Integer.MAX_VALUE;  
    int index = 0;  
    int sum = 0;  
  
    for (int i = 0; i < nums.length; i++) {  
  
        if (Math.abs(nums[i]) < minAbs) {  
            minAbs = Math.min(minAbs, Math.abs(nums[i]));  
            index = i;  
        }  
  
        if (k > 0 && nums[i] < 0) {  
            nums[i] = -nums[i];  
            k--;  
        }  
        sum += nums[i];  
    }  
  
    if (k % 2 == 1) {  
        sum -= 2 * nums[index];  
    }  
  
    return sum;  
}

看解析

题解的思路在于增加覆盖范围。每更新一次覆盖范围，就结果 +1（这里比较绕，但是这样就不用双层循环了）。

简化版本：

public int jump(int[] nums) {
      int result = 0;
      // 当前覆盖的最远距离下标
      int end = 0;
      // 下一步覆盖的最远距离下标
      int temp = 0;
      for (int i = 0; i <= end && end < nums.length - 1; ++i) {
          temp = Math.max(temp, i + nums[i]);
          // 可达位置的改变次数就是跳跃次数
          if (i == end) {
              end = temp;
              result++;
          }
      }
      return result;
  }

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

解析：(https://programmercarl.com/1005.K次取反后最大化的数组和.html)