leetcode hot100贪心

🔟 贪心

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

题解:

• 维护股价最小值, 维护利润最大值即可

• class Solution {
      public int maxProfit(int[] prices) {
          int n = prices.length;
          int minTemp=prices[0],maxTemp;
          int profit=0;
          for(int i=1;i<n;i++){
              if(prices[i]<=minTemp){
                  minTemp = prices[i];
              }else{
                  maxTemp=prices[i];
                  profit=Math.max(profit,maxTemp-minTemp);
              }
          }
          return profit;
      }
  }
  

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

题解:

• 我最初的想法是, 从索引0出发,尽可能多的走远, 如果走远不能到达/即碰到跳跃0步就break; 然后减少出发的步大小, 这个思路能过80的数据, 直到[1,2,2,0,3]:

  • 这样在nums[1]的时候就会直接跳到nums[3]处即跳跃0步不能往前走了, 然后break, 0处步大小–至为0, return false
  • 思路漏洞很明显, 只考虑了0处的步伐缩小, 没有考虑其他索引的最大值

• 思路:维护在索引i的最大值, 遍历数组,查看maxReach能否到达该处索引, 如果能到达, 更新maxReach:

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

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:0 <= j <= nums[i] i + j < n返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

题解:

• 如果要获取当前的下一步能够跳跃的最远的范围, 就要在当前范围内, 计算当前范围内索引值的跳跃值/也就是下一步的下一步跳得有多远,

• 所以当到达当前最大跳跃值后(i=end), 那么当前的最远距离就是刚才计算的上一跳的范围内索引值的最远跳跃值

• 所以只要保证n-1在最远跳跃范围内,即n-1<=furthest即可

• class Solution {
      public int jump(int[] nums) {
          int n=nums.length;
          int step=0,end=0,furthest=0;
          for(int i=0;i<n-1;i++){
              furthest=Math.max(furthest,i+nums[i]);
              //只要i!=end,就说明目前仍在上一跳的范围内, 上一跳能够直接跳到这,要设置i<n-1而不是i<n;就是以防n-1刚好是end的边界值, 如此在此处step又要预先跳一步了
              if(i==end){
                  step++;
                  end=furthest;
              }
          }
          return step;
      }
  }
  

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。返回一个表示每个字符串片段的长度的列表。

题解:

• 用哈希表存储每个单词出现的最远的地方, 循环遍历每次维护一个最长字段大小,

• 直至每次遍历的值的最远距离均小于当前最长字段/i==maxLength, 那么将当前的最长字段存入res, 更新计算mL

• class Solution {
      public List<Integer> partitionLabels(String s) {
          Map<Character,Integer> map = new HashMap<>();
          int n = s.length();
          for(int i=0;i<n;i++){
              map.put(s.charAt(i),i);
          }
          List<Integer> res = new ArrayList<>();
          int mL=0,start=0;
          for(int i=0;i<n;i++){
              mL=Math.max(mL,map.get(s.charAt(i)));
              if(i==mL){
                  res.add(i-start+1);
                  start=i+1;
              }
          }
          return res;
      }
  }