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

153、【动态规划】leetcode ——416. 分割等和子集:滚动数组(C++版本)

题目描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
原题链接:1049. 最后一块石头的重量 II

解题思路

本题要找的是最小重量,我们可以将石头划分成两个集合,当两个集合的重量越接近时,相减后,可达到的装量就会是最小,此时本题的思路其实就类似于 416. 分割等和子集(动态规划:二维数组+滚动数组) 。

首先,对所有石头的总重量求和,然后设置一个变量target表示总重量之和的二分之一,使用动态规划的方式,划分出一个集合之和dp[target],然后用总重量之和减去dp[target],就得到对石头的另一个集合划分之和。二者相减,就是最小重量。

  • 动态规划五步曲:

(1)dp[j]含义: 在背包容量为j的条件下,可装入的最大物品重量总和。

(2)递推公式: dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sumNums = 0;for(int i = 0; i < stones.size(); i++)       sumNums += stones[i];int target = sumNums / 2;int dp[1501] = {0};int n = stones.size();for(int i = 0; i < n; i++) {for(int j = target; j >= stones[i]; j--) {dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return abs(sumNums - dp[target] - dp[target]);}
};

参考文章:1049. 最后一块石头的重量 II

相关文章:

153、【动态规划】leetcode ——416. 分割等和子集:滚动数组(C++版本)

题目描述 原题链接&#xff1a;1049. 最后一块石头的重量 II 解题思路 本题要找的是最小重量&#xff0c;我们可以将石头划分成两个集合&#xff0c;当两个集合的重量越接近时&#xff0c;相减后&#xff0c;可达到的装量就会是最小&#xff0c;此时本题的思路其实就类似于 4…...

linux head命令(head指令)(获取文件或管道输出结果前n行,默认前10行)与sed命令区别

head命令是一个在Linux系统中常用的命令&#xff0c;用于读取文件的前几行&#xff08;默认读取前10行&#xff09; 文章目录使用方法读取文件的前10行&#xff1a;head filename读取文件的前n行&#xff1a;head -n行数 filename读取多个文件的前几行&#xff1a;head -n 行数…...

Mysql数据库09——分组聚合函数

类似pandas里面的groupby函数&#xff0c;SQL里面的GROUP BY子句也是可以达到分组聚合的效果。 常用的聚合函数有COUNT(),SUM(),AVG(),MAX(),MIN()&#xff0c;其用法看名字都看的出来&#xff0c;下面一一介绍 聚合函数 COUNT()计数 统计student表中计科系学生的人数。 SE…...

第43章 菜单实体及其约束规则的定义实现

1 Core.Domain.Security.Menu namespace Core.Domain.Security { /// <summary> /// 【菜单--类】 /// <remarks> /// 摘要&#xff1a; /// 通过该实体类及其属性成员&#xff0c;用于实现当前程序【Core】.【领域】.【安全】.【菜单】实体与“[ShopDemo].[…...

OpenAI最重要的模型【CLIP】

最近的 AI 突破 DALLE和 Stable Diffusion有什么共同点&#xff1f; 它们都使用 CLIP 架构的组件。 因此&#xff0c;如果你想掌握这些模型是如何工作的&#xff0c;了解 CLIP 是先决条件。 此外&#xff0c;CLIP 已被用于在 Unsplash 上索引照片。 但是 CLIP 做了什么&…...

分享112个JS菜单导航,总有一款适合您

分享112个JS菜单导航&#xff0c;总有一款适合您 112个JS菜单导航下载链接&#xff1a;https://pan.baidu.com/s/1Dm73d2snbu15hZErJjTXxg?pwdfz1c 提取码&#xff1a;fz1c Python采集代码下载链接&#xff1a;https://wwgn.lanzoul.com/iKGwb0kye3wj base_url "h…...

MySQL 3:MySQL数据库基本操作 DQL

数据库管理系统的一个重要功能是数据查询。数据查询不应简单地返回数据库中存储的数据&#xff0c;还应根据需要对数据进行过滤&#xff0c;确定数据的显示格式。MySQL 提供了强大而灵活的语句来实现这些操作。MySQL数据库使用select语句查询数据。 select [all|distinct]<…...

sql语句的优化

sql优化 优化数据访问 查询性能低下最基本的原因是访问的数据太多&#xff0c;大部分性能低下的查询都可以通过减少访问的数据量来优化所以关于低效的查询&#xff0c;需要确认是否检索了大量不需要的数据&#xff0c;以及mysql服务器层是否在分析大量不需要的数据 因为有些查…...

Shell脚本之——自动安装JDK

目录 1.修改主机名 2.创建文件&#xff0c;单独存放Shell脚本 3.编写Shell脚本 4.Shell脚本命令简介 (1)文件头 (2)打印命令 (3)设置全局变量 (4)条件判断 (5)解压 (6)文件重命名 (7)在/etc/profile指定行插入 5.完整脚本内容 6.重启环境变量 7.判断java是否配置…...

大数据---Hadoop安装Hadoop简易版

编写自动安装Hadoop的shell脚本 完整流程: 大数据—Hadoop安装教程&#xff08;二&#xff09; 文章目录编写自动安装Hadoop的shell脚本上传压缩包编写shell脚本vim hadoopautoinstall.sh运行上传压缩包 在opt目录下创建连个目录install和soft 将压缩包上传到install目录下 …...

Spring框架中使用到的设计模式以及对应的类(方法)

模板方法--->postProcessBeanFactory&#xff0c;onFresh、initPropertySource装饰器模式--->BeanWrapper委托者模式--->BeanDefinitionParseDelegate策略模式--->ClassPathXmlApplicationContext、FileSystemApplicationContext、XMLBeanDefinitionReader、Proper…...

类和类的定义

6.2 类和类的定义 面向对象最重要的概念就是类&#xff08;Class&#xff09;和实例&#xff08;Instance&#xff09;&#xff0c;必须牢记类是抽象的模板&#xff0c;比如学生类&#xff0c;而实例是根据类创建出来的一个个具体的对象&#xff0c;每个对象都拥有相同的方法&…...

丝绸之路——NFT 系列来袭!

丝绸之路的经历讲述了汉朝时代的一个重要历史事件。该系列中的 NFT 带有中国这段黄金时代令人愉悦的视觉元素&#xff0c;使其成为值得收藏的物品。 NFT 系列介绍 敦煌女神像01&#xff08;左&#xff09;&#xff1b;汉代士兵&#xff08;中&#xff09;&#xff1b;敦煌女神像…...

配置CMAKE编译环境:VSCODE + MinGW

一. MinGW安装 MinGW(Minimalist GNU For Windows)是个精简的Windows平台C/C、ADA及Fortran编译器&#xff0c;相比Cygwin而言&#xff0c;体积要小很多&#xff0c;使用较为方便。 MinGW最大的特点就是编译出来的可执行文件能够独立在Windows上运行。 MinGW的组成&#xff…...

六、mybatis与spring的整合

Spring整合Mybaits的步骤 引入依赖 在Spring整合Mybaits的时候需要引入一个中间依赖包mybatis-spring <dependency><groupId>org.mybatis</groupId><artifactId>mybatis</artifactId><version>3.5.5</version> </dependency&g…...

JavaWeb--JDBC

JDBC1 JDBC概述1.1 JDBC概念1.2 JDBC本质1.3 JDBC好处2 JDBC快速入门2.1 编写代码步骤2.2 具体操作3 JDBC API详解3.1 DriverManager3.2 Connection3.2.1 获取执行对象3.2.2 事务管理3.3 Statement3.3.1 概述3.3.2 代码实现3.4 ResultSet3.4.1 概述3.4.2 代码实现3.5 案例3.6 P…...

大数据框架之Hadoop:入门(四)Hadoop运行模式

Hadoop运行模式包括&#xff1a;本地模式、伪分布式模式以及完全分布式模式。 Hadoop官方网站&#xff1a;http://hadoop.apache.org/ 4.1本地运行模式 4.1.1官方Grep案例 1.创建在hadoop文件夹下面创建一个input文件夹 [roothdp101 hadoop]# mkdir input2.将Hadoop的xml配…...

《爆肝整理》保姆级系列教程python接口自动化(十一)--发送post【data】(详解

简介  前面登录的是传 json 参数&#xff0c;由于其登录机制的改变没办法演示&#xff0c;然而在工作中有些登录不是传 json 的&#xff0c;如 jenkins 的登录&#xff0c;这里小编就以jenkins 登录为案例&#xff0c;传 data 参数&#xff0c;给各位童鞋详细演练一下。 一、…...

【微服务】Nacos注册中心

&#x1f6a9;本文已收录至专栏&#xff1a;微服务探索之旅 &#x1f44d;希望您能有所收获 &#x1f44d;Nacos和Eureka一样也可以充当服务的注册中心&#xff0c;让我们一起看看有何区别&#xff1f; 点击跳转&#x1f449;【微服务】Eureka注册中心 &#x1f44d;Nacos除了可…...

跟开发打了半个月后,我终于get报bug的正确姿势了

在测试人员提需求的时候&#xff0c;大家经常会看到&#xff0c;测试员和开发一言不合就上BUG。然后开发一下就炸了&#xff0c;屡试不爽&#xff0c;招招致命。 曾经看到有个段子这么写道&#xff1a; 不要对程序员说&#xff0c;你的代码有BUG。他的第一反应是&#xff1a;…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

深度解析云存储:概念、架构与应用实践

在数据爆炸式增长的时代&#xff0c;传统本地存储因容量限制、管理复杂等问题&#xff0c;已难以满足企业和个人的需求。云存储凭借灵活扩展、便捷访问等特性&#xff0c;成为数据存储领域的主流解决方案。从个人照片备份到企业核心数据管理&#xff0c;云存储正重塑数据存储与…...

RabbitMQ 各类交换机

为什么要用交换机&#xff1f; 交换机用来路由消息。如果直发队列&#xff0c;这个消息就被处理消失了&#xff0c;那别的队列也需要这个消息怎么办&#xff1f;那就要用到交换机 交换机类型 1&#xff0c;fanout&#xff1a;广播 特点 广播所有消息​​&#xff1a;将消息…...