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

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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