leetcode【1423-可获得的最大点数】思考、优化、改进

た入场券 2022-10-28 10:28 151阅读 0赞

声 明 ： 该 系 列 是 我 的 随 笔 ， 会 记 录 一 些 刷 题 的 感 受 ， 思 路 。 文 章 难 免 有 错 误 或 语 句 不 够 严 谨 ， 欢 迎 指 正 。 \\color\{\#FF0000\}\{声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。 \} 声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。

如 果 读 者 关 于 这 道 题 有 其 他 疑 问 ， 也 欢 迎 在 评 论 区 和 我 讨 论 我 会 及 时 回 复 ， 互 相 进 步 ， 谢 谢 ！ \\color\{\#FF0000\}\{如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！\} 如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！

# 1.题目 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjI0MDMw_size_16_color_FFFFFF_t_70]

# 2 题目分析&心路历程 #

开始我认为这是一道简单的双指针只需在vector首尾维护两个指针，不断向中央靠近，sum累加两侧指针中较大的值即可。但是发现对于\[1,2,3,4,5,6,1\]，k=3这样的数组，左右都是1但是选择右边的1后，后续可以选择的是6,5而露出左边的1后可以选择的是1,2。这就造成了编码的困难。  
因为选择的卡牌是连续的。我们只需使用一个长度为n-k的滑动窗口对cardPoints进行遍历，对滑动窗口中的值求和（滑动窗口的值即为没有被选中的值）。我们寻找的是使得该求和最小的值。

# 3 代码&代码分析 #

class Solution { 
    public:
        int maxScore(vector<int>& cardPoints, int k) { 
            int n = cardPoints.size();
            int windowSize = n - k;
    
            int acc = 0;
            for(int i=0;i<windowSize;i++)
                acc += cardPoints[i];
            int sum = acc;
            for(int i = 0;i< k ;i++)
            { 
                acc = acc-cardPoints[i]+cardPoints[n-k+i];
                sum = min(sum,acc);
            } 
            int total = 0;
            for(int i =0;i<cardPoints.size();i++)
            { 
                total = total +cardPoints[i];
            }
            return total - sum;
        }
    
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjI0MDMw_size_16_color_FFFFFF_t_70]: /images/20221024/cadf4d0b6692406f82dc2701cbf554ca.png