毕业设计网页制作网站建设,网站开发需要学,与动漫有关的专业,小程序 wordpressEvery day a Leetcode
题目来源#xff1a;1423. 可获得的最大点数
解法1#xff1a;前缀和 后缀和
基于贪心的思想#xff0c;要使得获得的点数最大#xff0c;每次拿卡牌都应该选点数尽量高的卡牌。
但是拿卡牌有限制#xff0c;每次行动#xff0c;只可以从行的…Every day a Leetcode
题目来源1423. 可获得的最大点数
解法1前缀和 后缀和
基于贪心的思想要使得获得的点数最大每次拿卡牌都应该选点数尽量高的卡牌。
但是拿卡牌有限制每次行动只可以从行的开头或者末尾拿一张卡牌最终必须正好拿 k 张卡牌。
设数组 cardPoints 的长度为 n。分别求出它的前缀和数组 prevSum 和后缀和数组 suffixSum设我们从行的开头拿 i0ik 张卡牌那么我们只能从行的末尾拿 k-i 张卡牌设最大点数之和为 max_sum则有
for (int i 0; i k; i)max_sum max(max_sum, prevSum[i] suffixSum[n - (k - i)]);也可以将数组 suffixSum 反转有
reverse(suffixSum.begin(), suffixSum.end());
for (int i 0; i k; i)max_sum max(max_sum, prevSum[i] suffixSum[k - i]);代码
/** lc appleetcode.cn id1423 langcpp** [1423] 可获得的最大点数*/// lc codestart
class Solution
{
public:int maxScore(vectorint cardPoints, int k){if (k 0)return 0;if (k cardPoints.size())return accumulate(cardPoints.begin(), cardPoints.end(), 0);int n cardPoints.size();vectorint prevSum(n 1, 0), suffixSum(n 1, 0);for (int i 1; i n; i)prevSum[i] prevSum[i - 1] cardPoints[i - 1];for (int i n - 1; i 0; i--)suffixSum[i] suffixSum[i 1] cardPoints[i];// reverse(suffixSum.begin(), suffixSum.end());int max_sum 0;for (int i 0; i k; i){max_sum max(max_sum, prevSum[i] suffixSum[n - (k - i)]);}return max_sum;}
};
// lc codeend结果 复杂度分析
时间复杂度O(nk)其中 n 是数组 cardPoints 的长度。
空间复杂度O(n)其中 n 是数组 cardPoints 的长度。主要是 prevSum 和 suffixSum 的开销各使用了 n1 的空间。
解法2滑动窗口
记数组 cardPoints 的长度为 n由于只能从开头和末尾拿 k 张卡牌所以最后剩下的必然是连续的 n−k 张卡牌。
逆向思维我们可以通过求出剩余卡牌点数之和的最小值来求出拿走卡牌点数之和的最大值。
算法
由于剩余卡牌是连续的使用一个固定长度为 n−k 的滑动窗口对数组 cardPoints 进行遍历求出滑动窗口最小值然后用所有卡牌的点数之和减去该最小值即得到了拿走卡牌点数之和的最大值。
代码
// 滑动窗口class Solution
{
public:int maxScore(vectorint cardPoints, int k){if (k 0)return 0;if (k cardPoints.size())return accumulate(cardPoints.begin(), cardPoints.end(), 0);int n cardPoints.size();int windowSize n - k;int sum accumulate(cardPoints.begin(), cardPoints.begin() windowSize, 0);int min_sum sum;for (int i windowSize; i n; i){sum cardPoints[i];sum - cardPoints[i - windowSize];min_sum min(min_sum, sum);}return accumulate(cardPoints.begin(), cardPoints.end(), 0) - min_sum;}
};结果 复杂度分析
时间复杂度O(n)其中 n 是数组 cardPoints 的长度。
空间复杂度O(1)。
