题目解析:1423. 可获得的最大点数
题目解析: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(vector<int>& 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(vector<int>& 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)
,除了存储几个辅助变量外,代码不需要额外的空间。
原文地址:https://blog.csdn.net/PQ781826/article/details/142819051
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!