【4.18】贪心算法入门必刷题

买卖股票的最佳时机 II

• 122. 买卖股票的最佳时机 II - 力扣（LeetCode）

  解法一：动态规划

  class Solution {public int maxProfit(int[] prices) {int n = prices.length;int [][] dp = new int [n][2];dp[0][0] = 0;dp[0][1] = - prices[0];for(int i = 1 ; i < n ; i ++){//第i天不持有，第i - 1天持有，今天刚卖出去 ，或者第i - 1天就不持有dp[i][0] = Math.max(dp[i - 1][1] + prices[i] , dp[i - 1][0]);//第i天持有，今天才持有 / 之前就持有dp[i][1] = Math.max(dp[i - 1][1] , dp[i - 1][0] - prices[i]);}return dp[n - 1][0];}
  }
  

  解法二：贪心算法

  假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。

  相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

  此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！

  那么根据prices可以得到每天的利润序列：(prices[i] - prices[i - 1])…(prices[1] - prices[0])。

  所以可以使用贪心算法，局部最优就是每天都是正利润，这样就可以获得全局最优！

  class Solution {public int maxProfit(int[] prices) {int result = 0;for(int i = 1 ; i < prices.length ; i ++){int path = prices[i] - prices[i - 1];if( path > 0){result += path;}}return result;}
  }
  

跳跃游戏

• 55. 跳跃游戏 - 力扣（LeetCode）

  随着对nums的遍历更新覆盖范围，遍历范围也随着覆盖范围的更新而更新。

  class Solution {//最优子问题：在符合条件的范围内，每次跳到数字最大的下标上。public boolean canJump(int[] nums) {int cover = 0;for(int i = 0 ; i <= cover ; i ++){cover = Math.max(i + nums[i] , cover);if(cover >= nums.length - 1){return true;}}return false;}
  }
  

跳跃游戏 II

• 45. 跳跃游戏 II - 力扣（LeetCode）

  跳跃问题找的是覆盖距离，最远覆盖距离是当前走到的距离 + 当前下标的覆盖距离。

  所以最远覆盖距离都是从0开始算的。而i也是从0开始找的，如果碰到了最远的距离，说明不能继续往前走了，此时就要比较这个最远覆盖距离是否已经超过了界限。

  class Solution {public int jump(int[] nums) {//当前可以覆盖的最远距离的下标。int maxCover = 0;//下一个可以覆盖的最远距离下标。int next_maxCover = 0;//记录最大步数。int ans = 0;for(int i = 0 ; i < nums.length ; i ++){next_maxCover = Math.max(i + nums[i] , next_maxCover); //找到最远覆盖距离下标//遇到当前最远覆盖距离下标if(i == maxCover){//当前不是终点if(maxCover < nums.length - 1){ans ++;maxCover = next_maxCover;}else break;}}return ans;}
  }
  

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

• 1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

  解法一：

  class Solution {public int largestSumAfterKNegations(int[] nums, int k) {//局部最优：将绝对值从大到小排序，之后从头开始反转，如果是负数Arrays.sort(nums);while(k > 0){nums[0] = - nums[0];Arrays.sort(nums);k --;}int sum = 0;for(int i : nums){sum += i;}return sum;}
  }
  

  解法二：

  局部最优处理：对数组排序，遇到负数，就反转。如果下一个还是负数，就继续反转。否则遇到正数就正常反转。

  class Solution {public int largestSumAfterKNegations(int[] nums, int k) {//局部最优：将绝对值从大到小排序，之后从头开始反转，如果是负数Arrays.sort(nums);int idx = 0;for(int i = 0 ; i < k ; i ++){//nums[idx]是负数if(idx < nums.length - 1 && nums[idx] < 0){nums[idx] = - nums[idx];//如果下一个还是负数,idx ++，往下反转if(nums[idx] >= Math.abs(nums[idx + 1])) idx ++;continue;}nums[idx] = - nums[idx];}int sum = 0;for(int i : nums){sum += i;}return sum;}
  }