Topic
幾張卡牌 排成一行，每張卡牌都有一個對應的點數，點數由整數陣列 cardPoints 給出，
每次行動，你可以從行的開頭或者末尾拿一張卡牌，最終你必須正好拿 k 張卡牌，
你的點數就是你拿到手中的所有卡牌的點數之和，
給你一個整數陣列 cardPoints 和整數 k，請你回傳可以獲得的最大點數，
Example_1
輸入：cardPoints = [1,2,3,4,5,6,1], k = 3
輸出：12
解釋：第一次行動，不管拿哪張牌，你的點數總是 1 ，但是，先拿最右邊的卡牌將會最大化你的可獲得點數，最優策略是拿右邊的三張牌，最終點數為 1 + 6 + 5 = 12 ，
Example_2
輸入：cardPoints = [2,2,2], k = 2
輸出：4
解釋：無論你拿起哪兩張卡牌，可獲得的點數總是 4 ，
Example_3
輸入：cardPoints = [9,7,7,9,7,7,9], k = 7
輸出：55
解釋：你必須拿起所有卡牌，可以獲得的點數為所有卡牌的點數之和，
Example_4
輸入：cardPoints = [1,1000,1], k = 1
輸出：1
解釋：你無法拿到中間那張卡牌，所以可以獲得的最大點數為 1 ，
Example_5
輸入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
輸出：202
Tips
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length
Solution
本題運用滑窗同樣是一個比較簡單的方法
這里需要一個思路轉換
最大洗掉數為k個數
那么剩下的數字我們放到滑窗當中
并使其長度為原序列長減k
計算滑窗中的值為total
同時令最小值暫為total
若刪去的數字值最大，則滑窗中的總值total要最小
不斷右移滑窗直至結束
若滑窗的總值total比最小值min_sum要小
則將total賦值給min_sum
完成遍歷后
回傳原序列中的總值減min_sum即為結果
Code
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
n = len(cardPoints)
window = n - k
total = sum(cardPoints[:window])
min_sum = total
for i in range(window, n):
total += cardPoints[i]
total -= cardPoints[i - window]
if total < min_sum:
min_sum = total
return sum(cardPoints) - min_sum
Result
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/257469.html
標籤：python
上一篇：PyQt5 基礎框架