贪心算法【Lecode_HOT100】

1.买卖股票的最佳时机No.121

class Solution {public int maxProfit(int[] prices) {if (prices == null || prices.length == 0) {return 0;}// 初始化买入价格为最大值，最大利润为 0int minPrice = Integer.MAX_VALUE;int maxProfit = 0;// 遍历价格数组for (int price : prices) {// 更新最低买入价格if (price < minPrice) {minPrice = price;}// 计算当前价格卖出的利润else {maxProfit = Math.max(maxProfit, price - minPrice);}}return maxProfit;}
}

2.跳跃游戏No.55

class Solution {public boolean canJump(int[] nums) {int maxReach = 0;  // 初始化为 0，表示起始位置能够到达的最远距离// 遍历数组for (int i = 0; i < nums.length; i++) {// 如果当前位置不可达，返回 falseif (i > maxReach) {return false;}// 更新能够到达的最远位置maxReach = Math.max(maxReach, i + nums[i]);// 如果能够到达最后一个位置，返回 trueif (maxReach >= nums.length - 1) {return true;}}return false;  // 遍历结束，若不能到达最后一个位置，则返回 false}
}

public boolean canJump(int[] nums) {if(nums.length==1) return true;int cover = 0;for(int i = 0;i<=cover;i++){cover = Math.max(cover,i+nums[i]);if(cover>=nums.length-1){return true;}}return false;}

3.跳跃游戏IINo.45

class Solution {public int jump(int[] nums) {int n = nums.length;// 如果数组长度为 1，不需要跳跃if (n == 1) return 0;int jumps = 0;int farthest = 0;int currentEnd = 0;// 遍历到倒数第二个元素即可for (int i = 0; i < n ; i++) {// 更新能到达的最远位置farthest = Math.max(farthest, i + nums[i]);// 如果到达了当前区间的末尾，进行跳跃if (i == currentEnd) {jumps++;currentEnd = farthest;// 如果当前区间的末尾已经能够到达最后一个位置，提前结束if (currentEnd >= n - 1) {break;}}}return jumps;}
}

public int jump(int[] nums) {if(nums.length==1) return 0;int curr = 0;int next = 0;int jump = 0;for(int i = 0;i<nums.length;i++){next = Math.max(next,i+nums[i]);if(i==curr){jump++;curr = next;if(curr>=nums.length-1) break;}}return jump;}

4.划分字母区间No.763

• 思路
  • 统计每一个字符最后出现的位置
  • 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

class Solution {public List<Integer> partitionLabels(String s) {// Step 1: 记录每个字符最后出现的位置int[] lastIndex = new int[26];  // 因为字符是小写字母，共 26 个for (int i = 0; i < s.length(); i++) {lastIndex[s.charAt(i) - 'a'] = i;  // 更新字符的最后出现位置}List<Integer> result = new ArrayList<>();int currentEnd = 0;  // 当前片段的结束位置int start = 0;  // 当前片段的起始位置// Step 2: 遍历字符串，划分片段for (int i = 0; i < s.length(); i++) {currentEnd = Math.max(currentEnd, lastIndex[s.charAt(i) - 'a']);  // 更新当前片段的结束位置if (i == currentEnd) {  // 如果当前索引达到了当前片段的结束位置result.add(i - start + 1);  // 记录当前片段的长度start = i + 1;  // 更新下一个片段的起始位置}}return result;}
}