26 篇博文 含有标签「贪心」

1、题干​

你正在玩一个整数游戏。从整数 1 开始，期望得到整数 target 。

在一次行动中，你可以做下述两种操作之一：

• 递增，将当前整数的值加 1（即， x = x + 1）。
• 加倍，使当前整数的值翻倍（即，x = 2 * x）。

在整个游戏过程中，你可以使用 递增 操作 任意 次数。但是只能使用 加倍 操作 至多 maxDoubles 次。

给你两个整数 target 和 maxDoubles ，返回从 1 开始得到 target 需要的最少行动次数。

示例 1：

输入：target = 5, maxDoubles = 0
输出：4
解释：一直递增 1 直到得到 target 。

示例 2：

输入：target = 19, maxDoubles = 2
输出：7
解释：最初，x = 1 。
递增 3 次，x = 4 。
加倍 1 次，x = 8 。
递增 1 次，x = 9 。
加倍 1 次，x = 18 。
递增 1 次，x = 19 。

示例 3：

输入：target = 10, maxDoubles = 4
输出：4
解释：
最初，x = 1 。 
递增 1 次，x = 2 。 
加倍 1 次，x = 4 。 
递增 1 次，x = 5 。 
加倍 1 次，x = 10 。 

提示：

• 1 <= target <= 109
• 0 <= maxDoubles <= 100

2、解题思路​

• 使用贪心算法倒序处理，加倍变成减半，递增变成递减
• 先消耗掉所有减半次数 maxDoubles，消耗过程中如果是偶数则减半，如果是奇数则递减，每次消耗次数 count 都加1
• 剩余的操作只能是递减，需要的操作次数为剩余整数减1即 target - 1
• 最后返回 count + target - 1

3、复杂度​

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$

4、代码​

var minMoves = function (target, maxDoubles) {
  let count = 0;
  while (target > 1 && maxDoubles && ++count) {
    if (target % 2 === 0) maxDoubles--, (target /= 2);
    else target -= 1;
  }
  return count + target - 1;
};

5、执行结果​

• 执行用时: 64 ms
• 内存消耗: 37.8 MB

1、题干​

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意

示例 2：

输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组

示例 3：

输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示：

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

2、解法1-求子问题​

• 问题是求递增的三元子序列，实际可以先求解子问题，即先确定递增的二元子序列再找第三个元素
• 对于递增的二元子序列一定有这样一个规律：如果数列中存在递增二元子序列，那必定存在连续的递增二元子序列 （用反证法很容易推导）
• 所以找第一对递增二元子序列只需要找到两个相邻且递增的元素即可，这里将他们记为 l1 和 l2
• 如果后续能找到大于当前 l2 的元素就可以结束查找返回 true
• 如果后续无法找到大于当前 l2 的元素那就无法找到正解，因此需要不断用小于 l2 大于 l1 的数不断更新 l2
• 另外 l1 的值限制了 l2 的下限也可能导致无法找到正解，因此需要找到更小的递增二元子序列 m1 和 m2，其中 m1 < m2 <= l1（m2在实际编码中不声明），如果 m1 和 m2 都存在则更新 l1 和 l2 的值

3、代码​

var increasingTriplet = function (nums) {
    let l1, l2, m1;
    for (let i = 1; i < nums.length; i++) {
        if (isNaN(l2) && nums[i - 1] < nums[i]) l1 = nums[i - 1], l2 = nums[i];
        if (!isNaN(l2) && nums[i] > l2) return true;
        if (!isNaN(l2) && l1 < nums[i]) l2 = nums[i];
        if (!isNaN(m1) && nums[i] <= l1) l1 = m1, l2 = nums[i], m1 = undefined;
        if (nums[i] < l1) m1 = nums[i];
    }
    return false;
};

这里实际也用到了贪心思想，代码进一步简化后会跟官解贪心类似，与官解的不同点在于利用了递增二元子序列的连续性

4、执行结果​

执行用时: 84 ms 内存消耗: 51 MB

5、解法2-贪心​

3个月前写的代码，跟官解的贪心解法类似，先确定前两个元素并初始化为 nums[0] 和 Infinity，然后遍历后续元素并不断用更小的数更新前两个元素，最后如果存在第三个更大的数则表示存在递增三元子序列。

这种方式比较巧妙，用两个变量存储了两组递增二元子序列，中间两组子序列切换的过程实际不影响最终求解

6、代码​

var increasingTriplet = function (nums) {
    let [min, max] = [nums[0], Infinity];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > max) return true;
        
        if (nums[i] < min) min = nums[i];
        if (nums[i] > min && nums[i] < max) max = nums[i];
    }
    return false;
};

7、执行结果​

执行用时: 100 ms 内存消耗: 51.2 MB

这个题目还可以用回溯求解，但是时间复杂度比较高大概率会超时；另外题解区有二分的实现方案，这种方案具有通用性可以解决一类问题，非常值得学习。

1、题干​

Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。

给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌上的数值。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。

示例 1：

输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
输出：true
解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。

示例 2：

输入：hand = [1,2,3,4,5], groupSize = 4
输出：false
解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。

提示：

• 1 <= hand.length <= 104
• 0 <= hand[i] <= 109
• 1 <= groupSize <= hand.length

注意：此题目与 1296 重复：https://leetcode-cn.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

2、解法1​

先对原数组升序排序，然后进行双指针嵌套遍历，外层遍历找顺子起点，内层遍历找顺子后续元素，被找到的元素置为-1即寻找其他顺子元素时直接略过，若无法找到完整顺子则返回false

3、代码​

var isNStraightHand = function (hand, groupSize) {
    hand.sort((a, b) => a - b);
    for (let i = 0; i < hand.length; i++) {
        if (hand[i] < 0) continue;
        let count = 0;
        for (let j = i + 1; j < hand.length && count !== groupSize - 1; j++) {
            if (hand[j] - hand[i] === count + 1) count++, hand[j] = -1;
        }
        if (count !== groupSize - 1) return false;
    }
    return true;
};

代码逻辑简要说明

• 外层遍历：从下标i=0开始遍历数组内的元素，如果当前元素不为负数则作为顺子起点
• 内层遍历：从下标j=i+1(即顺子起点的下一个元素)开始遍历数组内的元素，寻找顺子后续元素
  • 对已找到的元素计数，计数变量记为count
  • 若当前元素与顺子起点的差值等于count+1，则说明该元素是顺子的后续元素
• 内层遍历结束，若找到的元素数量不等于groupSize - 1，说明顺子不存在应返回false

4、执行结果​

5、解法2​

先对原数组升序排序，然后对数组内数字进行哈希表计数（数字作key数量作value），然后遍历数组所有数字，以数量大于1的数字作为顺子起点，寻找顺子后续元素，若无法找到完整顺子则返回false

6、代码​

var isNStraightHand = function (hand, groupSize) {
    hand.sort((a, b) => a - b);
    const map = hand.reduce((acc, n) => acc.set(n, (acc.get(n) || 0) + 1), new Map());
    for (const n of hand) {
        if (!map.get(n)) continue;
        for (let i = 0; i < groupSize; i++) {
            if (!map.get(n + i)) return false;
            else map.set(n + i, map.get(n + i) - 1);
        }
    }
    return true;
};

7、执行结果​

执行用时: 100 ms 内存消耗: 47.1 MB

1、题干​

有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。

你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。

给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。

示例 1：

输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
输出：7
解释：你可以吃掉 7 个苹果：
- 第一天，你吃掉第一天长出来的苹果。
- 第二天，你吃掉一个第二天长出来的苹果。
- 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
- 第四天到第七天，你吃的都是第四天长出来的苹果。

示例 2：

输入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
输出：5
解释：你可以吃掉 5 个苹果：
- 第一天到第三天，你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天，你吃的都是第六天长出来的苹果。

提示：

• apples.length == n
• days.length == n
• 1 <= n <= 2 * 104
• 0 <= apples[i], days[i] <= 2 * 104
• 只有在 apples[i] = 0 时，days[i] = 0 才成立

又是优先队列，JS没有优先队列，又是被折磨的一天。。。 这道题跟课程表 III类似，可以看看我之前的题解，也是计数排序

2、执行结果​

3、解题思路​

• 总体思路：使用贪心策略，在尚未腐烂的苹果中优先选择保质期最小的苹果。
• 关键思路：基于计数排序求保质期最小的苹果，用数组存储苹果数量和保质期，数组的下标表示保质期、值表示该日期对应的苹果数量；找保质期最小的苹果只需要以上一个最小保质期为起点，遍历数组找到下标最小且值不为0的元素。
• 时间复杂度：由于遍历的起点是上一个最小的保质期，因此总体实现出来的时间复杂度是 $O(n)$，其中 $n$ 是最大保质期。

下面说明代码实现细节：

• 计数排序容器记为freshArr，其下标表示保质期、值表示该保质期之前的苹果数量
• 最小保质期记为minDay，用于记录有苹果剩余的最小保质期
• 可以吃掉苹果的最大数量记为res，即最终结果
• 接下来以最大保质期为限制逐天遍历，天数记为i
• 在第i天时，如果i没有超过n且过期天数大于0（i < days.length && days[i] > 0），进行以下操作
  • 在计数排序容器freshArr中按保质期i + days[i] - 1累加苹果数量
  • 更新最小保质期minDay = Math.min(minDay, i + days[i] - 1)
• 接下来只要找到有苹果剩余的最小保质期即可
  • 先确保最小保质期在今天之后，即minDay = Math.max(minDay, i)
  • 然后在计数排序容器freshArr中遍历，找到有苹果剩余的最小保质期
• 接下来更新最终结果和计数排序容器freshArr中的苹果数量
  • 注意更新之前确定该保质期有苹果剩余，即if (freshArr[minDay]) res++, freshArr[minDay]--
• 最后就得到可以吃掉苹果的最大数量res

4、代码​

var eatenApples = function (apples, days) {
    let res = 0, minDay = days[0] - 1;
    const freshArr = new Array(days.length).fill(0);
    for (let i = 0; i < freshArr.length; i++) {
        if (i < days.length && days[i] > 0) {
            freshArr[i + days[i] - 1] = (freshArr[i + days[i] - 1] || 0) + apples[i];
            minDay = Math.min(minDay, i + days[i] - 1);
        }
        minDay = Math.max(minDay, i);
        while (minDay < freshArr.length && !freshArr[minDay]) minDay++;
        if (freshArr[minDay]) res++, freshArr[minDay]--;
    }
    return res;
};

1、题干​

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

示例 1：

输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。

示例 2：

输入：courses = [[1,2]]
输出：1

示例 3：

输入：courses = [[3,2],[4,3]]
输出：0

提示:

• 1 <= courses.length <= 104
• 1 <= durationi, lastDayi <= 104

2、提交结果​

逻辑和代码比优先队列更简洁，执行效率更高。

3、解题思路​

破题思路还是看官解。这个题解主要说明如何在保证效率的前提下用更少代码替代优先队列。

每次答优先队列的题都巨难受，因为JS没有优先队列这种数据结构。由于数据范围特征明显1 <= duration[i] <= 1e4，可以用计数排序解这道题，代码比优先队列更简洁。凑巧的是测试用例也比较给力，执行效率比优先队列还好看些。接下来说下如何用计数排序替代优先队列。

设计思路​

优先队列解决的关键问题是快速插入、删除和查找最值。因此我们设计一个名为FPQ的数据结构解决这几个问题，FPQ主要包括的函数和变量是：list、max、constructor()、add()、del()

• list：元素容器，下标代表待排序的数据，元素值代表下标数字的数量
• max：所有元素中的最大值；可直接读取，时间复杂度为$O(1)$
• constructor()：构造函数，入参为整数n；时间复杂度为$O(n)$；函数逻辑如下：
  • 创建一个大小为n+1的数组list，初始化max为0
• add()：往list中添加元素，入参为整数n；时间复杂度为$O(1)$；函数逻辑如下：
  • list[n]自加1
  • 如果 n > max，则将max赋值为n
• del()：删除list中的元素，入参为整数 n；最坏时间复杂度为$O(n)$；函数逻辑如下：
  • list[n]自减1
  • 如果 n === max 且 list[n]===0，则需要重新计算最大值
  • 计算最大值：从下标 n 开始倒序遍历 list，如果list[n]>0，则将max赋值为list[n]并退出遍历

FPQ的插入方法比优先队列更高效，但删除方法不稳定，其效率可能比优先队列更好也可能更差。另外由于使用计数排序，因此使用场景也很有限。

4、代码​

var scheduleCourse = function (courses) {
  courses.sort((a, b) => a[1] - b[1]);

  const max = courses.reduce((acc, cur) => (cur[0] > acc ? cur[0] : acc), courses[0][0]);
  const pq = new FPQ(max);

  let res = 0;
  let time = 0;
  for (let i = 0; i < courses.length; i++) {
    if (time + courses[i][0] <= courses[i][1]) {
      res++;
      time += courses[i][0];
      pq.add(courses[i][0]);
    } else if (courses[i][0] < pq.max && time + courses[i][0] - pq.max < courses[i][1]) {
      time += courses[i][0] - pq.max;
      pq.add(courses[i][0]);
      pq.del(pq.max);
    }
  }

  return res;
};

class FPQ {
  constructor(n) {
    this.list = new Array(n + 1).fill(0);
    this.max = 0;
  }

  add(n) {
    this.list[n] += 1;
    if (n > this.max) this.max = n;
  }

  del(n) {
    this.list[n] -= 1;
    if (n !== this.max || this.list[n]) return;
    while (n > -1) {
      if (this.list[n] || !n) return (this.max = n);
      n--;
    }
  }
}

1、题干​

给你一座由 n x n 个街区组成的城市，每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ，其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。

城市的 天际线 是从远处观察城市时，所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 天际线 可能不同。

我们被允许为 任意数量的建筑物 的高度增加 任意增量（不同建筑物的增量可能不同） 。 高度为 0 的建筑物的高度也可以增加。然而，增加的建筑物高度 不能影响 从任何主要方向观察城市得到的 天际线 。

在 不改变 从任何主要方向观测到的城市 天际线 的前提下，返回建筑物可以增加的 最大高度增量总和 。

示例 1：

输入：grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出：35
解释：建筑物的高度如上图中心所示。
用红色绘制从不同方向观看得到的天际线。
在不影响天际线的情况下，增加建筑物的高度：
gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

示例 2：

输入：grid = [[0,0,0],[0,0,0],[0,0,0]]
输出：0
解释：增加任何建筑物的高度都会导致天际线的变化。

提示：

• n == grid.length
• n == grid[r].length
• 2 <= n <= 50
• 0 <= grid[r][c] <= 100

解题思路​

题目比较简单，两次遍历先取行列最大值再累加最大差值即可。详细步骤如下：

• 先计算各行最大值maxInRows和各列最大值maxInCols
• 再遍历矩阵grid中每个元素，元素增大的上限是该行最大值maxInRows[i]和该列最大值maxInCols[j]中较小的那个
• 求局部最优解：计算出每个建筑物可以增加的最大高度(Math.min(maxInRows[i], maxInCols[j]) - grid[i][j])
• 累加可得全局最优解：建筑物高度可以增加的最大总和

时间复杂度：$O(n^2)$

代码​

var maxIncreaseKeepingSkyline = function (grid) {
    const maxInRows = new Array(grid.length).fill(0);
    const maxInCols = new Array(grid[0].length).fill(0);

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            maxInRows[i] = Math.max(maxInRows[i], grid[i][j]);
            maxInCols[j] = Math.max(maxInCols[j], grid[i][j]);
        }
    }

    let res = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            res += (Math.min(maxInRows[i], maxInCols[j]) - grid[i][j]);
        }
    }

    return res;
};