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

LeetCode1049. 最后一块石头的重量 II

1049. 最后一块石头的重量 II

文章目录

    • [1049. 最后一块石头的重量 II](https://leetcode.cn/problems/last-stone-weight-ii/)
      • 一、题目
      • 二、题解
        • 方法一:01背包二维数组
          • 算法思路
          • 具体实现
        • 方法二:01背包一维数组


一、题目

有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 xy,且 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 <= 30
  • 1 <= stones[i] <= 100

二、题解

方法一:01背包二维数组

算法思路

01背包问题回顾

在01背包问题中,我们有一组物品,每个物品有两个属性:重量和价值。背包有一个固定的容量,我们的目标是在不超过背包容量的情况下,选择物品放入背包,使得放入的物品总价值最大。

我们可以将这个问题的状态定义为 dp[i][j],表示在前 i 个物品中,背包容量为 j 的情况下,可以获得的最大价值。状态转移方程可以表示为:

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

将题目映射到01背包

现在我们回到题目中,虽然题目描述中没有直接提到背包,但我们可以通过观察发现类似的特性:我们要将石头分成两堆,使得两堆的重量差尽量小。

在01背包问题中,我们选择物品放入背包的状态是离散的:要么放入,要么不放入。在本题中,我们可以类比,将石头看作是我们要选择放入背包的“物品”,每块石头的重量看作是物品的“重量”。我们要将石头分成两堆,使得两堆的重量差尽量小,相当于在一个背包的容量为总重量的一半时,选择一些石头放入背包,使得背包中的石头总重量尽量接近总重量的一半。

(这里的背包容量就对应着总重量的一半,而每块石头的重量和价值相同)。这就是为什么我们能够将这个问题映射到01背包问题。

具体实现
  1. 状态定义: 定义一个二维数组 dp[i][j],表示在前 i 块石头中,能否找到一种分法,使得其中一组的总重量恰好为 j。这里 i 的范围是从 0 到石头的总数,j 的范围是从 0 到总重量的一半(因为我们要将石头分成两组,两组的重量和不能超过总重量的一半,否则不符合题意)。

  2. 状态转移: 对于每一块石头,我们可以选择将其放入其中一组,或者不放入。如果我们不放入第 i 块石头,那么问题就转化为在前 i-1 块石头中寻找一种分法,使得其中一组的总重量恰好为 j。如果我们放入第 i 块石头,那么问题就转化为在前 i-1 块石头中寻找一种分法,使得其中一组的总重量恰好为 j - stones[i]

    综合考虑这两种情况,我们可以得到状态转移方程:

    dp[i][j] = dp[i-1][j] || dp[i-1][j-stones[i]]
    
  3. 边界条件: 初始化时,当只有一块石头可选时,如果这块石头的重量不超过 j,那么我们可以将其放入其中一组,否则不放入。

  4. 最终结果: 最终的答案应该是在所有可能的总重量 j 中,找到最大的 j,使得 dp[n-1][j]truen 为石头的总数)。然后最小可能的剩余重量就是 sum - 2 * j

根据上述思路,可以实现出解题代码:

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for (int i = 0; i < stones.size(); i++) {sum += stones[i];}int n = stones.size();vector<vector<int>> dp(n, vector<int>(sum / 2 + 1, 0));// 初始化for (int i = 0; i <= sum / 2; i++) {if (stones[0] <= i) {dp[0][i] = stones[0];}}// 填写dp数组for (int i = 1; i < n; i++) {for (int j = 1; j <= sum / 2; j++) {if (stones[i] > j) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);}}}return sum - 2 * dp[n - 1][sum / 2];}
};

方法二:01背包一维数组

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for (int i = 0; i < stones.size(); i++) {sum += stones[i];}vector<int> dp(sum/2+1, 0);// 填写dp数组for (int i = 0; i < stones.size(); i++) {for (int j = sum/2; j >= stones[i]; j--) {  dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]);}        }return sum - 2 * dp[sum/2];}
};

Q:为什么 for (int j = sum/2; j >= stones[i]; j–)要倒序遍历?

A:我们从前往后遍历石头,同时从总重量的一半开始递减遍历,这是因为我们想在填写 dp[j] 时,基于之前的状态 dp[j-stones[i]] 进行更新。如果我们从小到大遍历 j,那么在填写 dp[j] 时,我们可能会使用当前石头的重量(stones[i]),而这就会导致重复使用同一块石头,与题意不符。

所以,倒序遍历 j 可以确保在填写 dp[j] 时,我们只会考虑之前的状态,而不会用到当前石头。这是为了避免在填写 dp[j] 时,使用当前石头导致重复计算的情况。

Q:为什么一定要先遍历石头重量这一行然后遍历重量那一列?

A:这是为了确保状态转移方程的正确性。让我们通过一个例子来理解。

假设我们有以下石头的重量:stones = [2, 7, 4]

我们想要使用动态规划找到一种分法,使得其中一组的总重量尽量接近总重量的一半。在此例中,总重量是 2 + 7 + 4 = 13,所以我们希望找到一种分法,使得其中一组的重量接近 13 / 2 = 6

现在,假设先遍历重量(j),再遍历石头(i)。在这种情况下,第一次遍历(j = sum/2,i从0到stones.size())后我们的动态规划状态数组如下所示:

stones = [2, 7, 4]
dp[i][j]:0   1   2   3   4   5   6      2:     0   0   0   0   0   0   4      7:     0   0   0   0   0   0   4      4:     0   0   0   0   0   0   4      

在这种遍历顺序下,最后一列一直到最后都不会再更新了,显然是一个错误的遍历顺序。

相关文章:

LeetCode1049. 最后一块石头的重量 II

1049. 最后一块石头的重量 II 文章目录 [1049. 最后一块石头的重量 II](https://leetcode.cn/problems/last-stone-weight-ii/)一、题目二、题解方法一&#xff1a;01背包二维数组算法思路具体实现 方法二&#xff1a;01背包一维数组 一、题目 有一堆石头&#xff0c;用整数数…...

universal robot 机械臂 官方基本教程

https://academy.universal-robots.cn/modules/e-Series-core-track/Chinese/module3/story_html5.html?courseId2166&languageChinese 教程1 控制箱内部 包含&#xff1a; 主机板&#xff0c;SD卡&#xff0c;和安全控制板 安全控制板负责所有控制信息&#xff0c;包括…...

网络常见安全漏洞

引言 随着互联网的迅猛发展&#xff0c;网络安全问题日益严重。在网络世界中&#xff0c;各种常见的安全漏洞给人们的通信和数据安全带来了巨大的威胁。本文将介绍一些常见的网络安全漏洞&#xff0c;并提供一些防范措施。 1. XSS&#xff08;跨站脚本攻击&#xff09; 跨站…...

【JS案例】JS实现图片放大镜功能

JS案例图片放大镜 &#x1f31f;效果展示 &#x1f31f;HTML结构 &#x1f31f;CSS样式 &#x1f31f;实现思路 &#x1f31f;具体实现 1.初始化数据图片 2.获取所需DOM元素 3.初始化页面 初始化缩略图 绑定事件 &#x1f31f;完整代码 &#x1f31f;写在最后 &…...

linux centos7 bash中字符串反向输出

给定一个字符串&#xff0c;如何反向(倒序)输出&#xff1f; 字符串反转的方法&#xff1a;a.对各个字符位置进行循环调换&#xff08;从原字符串左边取出放在新字符串的右边&#xff1b;从原字符串右边取出放在新字符串的左边&#xff09;。b.对各个字符由水平排列转为垂直排…...

c++:QT day1 认识与学习

...

git rebase和merge区别

一、概述 merge和rebase 标题上的两个命令&#xff1a;merge和rebase都是用来合并分支的。 这里不解释rebase命令&#xff0c;以及两个命令的原理&#xff0c;详细解释参考这里。 下面的内容主要说的是两者在实际操作中的区别。 1.1 什么是分支 分支就是便于多人在同一项目…...

Vue插槽实现商品列表-编辑渲染

商品列表 文章目录 商品列表核心步骤创建组件 1. MyTag组件详细步骤双击显示&#xff0c;自动聚焦失去焦点&#xff0c;隐藏输入框回显标签信息回车修修改内容&#xff0c;同时隐藏输入框 MyTable组件详细步骤1-动态的设置整个表格的数据 &#xff1a; props2-实现自定义结构-插…...

Vue开发之父子组件

创建父子组建&#xff0c;分三步。一是创建文件&#xff0c;二是引入组建&#xff0c;三是组件间通信。在components目录下新建sub文件夹&#xff0c;用于存放一下可以复用的子组件。比如新建一个SubCon.vue组件 <template><div class"first-app">{{ ms…...

fastadmin think-queue supervisor配置

起因是微信支付回调需要同时做发货处理&#xff0c;但是发货接口不能影响,需要队列进行异步处理1. 1.fastadmin 后台购买queue插件(基于think-queue消息队列) 2.代码 2.1 添加文件&#xff1a;application---->extra--->queue.php 内容&#xff1a;我这里用的数据库做…...

STM32 进不了main 函数

1. 我用的是STM32L151C8T6 的芯片&#xff0c;在github 上找了个别人的例程&#xff0c;拿来当模板改&#xff0c;由于他用的是HSE 外部晶振&#xff0c;我用的是内部晶振HSI&#xff0c;所以需要改系统时钟&#xff0c;改完后debug&#xff0c; 一直进不了main 函数&#xff0…...

不用循环数组,js+html实现贪吃蛇

功能描述&#xff1a;每走10步随机改变一个方方向&#xff0c;当键盘按下方向键 w,s,a,d时&#xff0c;使用键盘方向控制蛇的移动&#xff0c;蛇头每撞到一次自身时改变屏幕颜色&#xff0c;蛇头碰到边界时从另一边回来。 实现思路&#xff1a;用个30大小的数组存放每个结点&a…...

什么是线程安全和线程不安全?

线程安全(Thread Safety)和线程不安全(Thread Unsafety)是与并发编程相关的概念,特别是在多线程环境中使用共享资源时会涉及到这些概念。 线程安全: 当多个线程同时访问共享资源时,如果在没有额外的同步措施的情况下,这些线程仍然能够正确地执行并保持数据的一致性,那…...

VUE笔记(十)Echarts

一、Echarts简介 1、什么是echarts ECharts是一款基个基于 JavaScript 的开源可视化图表库 官网地址&#xff1a;Apache ECharts 国内镜像&#xff1a;ISQQW.COM x ECharts 文档&#xff08;国内同步镜像&#xff09; - 配置项 示例&#xff1a;echarts图表集 2、第一个E…...

FPGA原理与结构——时钟IP核原理学习

一、前言 在之前的文章中&#xff0c;我们介绍了FPGA的时钟结构 FPGA原理与结构——时钟资源https://blog.csdn.net/apple_53311083/article/details/132307564?spm1001.2014.3001.5502 在本文中我们将学习xilinx系列的FPGA所提供的时钟IP核&#xff0c;来帮助我们进一…...

创建python环境——Anaconda

在Windows中安装Anaconda和简单使用 一.Anaconda发行概述 Anaconda是一个可以便捷获取和管理包&#xff0c;同时对环境进行统一管理的发行版本&#xff0c;它包含了conda、 Python在内的超过180个科学包及其依赖项。 1.Anaconda发行版本具有以下特点&#xff1a; (1)包含了…...

使用Linux部署Kafka教程

目录 一、部署Zookeeper 1 拉取Zookeeper镜像 2 运行Zookeeper 二、部署Kafka 1 拉取Kafka镜像 2 运行Kafka 三、验证是否部署成功 1 进入到kafka容器中 2 创建topic 生产者 3 生产者发送消息 4 消费者消费消息 四、搭建kafka管理平台 五、SpringBoot整合Kafka 1…...

pyechart笔记:opts.AxisOpts

定制化图表的轴线&#xff08;x轴和y轴&#xff09;的样式和设置 0 不设置坐标轴 c1(Bar().add_xaxis([力量,智力,敏捷]).add_yaxis(全能骑士,# 系列名称&#xff0c;用于 tooltip 的显示&#xff0c;legend 的图例筛选。[429,321,296],#系列数据).add_yaxis(猴子,[352,236,4…...

深度思考rpc框架面经之五:rpc熔断限流、rpc复用连接机制

11 RPC框架如何实现限流和熔断 推荐文章&#xff1a;RPC实现原理之核心技术-限流熔断 11.1 为什么Dubbo要做服务的限流&#xff1f;(根本原因是服务端进行自我保护) 限流是一种常见的系统保护手段。在分布式系统和微服务架构中&#xff0c;一个接口的过度使用可能会导致资源…...

Go 数组

数组用于在单个变量中存储相同类型的多个值&#xff0c;而不是为每个值声明单独的变量。 声明数组 在Go中&#xff0c;有两种声明数组的方式&#xff1a; 使用var关键字&#xff1a; 语法 var array_name [length]datatype{values} // 这里定义了长度 或者 var array_n…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

uni-app学习笔记三十五--扩展组件的安装和使用

由于内置组件不能满足日常开发需要&#xff0c;uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件&#xff0c;需要安装才能使用。 一、安装扩展插件 安装方法&#xff1a; 1.访问uniapp官方文档组件部分&#xff1a;组件使用的入门教程 | uni-app官网 点击左侧…...