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

1、题干​

给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：

• nums.length 为偶数
• 对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立

注意，空数组同样认为是美丽数组。

你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。

返回使 nums 变为美丽数组所需删除的 最少 元素数目。

示例 1：

输入：nums = [1,1,2,3,5]
输出：1
解释：可以删除 nums[0] 或 nums[1] ，这样得到的 nums = [1,2,3,5] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。

示例 2：

输入：nums = [1,1,2,2,3,3]
输出：2
解释：可以删除 nums[0] 和 nums[5] ，这样得到的 nums = [1,2,2,3] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 2 个元素。

提示：

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

2、思路​

模拟一遍删除过程就能过。其他题解说是贪心，也有证明过程，看完还是不懂不理解。这题证明比AC难得多。

3、代码​

function minDeletion(nums: number[]): number {
    let cur = -Infinity, size = 0;
    
    for (const k of nums) {
        if (size % 2 === 0 || k !== cur) cur = k, size++;
    }

    return nums.length - size + (size % 2);
};

1、题干​

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你需要执行以下操作 恰好 k 次，最大化你的得分：

1. 从 nums 中选择一个元素 m 。
2. 将选中的元素 m 从数组中删除。
3. 将新元素 m + 1 添加到数组中。
4. 你的得分增加 m 。

请你返回执行以上操作恰好 k 次后的最大得分。

示例 1：

输入：nums = [1,2,3,4,5], k = 3
输出：18
解释：我们需要从 nums 中恰好选择 3 个元素并最大化得分。
第一次选择 5 。和为 5 ，nums = [1,2,3,4,6] 。
第二次选择 6 。和为 6 ，nums = [1,2,3,4,7] 。
第三次选择 7 。和为 5 + 6 + 7 = 18 ，nums = [1,2,3,4,8] 。
所以我们返回 18 。
18 是可以得到的最大答案。

示例 2：

输入：nums = [5,5,5], k = 2
输出：11
解释：我们需要从 nums 中恰好选择 2 个元素并最大化得分。
第一次选择 5 。和为 5 ，nums = [5,5,6] 。
第二次选择 6 。和为 6 ，nums = [5,5,7] 。
所以我们返回 11 。
11 是可以得到的最大答案。

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 100

2、思路​

根据题意可知 k 次得分是首项为 Math.max(...nums) 公差为 $1$ 的等差数列，套用等差数列求和公式即可

3、代码​

function maximizeSum(nums: number[], k: number): number {
    return k * (2 * Math.max(...nums) + k - 1) / 2;
};

1、题干​

给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。

在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。

• 例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3] 。

数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。

• 例如，[-1,2,3] 的 MEX 是 0 ，而 [1,0,3] 的 MEX 是 2 。

返回在执行上述操作 任意次 后，nums 的最大 MEX 。

示例 1：

输入：nums = [1,-10,7,13,6,8], value = 5
输出：4
解释：执行下述操作可以得到这一结果：
- nums[1] 加上 value 两次，nums = [1,0,7,13,6,8]
- nums[2] 减去 value 一次，nums = [1,0,2,13,6,8]
- nums[3] 减去 value 两次，nums = [1,0,2,3,6,8]
nums 的 MEX 是 4 。可以证明 4 是可以取到的最大 MEX 。

示例 2：

输入：nums = [1,-10,7,13,6,8], value = 7
输出：2
解释：执行下述操作可以得到这一结果：
- nums[2] 减去 value 一次，nums = [1,-10,0,13,6,8]
nums 的 MEX 是 2 。可以证明 2 是可以取到的最大 MEX 。

提示：

• 1 <= nums.length, value <= 105
• -109 <= nums[i] <= 109

2、思路​

• 对 nums 所有元素与 value 取模计数，得到数组 ms
• 遍历区间 [0,nums.length)，消费 ms，直到遍历结束 或 ms 中某个余数被消耗完（ms[i % value] < 1） ，此时的下标 i 即所求结果

3、代码​

function findSmallestInteger(nums: number[], value: number): number {
    const ms = new Array(value).fill(0);
    for (const n of nums) {
        const mod = n % value + (n % value < 0 ? value : 0);
        ms[mod]++;
    }

    let ans = 0;
    for (let i = 0; i < nums.length; i++, ans++) {
        const mod = i % value;
        if (ms[mod] < 1) break;
        ms[mod]--;
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。

子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

示例 1：

输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。

示例 2：

输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。

提示：

• n == nums.length
• m == queries.length
• 1 <= n, m <= 1000
• 1 <= nums[i], queries[i] <= 106

2、思路1-暴力​

• 对 nums 升序排序，求前缀和
• 暴力查找不大于 queries[i] 的前缀和数量

3、代码​

function answerQueries(nums: number[], queries: number[]): number[] {
    nums.sort((a, b) => a - b);
    for (let i = 1; i < nums.length; i++) nums[i] += nums[i - 1];

    let ans = queries.map(Number);
    for (let i = 0; i < queries.length; i++) {
        if (nums.at(-1) <= queries[i]) ans[i] = nums.length;
        else ans[i] = nums.findIndex((s) => s > queries[i]);
    }

    return ans;
};

4、复杂度​

• 时间复杂度： $O(n^2)$
• 空间复杂度： $O(\log{n})$

5、执行结果​

6、思路2-排序优化​

在思路1的基础上进行优化，如果 queries 是升序数组，那么查找子序列就不用每次都从头到尾遍历前缀和数组，可以从上一个找到的前缀和下标开始往后查找，查找过程复杂度从 $O(n^2)$ 降到 $O(n)$

7、代码​

function answerQueries(nums: number[], queries: number[]): number[] {
    nums.sort((a, b) => a - b);
    for (let i = 1; i < nums.length; i++) nums[i] += nums[i - 1];

    const qs = queries.map((n, i) => [n, i]).sort((a, b) => a[0] - b[0]);

    let ans = queries.map(Number);
    for (let i = 0, j = 0; i < qs.length; i++) {
        if (nums.at(-1) <= qs[i][0]) {
            ans[qs[i][1]] = nums.length;
            continue;
        }

        while (nums[j] <= qs[i][0]) j++;
        ans[qs[i][1]] = j;
    }

    return ans;
};

8、复杂度​

• 时间复杂度： $O(n \log{n})$
• 空间复杂度： $O(n)$

9、执行结果​

1、题干​

给你两个非负整数数组 rowSum 和 colSum ，其中 rowSum[i] 是二维矩阵中第 i 行元素的和， colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。

请找到大小为 rowSum.length x colSum.length 的任意 非负整数 矩阵，且该矩阵满足 rowSum 和 colSum 的要求。

请你返回任意一个满足题目要求的二维矩阵，题目保证存在 至少一个 可行矩阵。

示例 1：

输入：rowSum = [3,8], colSum = [4,7]
输出：[[3,0],
      [1,7]]
解释：
第 0 行：3 + 0 = 3 == rowSum[0]
第 1 行：1 + 7 = 8 == rowSum[1]
第 0 列：3 + 1 = 4 == colSum[0]
第 1 列：0 + 7 = 7 == colSum[1]
行和列的和都满足题目要求，且所有矩阵元素都是非负的。
另一个可行的矩阵为：[[1,2],
                  [3,5]]

示例 2：

输入：rowSum = [5,7,10], colSum = [8,6,8]
输出：[[0,5,0],
      [6,1,0],
      [2,0,8]]

示例 3：

输入：rowSum = [14,9], colSum = [6,9,8]
输出：[[0,9,5],
      [6,0,3]]

示例 4：

输入：rowSum = [1,0], colSum = [1]
输出：[[1],
      [0]]

示例 5：

输入：rowSum = [0], colSum = [0]
输出：[[0]]

提示：

• 1 <= rowSum.length, colSum.length <= 500
• 0 <= rowSum[i], colSum[i] <= 108
• sum(rowSum) == sum(colSum)

以为是个回溯，没想到是个贪心，磨蹭半天才想到，还不是最优的思路

2、思路1​

• 生成元素全为 0 的矩阵 grid，grid[0] 初始化为 colSum
• 遍历所有行的元素（最后一行除外），通过 rowSum[i] 的约束将超出的数转移到下一行

3、代码​

function restoreMatrix(rowSum: number[], colSum: number[]): number[][] {
    const grid = rowSum.map(() => colSum.map(() => 0));
    grid[0] = colSum;

    for (let i = 0; i < rowSum.length - 1; i++) {
        let sum = grid[i].reduce((a, c) => a + c, 0);
        for (let j = 0; j < colSum.length && sum > rowSum[i]; j++) {
            grid[i + 1][j] = Math.min(sum - rowSum[i], grid[i][j]);
            grid[i][j] -= grid[i + 1][j];
            sum -= grid[i + 1][j];
        }
    }

    return grid;
};

4、复杂度​

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

5、执行结果​

6、思路2​

更直接的贪心，通过 rowSum[i] 与 colSum[j] 直接约束 grid[i][j]

7、代码​

function restoreMatrix(rowSum: number[], colSum: number[]): number[][] {
    const grid = rowSum.map(() => colSum.map(() => 0));

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

    return grid;
};

8、复杂度​

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

9、执行结果​

1、题干​

你正在参加一场比赛，给你两个 正 整数 initialEnergy 和 initialExperience 分别表示你的初始精力和初始经验。

另给你两个下标从 0 开始的整数数组 energy 和 experience，长度均为 n 。

你将会 依次 对上 n 个对手。第 i 个对手的精力和经验分别用 energy[i] 和 experience[i] 表示。当你对上对手时，需要在经验和精力上都 严格 超过对手才能击败他们，然后在可能的情况下继续对上下一个对手。

击败第 i 个对手会使你的经验 增加 experience[i]，但会将你的精力 减少  energy[i] 。

在开始比赛前，你可以训练几个小时。每训练一个小时，你可以选择将增加经验增加 1 或者 将精力增加 1 。

返回击败全部 n 个对手需要训练的 最少 小时数目。

示例 1：

输入：initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
输出：8
解释：在 6 小时训练后，你可以将精力提高到 11 ，并且再训练 2 个小时将经验提高到 5 。
按以下顺序与对手比赛：
- 你的精力与经验都超过第 0 个对手，所以获胜。
  精力变为：11 - 1 = 10 ，经验变为：5 + 2 = 7 。
- 你的精力与经验都超过第 1 个对手，所以获胜。
  精力变为：10 - 4 = 6 ，经验变为：7 + 6 = 13 。
- 你的精力与经验都超过第 2 个对手，所以获胜。
  精力变为：6 - 3 = 3 ，经验变为：13 + 3 = 16 。
- 你的精力与经验都超过第 3 个对手，所以获胜。
  精力变为：3 - 2 = 1 ，经验变为：16 + 1 = 17 。
在比赛前进行了 8 小时训练，所以返回 8 。
可以证明不存在更小的答案。

示例 2：

输入：initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]
输出：0
解释：你不需要额外的精力和经验就可以赢得比赛，所以返回 0 。

提示：

• n == energy.length == experience.length
• 1 <= n <= 100
• 1 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100

2、思路​

需要增加的精力值是：energy 数组总和超出 initialEnergy 的部分再加 1，即 max(sum(energy) - initialEnergy + 1, 0)

需要增加的经验值是：experience 中所有元素超出 initialExperience 的部分再加 1，即 sum(max(experience[i] - initialExperience + 1, 0))

计算经验值的过程中，initialExperience 需要累加已经比较过的 experience[i]

3、代码​

function minNumberOfHours(initialEnergy: number, initialExperience: number, energy: number[], experience: number[]): number {
    const se = energy.reduce((a, c) => a + c, 0);
    let ans = se < initialEnergy ? 0 : se - initialEnergy + 1;

    for (const e of experience) {
        if (initialExperience <= e) {
            ans += e - initialExperience + 1;
            initialExperience = e + 1;
        }
        initialExperience += e;
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。

如果符合下列情况之一，则数组 A 就是 锯齿数组：

• 每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] < A[2] > A[3] < A[4] > ...
• 或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] < A[1] > A[2] < A[3] > A[4] < ...

返回将数组 nums 转换为锯齿数组所需的最小操作次数。

示例 1：

输入：nums = [1,2,3]
输出：2
解释：我们可以把 2 递减到 0，或把 3 递减到 1。

示例 2：

输入：nums = [9,6,1,6,2]
输出：4

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

2、思路​

这里操作的方式可以考虑3种：只减小偶数索引的数，只减小奇数索引的数，两种索引的数都减小。显然第三种操作无法达到最小操作次数。

总体思路是：尝试只减小偶数索引的数或奇数索引的数，减小后的数尽可能与相邻的数相差最小，那减小后的数字应为 min(nums[i-1],nums[i+1])；最后取两个结果中较小的那个数字。

3、代码​

function movesToMakeZigzag(nums: number[]): number {
    let ans1 = 0;
    for (let i = 0; i < nums.length; i += 2) {
        const min = Math.min(nums[i - 1] ?? nums[i + 1], nums[i + 1] ?? nums[i - 1]);
        if (nums[i] >= min) ans1 += nums[i] - min + 1;
    }

    let ans2 = 0;
    for (let i = 1; i < nums.length; i += 2) {
        const min = Math.min(nums[i - 1] ?? nums[i + 1], nums[i + 1] ?? nums[i - 1]);
        if (nums[i] >= min) ans2 += nums[i] - min + 1;
    }

    return Math.min(ans1, ans2);
};

4、复杂度​

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

5、执行结果​

1、题干​

有两个长度相同的字符串 s1 和 s2，且它们其中 只含有 字符 "x" 和 "y"，你需要通过「交换字符」的方式使这两个字符串相同。

每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。

交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换 s1[i] 和 s2[j]，但不能交换 s1[i] 和 s1[j]。

最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回 -1 。

示例 1：

输入：s1 = "xx", s2 = "yy"
输出：1
解释：
交换 s1[0] 和 s2[1]，得到 s1 = "yx"，s2 = "yx"。

示例 2：

输入：s1 = "xy", s2 = "yx"
输出：2
解释：
交换 s1[0] 和 s2[0]，得到 s1 = "yy"，s2 = "xx" 。
交换 s1[0] 和 s2[1]，得到 s1 = "xy"，s2 = "xy" 。
注意，你不能交换 s1[0] 和 s1[1] 使得 s1 变成 "yx"，因为我们只能交换属于两个不同字符串的字符。

示例 3：

输入：s1 = "xx", s2 = "xy"
输出：-1

提示：

• 1 <= s1.length, s2.length <= 1000
• s1.length == s2.length
• s1, s2 只包含 'x' 或 'y'。

2、思路​

出现不同字符需要交换时有两种情况：$\frac{xx}{yy}$、$\frac{xy}{yx}$

• 情况1 $\frac{xx}{yy}$：只用1次对角线交换
• 情况2 $\frac{xy}{yx}$：需要先上下交换再对角线交换，共计2次交换
• 因此尽量将不同字符组合成情况1就能使交换次数最少

具体实现时，分别统计字符串 s1 中需要交换的 x 与 y，记为 dx、dy

• 若 dx + dy 为奇数，则无法使得两个字符串相同，返回 -1
• 若 dx + dy 为偶数，且 dx 也是偶数，那么不同字符可以全部组合成情况1，最小交换次数为 (dx + dy) / 2
• 若 dx + dy 为偶数，dx 是奇数，那么就会出现1组情况2，最小交换次数为 (dx + dy) / 2 + 1

3、代码​

function minimumSwap(s1: string, s2: string): number {
    let dx = 0, dy = 0;
    for (let i = 0; i < s1.length; i++) {
        if (s1[i] !== s2[i]) s1[i] === 'x' ? dx++ : dy++;
    }

    return (dx + dy) % 2 ? -1 : (dx + dy) / 2 + (dx % 2);
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个非负整数数组 nums 。在一步操作中，你必须：

• 选出一个正整数 x ，x 需要小于或等于 nums 中 最小 的 非零 元素。
• nums 中的每个正整数都减去 x。

返回使 nums 中所有元素都等于 0 需要的 最少 操作数。

示例 1：

输入：nums = [1,5,0,3,5]
输出：3
解释：
第一步操作：选出 x = 1 ，之后 nums = [0,4,0,2,4] 。
第二步操作：选出 x = 2 ，之后 nums = [0,2,0,0,2] 。
第三步操作：选出 x = 2 ，之后 nums = [0,0,0,0,0] 。

示例 2：

输入：nums = [0]
输出：0
解释：nums 中的每个元素都已经是 0 ，所以不需要执行任何操作。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

2、思路1​

根据题目描述，每一步都消除了所有最小的正整数，因此最少步数就是数组 nums 去重后正整数的个数。

第一个思路是：排序后统计去重正整数个数

3、代码​

function minimumOperations(nums: number[]): number {
    nums.sort((a, b) => a - b);

    let step = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] && nums[i] !== nums[i - 1]) step++;
    }

    return step;
};

4、复杂度​

• 时间复杂度：$O(n \log n)$
• 空间复杂度：$O(\log n)$

5、执行结果​

6、思路2​

哈希去重统计正整数的个数

7、代码​

function minimumOperations(nums: number[]): number {
    const set = new Set(nums);
    return set.size - (set.has(0) ? 1 : 0);
};

或者这样

function minimumOperations(nums: number[]): number {
    return new Set(nums.filter(Boolean)).size;
};

8、复杂度​

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

9、执行结果​

1、题干​

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。

花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n] 。

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i -  ranges[i], i + ranges[i]] 。

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。

示例 1：

输入：n = 5, ranges = [3,4,1,1,0,0]
输出：1
解释：
点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。

示例 2：

输入：n = 3, ranges = [0,0,0,0]
输出：-1
解释：即使打开所有水龙头，你也无法灌溉整个花园。

提示：

• 1 <= n <= 104
• ranges.length == n + 1
• 0 <= ranges[i] <= 100

写了个奇怪的动态规划思路

2、思路​

用 [i-r,i) 区间的最少水龙头数更新 dp[i]，用 dp[i] 更新 (i,i+r] 区间的最少水龙头数。

dp 数组元素有正负两种状态，正数表示自身可以达到最少水龙头数，负数表示被其他水龙头覆盖达到最少水龙头数；负数在更新 (i,i+r] 区间时需要 +1，正数则不需要。

3、代码​

function minTaps(n: number, ranges: number[]): number {
    const dp = ranges.map(() => Infinity);

    for (let i = 0, r = 0; i <= n; i++) {
        r = ranges[i];
        if (i - r < 1) dp[i] = 1;

        for (let j = Math.max(0, i - r); j <= Math.min(n, i + r); j++) {
            const di = Math.abs(dp[i]), dj = Math.abs(dp[j]);
            if (j < i && dj + 1 <= di) dp[i] = dj + 1;
            else if (j > i) {
                if (dp[i] > 0 && di <= dj) dp[j] = -di;
                else if (dp[i] <= 0 && di + 1 <= dj) dp[j] = -di - 1;
            }
        }
    }

    return dp.at(-1) < Infinity ? Math.abs(dp.at(-1)) : -1;
};

4、复杂度​

• 时间复杂度：$O(mn)$
• 空间复杂度：$O(n)$

5、执行结果​