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虚拟机在安装信息摘要时直接自动跳过,直接跳到设置用户名和密码,在重复多次的重新删除安装后发现了问题所在: 在进行到选择操作系统来源时,注意是否出现“该操作系统将使用…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
