Leetcode 刷题记录 18—— 贪心算法

本系列为笔者的 Leetcode 刷题记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答，01~07为C++语言，08及以后为Java语言。

01 买卖股票的最佳时机

class Solution {public int maxProfit(int[] prices) {int minPrice = prices[0];int ans = 0;for(int i=0; i<prices.length; i++){//最低股票价格minPrice = Math.min(prices[i], minPrice);//当日股票价格 - 最低股票价格 取最大值ans = Math.max(prices[i] - minPrice, ans); }return ans;}
}

02 跳跃游戏

class Solution {public boolean canJump(int[] nums) {//只要道路不断延申，人终将走到终点int path = 0;for(int i=0; i<nums.length; i++){if(i > k) return false;k = Math.max(k, i + nums[i]);}return true;}
}

03 跳跃游戏Ⅱ

class Solution {public int jump(int[] nums) {int ans = 0, path = 0;int start = 0, end = 1; //初始起跳范围，左闭右开区间while(end < nums.length){for(int i=start; i<end; i++){path = Math.max(path, i + nums[i]);}//更新起跳范围start = end;end = path + 1;ans++;}return ans;}
}

04 划分字母区间

class Solution {public List<Integer> partitionLabels(String s) {int[] last = new int[26];int n = s.length();for(int i=0; i<n; i++){last[s.charAt(i) - 'a'] = i; //字母 -> 索引}List<Integer> partition = new LinkedList<>();int start = 0, end = 0;for(int i=0; i<n; i++){end = Math.max(end, last[s.charAt(i) - 'a']);if(end == i){partition.add(end - start + 1);start = end + 1;}}return partition;}
}