西宁公司网站建设,四川建设工程信息网官网,网站被禁用如何解决,网站开发与设计实训实训报告题目解析#xff1a;1423. 可获得的最大点数 Problem: 1423. 可获得的最大点数 题目描述#xff1a;
你有一个整数数组 cardPoints#xff0c;表示排成一行的几张卡牌的点数。你每次可以从这排卡牌的 开头或末尾 拿一张卡牌#xff0c;最终你需要正好拿 k 张卡牌。目…题目解析1423. 可获得的最大点数 Problem: 1423. 可获得的最大点数 题目描述
你有一个整数数组 cardPoints表示排成一行的几张卡牌的点数。你每次可以从这排卡牌的 开头或末尾 拿一张卡牌最终你需要正好拿 k 张卡牌。目标是计算你能够拿到的 最大点数。
示例 示例 1 输入cardPoints [1, 2, 3, 4, 5, 6, 1], k 3输出12解释最优选择是从右侧拿三张卡牌点数为 1 6 5 12。 示例 2 输入cardPoints [2, 2, 2], k 2输出4解释不管选择哪两张牌总是 2 2 4。 示例 3 输入cardPoints [9, 7, 7, 9, 7, 7, 9], k 7输出55解释所有卡牌都需要选择所以直接将它们的和返回。 解题思路
方法一正向思维暴力法
最直接的思路就是使用正向思维从数组的两端开始取卡牌。我们可以从数组的开头拿一些卡牌剩下的从末尾拿。为了找到能够获得的最大点数尝试不同的取卡顺序计算所有可能的组合得分。
正向思维的具体步骤
从开头拿 0 到 k 张卡牌剩余的从末尾拿。枚举所有可能的组合计算其点数。选择点数最大的作为结果。
虽然这个方法能解出问题但时间复杂度是 O(k)对于较大的 k 值计算速度会变慢。
代码实现
class Solution {
public:int maxScore(vectorint cardPoints, int k) {int n cardPoints.size();int leftSum 0, rightSum 0;// 先计算最左侧k张牌的总和for (int i 0; i k; i) {leftSum cardPoints[i];}int maxPoints leftSum;// 逐步将左侧的卡牌移到右侧同时更新最大得分for (int i 0; i k; i) {leftSum - cardPoints[k - 1 - i]; // 从左侧减少一张卡牌rightSum cardPoints[n - 1 - i]; // 从右侧增加一张卡牌maxPoints max(maxPoints, leftSum rightSum);}return maxPoints;}
};
复杂度分析
时间复杂度O(k)。我们需要遍历 k 次来计算所有可能的得分。空间复杂度O(1)。只使用了常量级别的额外空间。 方法二滑动窗口优化逆向思维
上面的正向思维方法虽然能够解决问题但效率相对较低。我们可以通过逆向思维使用滑动窗口优化。
关键点
我们可以将问题转化为滑动窗口问题通过取出未选择的卡牌部分来最大化剩余部分的和。具体来说卡牌的总数为 n我们选择的卡牌总数为 k则有 n - k 张卡牌是不被选择的。如果能找到不被选择的 n - k 张卡牌的最小和那么总和减去这部分卡牌和就是我们需要的最大点数。
优化思路
首先计算卡牌的总和 totalSum。使用滑动窗口法找出大小为 n - k 的子数组的最小和。最大点数就是 totalSum - minWindowSum。
通过这个方法问题的复杂度从暴力解法的 O(2^k) 优化为 O(n)大大提升了效率。 代码实现
class Solution {
public:int maxScore(vectorint cardPoints, int k) {int n cardPoints.size();// 如果k等于数组长度直接返回整个数组的和if (k n) {return accumulate(cardPoints.begin(), cardPoints.end(), 0);}// 计算总点数int totalPoints accumulate(cardPoints.begin(), cardPoints.end(), 0);// 滑动窗口的长度为n - k找到最小的窗口和int windowSize n - k;int currentWindowSum accumulate(cardPoints.begin(), cardPoints.begin() windowSize, 0);int minWindowSum currentWindowSum;// 使用滑动窗口计算最小的窗口和for (int i windowSize; i n; i) {currentWindowSum cardPoints[i] - cardPoints[i - windowSize];minWindowSum min(minWindowSum, currentWindowSum);}// 最大点数为总点数减去最小的窗口和return totalPoints - minWindowSum;}
};复杂度分析
时间复杂度O(n)我们只需遍历数组两次一次用于计算总和一次用于计算最小滑动窗口和。空间复杂度O(1)除了存储几个辅助变量外代码不需要额外的空间。
