python - LeetCode "Maximum Points You Can Obtain from Cards"python 代码无法正常工作，我需要显示原因

Question

我无法理解我的代码在 LeetCode 问题“您可以从卡片中获得的最大分数”中遇到的问题

首先，我将在这里发布问题:

---

有几张卡片排成一排，每张卡片都有一个关联的点数。这些点数在整数数组 cardPoints 中给出。

在一个步骤中，您可以从该行的开头或末尾取出一张卡。你必须恰好拿走 k 张牌。

你的分数是你拿走的牌的分数总和。

给定整数数组cardPoints和整数k，返回可以获得的最大分数。

示例 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

示例 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

示例 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

示例 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1. 

示例 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

约束:

1 <= cardPoints.length <= 10^5

1 <= cardPoints[i] <= 10^4

1 <= k <= cardPoints.length

---

这是leetcode上问题的链接:

https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards

如果您熟悉这个问题，您可能会明白解决这个问题的最佳方法是使用滑动窗口。

我明白这一点，并且能够让一个版本正常工作。但我的第一次尝试是通过暴力破解，检查列表中的第一个和最后一个项目，取最大值，然后将其从列表中弹出。

这是我使用的代码:

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        myList = []
        if len(cardPoints) == k:
            return sum(cardPoints)
        else:
            while len(myList) < k:
                if cardPoints[0] > cardPoints[-1]:
                    myList.append(cardPoints[0])
                    cardPoints.pop(0)
                elif cardPoints[0] < cardPoints[-1]:
                    myList.append(cardPoints[-1])
                    cardPoints.pop(-1)
                elif cardPoints[0] == cardPoints[-1]:
                    if cardPoints[1] > cardPoints[-2]:
                        myList.append(cardPoints[0])
                        cardPoints.pop(0)
                    elif cardPoints[1] < cardPoints[-2]:
                        myList.append(cardPoints[-1])
                        cardPoints.pop(-1)
                    else: 
                        myList.append(cardPoints[-1])
                        cardPoints.pop(-1)
            return sum(myList)

正如您所看到的，这是一种非常困惑的方法，但它不起作用。它适用于一些测试用例，但它停止的测试用例在这里:

Input:

[11,49,100,20,86,29,72]
4

Output:

207

Expected:

232

我已经一步步解决了这个问题，但我不明白为什么它会期待 232。

据我了解，我们应该根据哪个值较高，从列表中取出第一项或最后一项。

在这种情况下，我们首先比较 11和72 .

服用72进入新列表，然后我们比较 11和29 .

服用29进入新列表，然后我们比较 11和86 .

服用86进入新列表，然后我们比较 11和20 .

服用20进入新列表，我们得到最终列表 72, 29, 86, 20 .

总计，72 + 29 + 86 + 20 = 207 ，这是我的代码得到的答案。

为什么代码期望 232 ？

有人可以解释一下我在这里缺少什么吗？

Answer 1

正如评论中已经指出的，您不应该为此使用贪婪方法，因为否则您可能会选择错误的序列。例如，如果您的数组是 [1,100,3,2] 和 k=2，那么您的算法会产生 5，尽管它必须为101。

正确的方法是尝试 cardPoints[-k] 和 cardPoints[k - 1] 之间长度为 k 的每个数组子段(两者都包括在内)，然后选择总和最大的一项。您只需要检查 k + 1 个段，时间复杂度仅为 O(k)(见下文)。

def maxScore(self, cardPoints: List[int], k: int) -> int:
    currentScore = sum(cardPoints[:k])
    maxScore = currentScore
    size = len(cardPoints)
    for i in range(k):
        currentScore += cardPoints[size - 1 - i]
        currentScore -= cardPoints[k - 1 - i]
        maxScore = max(maxScore, currentScore)
        
    return maxScore 

我们从左段的总和开始，然后逐渐将其转换为右段。在每一步中，我们都会确保更新最高分数。

我在 LeetCode 上运行了这个解决方案，它被很好地接受了。