hxy的博客

Mia san Mia!

0%

贪心算法刷题

发表于 更新于 分类于 Valine：

按照算法和数据结构进行分类，一起来刷题，用于自己在面试前查漏补缺。我的意向岗位是前端，选择用javascript来刷题，优点是动态语言，语法简单，缺点是遇见复杂数据结构会出现较难的写法，如堆、并查集，每题对应leetcode的题号。本篇是贪心算法

专题部分

贪心算法

贪心思想保证每次操作都是局部最优的，并且最后得到的结果是全局最优的。

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

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

示例 2：

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

提示：

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

贪心取当前能跳最远的地方，如果无法跳再远就失败了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
    let n = nums.length;
    let farthest = 0;
    for (let i = 0; i < n - 1; i++) {
        // 不断计算能跳到的最远距离
        farthest = Math.max(farthest, i + nums[i]);
        // 可能碰到了 0，卡住跳不动了
        if (farthest <= i) return false;
    }
    return farthest >= n - 1;
};

56. 合并区间

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

示例 1：

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

示例 2：

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

提示：

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

先按开始顺序排好，在贪心选择可以合并的区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    if (!intervals || !intervals.length) return [];
    // 按区间的 start 升序排列
    intervals.sort((prev, next) => prev[0] - next[0]);
    let res = [];
    res.push(intervals[0]);
    for (let i = 1; i < intervals.length; i++) {
        let curr = intervals[i];
        // res 中最后一个元素的引用
        let last = res[res.length - 1];
        if (curr[0] <= last[1]) {
            // 找到最大的 end
            last[1] = Math.max(last[1], curr[1]);
        } else {
            // 处理下一个待合并区间
            res.push(curr);

        }
    }
    return res;
};

135. 分发糖果

每个孩子有一个评分，如果评分高于旁边的孩子，则被分配的糖果数量也必须更多，求最少总糖果数量，使得每个孩子都有糖果。

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1：

输入：[1,0,2]
输出：5
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

贪心策略，从左往右和从右往左各遍历一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} ratings
 * @return {number}
 * 贪心算法
 * 两次遍历
 */
var candy = function(ratings) {
    let len = ratings.length;
    if (len < 2) return len;
    let num = new Array(len).fill(1);
    for (let i = 1; i < len; i++) {
        // 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加1
        if (ratings[i] > ratings[i - 1]) {
            num[i] = num[i - 1] + 1;
        }
    }
    for (let i = len - 1; i > 0; i--) {
        // 再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加1
        if (ratings[i] < ratings[i - 1]) {
            num[i - 1] = Math.max(num[i - 1], num[i] + 1);
        }
    }
    // 求和
    return num.reduce((a, b) => a + b);
};

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

1 <= people.length <= 2000
0 <= hi <= 106
0 <= ki < people.length
题目数据确保队列可以被重建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[][]} people
 * @return {number[][]}
 * 贪心算法
 */
var reconstructQueue = function(people) {
    // 首先按照身高h降序排列，同时如果身高相同那么按照k增序，个高的人忽略前面个矮的人
    people.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]);
    // 结果数组
    let res = [];
    // 先安排高个子的位置
    for (let i = 0; i < people.length; i++) {
        // 先安排高个子k小,再安排高个子k大的
        res.splice(people[i][1], 0, people[i]);
    }
    return res;
};

435. 无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:

输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

题目描述：计算让一组区间不重叠所需要移除的区间个数。

计算最多能组成的不重叠区间个数，然后用区间总个数减去不重叠区间的个数。

在每次选择中，区间的结尾最为重要，选择的区间结尾越小，留给后面的区间的空间越大，那么后面能够选择的区间个数也就越大。

按区间的结尾进行排序，每次选择结尾最小，并且和前一个区间不重叠的区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number[][]} intervals
 * 贪心算法
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    // 序列长度
    let n = intervals.length;
    if (n <= 1) return 0;
    // 按 end 升序排序
    intervals.sort((a, b) => a[1] - b[1]);
    // 初始化删除区间数为0
    let count = 0;
    // 排序后，初始化区间尾为最小值
    let x_end = intervals[0][1];
    for(let i = 1; i < n; i++) {
        // 当前开头小于结尾，需要删除
        if (intervals[i][0] < x_end) {
            // 需要删除该项
            count++;
        } else {
            // 找到下一个选择的区间结尾
            x_end = intervals[i][1];
        }
    }
    return count;
};

455. 分发饼干

每个孩子都有一个满足度，每个饼干都有一个大小，只有饼干的大小大于等于一个孩子的满足度，该孩子才会获得满足。求解最多可以获得满足的孩子数量。

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

因为最小的孩子最容易得到满足，因此先满足最小孩子。给一个孩子的饼干应当尽量小又能满足该孩子，这样大饼干就能拿来给满足度比较大的孩子。因此采用贪心策略

证明：假设在某次选择中，贪心策略选择给当前满足度最小的孩子分配第 m 个饼干，第 m 个饼干为可以满足该孩子的最小饼干。假设存在一种最优策略，给该孩子分配第 n 个饼干，并且 m < n。我们可以发现，经过这一轮分配，贪心策略分配后剩下的饼干一定有一个比最优策略来得大。因此在后续的分配中，贪心策略一定能满足更多的孩子。也就是说不存在比贪心策略更优的策略，即贪心策略就是最优策略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 * 贪心算法
 */
var findContentChildren = function(g, s) {
    // 按孩子要求先排序
    g.sort((a, b) => a - b);
    // 按饼干尺寸先排序
    s.sort((a, b) => a - b);
    // 孩子从小到大编号
    let child = 0, cookie = 0;
    // 保证循环
    while (child < g.length && cookie < s.length) {
        // 贪心选择给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干
        if (g[child] <= s[cookie]) child++;
        // 饼干数+1
        cookie++;
    }
    return child;
};

678. 有效的括号字符串

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。

可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串

示例 1:

输入: “()”
输出: True

示例 2:

输入: “(*)”
输出: True

示例 3:

输入: “(*))”
输出: True

使用两个栈模拟（ 号和 *号，贪心将（出栈，使用栈来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @param {string} s
 * @return {boolean}
 * 栈
 */
var checkValidString = function(s) {
    // 两个栈分别存放左括号和*
    let left = [], star = [];
    // 遍历数组
    for(let i = 0; i < s.length; i++){
        // 左括号位置入栈
        if(s[i] === "(") left.push(i);
        // *号位置入栈
        if(s[i] === "*") star.push(i);
        // 右括号
        if(s[i] === ")") {
            // 优先出栈(
            if(left.length === 0){
                // (和*两个都没有，出错
                if(star.length === 0) return false;
                // *号出栈
                star.pop();
            } else {
                // (号出栈
                left.pop();
            }
        }
    }
    // *数量不足以抵消左括号
    if(left.length > star.length) return false;
    // 两个都有
    while(left.length && star.length){
        // 左括号在*右侧
        if(left.pop() > star.pop()) return false;
    }
    return true;
};

改为遍历两次优化栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * @param {string} s
 * @return {boolean}
 * 模拟栈
 */
var checkValidString = function(s) {
    // 分别存放剩余左括号和*数量
    let left = 0, star = 0;
    // 遍历数组
    for(let i = 0; i < s.length; i++){
        // 左括号数量+1
        if(s[i] === "(") left++;
        // *号数量+1
        if(s[i] === "*") star++;
        // 右括号
        if(s[i] === ")") {
            // 优先选择左括号
            if(left === 0){
                // 两个都没有，出错
                if(star <= 0) return false;
                // *号数量-1
                star--;
            } else {
                // (号数量-1
                left--;
            }
        }
    }
    // 存放剩余右括号数量
    let right = 0;
    star = 0;
    // 遍历数组
    for(let i = s.length - 1; i >= 0; i--){
        // 右括号数量-1
        if(s[i] === ")") right++;
        // *号数量+1
        if(s[i] === "*") star++;
        // 左括号
        if(s[i] === "(") {
            // 优先选择右括号
            if(right === 0){
                // 两个都没有，出错
                if(star <= 0) return false;
                // *号数量-1
                star--;
            } else {
                // )号数量-1
                right--;
            }
        }
    }
    return true;
};

1011. 在 D 天内送达包裹的能力

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。

示例 2：

1
2
3
4
5
6
7
输入：weights = [3,2,2,4,1,4], D = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4

示例 3：

1
2
3
4
5
6
7
输入：weights = [1,2,3,1,1], D = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1

提示：

  1. 1 <= D <= weights.length <= 50000
  2. 1 <= weights[i] <= 500

二分查找+贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param {number[]} weights
 * @param {number} D
 * @return {number}
 */
var shipWithinDays = function(weights, D) {
    // 二分查找+贪心
    let left = 0;
    let right = 0;
    for(let i = 0; i < weights.length; i++){
        right += weights[i];
        left = Math.max(left, weights[i]);
    }
    let mid;
    while(left < right){
        mid = left + Math.floor((right - left) / 2);
        let cnt = 1;
        let sum = 0;
        for (let i = 0; i < weights.length; i++){
            if (sum + weights[i] <= mid ){
                sum += weights[i];
            } else {
                cnt++;
                sum = weights[i];
            }
        }
        if (cnt <= D) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

1663. 具有给定数值的最小字符串

小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。

字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。

给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。

注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：

  • x 是 y 的一个前缀；
  • 如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。

示例 1：

1
2
3
输入：n = 3, k = 27
输出："aay"
解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。

示例 2：

1
2
输入：n = 5, k = 73
输出："aaszz"

提示：

  • 1 <= n <= 105
  • n <= k <= 26 * n
    贪心算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getSmallestString = function(n, k) {
    // 结果字符串
    let ans = "";
    // 剩下的字符个数
    for (let rest = n; rest >= 1; rest--) {
        // 贪心将当前位置取序号最小的字母，后面尽可能取最接近26的数
        let bound = k - 26 * (rest - 1);
        if (bound > 0) {
            // 选择当前基底的数
            ans += String.fromCharCode('a'.charCodeAt() + bound +  - 1);
            k -= bound;
        } else {
            // 先选择加入a
            ans += 'a';
            k -= 1;
        }
    }
    return ans;
};
-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道