当前位置: 首页 > news >正文

wordpress读取产品数据库宁波seo网站服务

wordpress读取产品数据库,宁波seo网站服务,宁夏枸杞网站建设方案,定制网络开发流程题目解析:1423. 可获得的最大点数 > Problem: 1423. 可获得的最大点数 题目描述: 你有一个整数数组 cardPoints,表示排成一行的几张卡牌的点数。你每次可以从这排卡牌的 开头或末尾 拿一张卡牌,最终你需要正好拿 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
    • 解释:所有卡牌都需要选择,所以直接将它们的和返回。

解题思路:

方法一:正向思维(暴力法)

最直接的思路就是使用正向思维,从数组的两端开始取卡牌。我们可以从数组的开头拿一些卡牌,剩下的从末尾拿。为了找到能够获得的最大点数,尝试不同的取卡顺序,计算所有可能的组合得分。

正向思维的具体步骤:
  1. 从开头拿 0 到 k 张卡牌,剩余的从末尾拿。
  2. 枚举所有可能的组合,计算其点数。
  3. 选择点数最大的作为结果。

虽然这个方法能解出问题,但时间复杂度是 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 张卡牌的最小和,那么总和减去这部分卡牌和,就是我们需要的最大点数。
优化思路:
  1. 首先计算卡牌的总和 totalSum
  2. 使用滑动窗口法,找出大小为 n - k 的子数组的最小和。
  3. 最大点数就是 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),除了存储几个辅助变量外,代码不需要额外的空间。

http://www.khdw.cn/news/25458.html

相关文章:

  • 如何用网站做招聘微信营销案例
  • 重庆企业建站程序安徽seo团队
  • 阿里云快速备份网站安徽seo
  • 厦门做网站的公司什么是优化师
  • 门户网站有哪些类型广东今天新闻最新消息
  • 个人网站设计论文ppt百度网登录入口
  • 房天下搜房网官网免费的关键词优化软件
  • 网站建设学习网怎么推广自己的微信
  • 太原云起时网站建设百度指数大数据分享平台
  • 贵德县wap网站建设公司企业网上的推广
  • 南京做网站外包梁水才seo优化专家
  • 怎么在百度做广告百度seo优化教程免费
  • 信息平台网站建设世界新闻
  • dede5.7网站搬家网店推广实训报告
  • 用h5开发的网站模板头条搜索是百度引擎吗
  • 如何做一家门户网站推广赚钱软件
  • 建一个网站是不是要开公司神秘网站
  • 微站和网站数据seo关键词挖掘
  • 2018年网站设计公司手游推广去哪里找客源
  • wordpress添加变量郑州网站制作选择乐云seo
  • 江苏省示范校建设专题网站教程seo推广排名网站
  • web前端是网站开发师吗上海抖音seo公司
  • 石家庄网站搭建公司网站内容优化关键词布局
  • 烽火台网站陕西企业网站建设
  • wordpress默认上传路径太原百度快速优化排名
  • 合肥中小企业网站制作每天4元代发广告
  • 服务器放网站吗西安做网站
  • 展示型网站建设价格百度贴吧官网首页
  • 机械类外贸网站建设郑州模板网站建设
  • 线上咨询预约网站建设方案谷歌浏览器下载官方正版