[leetCode 丶 20241120] 1423. 可获得的最大点数

原题: 1423.可获得的最大点数

描述:

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

示例 1：

输入： cardPoints = [1,2,3,4,5,6,1], k = 3
输出： 12
解释： 第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12

示例 2：

输入： cardPoints = [2,2,2], k = 2
输出： 4
解释： 无论你拿起哪两张卡牌，可获得的点数总是 4 。

示例 3

输入： cardPoints = [9,7,7,9,7,7,9], k = 7
输出： 55
解释： 你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。

示例 4

输入： cardPoints = [1,1000,1], k = 1
输出： 1
解释： 你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。

示例 5

输入： cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出： 202

提示

1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

个人版答案

执行用时: 2 ms 执行内存消耗: 53.66 M

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        if(k == 1){
            return Math.max(cardPoints[0], cardPoints[cardPoints.length - 1]);
        }
        if (k == cardPoints.length){
            return Arrays.stream(cardPoints).sum();
        }
        int right = 0;
        for (int i = 0; i < k; i++) {
            right += cardPoints[cardPoints.length - k + i];
        }
        int res = right, left = 0;
        for (int i = 0; i < k; i++){
            left += cardPoints[i];
            right -= cardPoints[cardPoints.length - k + i];
            res = Math.max(res, left + right);
        }
        return res;
    }
}

优秀解法

执行耗时: 0 ms

class Solution {
    public int maxScore(int[] c, int k) {
        int i = 0, res = 0, x = 0;
        for (i = k; 0 != i--; res += c[i]) ;
        if ((i = c.length) == k) return res;
        for (x = res; 0 != k; res = (x += c[--i] - c[--k]) > res ? x : res) ;
        return res;
    }
}

个人解题思路与优秀答案解析

题目分析及个人版思路

= 1 , 第一个和最后一个比大小
= length. 数组和
每次都要从开头和结尾拿一个元素, 直到拿K个元素后. 保证点数和最大...此消彼长法, 秒了
倒序反人类, 那我们就假设从队尾拿K个元素的和为 right. 这时候从左边开头拿的是0.
如果从左边拿了一个下标0, 那右侧应该去掉哪个? 对咯, 要去掉从队尾查的第K个元素. 所以应该是什么? length - k + 0;
如果从左边拿了一个下标0,1, 那右侧应该去掉哪个? 对咯, 要去掉从队尾查的第K个元素. 所以应该是什么? length - k + 0,length - k + 1;
....
k + 5. 那我们等于遍历了一遍左右依次拿的. 那么我们从第五步开始, 每次结果都跟提前求和的right对比. 只取最大值. 那么当我们遍历完之后, 就怎么样了? 就拿到最大值咯.
k + 6. 思路清晰, 上代码

进阶版思路
没办法...跟我一起喊, 天才!!! 这必须算法大佬