动态规划专练( 1049.最后一块石头的重量Ⅱ)
1049.最后一块石头的重量Ⅱ
有一堆石头,用整数数组 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
题解:
这个题居然是个01背包,这是我万万想不到的。
看解释,我们只要把这个数组分成最接近元素和一半的两堆,然后再减一下就可以得到碰撞后的最小值了是不是啊。
那不就是要求,数组中的某个集合最接近某个值的问题吗。可以转成01背包的思想,和416.分那个等和子集一样的思路。
代码如下:
package com.offer;/*** @author bwzfy* @create 2024/4/12**/
public class _1049最后一块石头的重量Ⅱ {public static void main(String[] args) {System.out.println(lastStoneWeightII(new int[]{31, 26, 33, 21, 40}));}public static int lastStoneWeightII(int[] stones) {int sum = 0;for (int i = 0; i < stones.length; i++) {sum += stones[i];}int target = sum / 2;// 目标找出数组中,的一组数据加起来的和最接近target,01背包问题int[][] dp = new int[stones.length][target + 1];for (int i = 1; i <= target; i++) {if (stones[0] <= i) {dp[0][i] = stones[0];}}for (int i = 1; i < stones.length; i++) {for (int j = 1; j <= target; j++) {// 能装入石头if (stones[i] <= j) {dp[i][j] = Math.max(dp[i - 1][j], stones[i] + dp[i - 1][j - stones[i]]);} else {dp[i][j] = dp[i - 1][j];}}}int heap1 = dp[stones.length - 1][target];int heap2 = sum - heap1;return Math.abs(heap1 - heap2);}}相关文章:
动态规划专练( 1049.最后一块石头的重量Ⅱ)
1049.最后一块石头的重量Ⅱ 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x < y。那么粉碎的可能结果如…...
2024年最佳WordPress插件
我喜欢的最佳WordPress插件(也是经验丰富的WordPress开发者强烈推荐的)。所有这些插件都是编码干净、超快且一流的。我还包括了对我不喜欢的插件的想法……只为了让你有进一步的了解。 目录 隐藏 1 古腾堡块: 2 内容: 3 缓存…...
Docker 安装 RocketMQ
目录 一、新建两个配置文件 1.1 创建docker-compose.yml文件 1.2 .新建broker.conf文件 二、运行 三、可视化界面 一、新建两个配置文件 1.1 创建docker-compose.yml文件 version: 3.5 services:rmqnamesrv:image: foxiswho/rocketmq:servercontainer_name: rmqnamesrvports…...
计算机网络——交换机和路由器
目录 前言 引言 交换机是用来做什么的? 与路由器有什么区别? 网关 子网掩码 网关、路由 前言 本博客是博主用于复习计算机网络的博客,如果疏忽出现错误,还望各位指正。 这篇博客是在B站掌芝士zzs这个UP主的视频的总结&am…...
Redis Pipelining 底层原理分析及实践
作者:vivo 互联网服务器团队-Wang Fei Redis是一种基于客户端-服务端模型以及请求/响应的TCP服务。在遇到批处理命令执行时,Redis提供了Pipelining(管道)来提升批处理性能。本文结合实践分析了Spring Boot框架下Redis的Lettuce客户端和Redisson客户端对P…...
milvus各组件的结构体分析
milvus各组件的结构体分析 各组件启动,需要构建各组件的结构体,一共8个。 runComponent(ctx, localMsg, wg, components.NewRootCoord, metrics.RegisterRootCoord) runComponent(ctx, localMsg, wg, components.NewProxy, metrics.RegisterProxy) run…...
vue2和vue3 全选
vue3 <template><input type"checkbox" v-model"selectAll" />全选<ul><li v-for"item in list" :key"item.id">{{ item.value }} <input type"checkbox" v-model"item.check" />…...
Java中的Set、List、Map的区别及主要实现类方法
Java中的Set、List、Map的区别 数组是大小固定的,并且同一个数组只能存放类型一样的数据(基本类型/引用类型),JAVA集合可以存储和操作数目不固定的一组数据。 所有的JAVA集合都位于 java.util包中! JAVA集合只能存放引…...
gitignore:常用说明
示例: Java HELP.md target/ !.mvn/wrapper/maven-wrapper.jar !**/src/main/** !**/src/test/**### IntelliJ IDEA.idea *.iws *.iml *.ipr### NetBeans/nbproject/private/ /nbbuild/ /dist/ /nbdist/ /.nb-gradle/ build/ logs/### VS Code.vscode/ 说明&#…...
HarmonyOS NEXT应用开发—在Native侧实现进度通知功能
介绍 本示例通过模拟下载场景介绍如何将Native的进度信息实时同步到ArkTS侧。 效果图预览 使用说明 点击“Start Download“按钮后,Native侧启动子线程模拟下载任务Native侧启动子线程模拟下载,并通过Arkts的回调函数将进度信息实时传递到Arkts侧 实…...
水利自动化控制系统平台介绍
水利自动化控制系统平台介绍 在当今社会,水资源的管理和保护日益成为全球关注的重要议题。随着科技的进步和信息化的发展,水利监测系统作为一种集成了现代信息技术、自动化控制技术以及环境监测技术的综合性平台,正在逐步改变传统的水利管理模…...
flask后端+网页前端:基于 socket.io 的双向通信和服务器部署
我想实现的效果是,我的服务器提供两个路由网址,网页A用于拍照、然后录音,把照片和录音传给服务器,服务器发射信号,通知另一个路由的网页B更新,把刚刚传来的照片和录音显示在网页上。 然后网页B用户根据这个…...
【Docker】解决 docker build 提示 `Wrong architecture ‘amd64‘`
解决 docker build 提示 Wrong architecture amd64 使用 securify2 的 docker 版本进行 sc 安全扫描 执行语句 RUN wget https://github.com/souffle-lang/souffle/releases/download/1.6.2/souffle_1.6.2-1_amd64.deb -O /tmp/souffle.deb &&\ gdebi --n /tmp/souff…...
机器学习_XGBoost模型_用C++推理示例Demo
1. 需求 将 python 训练好的 xgboost 模型, 使用C 进行加载并进行推理(预测) 2. 代码实现 #include <iostream> #include <fstream> #include <sstream> #include <vector> #include <string> #include <xgboost/c_api.h>const char *m…...
C语言 | Leetcode C语言题解之第21题合并两个有序链表
题目: 题解: /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {/…...
2024考研调剂须知
----------------------------------------------------------------------------------------------------- 考研复试科研背景提升班 教你快速深入了解掌握考研复试面试中的常见问题以及注意事项,系统的教你如何在短期内快速提升自己的专业知识水平和编程以及英语…...
PCIE协议版--M.2接口规范V1.0中文版1——电气规格篇
3.电气规范 3.1 Connectivity Socket 1 系统接口信号 表15适用于Socket 1-SD和Socket 1-DP输出版本。 3.1.1.补充NFC信号 当一个SIM设备被用作安全元素时,NFC解决方案可以与表16中列出的附加信号相结合。 3.1.2.电源和地 PCI Express M.2 Socket 1使用一个3.3 V…...
【JVM】JVM堆占用情况分析(频繁创建的对象、内存泄露等问题)、jmap+jhat、jvisualvm工具使用
文章目录 一. 相关命令1. 查看进程堆内存整体使用情况:OOM的可能2. 统计类的对象数量以及内存占用:定位内存泄漏 二. 分析内存占用1. 使用 jhat 排查对象堆占用情况1.1. 排查步骤1.2. 具体分析例子a. 分析频繁创建对象导致的OOM 1.3. OQL查看某一个对象的…...
【蓝桥杯每日一题】4.11 更小的数(不用区间DP)
题目来源: 蓝桥杯 2023 省 A]更小的数 - 洛谷 这题只需要用到双指针就OK~ 思路1: 翻转数组的子数组,然后进行比较大小将翻转后的数组存储在字符串 k k k中,然后将字符串 k k k与字符串 a a a进行逐一元素比较(因为…...
【线段树】2276. 统计区间中的整数数目
算法可以发掘本质,如: 一,若干师傅和徒弟互有好感,有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。 二,有无限多1X2和2X1的骨牌,某个棋盘若干格子坏了,如何在没有坏…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...
使用ch340继电器完成随机断电测试
前言 如图所示是市面上常见的OTA压测继电器,通过ch340串口模块完成对继电器的分路控制,这里我编写了一个脚本方便对4路继电器的控制,可以设置开启时间,关闭时间,复位等功能 软件界面 在设备管理器查看串口号后&…...
GC1808:高性能音频ADC的卓越之选
在音频处理领域,高质量的音频模数转换器(ADC)是实现精准音频数字化的关键。GC1808,一款96kHz、24bit立体声音频ADC,以其卓越的性能和高性价比脱颖而出,成为众多音频设备制造商的理想选择。 GC1808集成了64倍…...
