代码随想录算法训练营第四十三天|动态规划|1049. 最后一块石头的重量 II、494. 目标和、474.一和零
1049. 最后一块石头的重量 II
文章
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:
如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。
示例:
输入:[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],这就是最优值。
提示:
1 <= stones.length <= 30
1 <= stones[i] <= 1000
和416. 分割等和子集 (opens new window)非常像了,尽可能平均分。
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {vector<int> dp(15001, 0);int sum = 0;for (int i = 0; i < stones.size(); i++) sum += stones[i];int target = sum / 2;for (int i = 0; i < stones.size(); i++) { // 遍历物品for (int j = target; j >= stones[i]; j--) { // 遍历背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[target] - dp[target];}
};
494. 目标和
文章
给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例:
输入:nums: [1, 1, 1, 1, 1], S: 3
输出:5
解释:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
提示:
数组非空,且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。
left + right = sum,而sum是固定的。right = sum - left
公式来了, left - (sum - left) = target 推导出 left = (target + sum)/2 。
所有元素凑成left有多少种方法 组合问题
dp[i][j] dp1-i凑成j的方法个数
dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j]
一维:dp[j]=dp[j-nums[i]+dp[j] 注意从后往前
注意这种情况: bagSize = (S + sum) / 2 小于0 此时 没有结果。
class Solution {
public:int findTargetSumWays(vector<int>& nums, int S) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(S) > sum) return 0; // 此时没有方案if ((S + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (S + sum) / 2;vector<int> dp(bagSize + 1, 0);dp[0] = 1;for (int i = 0; i < nums.size(); i++) {for (int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
};
474.一和零
文章讲解
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小,该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。
示例 1:
输入:strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出:4
解释:最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ,因此答案是 4 。 其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。
示例 2:
输入:strs = [“10”, “0”, “1”], m = 1, n = 1
输出:2
解释:最大的子集是 {“0”, “1”} ,所以答案是 2 。
提示:
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 ‘0’ 和 ‘1’ 组成
1 <= m, n <= 100
题目的关键是将0和1拆解开
dp[i] [jm] [jn]=max( dp[i-1] [jm-nums0[i]] [jn-nums1[i]] +1 , dp[i-1] [jm] [jn]
初始化:0
从后往前
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(auto str:strs){int num1=0;int num0=0;for(auto c :str){if (c == '0') num0++;else num1++;}for(int i=m;i>=num0;i--){for(int j=n;j>=num1;j--){dp[i][j]=max(dp[i][j],dp[i-num0][j-num1]+1);}}}return dp[m][n];}
};
相关文章:
代码随想录算法训练营第四十三天|动态规划|1049. 最后一块石头的重量 II、494. 目标和、474.一和零
1049. 最后一块石头的重量 II 文章 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x < y。那么粉碎的可能结果如下: 如果 x y&a…...
vue3+elementPlus:el-table-column表格列动态设置单元格颜色
:cell-style属性 //html<el-tableempty-text"暂无数据":data"datalist.table":max-height"height"row-key"id"border:cell-style"cellStyle"> <el-table>//js //动态设置单元格颜色 const cellStyle ({ row, c…...
python和shell脚本,每隔五分钟将远端服务器中的文件夹数据下载到跳板机
python脚本 import subprocess import datetime import timedef run_scp_command(source_path, target_path):command [scp -r , source_path, target_path]try:subprocess.run(command, checkTrue)print("File transferred successfully!")except subprocess.Call…...
Websocket在Asp.net webApi(.net framework)上的应用
之前在写看板部分的web api的时候,都是通过Ajax在规定时间内轮询调用web api,这样简单省事,但是当看板多了(并发量上来)以后,比较消耗服务器的性能,所以最近研究了websocket,希望使用…...
App前端开发跨平台框架比较:React Native、Flutter、Xamarin等
引言 移动应用开发领域的跨平台框架正在不断演进,为开发者提供更多选择。在本文中,我们将比较几个流行的跨平台框架:React Native、Flutter和Xamarin等。讨论它们的优缺点、适用场景以及开发体验。 第一部分 React Native: 优缺点、适用场景…...
VR数字展厅在企业中应用的优势有哪些?
随着VR全景技术的成熟,VR数字展厅逐渐成为了企业展示形象和产品的重要手段之一。VR企业数字展厅是一种通过VR技术、3D建模技术展示企业形象和产品的创新方式,将企业线下的展厅搬到线上,为企业品牌形象带来了很多优势。 VR数字展厅在企业中应用…...
【数据库】索引 视图 触发器 分页查询
目录 1、索引 2、视图 3、触发器 4、分页查询⚠️ 1、索引 提升查询效率、当数据量小的时候,索引看不出来效果,当数据量很大的时候,索引会显著提高查询速度 当给表添加索引之后,新插入一条数据,就会让索引进行重新…...
*地宫取宝c++
题目 输入样例1: 2 2 2 1 2 2 1输出样例1: 2输入样例2: 2 3 2 1 2 3 2 1 5输出样例2: 14 思路 题目说从入口开始,只能向右或向下行走到达右下角,类似“摘花生”这道题的模型。题目又说只有当格子里的宝…...
同态滤波算法详解
同态滤波是一种用于增强图像的方法,特别适用于去除图像中的照明不均和阴影。该算法基于照射反射模型,将图像分解为两个分量:照射分量(illumination component)和反射分量(reflection component)…...
财务管理系统报账和挂账分别什么区别!报销又是什么【第三期】
前言 已经写了两期 财务管理系统之saas多租户架构是什么以及分库分表以及如何选择分布式事务方案 【程序员聊业务】财务管理系统之模块分类 报账和挂账概念 报账是指企业或个人因业务需要而发生的各项费用支出,在支付后,需要将相关的票据、凭证等提交…...
最少刷题数
最少刷题数 题目分析 对于每一名同学计算还需要再刷多少题才能保证刷题数比他多的人数不超过刷题数比他少的学生人数。我们可以考虑统计每一个分数的前缀和数组,sum[i]表示当前学生中,刷题数小于等于i的人数。那么对于学生i的刷题数a[i],su…...
Python刘诗诗
写在前面 刘诗诗在电视剧《一念关山》中饰演了女主角任如意,这是一个极具魅力的女性角色,她既是一位有着高超武艺和智慧的女侠士,也曾经是安国朱衣卫前左使,身怀绝技且性格坚韧不屈。剧中,任如意因不满于朱衣卫的暴行…...
探索ChatGPT在软件架构师工作中的应用
随着人工智能技术的不断发展,自然语言处理模型如OpenAI的ChatGPT已经成为了解决各种实际问题的强大工具之一。在软件架构师这个领域,ChatGPT也有着广泛的应用。本文将探讨软件架构师如何有效地利用ChatGPT来解决问题和提高工作效率。 ChatGPT简介 Chat…...
pytest--allure报告中添加用例详情
前言 前面介绍了如何生成allure的报告,看着allure的页面非常好看,但是感觉少了一些内容,allure还可以增加一些用例详情内容,这样让我们的报告看着更加绚丽。 allure增加用例详情 我们可以在报告测试套件中增加用例详情内容。 …...
【深度学习笔记】9_5 多尺度目标检测
注:本文为《动手学深度学习》开源内容,部分标注了个人理解,仅为个人学习记录,无抄袭搬运意图 9.5 多尺度目标检测 在9.4节(锚框)中,我们在实验中以输入图像的每个像素为中心生成多个锚框。这些…...
Linux--vim
一.什么是vim Vim(Vi IMproved)是一种文本编辑器,通常在Linux和其他类Unix操作系统中使用。它是Vi编辑器的增强版本,提供了更多的功能和定制选项。Vim具有强大的文本编辑和编程功能,支持语法高亮、代码折叠、宏录制、…...
FreeRTOS操作系统学习——中断管理
中断管理介绍 嵌入式实时系统需要对整个系统环境产生的事件作出反应。这些事件对处理时间和响应时间都有不同的要求。事件通常采用中断方式检测,中断服务例程(ISR)中的处理量应当越短越好。ISR是在内核中被调用的, ISR执行过程中,用户的任务…...
DHCP中继实验(思科)
华为设备参考:DHCP中继实验(华为) 一,技术简介 DHCP中继,可以实现在不同子网和物理网段之间处理和转发DHCP信息的功能。如果DHCP客户机与DHCP服务器在同一个物理网段,则客户机可以正确地获得动态分配的IP…...
基于SpringBoot的“心灵治愈交流平台”的设计与实现(源码+数据库+文档+PPT)
基于SpringBoot的“心灵治愈交流平台”的设计与实现(源码数据库文档PPT) 开发语言:Java 数据库:MySQL 技术:SpringBoot 工具:IDEA/Ecilpse、Navicat、Maven 系统展示 系统功能界面图 登录、用户注册界面图 心灵专…...
【SpringBoot】自定义工具类实现Excel数据新建表存入MySQL数据库
🏡浩泽学编程:个人主页 🔥 推荐专栏:《深入浅出SpringBoot》《java对AI的调用开发》 《RabbitMQ》《Spring》《SpringMVC》《项目实战》 🛸学无止境,不骄不躁,知行合一 文章目录 …...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
