LeetCode 1423. 可获得的最大点数【定长滑窗,逆向和正向思维】1574

本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。几张卡牌排成一行每张卡牌都有一个对应的点数。点数由整数数组cardPoints给出。每次行动你可以从行的开头或者末尾拿一张卡牌最终你必须正好拿k张卡牌。你的点数就是你拿到手中的所有卡牌的点数之和。给你一个整数数组cardPoints和整数k请你返回可以获得的最大点数。示例 1输入cardPoints[1,2,3,4,5,6,1],k3输出12解释第一次行动不管拿哪张牌你的点数总是1。但是先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌最终点数为16512。示例 2输入cardPoints[2,2,2],k2输出4解释无论你拿起哪两张卡牌可获得的点数总是4。示例 3输入cardPoints[9,7,7,9,7,7,9],k7输出55解释你必须拿起所有卡牌可以获得的点数为所有卡牌的点数之和。示例 4输入cardPoints[1,1000,1],k1输出1解释你无法拿到中间那张卡牌所以可以获得的最大点数为1。示例 5输入cardPoints[1,79,80,1,1,1,200,1],k3输出202提示1 cardPoints.length 10^51 cardPoints[i] 10^41 k cardPoints.length解法1 逆向思维拿走k kk张剩下n − k n - kn−k张。这里n nn是c a r d P o i n t s cardPointscardPoints的长度。由于拿走的点数和剩下的点数和所有点数和常数所以为了最大化拿走的点数和应该最小化剩下的点数和。由于只能从开头或末尾拿牌所以最后剩下的牌必然是连续的。至此问题变成计算长为n − k n - kn−k的连续子数组和的最小值。这可以用定长滑窗解决。设m n − k mn−kmn−k计算第一个长为m mm的子数组元素和即s c a r d P o i n t s [ 0 ] c a r d P o i n t s [ 1 ] ⋯ c a r d P o i n t s [ m − 1 ] scardPoints[0]cardPoints[1]⋯cardPoints[m−1]scardPoints[0]cardPoints[1]⋯cardPoints[m−1]。初始化m i n S s minSsminSs。计算下一个子数组的元素和即s ′ c a r d P o i n t s [ 1 ] c a r d P o i n t s [ 2 ] ⋯ c a r d P o i n t s [ m ] s cardPoints[1]cardPoints[2]⋯cardPoints[m]s′cardPoints[1]cardPoints[2]⋯cardPoints[m]。由于s ′ − s c a r d P o i n t s [ m ] − c a r d P o i n t s [ 0 ] s′−scardPoints[m]−cardPoints[0]s′−scardPoints[m]−cardPoints[0]所以只需要把s ss增加c a r d P o i n t s [ m ] − c a r d P o i n t s [ 0 ] cardPoints[m]−cardPoints[0]cardPoints[m]−cardPoints[0]就可以O ( 1 ) O(1)O(1)算出下一个子数组的元素和。依照这个方法从i m imim开始向后枚举每次把s ss增加c a r d P o i n t s [ i ] − c a r d P o i n t s [ i − m ] cardPoints[i]−cardPoints[i−m]cardPoints[i]−cardPoints[i−m]然后用s ss更新m i n S minSminS的最小值。最后用c a r d P o i n t s cardPointscardPoints的元素和减去m i n S minSminS就得到了答案。注若用 模板 中的有分支写法需要特判m 0 m0m0也就是n k nknk的情况此时直接返回c a r d P o i n t s cardPointscardPoints的元素和。classSolution{publicintmaxScore(int[]cardPoints,intk){intncardPoints.length;intmn-k;ints0;for(inti0;im;i){scardPoints[i];}inttotals;intminSs;for(intim;in;i){totalcardPoints[i];scardPoints[i]-cardPoints[i-m];minSMath.min(minS,s);}returntotal-minS;}}classSolution{public:intmaxScore(vectorintcardPoints,intk){intncardPoints.size();intmn-k;intsreduce(cardPoints.begin(),cardPoints.begin()m);intmin_ss;for(intim;in;i){scardPoints[i]-cardPoints[i-m];min_smin(min_s,s);}returnreduce(cardPoints.begin(),cardPoints.end())-min_s;}};classSolution:defmaxScore(self,cardPoints:List[int],k:int)-int:nlen(cardPoints)mn-k min_sssum(cardPoints[:m])foriinrange(m,n):scardPoints[i]-cardPoints[i-m]min_smin(min_s,s)returnsum(cardPoints)-min_s# 写法2classSolution:defmaxScore(self,cardPoints:List[int],k:int)-int:mlen(cardPoints)-k min_sssum(cardPoints[:m])forin_,outinzip(cardPoints[m:],cardPoints):sin_-out min_smin(min_s,s)returnsum(cardPoints)-min_simplSolution{pubfnmax_score(card_points:Veci32,k:i32)-i32{letncard_points.len();letmn-kasusize;letmutscard_points.iter().take(m).sum::i32();letmutmin_ss;foriinm..n{scard_points[i]-card_points[i-m];min_smin_s.min(s);}card_points.iter().sum::i32()-min_s}}funcmaxScore(cardPoints[]int,kint)int{n:len(cardPoints)m:n-k s:0for_,x:rangecardPoints[:m]{sx}total:s minS:sfori:m;in;i{totalcardPoints[i]scardPoints[i]-cardPoints[i-m]minSmin(minS,s)}returntotal-minS}varmaxScorefunction(cardPoints,k){constncardPoints.length;constmn-k;lets0;for(leti0;im;i){scardPoints[i];}lettotals;letminSs;for(letim;in;i){totalcardPoints[i];scardPoints[i]-cardPoints[i-m];minSMath.min(minS,s);}returntotal-minS;};复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn为c o d e P o i n t s codePointscodePoints的长度。空间复杂度O ( 1 ) O(1)O(1)Python忽略切片开销。解法2 正向思维答案等于如下结果的最大值前k kk个数的和前k − 1 k -1k−1个数和后1 11个数的和前k − 2 k-2k−2个数和后2 22个数的和……前2 22个数和后k − 2 k-2k−2个数的和前1 11个数和后k − 1 k -1k−1个数的和后k kk个数的和。算法计算前k kk个数的和记为s ss。初始答案a n s s ans sanss。从i 1 i 1i1开始枚举到i k i kik。每次枚举把s ss增加c a r d P o i n t s [ n − i ] − c a r d P o i n t s [ k − i ] cardPoints[n - i] - cardPoints[k - i]cardPoints[n−i]−cardPoints[k−i]然后更新a n s ansans的最大值。返回a n s ansans。classSolution{publicintmaxScore(int[]cardPoints,intk){ints0;for(inti0;ik;i){scardPoints[i];}intanss;for(inti1;ik;i){scardPoints[cardPoints.length-i]-cardPoints[k-i];ansMath.max(ans,s);}returnans;}}classSolution{public:intmaxScore(vectorintcardPoints,intk){intsreduce(cardPoints.begin(),cardPoints.begin()k);intanss;for(inti1;ik;i){scardPoints[cardPoints.size()-i]-cardPoints[k-i];ansmax(ans,s);}returnans;}};classSolution:defmaxScore(self,cardPoints:List[int],k:int)-int:ansssum(cardPoints[:k])foriinrange(1,k1):scardPoints[-i]-cardPoints[k-i]ansmax(ans,s)returnansclassSolution:defmaxScore(self,cardPoints:List[int],k:int)-int:ansssum(cardPoints[-k:])# 为方便下面 zip改为先计算后 k 个数的和forx,yinzip(cardPoints,cardPoints[-k:]):sx-y ansmax(ans,s)returnansimplSolution{pubfnmax_score(card_points:Veci32,k:i32)-i32{letkkasusize;letmutscard_points.iter().take(k).sum::i32();letmutanss;foriin1..k{scard_points[card_points.len()-i]-card_points[k-i];ansans.max(s);}ans}}funcmaxScore(cardPoints[]int,kint)int{s:0for_,x:rangecardPoints[:k]{sx}ans:sfori:1;ik;i{scardPoints[len(cardPoints)-i]-cardPoints[k-i]ansmax(ans,s)}returnans}varmaxScorefunction(cardPoints,k){lets0;for(leti0;ik;i){scardPoints[i];}letanss;for(leti1;ik;i){scardPoints[cardPoints.length-i]-cardPoints[k-i];ansMath.max(ans,s);}returnans;};复杂度分析时间复杂度O ( k ) O(k)O(k)。空间复杂度O ( 1 ) O(1)O(1)。思考题把题目改成拿走的卡牌数量无限制但c a r d P o i n t s cardPointscardPoints中有负数。如何求出可以获得的最大点数和