算法疑难杂症

思维复杂代码简单与思维简单代码复杂

字数统计: 2.2k字   |   阅读时长: 8分
, , ,

摘要: 将问题转化为 TopK 问题。

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

各位好，今天我们来看一个思维量比较大的题，一种直接的思路还是非常好想的，但是过程比较繁琐，有一些边界情况需要讨论，因此最终代码中有复杂的控制逻辑，容易出错，也不好优化。

还有一种稍微拐个弯的思路，比较难想，但是一旦想到了，解决问题的过程就会非常简洁。最终可以理解为将问题转化为了取前 k 大元素的问题。这种方法的最优性可以通过贪心算法中常见的微扰法进行论证。进一步地，如果用快速选择算法，还可以优化时间复杂度。

题目

「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N 张卡牌中选出 cnt 张卡牌，若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。 给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。

提示：

1
2
1 <= cnt <= cards.length <= 10^5
1 <= cards[i] <= 1000

示例 1：
输入：cards = [1,2,8,9], cnt = 3
输出：18
解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。

示例 2：
输入：cards = [3,3,1], cnt = 1
输出：0
解释：不存在获取有效得分的卡牌方案。

题解

算法1: 思维简单，代码复杂

如果没有恰好选 cnt 张牌的限制，那么我们就可以按照最直接的想法，将所有偶数牌都选上，然后奇数牌若有偶数张就都选上，如果是奇数张就舍弃最小的那张，即得答案。但这里有个恰好选 cnt 张牌的限制。

选择一张偶数牌，已累积的和的奇偶性不变，而选一张奇数牌，已累积的和的奇偶性会发生改变，这会影响到当前选法的可行性。因此奇数牌和偶数牌应该分别考虑。

首先将所有牌按照奇偶性分成两组，奇数组 odd_list 和偶数组 even_list。然后将两组分别排序。

如果当前的累加和为偶数，并且选了一张奇数牌，则后续必须再选一张奇数牌，使得结果变回偶数才行。这就隐含了两点：

  • 选了当前奇数牌后，已选牌的张数小于 cnt，也就是还有选牌额度，用于选一张奇数牌将累加和变回偶数；
  • 奇数牌的排队尚未耗尽，也就是后续还有奇数牌可选。

同时，用于将累加和变回偶数的那张奇数牌，也应该选奇数牌堆中最大的。于是我们就有了将奇数牌两两分组的想法，也就是将最大与第2大分一组、第3大和第4大分一组，以此类推。

然后将偶数也类似地两两分组，然后两张两张地选牌。对比奇数牌堆与偶数排队的最大两张牌的和，哪个大就选哪个。直至剩余的选牌额度耗尽或者还能再选一张牌。如果还能再选一张，就将偶数排队中剩余的最大的牌选入即可。

这里有个细节需要注意：如果 cnt 为奇数，那么偶数牌堆必须保持有至少一张牌，使得最后需要补一张牌的时候有偶数牌可补。

有两种情况是无解的，一种是 cnt 为奇数，但牌堆没有偶数牌，也就是最后需要补一张牌的时候没有偶数牌可补。

代码 (Python)

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
class Solution:
    def maxmiumScore(self, cards: List[int], cnt: int) -> int:
        n = len(cards)
        odd_list = []
        even_list = []
        for x in cards:
            if x % 2 == 0:
                even_list.append(x)
            else:
                odd_list.append(x)
        even_list.sort()
        odd_list.sort()
        n_even = len(even_list)
        n_odd = len(odd_list)

        if cnt % 2 == 1 and n_even == 0:
            # 无可行解情况1：cnt 为奇数但没有偶数元素
            return 0
        if cnt == n and n_odd % 2 == 1:
            # 无可行解情况2：cnt 为 n 但奇数元素有奇数个
            return 0

        i_even = n_even - 1
        i_odd = n_odd - 1
        ans = 0
        while cnt >= 2:
            odd = -1
            if i_odd >= 1:
                odd = odd_list[i_odd] + odd_list[i_odd - 1]
            even = -1
            if (cnt % 2 == 1 and i_even >= 2) or (cnt % 2 == 0 and i_even >= 1):
                # 若 cnt 为奇数，则偶数列表中至少要留一个
                even = even_list[i_even] + even_list[i_even - 1]
            if odd >= even:
                ans += odd
                i_odd -= 2
            else:
                ans += even
                i_even -= 2
            cnt -= 2
        if cnt == 1:
            ans += even_list[i_even]
        return ans

算法2：思维复杂，代码简单

前面的算法非常直接，就是考虑选奇数牌和偶数牌分别对结果有什么影响，然后推导出一些选牌原则：比如如果要让结果合法，奇数牌必须两个两个地选；比如如果 cnt 是奇数，则至少有一张偶数牌。然后选牌过程始终按照原则来，保持结果合法，所得的最大值就是结果。

而这里我们直接不考虑奇偶性的限制，直接选最大的 cnt 张牌出来，然后再对结果进行修正。这个思路比之前的思路绕了一下，一开始不容易想出来。但是最终的算法却更简单，控制条件更少，代码更精简。

排序后，选取前 cnt 个数，累加和为 $s$。若 $s$ 是偶数，那么直接就是答案，如果为奇数，则需要进行修正，下面我们看一下修正的过程。

由于 $s$ 是奇数，我们想将其变为偶数，因此从整体来看我们要做的操作是将某个奇数变成一个偶数，或者将某个偶数变成一个奇数。

为了使得操作之后的 cnt 个数的累加和最大，直觉上应该将手牌中最小的奇数牌替换为牌堆中最大的偶数牌；也可以将手牌中最小的偶数牌替换为牌堆中最大的奇数牌。这两种操作哪个更大就取哪个。

微扰法证明贪心策略最优性

下面还有一个最重要的问题，即为什么执行上面一步修正就会得到最优解，有没有可能需要交换多组牌才能得到最优解。

由于手牌是最大的 cnt 张牌，因此牌堆的牌都比手牌小，因此按上述逻辑进行一次替换修正了累加和的奇偶性后，如果继续换牌，不会使得累加和更大。

这种通过论证对某个策略的任意微小改变都不会使得结果更好，来说明该策略最优性的做法，是证明贪心正确性常用的微扰法。

快速选择算法

上述算法整体分为两步。第一步是取最大的 cnt 个数字，第二部是修正。

取最大的 cnt 个数字如果用排序的话，时间复杂度为 $O(N\log N)$，修正的过程明显是 $O(N)$。

如果用快速选择算法，可以在最坏情况下取得 $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
21
22
23
24
25
26
27
28
29
30
31
32
33
INF = int(2e9)

class Solution:
    def maxmiumScore(self, cards: List[int], cnt: int) -> int:
        def post_process(parity: int) -> int:
            # 在 cards[0:cnt] 中找奇偶性为 parity 的，记为 x
            # 再在 cards[cnt:n] 中找奇偶性相反的，记为 y
            # 若找到一组，则返回 y - x，否则返回 -INF
            # 由于 cards 有序，肯定有 y - x <= 0，因此返回 1 肯定代表无解
            l = cnt - 1
            while l >= 0 and cards[l] % 2 != parity:
                l -= 1
            if l >= 0:
                # 找到奇偶性为 parity 的 x = cards[l]
                r = cnt
                while r < n and cards[r] % 2 != (parity ^ 1):
                    r += 1
                if r < n:
                    # 找到奇偶性为 parity^1 的 y = cards[r]
                    return cards[r] - cards[l]
            return -INF

        n = len(cards)
        cards.sort(reverse=True)
        ans = sum(cards[0:cnt])
        if ans % 2 == 0:
            return ans

        delta0 = post_process(0)
        delta1 = post_process(1)
        if delta0 == -INF and delta1 == -INF:
            return 0
        return max(delta0, delta1) + ans
Share