贪心算法 力扣hot100热门面试算法题 面试基础 核心思路 背题

贪心算法

买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

核心思路

如果假设今日买入，未来最高点是未知的，需要遍历后续数组，所以时间复杂度变成n^2；
那么如果假设今日卖出，遍历到此处时历史最低价是已知晓的信息，就降低了时间复杂度，只需要遍历一遍并记录实时最小值和实时最大利润即可；

示例代码

class Solution {
    public int maxProfit(int[] prices) {
        int min = 10010;
        int max = 0;
        for(int num : prices){
            if(num<min) min = num;
            if(max < num - min)max = num - min;
        }
        return max;
    }
}

跳跃游戏

https://leetcode.cn/problems/jump-game/

核心思路

倒序 可达性分析

示例代码

class Solution {
    public boolean canJump(int[] nums) {
        //i表示可到达的下标
        int i = nums.length - 1;

        //j表示需要确定的下标
        //若倒二可到达倒一，则计算倒三是否可以到达倒二，否则计算到三是否可以到达倒一；
        for (int j = nums.length - 2; j >= 0; j--) {
            if (nums[j] >= i - j) {
                i = j;
            }
        }
        //若i==0，代表可到达
        if (i == 0) return true;
        return false;
    }
}

跳跃游戏II

https://leetcode.cn/problems/jump-game-ii/

返回到达 nums[n - 1] 的最小跳跃次数

核心思路

贪心策略：在当前位置所能跳到的区间内，找下一次能跳到更远的位置。

示例代码

class Solution {
    public int jump(int[] nums) {

        int p = nums.length - 1;
        //每一步的开始
        int start = 0;
        int cnt = 0;
        while (start < p) {
            int end = -1;
            //在start位置，[s,e]闭区间即能跳到的的范围
            int s = start + 1;
            int e = start + nums[start];
            
            //e没跳到最后的话，就找一下：跳到区间的哪个位置可以下一次跳的更远
            if (e < p) {
                for (int i = s; i <= e && i <= p; i++) {
                    if (end <= i + nums[i]) {
                        end = i + nums[i];
                        start = i;
                    }
                }
            }else{
                cnt++;
                break;
            }

            cnt++;
        }
        return cnt;
    }
}

划分字母区间

https://leetcode.cn/problems/partition-labels/

核心思路

本质是合并区间:

​ 遍历，记录下每个字母最后出现的下标；
​ 再次遍历，合并区间，计算长度

示例代码

class Solution {
    public List<Integer> partitionLabels(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        int[] last = new int[26];
        for (int i = 0; i < n; i++) {
            last[s[i] - 'a'] = i; // 每个字母最后出现的下标
        }

        List<Integer> ans = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < n; i++) {
            end = Math.max(end, last[s[i] - 'a']); // 更新当前区间 右端点的最大值
            if (end == i) { // 当前区间合并完毕
                ans.add(end - start + 1); // 区间长度加入答案
                start = i + 1; // 下一个区间的左端点
            }
        }
        return ans;
    }
}