贪心算法高频问题

区间问题

对于区间问题有两种情况:

  • A区间在前
  • B区间在前

在每一种情况又分为三种

  • 重叠一部分
  • 包含
  • 不重叠

如图

image-20240416161313238

L252 会议室

LeetCode252.给定一个会议时间安排的数组 intervals ,每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ,请你判断一个人是否能够参加这里面的全部会议。

示例 1::
输入: intervals = [[0,30],[15,20],[5,10]]
解释: 存在重叠区间,一个人在同一时刻只能参加一个会议。

这道题不难,重点是发现规律,当给区间第一个拍完序后,只需要前一个会议的结束时间是否在后一个会议开始时间以前就行

public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals,(o1, o2) -> o1[0]-o2[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0]<intervals[i-1][1]){
                return false;
            }
        }
        return true;
    }

L56 合并区间

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间

示例 1:

输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

首先分析这道题,能合并的区间有什么特征?

首先,区间a的结尾,一定大于区间b的开头,为了更好找到,这道题首先排序

然后可以设置idx,每次当不重叠直接添加,如果重叠就把当前res中的区间进行合并,但是这里需要注意:

合并区间还有一种情况:【1,4】【2,3】;在这种情况下,我们需要判断结果集和当前interval的【1】更大的一个,否则会出现错误

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        int[][] res = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval : intervals) {
            if (idx == -1 || interval[0] > res[idx][1]) {
                res[++idx] = interval;
            } else {
                res[idx][1] = Math.max(interval[1], res[idx][1]);
            }
        }

        return Arrays.copyOf(res, idx + 1);
    }
}

L57 插入区间

给你一个 无重叠的 *,*按照区间起始端点排序的区间列表 intervals,其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束,并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

intervals 中插入区间 newInterval,使得 intervals 依然按照 starti 升序排列,且区间之间不重叠(如果有必要的话,可以合并区间)。

返回插入之后的 intervals

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例 1:

输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
输出:[[1,5],[6,9]]

示例 2:

输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]
解释:这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

提示:

  • 0 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 105
  • intervals 根据 starti升序 排列
  • newInterval.length == 2
  • 0 <= start <= end <= 105

这道题整体思路分三部分,以示例2为例:

  1. 首先将小于newInterval的区间(newInterval【0】>intervals【i】【1】),全部添加到结果集
  2. 合并需要合并的区间,可以将newInterval直接合并
  3. 将新区间右边并相离的区间加入结果集

这里有点容易错:

合并区间的时候,需要 newInterval[1] >= intervals[i][0],需要加入=的条件,否则区间会重复

代码实现:

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] res = new int[intervals.length + 1][2];
        int idx = 0;
        int i = 0;
        // 遍历区间列表:
        // 首先将新区间左边且相离的区间加入结果集
        while (i < intervals.length && newInterval[0] > intervals[i][1]) {
            res[idx++] = intervals[i++];
        }
   // 判断当前区间是否与新区间重叠,重叠的话就进行合并,直到遍历到当前区间在新区间的右边且相离,
   // 将最终合并后的新区间加入结果集
        while (i < intervals.length && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        res[idx++] = newInterval;
        //最后将新区间右边且相离的区间加入结果集
        while (i < intervals.length) {
            res[idx++] = intervals[i++];
        }
        return Arrays.copyOf(res, idx);
    }
}

字符串分割

L763 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。

注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s

返回一个表示每个字符串片段的长度的列表。

示例 1:

输入:s = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的,因为划分的片段数较少。 

示例 2:

输入:s = "eccbbbbdec"
输出:[10]

提示:

  • 1 <= s.length <= 500
  • s 仅由小写英文字母组成

这道题的关键在于如何分割字符串,我们分割字符串的关键是:分割的串的在s中最后一次出现的位置,便是分割的地方,知道这个,我们很容易想到一个方法:使用一个26长度的字典,遍历一遍字符串,每一个字符串最后出现的索引作为字典的值

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] arr = new int[26];
        List<Integer> res = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i) - 'a'] = i;
        }
        int idx = -1;
        int start = -1;
        for (int i = 0; i < s.length(); i++) {
            idx = Math.max(arr[s.charAt(i) - 'a'], idx);
            if (i == idx) {
                res.add(i - start);
                start = i;
            }
        }
        return res;
    }
}

L134 加油站

在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。

给定两个整数数组 gascost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则 保证 它是 唯一 的。

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
因此,3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。
因此,无论怎样,你都不可能绕环路行驶一周。

提示:

  • gas.length == n
  • cost.length == n
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104

这道题如果使用贪心需要观察规律:

思路:

  1. 总油量 >= 总油耗 时必然有解
  2. 已知必然有解的前提, 只需要遍历一遍油量差值,找到第一个 后缀和非负 的下标即可

证明:

  • 抽象一个由 gas[i] - cost[i] 差值组成的数组, 包含 负数 和 非负数;比如: arr = [-, +, +, + -, -, +, ...]

  • 连续的 负数 - 代表都无法继续前往, 可以合并为一个值 (非负数也同理) => [-, +, -, +, ...]

  • 前正后负的情况 ([+, -]) 也可以合并, 比如: arr[1] 和 arr[2] => 可能有两种情况:[-, -, +, ...] 或者 [-, +, +, ...]

  • 重复上述的合并过程

  • 最终都会合并成 [-, +] 或者 [+, -]

  • 由于 总油量 > 总油耗|+| > |-| 所以最终必定有解

也就说,我们只需要找到第一个为负数油量右边的证书油量就可以了

代码实现:

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
           int total = 0;
        int curSum = 0;
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            total += gas[i] - cost[i];
            curSum += gas[i] - cost[i];
            if (curSum < 0) {
                start = i + 1;
                curSum = 0;
            }
        }
        if (total < 0) {
            return -1;
        }
        return start;
    }
}

跳跃游戏问题

L55 跳跃游戏

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false

示例 1:

输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:

输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105

自己独立解答,纪念一下!

这里是思路:

看到这道题,首先要分析:

  1. 什么时候走得到,什么时候走不到?

如果没有0,一定可以走到,那么0就是关键了,但是题目说,可以根据数组的数字选择跳动的数量,因此我们可以定义两个指针,right和left,right有3种情况

  • 一种是遇见0
  • 一种是遇见需要改变left位置
  • 一种不需要改变left位置
  1. 问题的核心:

那么我们自己画图来想,例如示例2,第一个元素可以走3步到0,它和后面的2什么关系呢?

一开始想的肯定是:那如果两个指针,左指针不动,右指针如果遇见比自己小的就下一个,和自己想同或者大于就把左指针移动到这里,可是这种情况会有缺陷:我们可以把数字改改:

{5,1,1,4,…}

没错,如果遇见这种情况,肯定是错误的,因此我们还需要研究下标,回到示例2,3,2,1能走的位置是相同的,也就是说,我们只需要找到0的位置判断left能走的距离是否超过就行;

因此,right指针当前能走的最大的一个根据1,2,3可以判断出:

(right-left)+nums【right】

所以只需要num【left】和这个判断即可

需要的位置(假设right在0处停下):right-left

能走的最大位置: flag = nums[left]>(right-left);

  1. 在这里已经可以实现代码了,但是我们还是忽略了一个情况:【2,0,0】,假如刚好是到了最后一个怎么办?

也就是说,最后一个是0的情况我们没有考虑

所以加一个条件,判断right指针是否已经到了最后一个,到最后一个的时候,可以等于

完整代码如下:

class Solution {
    public boolean canJump(int[] nums) {
        int left =0,right =0;
        boolean flag = true;
        while (flag&&right<nums.length){
            if (nums[right]==0){
                flag = nums[left]>(right-left);
            }else if (nums[left]<=nums[right]+right-left){
                left = right;
            }
            right++;
        }
        //因为已经执行了right++,所以这里要-1
       return nums.length==right? nums[left]>=(right-left-1):flag;
    }
}

另一种实现:

这种实现思路是始终记录每一个点能走的最远的地方,当有一个最远的大于等于数组最后一个的下标就返回true

如图:

image-20240419121215409

代码实现:

 public boolean canJump(int[] nums) {
        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;
    }

L45 跳跃游戏 II

给定一个长度为 n0 索引整数数组 nums。初始位置为 nums[0]

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

这道题已经给定了条件,一定可以到达最后一个下标,因此我们只需要考虑如何可以最少跳越就行

换言之,我们只需要找到最长的步数即可

大致过程是这样的,首先我们定义两个指针,和一个变量maxPosition(当前所有走过的位置里面能走最远的索引),right指针指向这里,然后一步步走left,没走一步算出当前最大的maxPosition并存储,当left走到right的时候,说明步数耗尽,此时有两种情况,已经到最后,或者还没到,如果还没到就继续移动right到maxPosition就行,因为这里的maxPosition存的是计算好能走的最远的下标,无需担心多走

这里无需关心长度为1的情况,因为长度为1会刚好覆盖结果

class Solution {
   public int jump(int[] nums) {
        int res =0;
        int right = 0;
        int maxPosition = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxPosition = Math.max(maxPosition,nums[i]+i);
            if (i==right){
                right = maxPosition;
                res++;
            }
            if (right>=nums.length-1){
                return res;
            }
        }
        return res;
    }
}