day-42 代码随想录算法训练营 动态规划 part 04
416.分割等和子集
分析:需要总和能分成两半,并且有子集能装满一半
思路:
- 1.dp存储:容量为j时装入的最大数值和dp[j]
- 2.dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
- 3.全部初始化为0
- 4.遍历顺序:外层遍历元素,内层遍历重量
2: dp[j]就是上一轮,还没有遍历到当前nums[i]时的最大和,所以相当于不装nums[j]
dp[j-nums[i]],为啥要 j-nums[i] 的容量呢,因为要满足容量为 j ,所以装之前要找到 容量为 j-nums[i] 装入的最大和,然后装入当前 nums[i] ,总容量才为 j (要是直接dp[j]+nums[i],就会导致容量超过 j 。
1049.最后一块石头的重量 ||
分析:石头相撞,剩余多出的部分,相当于能分成的最近似的两堆石头
思路:
- 1.dp存储:先将stones总和求出,求出一半,dp存储的是容量为 j 装的最大重量
- 2.dp[j]=max(dp[j],dp[j-stones[i]]-stones[i]);
- 3.初始化:全部初始化为0
- 4.遍历顺序:外层遍历石头,内层遍历容量
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int total=0;for(auto it:stones) total+=it;int target=total/2;vector<int>dp(total+1,0);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 total-dp[target]*2;//装入的最大重量跟剩下的相抵消,剩余的就是最后一块石头}
};
494.目标和(一刷坐牢)
分析:正数总和-负数总和=目标和 -> 正数总和=(目标和+总和)/2
思路:
- 1.dp存储:当和(容量)为 j 时,有dp [ j ] 中装法 。
- 2.dp[ j ] =dp [ j - nums [ i ] ] ;
- 3.初始化:dp [ 0 ] =1 ;
- 4.遍历顺序:外层遍历数组,内层遍历容量
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum=0;for(int it:nums) sum+=it;if(abs(target)>sum) return 0;//当总和小于目标和的绝对值时,不可能有情况(因为target被抵消过)//add表示正数的总和,sub表示负数的总和//add-(sum-add)=target//add=(target+sum)/2if((target+sum)%2==1) return 0;int bagSize=(target+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.一和零(坐牢)
分析:这一题还是背包,不同是有物品有两个维度: 0 和 1
思路:
- 1.dp存储:当 0 容量为 i ,1 容量为 j 时,最多能装dp [ i ][ j ] 个字符串
- 2.dp [ j ]:dp [ i ] [ j ] =max( dp [ i ] [ j ] , dp [ i - zeroNum ][ j - oneNum ] + 1 ]
- 3.初始化:全部初始化为0
- 4.遍历顺序:外层遍历字符串数组,内层进行两个循环遍历
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>>dp(m+1,vector<int>(n+1,0));for(string str:strs){int oneNum=0,zeroNum=0;for(char c:str){if(c=='0') zeroNum++;else oneNum++;}for(int i=m;i>=zeroNum;i--){for(int j=n;j>=oneNum;j--){dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);}}}return dp[m][n];}
};
相关文章:
day-42 代码随想录算法训练营 动态规划 part 04
416.分割等和子集 分析:需要总和能分成两半,并且有子集能装满一半 思路: 1.dp存储:容量为j时装入的最大数值和dp[j]2.dp[j]max(dp[j],dp[j-nums[i]]nums[i]) 3.全部初始化为04.遍历顺序:外层遍历元素,内…...
Swift 周报 第三十六期
文章目录 前言新闻和社区消息称苹果公司和印度财政部官员磋商,扩大在印度的制造产能iPhone 15 Pro 机型新增泰坦灰iPhone 15 全系配 USB-C 苹果拒绝接口和安卓互通 提案正在审查的提案 Swift论坛推荐博文话题讨论关于我们 前言 本期是 Swift 编辑组整理周报的第三十…...
手写Mybatis:第19章-二级缓存
文章目录 一、目标:二级缓存二、设计:二级缓存三、实现:二级缓存3.1 工程结构3.2 二级缓存类图3.3 二级缓存队列3.3.1 FIFI缓存策略3.3.2 事务缓存3.3.3 事务管理3.3.4 修改一级缓存 3.4 缓存执行器3.4.1 执行器接口3.4.2 执行器抽象基类3.4.…...
Alibaba Canal 使用记录
项目中使用 canal 来同步数据到 Elasticsearch, 遇到很多问题,做一下记录: 版本问题: 1. 解析binlog出错 ,表现为 limit excceed:xx 目前使用 mariadb 10.9.7/10.10.6 canal 1.1.6 hotfix ,在这个版本组…...
GIT实战篇,教你如何使用GIT可视化工具
系列文章目录 手把手教你安装Git,萌新迈向专业的必备一步 GIT命令只会抄却不理解?看完原理才能事半功倍! 快速上手GIT命令,现学也能登堂入室 GIT实战篇,教你如何使用GIT可视化工具 系列文章目录一、GIT有哪些常用工具…...
lv3 嵌入式开发-4 linux shell命令(文件搜索、文件处理、压缩)
目录 1 查看文件相关命令 1.1 常用命令 1.2 硬链接和软链接 2 文件搜索相关命令 2.1 查找文件命令 2.2 查找文件内容命令 2.3 其他相关命令 3 文件处理相关命令 3.1 cut 3.2 sed 过滤 3.3 awk 匹配 4 解压缩相关命令 4.1 解压缩文件的意义 4.2 解压缩相关命令 1 …...
SpringBoot2.0集成WebSocket,多客户端
适用于单客户端,一个账号登陆一个客户端,登陆多个客户端会报错 The remote endpoint was in state [TEXT_FULL_WRITING] 这是因为此时的session是不同的,只能锁住一个session,解决此问题的方法把全局静态对象锁住,因…...
华为OD机试 - 等和子数组最小和 - 深度优先搜索(Java 2022 Q4 100分)
目录 专栏导读一、题目描述二、输入描述三、输出描述四、解题思路五、Java算法源码六、效果展示1、输入2、输出 华为OD机试 2023B卷题库疯狂收录中,刷题点这里 专栏导读 本专栏收录于《华为OD机试(JAVA)真题(A卷B卷)》…...
浏览器会因为什么样的脚本而崩溃
浏览器可能因为以下几种情况而崩溃: 无限循环:如果JavaScript脚本包含一个无限循环,浏览器将无法停止脚本的执行,导致浏览器不响应甚至崩溃。例如,以下代码会导致无限循环: while (true) {// 无限循环 } 内…...
生成与调用C++动态链接库(so文件)
文章目录 前言生成C动态链接库步骤1:编写C源码步骤2:生成共享库步骤3:验证生成的SO文件 调用C动态链接库步骤1:修改原来makefile步骤2:编译调用程序步骤3:运行调用程序 总结 前言 动态链接库是代码重用和模…...
韶音的耳机怎么样,韶音骨传导耳机值得入手吗
韶音关于骨传导耳机的产品在质量方面还是有着不错的表现,其最具代表性的骨传导耳机就是韶音OpenRun Pro,在国产骨传导耳机中是具备了一定的知名度,有着自主研发的声学技术。 最突出的点就在于颜色上多样化,有着经典的黑色…...
STM32G030F6 (SOP-20)Cortex ® -M0+, 32KB Flash, 8KB RAM, 17 GPIOs
淘宝淘了一批 STM32G030F6P6 SOP20.先备注一下, 还没想到能干嘛用. 手上的 STM32F103C6T6还剩一些. 一堆 “淘宝原厂STM32F103C8T6”, 还烫着手. 理解信息: ( 逐步补充 ) System Clock GPIOs GPIOs 17 PA[7:0] : 8bits USART Timer ADC I2…...
常用的字符集和字符编码
基础概念 字符 字符是各种文字和符号的总称,包括各国家文字、标点符号、图形符号、数字等 字符集 一个操作系统支持的字符的集合。 字符编码和解码 将每个字符都设置一个唯一编号,编码就是将字符集中的字符编号以一定形式转化为字节存储下来,…...
容器技术简介
引言 随着云计算、大数据、人工智能等技术的不断发展,容器技术作为一种新兴的虚拟化技术,正逐渐成为IT领域的热点。容器技术可以帮助开发者更好地管理、部署和扩展应用程序,提高开发效率和应用程序的可靠性。本文将深入探讨容器技术的概念、…...
数据分享|R语言用lme4多层次(混合效应)广义线性模型(GLM),逻辑回归分析教育留级调查数据...
全文链接:http://tecdat.cn/?p22813 本教程为读者提供了使用频率学派的广义线性模型(GLM)的基本介绍。具体来说,本教程重点介绍逻辑回归在二元结果和计数/比例结果情况下的使用,以及模型评估的方法(点击文末“阅读原文…...
macos 不支持svn安装
macos 10.13可能不支持svn命令,所以要安装 xcode-select --install 弹窗在线安装失败的话只能手动下载安装 打开:Sign In - Apple 搜索Command Line Tools (macOS 10.13) 下载9.4.1版本直接安装后即可...
如何通过实际操作来加深对Linux命令和概念的理解?
作为一个新手,你一定不要被Linux那堆命令吓到。其实,它们就像你的“超能力”,只要你掌握它们,你就能成为Linux世界的超级英雄! 首先,我们要了解的是,Linux命令其实就像你的“魔法咒语”&#x…...
【开发语言】C语言与Python的互操作详解
博主未授权任何人或组织机构转载博主任何原创文章,感谢各位对原创的支持! 博主链接 本人就职于国际知名终端厂商,负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作,目前牵头6G算力网络技术标准研究。 博客…...
华为配置聚合vlan(Super vlan--Sub vlan)
聚合vlan,Aggregation vlan,也称Super vlan,可以实现用Sub vlan二层隔离广播域,但又将这些Sub vlan聚合使用同一IP子网和网关的情况。 这样,多个Sub-VLAN共享一个网关地址,节约了子网号、子网定向广播地址、…...
CentOS7安装时直接跳过了安装信息摘要页面的解决方法
最近在配置Hadoop虚拟机的时候,创建的centos7虚拟机在安装信息摘要时直接自动跳过,直接跳到设置用户名和密码,在重复多次的重新删除安装后发现了问题所在: 在进行到选择操作系统来源时,注意是否出现“该操作系统将使用…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
Xela矩阵三轴触觉传感器的工作原理解析与应用场景
Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知,帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量,能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度,还为机器人、医疗设备和制造业的智…...
C# winform教程(二)----checkbox
一、作用 提供一个用户选择或者不选的状态,这是一个可以多选的控件。 二、属性 其实功能大差不差,除了特殊的几个外,与button基本相同,所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...
高分辨率图像合成归一化流扩展
大家读完觉得有帮助记得关注和点赞!!! 1 摘要 我们提出了STARFlow,一种基于归一化流的可扩展生成模型,它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流(TARFlow&am…...
