直播网站建设书籍,app多少钱,建设农家书屋官方网站,音乐网站开发开发#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域新星创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 滑动窗口 求解思路 实现代码 运行结果 共勉 题目链接
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 求解思路实现代码运行结果 ⚡ 滑动窗口 求解思路
首先不知道大家有没有和我一样上来先通过dfs先走一遍然后缓存也过不了最后dp也过不了直到最后重新更换解法。。。。题目让我们求的是首尾最大和那我们可以变通一下先求解非首尾开头的子数组的最小和然后通过数组的总和减去当前的最小和最终的答案就是我们首尾开头的最大元素和。这个过程我们可以通过滑动窗口来实现。实现代码如下所示 实现代码
class Solution {public int maxScore(int[] cardPoints, int k) {int mcardPoints.length;km-k;int resArrays.stream(cardPoints).sum();if(k0){return res;}int sum0,minInteger.MAX_VALUE;int left0;for(int right0;rightm;right){sumcardPoints[right];if(right-left1k){minMath.min(min,sum);}if(right-k10){sum-cardPoints[left];left;}}return res-min;}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
