算法leetcode

力扣2216-美化数组的最少删除数

字数统计: 1.4k字   |   阅读时长: 5分
, , ,

摘要: 定式化的动态规划、技巧性的贪心

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文的题目有动态规划和谈心两种解法。其中动态规划的思路比较定式化，更好想一些。贪心需要一些灵感和技巧，并且涉及到证明，反而不是太容易。

题目

给你一个下标从 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
2
1 <= nums.length <= 1e5
0 <= nums[i] <= 1e5

题解

算法1：动态规划

定义 $dp[i][k]$，其中 $k=0,1$：

  • $dp[i][0]$ 表示在 $nums[0..i-1]$ 上删除了偶数次时，$nums[i..n-1]$ 上最少删除次数。
  • $dp[i][1]$ 表示在 $nums[0..i-1]$ 上删除了奇数次时，$nums[i..n-1]$ 上最少删除次数。

其中 $i$ 为阶段、$k$ 为附加信息。

如果这样定义，目标为 $dp[0][0]$，边界值为：

下面考虑状态转移方程。如果 $nums[i] = nums[i+1] = c$ 并且 $i \% 2 = k$，此时 $nums[0..i-1]$ 上删除之后刚好还剩偶数个。此时 $nums[i]$ 只能选择删掉，$c$ 是否保留由下一阶段去决策。除了以上情况，在当前阶段 $nums[i]$ 删掉或不删掉两种决策都需要考虑。

一共 $O(n)$ 个阶段，每个阶段有 $O(1)$ 个状态。从当前阶段的某个状态下，到下一阶段共有 $O(1)$ 种决策，综合起来的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minDeletion(self, nums: List[int]) -> int:
        self.n = len(nums)
        self.nums = nums
        ans = self.solve(0, 0)
        return ans

    @lru_cache(maxsize=int(1e6))
    def solve(self, i: int, k: int) -> int:
        if i == self.n - 1:
            if (self.n - 1) % 2 == k:
                return 1
            else:
                return 0

        # i < self.n - 1
        if self.nums[i] == self.nums[i + 1] and i % 2 == k:
            return self.solve(i + 1, (k + 1) % 2) + 1
        else:
            return min(self.solve(i + 1, (k + 1) % 2) + 1, self.solve(i + 1, k))

算法2：贪心

数组上从左到右每两个视为一组。

对于某个相邻的元素 $s[i]$ 和 $s[i+1]$，如果 $i=2k$，且元素相同，记为 $s[i] = s[i+1] = c$，那么这里就不符合要求了。需要通过删除元素使其符合要求。此时考虑删除元素的位置 $j$：

如果 $j > i + 1$，那么删除之后并不会改变 $s[i]$ 和 $s[i+1]$ 不合法的现状。因此不论删不删 $j > i + 1$ 处的 $s[j]$，在 $s[0..i+1]$ 范围内肯定要删一个。因此删除位置一定满足 $j \leq i + 1$。

如果 $j < i$，删除之后相邻的相同元素仍然存在，这是位置向前移了一位，它们不在同一组了。但是如果 $s[i-1]$ 也为 $c$，则原本已经没问题的 $s[i-1]$ 又成为了新问题，删除操作还是可能浪费了。

如果 $j = i, i+1$，那么删除之后 $s[i]$ 和 $s[i+1]$ 的不合法问题肯定会解决，此时 $s[i+2..n-1]$ 向前移位，如果 $s[i+2]$ 也为 $c$，那么这里又会出现问题，需要继续解决，但这个问题是后续元素的问题了，与前面已经解决 $s[0..i-1]$ 无关，如果删除位置 $j < i$，$s[i+2] = c$ 的问题最终还是需要解决。因此删除位置 $j = i, i + 1$，情况不会更糟。

综上，对于不合法的情况 $s[i] = s[i+1] = c$ 且 $i=2k$，删除 $s[i]$ 一定可以解决当前问题，并且如果引入了新问题，情况相比删其它位置也不会更糟。

删除之后，剩下元素如果为奇数个，则还需要额外删除一次。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minDeletion(self, nums: List[int]) -> int:
        n = len(nums)
        cnt = 0
        i = 1
        while i < n:
            if (i - cnt) % 2 == 1 and nums[i] == nums[i - 1]:
                cnt += 1
            i += 1
        if (n - cnt) % 2 == 1:
            cnt += 1
        return cnt
Share