最后一块石头的重量(超级妙的背包问题)
1049. 最后一块石头的重量 II
有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:
- 如果
x == y,那么两块石头都会被完全粉碎; - 如果
x != y,那么重量为x的石头将会完全粉碎,而重量为y的石头新重量为y-x。
最后,**最多只会剩下一块 **石头。返回此石头 **最小的可能重量 **。如果没有石头剩下,就返回 0。
示例 1:
**输入:**stones = [2,7,4,1,8,1]
**输出:**1
**解释:**
组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1],
组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1],
组合 2 和 1,得到 1,所以数组转化为 [1,1,1],
组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。
示例 2:
**输入:**stones = [31,26,33,21,40]
**输出:**5
提示:
1 <= stones.length <= 301 <= stones[i] <= 100
这一题很难想到背包问题
这道题看出是背包问题比较有难度
最后一块石头的重量:从一堆石头中,每次拿两块重量分别为x,y的石头,若x=y,则两块石头均粉碎;若x<y,两块石头变为一块重量为y-x的石头求最后剩下石头的最小重量(若没有剩下返回0)
问题转化为:把一堆石头分成两堆,求两堆石头重量差最小值
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size();int sum = 0;for (auto u : stones) {sum += u;}int bag = sum / 2;vector<int> dp(bag + 1, 0);for (int i = 0; i < n; i++) {for (int j = bag; j >= stones[i]; j--) {dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[bag];}
};
相关文章:
最后一块石头的重量(超级妙的背包问题)
1049. 最后一块石头的重量 II 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x < y。那么粉碎的可能结果…...
如何评估和提升审查者在前端代码审查中的专业技能?
评估和提升审查者在前端代码审查中的专业技能可以通过以下步骤: 技能评估: 定期进行技能评估,了解审查者在前端开发各方面的能力,包括但不限于HTML、CSS、JavaScript、框架使用、代码规范等。 代码审查实践: 通过实…...
C++(区别于C的)基础内容总结
参考: C 教程 | 菜鸟教程 (runoob.com) 简介 C 被认为是一种中级语言,它综合了高级语言和低级语言的特点。 C 是由 Bjarne Stroustrup 于 1979 年在新泽西州美利山贝尔实验室开始设计开发的。C 进一步扩充和完善了 C 语言,最初命名为带类的C&…...
实现代码灵活性:用Roslyn动态编译和执行存储在数据库中的C#代码
在许多现代应用程序中,动态编译和执行代码是提升灵活性和功能的一种强大技术。本文将介绍如何使用Roslyn编译器平台动态编译和执行存储在数据库中的C#代码,并结合实际公司案例来说明这些技术的应用场景。 1. 引言 在很多应用场景中,我们可能…...
探索哈希表:C++中的实现与操作详解【Map、Set、数据结构】
探索哈希表:C中的实现与操作详解 介绍 哈希表(Hash Table)是一种常见的数据结构,它提供了一种高效的键值对存储方式,能够快速进行插入、删除和查找操作。在这篇博客中,我们将详细介绍哈希表的概念、在C中的…...
Python酷库之旅-第三方库Pandas(062)
目录 一、用法精讲 241、pandas.Series.view方法 241-1、语法 241-2、参数 241-3、功能 241-4、返回值 241-5、说明 241-6、用法 241-6-1、数据准备 241-6-2、代码示例 241-6-3、结果输出 242、pandas.Series.compare方法 242-1、语法 242-2、参数 242-3、功能 …...
python学习之旅(基础篇看这篇足够了!!!)
目录 前言 1.输入输出 1.1 输入 1.2 输出 2. 变量与常量 2.1 变量 2.2 常量 2.3 赋值 2.4格式化输出 3. 数据类型 4. 四则运算 5.“真与假” 5.1 布尔数 5.2 比较运算和逻辑运算 5.3 布尔表达式 6.判断语句 6.1 基本的if语句 6.2 if-else语句 6.3 if-elif-el…...
Azure OpenAI Embeddings vs OpenAI Embeddings
题意:Azure OpenAI 嵌入与 OpenAI 嵌入的比较 问题背景: Is anyone getting different results from Azure OpenAI embeddings deployment using text-embedding-ada-002 than the ones from OpenAI? Same text, same model, and the results are cons…...
重生奇迹MU职业成长三步走
在重生奇迹MU游戏中,转职是最重要的玩法之一。每个职业在转职后都会发生巨大的变化,经过三次转职后,你才有资格成为该游戏中最强大的冒险者。 一转,一切才刚刚开始 玩家完成第一次转职任务后,标志着我们成功度过了游…...
2024年中国数据中台行业研究报告
数据中台丨研究报告 核心摘要: 数据中台是企业数字化建设的重要构成,其通过整合企业基础设施和数据能力,实现数据资产化和服务复用,降低运营成本,支撑业务创新。受宏观经济影响,部分企业减少了对数据中台等…...
MySQL——数据表的基本操作(一)创建数据表
数据库创建成功后,就需要创建数据表。所谓创建数据表指的是在已存在的数据库中建立新表。需要注意的是,在操作数据表之前,应该使用 “ USE 数据库名 ” 指定操作是在哪个数据库中进行,否则会抛出 “ No database selected ” 错误。创建数据表…...
EPLAN EDZ 文件太大导入很慢如何解决?
目前各个品牌都在提供 EPLAN EDZ部件库文件,但是一般都是一个总的EDZ文件,导入过程中,因为电脑配置和其他问题,导致导入过程中EPLAN会崩溃或者长时间不动。 我们分析下EDZ文件的构成,这是个压缩文件,换了个壳而已。用压缩软件把edz打开,这里不是解压,直接右键,用解压…...
刷题——缺失的第一个正整数
缺失的第一个正整数_牛客题霸_牛客网 我选择了一个我比较能看懂的, int minNumberDisappeared(vector<int>& nums) {// write code heremap<int, int>hash;int n nums.size();//哈希表记录数组中出现的每个数字for(int i 0; i < n; i)hash[n…...
代理设置--一些库的代理设置
首先最好能获取一个免费代理,来继续下面的阅读和实验 也可以在本机设置代理,具体流程由于比较敏感,请自行搜索 代理设置成功后的测试网站是 http://www.httpbin.org/get , 访问该链接可以得到请求相关的信息,返回结果中的 ori…...
Debezium系列之:PostgreSQL数据库赋予账号数据采集权限的详细步骤
Debezium系列之:PostgreSQL数据库赋予账号数据采集权限的详细步骤 一、账号需要的权限二、创建账号,赋予登陆、复制权限三、赋予账号数据库权限四、赋予账号对表的权限五、创建PostgreSQL数据库复制组六、账号权限授予完整案例七、扩展——分区表设置八、扩展-撤销账号的权限…...
javascript:判断输入值是数字还是字母
1 代码示例 要判断输入值是数字还是字母,我们可以通过JavaScript获取输入框的值,然后使用isNaN函数来检查输入值是否为数字。 <!DOCTYPE html> <html><head><meta charset"UTF-8"><title></title><s…...
Java-排序算法-复盘知识点
刷了24道简单排序题,18道中等排序题之后,给排序算法来个简单的复盘(从明天开始刷动态规划咯) 1.对于找多数元素(出现次数超过一半的元素)可以使用摩尔投票法。 2.HashSet的add方法非常实用:如…...
HarmonyOS 原生智能之语音识别实战
HarmonyOS 原生智能之语音识别实战 背景 公司很多业务场景使用到了语音识别功能,当时我们的语音团队自研了语音识别模型,方案是云端模型加端侧SDK交互,端侧负责做语音采集、VAD、opus编码,实时传输给云端,云端识别后…...
基于Gromacs的蛋白质与小分子配体相互作用模拟教程
在生命科学的广阔领域中,蛋白质与小分子配体之间的相互作用扮演着至关重要的角色。这些相互作用不仅影响着生物体内的各种生命活动,如信号传导、代谢调控和药物作用等,同时也是药物设计和开发的核心内容。因此,深入理解并模拟这些…...
Ubuntu下python3.12安装, 分布式 LLM 推理 exo 安装调试过程, 运行自己的 AI 集群
创作不易 只因热爱!! 热衷分享,一起成长! “你的鼓励就是我努力付出的动力” —调试有点废,文章有点长,希望大家用心看完,肯定能学废,感谢. 1. Ubuntu下python3.12安装 1.1 导入 Python 的稳定版 PPA,不用编译 sudo add-apt-repository ppa:deadsnakes/ppa sudo…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
