贪心思想
保证每次操作都是局部最优的,并且最后得到的结果是全局最优的——减少遍历的次数
1.买卖股票的最佳时机 121简单
这里的贪心思想是更新股票的最低价和最大利润,规则是先买后卖
class Solution { public int maxProfit(int[] prices) { // 记录股票的最低价 int minPrice = Integer.MAX_VALUE; // 记录最大利润 int maxProfit = 0; for (int i = 0; i < prices.length; i++) { if (prices[i] < minPrice) { minPrice = prices[i]; } else if (prices[i] - minPrice > maxProfit) { maxProfit = prices[i] - minPrice; } } return maxProfit; } }
2. 跳跃游戏 55 中等
这里的贪心是每次跳跃都有多种选择,每次选择跳跃最大的
class Solution { public boolean canJump(int[] nums) { int k = 0; for (int i = 0; i < nums.length; i++) { if (i > k) return false; k = Math.max(k, i + nums[i]); } return true; } }
3. 跳跃游戏 II 45 中等
for循环中的减1是因为跳到最后一个元素位置的时候,此次游戏就已经结束了。这里的贪心是每次跳跃的最大位置如果刚好是i所在的位置,那么需要一次跳跃。
class Solution { public int jump(int[] nums) { // 记录每次能iao的最大范围 int k = 0; // 跳到最后一个位置需要跳跃的总次数 int sum = 0; // 能跳到的最远的位置 int end = 0; for (int i = 0; i < nums.length - 1; i++) { // if (k >= nums.length - 1) { // break; // } k = Math.max(k, nums[i] + i); if (i == end) { end = k; sum++; } System.out.println(k); } return sum; } }
4. 划分字母区间 763 中等
贪心就是找一个区间内每个字母出现的最后位置,一个区间的结束刚好等于i的时候,说明这个区间结束了,定义start是本题需要返回区间的长度,end和start可以方便计算区间长度,比每次遍历长度+1节省性能。
class Solution { public ListpartitionLabels(String s) { // 遍历一次数组,找到每个字母最后一次的下标 int[] last = new int[26]; int sLength = s.length(); for (int i = 0; i < sLength; i++) { last[s.charAt(i) - 'a'] = i; } // 遍历数组,更新max,如果i==max,说明可以在这个位置分割字符串了 // 存储结果的序列 List partition = new ArrayList (); int start = 0; int end = 0; for (int i = 0; i < sLength; i++) { end = Math.max(end, last[s.charAt(i) - 'a']); if (end == i) { partition.add(end - start + 1); start = end + 1; } } return partition; } }