2024.2.3每日一题

LeetCode

石子游戏 VII

1690. 石子游戏 VII - 力扣(LeetCode)

题目描述

石子游戏中,爱丽丝和鲍勃轮流进行自己的回合,爱丽丝先开始

n 块石子排成一排。每个玩家的回合中,可以从行中 移除 最左边的石头或最右边的石头,并获得与该行中剩余石头值之 相等的得分。当没有石头可移除时,得分较高者获胜。

鲍勃发现他总是输掉游戏(可怜的鲍勃,他总是输),所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值

给你一个整数数组 stones ,其中 stones[i] 表示 从左边开始 的第 i 个石头的值,如果爱丽丝和鲍勃都 发挥出最佳水平 ,请返回他们 得分的差值

示例 1:

输入:stones = [5,3,1,4,2]
输出:6
解释:
- 爱丽丝移除 2 ,得分 5 + 3 + 1 + 4 = 13 。游戏情况:爱丽丝 = 13 ,鲍勃 = 0 ,石子 = [5,3,1,4] 。
- 鲍勃移除 5 ,得分 3 + 1 + 4 = 8 。游戏情况:爱丽丝 = 13 ,鲍勃 = 8 ,石子 = [3,1,4] 。
- 爱丽丝移除 3 ,得分 1 + 4 = 5 。游戏情况:爱丽丝 = 18 ,鲍勃 = 8 ,石子 = [1,4] 。
- 鲍勃移除 1 ,得分 4 。游戏情况:爱丽丝 = 18 ,鲍勃 = 12 ,石子 = [4] 。
- 爱丽丝移除 4 ,得分 0 。游戏情况:爱丽丝 = 18 ,鲍勃 = 12 ,石子 = [] 。
得分的差值 18 - 12 = 6 。

示例 2:

输入:stones = [7,90,5,1,100,10,10,2]
输出:122

提示:

  • n == stones.length
  • 2 <= n <= 1000
  • 1 <= stones[i] <= 1000

思路

从记忆化搜索到递推

灵神题解

1690. 石子游戏 VII - 力扣(LeetCode)

代码

C++
class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<int> s(n + 1);
        partial_sum(stones.begin(), stones.end(), s.begin() + 1);
        vector<vector<int>> f(n, vector<int>(n));
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                f[i][j] = max(s[j + 1] - s[i + 1] - f[i + 1][j],s[j] - s[i] - f[i][j - 1]);
            }
        }
        return f[0][n - 1];
    }
};
Java
class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[] s = new int[n + 1];
        for(int i = 0; i < n; i++){
            s[i + 1] += s[i] + stones[i];
        }
        int [][] f = new int[n][n];
        for(int i = n - 2;i >= 0; i--){
            for(int j = i + 1;j < n; j++){
                f[i][j] = Math.max(s[j + 1] - s[i + 1] - f[i + 1][j],s[j] - s[i] - f[i][j - 1]);
            }
        }
        return f[0][n - 1];
    }
}

今日所学

C++使用partial_sum求前缀和

partial_sum(stones.begin(), stones.end(), s.begin() + 1);

partial_sum是C++标准库中的一个算法,用于计算给定范围内元素的部分和。它接受两个迭代器作为输入范围,并将结果存储在另一个迭代器指向的容器中。

用法:

std::partial_sum(first, last, result);

其中,firstlast分别表示输入范围的起始和结束迭代器,result表示存储结果的容器的起始迭代器。

示例:

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    std::vector<int> result(nums.size());

    std::partial_sum(nums.begin(), nums.end(), result.begin());

    for (int i : result) {
        std::cout << i << " ";
    }

    return 0;
}  

输出结果:

1 3 6 10 15

image-20240203094844925

image-20240203094852022

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/367971.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【已更新】2024美赛C题代码教学思路数据处理数学建模分析Momentum in Tennis

问题一完整的代码已给出&#xff0c;预计2号晚上或者3号凌晨全部给出。 代码逻辑如下&#xff1a; C题第一问要求我们开发一个模型&#xff0c;捕捉得分时的比赛流程&#xff0c;并将其应用于一场或多场比赛。你的模型应该确定哪名球员在比赛的特定时间表现得更好&#xff0c;…

C系列-动态内存管理

&#x1f308;个人主页: 会编程的果子君 ​&#x1f4ab;个人格言:“成为自己未来的主人~” 目录 为什么要有动态内存分配 malloc和free malloc free calloc和realloc calloc realloc 常见的动态内存的错误 对NULL指针的解引用操作 ​编辑 对动态开辟空间的越界访问…

Three.js学习3:第一个Three.js页面

一、一图看懂Three.js 坐标 这个没什么好说的&#xff0c;只是需要注意颜色。在 Three.js 提供的编辑器中&#xff0c;各种物体的坐标也这样的色彩&#xff1a; 红色&#xff1a;x 轴 绿色&#xff1a;y 轴 蓝色&#xff1a;z 轴 Three.js 提供的编辑器可以在本地 Three.js …

python算法与数据结构(搜索算法和拓扑排序算法)---广度优先搜索和拓扑排序

广度优先搜索BFS 定义&基本内容 广度优先是按照层次由近及远的进行搜索&#xff0c;在当前层次所有可及节点都搜索完毕后才会继续往下搜索&#xff0c;其本质就是寻找从起点到终点的最短路程。 树的广度优先搜索 树的广度优先遍历&#xff0c;可以看成是层序遍历。 访问…

java数据结构与算法刷题-----LeetCode15. 三数之和

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 解题思路 和LeetCode1.两数之和一样&#xff0c;但是这道题边界条件更多。…

基于协同过滤的个性化电影推荐系统分析设计python+flask

本系统为用户而设计制作个性化电影推荐管理&#xff0c;旨在实现个性化电影推荐智能化、现代化管理。本个性化电影推荐自动化系统的开发和研制的最终目的是将个性化电影推荐的运作模式从手工记录数据转变为网络信息查询管理&#xff0c;从而为现代管理人员的使用提供更多的便利…

2401Idea用GradleKotlin编译Java控制台中文出乱码解决

解决方法 解决方法1 在项目 build.gradle.kts 文件中加入 tasks.withType<JavaCompile> {options.encoding "UTF-8" } tasks.withType<JavaExec> {systemProperty("file.encoding", "utf-8") }经测试, 只加 tasks.withType<…

谷粒商城【成神路】-【4】——分类维护

目录 1.删除功能的实现 2.新增功能的实现 3.修改功能的实现 4.拖拽功能 1.删除功能的实现 1.1逻辑删除 逻辑删除&#xff1a;不删除数据库中真实的数据&#xff0c;用指定字段&#xff0c;显示的表示是否删除 1.在application.yml中加入配置 mybatis-plus:global-config:…

俩种方法解决 VScode中 NPM 脚本消失,NPM 脚本未显示在资源管理器侧栏中

npm脚本是npm包管理器的一个功能&#xff0c;允许开发者在package.json文件中定义一系列命令脚本&#xff0c;用于执行各种开发任务。 今天打开准备运行的时候发现找不到NPM脚本了&#xff0c;左侧的一栏完全没有显示&#xff0c;在网上查阅了很多资料后总结出俩个方法可以用来…

寒假作业2月3号

第二章 引用内联重载 一&#xff0e;选择题 1、适宜采用inline定义函数情况是&#xff08;C&#xff09; A. 函数体含有循环语句 B. 函数体含有递归语句 C. 函数代码少、频繁调用 D. 函数代码多、不常调用 2、假定一个函数为A(int i4, int j0) {;}, 则执行“A (1);”语句…

解密二进制世界:Hex-Rays IDA Pro forMac/win交互式反汇编工具

在当今数字化时代&#xff0c;软件和硬件的安全性成为了重中之重。为了保护软件和硬件免受黑客和恶意攻击的威胁&#xff0c;人们需要了解和分析代码的内部结构和工作原理。而Hex-Rays IDA Pro作为一款强大的交互式反汇编工具&#xff0c;为安全专业人士提供了解密二进制世界的…

Juc07_乐观锁和悲观锁、公平锁和非公平锁、递归锁(可重入锁)、死锁及排查、自旋锁

1、 乐观锁和悲观锁 ①. 悲观锁(synchronized关键字和Lock的实现类都是悲观锁) 什么是悲观锁&#xff1f;认为自己在使用数据的时候一定有别的线程来修改数据&#xff0c;因此在获取数据的时候会先加锁&#xff0c;确保数据不会被别的线程修改适合写操作多的场景&#xff0c;…

lua 语法介绍与 NGINX lua 高级用法实战操作

文章目录 一、概述二、lua 安装三、lua 语法1&#xff09;lua 数据类型2&#xff09;lua 变量3&#xff09;lua 拼接字符串4&#xff09;lua 循环5&#xff09;lua 函数6&#xff09;lua 条件控制7&#xff09;lua 库模块 四、NGINX lua 高级用法 一、概述 lua是一种轻量小巧的…

【AI绘画UI+Windows部署】Fooocus:Controlnet原作者结合了sd的开源和Midjourney重新设计的UI

代码&#xff1a;https://github.com/lllyasviel/Fooocus windows一键启动包下载&#xff1a;https://github.com/lllyasviel/Fooocus/releases/download/release/Fooocus_win64_2-1-831.7z B站视频教程&#xff1a;AI绘画入门神器&#xff1a;Fooocus | 简化SD流程&#xff0c…

Boosting semantic human matting with coarse annotations

前向推理在modelscope中开源了&#xff0c;但是训练没开源&#xff0c;且是基于TensorFlow的&#xff0c;复现起来是比较麻烦的。 1.Introduction 分割技术主要集中在像素级二元分类&#xff0c;抠图被建模为前景图像F和背景图像B的加权融合&#xff0c;大多数matte方法采用指…

不做中位剧的腾讯,能靠精品撑起长视频会员吗?

回顾腾讯视频的2023年,马化腾用“厚积薄发”来形容。 在腾讯年会上,马化腾回顾了过去一年长视频业务板块的发展情况,同时也清晰地提出了未来的规划,总结来说就是以下三点: 1、《繁花》《三体》《漫长的季节》是腾讯过去一年特别出彩的剧集,几部大剧撑起了长视频会员业务…

设计模式——2_1 命令(Command)

文章目录 定义图纸一个例子&#xff1a;空调和他的遥控器只有控制面板的空调遥控器可以撤销的操作 碎碎念命令和Runnable命令和事务 定义 把请求封装成一个对象&#xff0c;从而使你可以用不同的请求对客户进行参数化&#xff0c;对请求排队或记录请求日志&#xff0c;以及支持…

Spring Bean 生命周期常见错误

虽然说 Spring 容器上手简单&#xff0c;可以仅仅通过学习一些有限的注解&#xff0c;即可达到快速使用的目的。但在工程实践中&#xff0c;我们依然会从中发现一些常见的错误。尤其当你对 Spring 的生命周期还没有深入了解时&#xff0c;类初始化及销毁过程中潜在的约定就不会…

超越现实,体验无限可能——VMware Workstation 的魅力之旅

随着科技的飞速发展&#xff0c;虚拟化技术已经深入人心&#xff0c;成为现代人工作与学习的必备工具。在这其中&#xff0c;VMware Workstation以其卓越的性能和稳定的运行环境&#xff0c;成为众多电脑爱好者和专业人士的首选。今天&#xff0c;让我们一起探索VMware Worksta…

初探unity中的ECS

ECS是一种软件架构模式&#xff0c;就像MVC一样。ECS最早在游戏《守望先锋》中提及到的相关链接。ECS具体是指实体&#xff08;entity&#xff09;、 组件&#xff08;component&#xff09;和系统&#xff08;system&#xff09;&#xff1a; 实体&#xff1a;实体是一个ID&a…