力扣474-一和零(Java详细题解)
题目链接:474. 一和零 - 力扣(LeetCode)
前情提要:
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
最近刚学完01背包,所以现在的题解都是以01背包问题为基础再来写的。
如果大家不懂01背包的话,建议可以去学一学,01背包问题可以说是背包问题的基础。
如果大家感兴趣,我后期可以出一篇专门讲解01背包问题。
dp五部曲。
1.确定dp数组和i下标的含义。
2.确定递推公式。
3.dp初始化。
4.确定dp的遍历顺序。
5.如果没有ac打印dp数组 利于debug。
每一个dp题目如果都用这五步分析清楚,那么这道题就能解出来了。
题目思路:
本题要求的是m个0n个1时子集中的最大长度。
其实这m个0n个1就是一种容器,我们要将该容器装满,求得子集的最大长度即可。
那么可以将这种容器抽象为背包,只不过这个背包是二维的,最大容量为m个0,n个1。
那么问题可以转化为将这个背包装满,求物品的数量。
接下来我们用动规五部曲来系统分析一下。
1.确定dp数组和i下标的含义。
我们这个背包是二维的,所以我们的dp数组也得是二维的。
dp[i] [j]指有i个0m个1时最大能装的物品数量。
2.确定递推公式。
首先我们来看看纯01背包问题的递推公式。
dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]);
那么本题的递推公式其实和01背包递推公式相似。
每个物品只有选和不选俩种状态。
不选的话就是dp[i] [j]因为没有选该物品,所以背包容量不变。
选的话就是dp[i - x] [j - y] + 1;其实x表示的是当前物品0的数量,y表示当前物品1的数量。
因为选的话,就得求出加入当前物品之前的背包容量能装入的最大物品数量,再加上该物品。也就是 + 1;
所以我们的递推公式就是 dp[i] [j] = Math.max(dp[i] [j],dp [i - x] [j - y] + 1);
3.dp初始化。
dp[0] [0]指的就是当背包中有0个0和0个1时能装入的物品数量,所以dp[0] [0] = 0;
其他的非0下标可以通过dp数组推出来,所以其他的我们就不初始化,没有意义。
4.确定dp的遍历顺序。
该题与01背包的遍历顺序相同,物品从前往后遍历,背包容量从后往前遍历上为了保证每个物品只放入了一次。
5.如果没有ac打印dp数组 利于debug。
如果没有出现差错,我们就可以不用打印,因为我是写题解,所以我就不添加核心代码以外的代码,不然代码显的有些冗余。
举个例子。

最终代码:
class Solution {public int findMaxForm(String[] strs, int m, int n) {// 本题核心思路就是把这个背包装满,最多能装多少物品。//同时本题背包具有俩个维度。//递推公式 dp[i][j]是指在i个0j个1下能装满的物品数量。//那么每个物品也只有选和不选,该物品不选就是dp[i][j]//选的话就是dp[i - x][j - y] + 1,选择该物品的话要将装入前能装的最多物品加1,也就是加上这个物品//本题是把每个子集当做一个物品//确定dp数组int dp[][] = new int[m + 1][n + 1];//初始化dp数组dp[0][0] = 0;//遍历物品for (String s : strs) {int x = 0, y = 0;//统计每个物品的01数量for (int v = 0;v < s.length();v ++) {if (s.charAt(v) == '0') {x++;} else {y++;}}//遍历背包//由于背包是俩个维度所以俩个要从后往前遍历 确保物品只放入了一次for (int i = m; i >= x; i--) {for (int j = n; j >= y; j--) {//递推公式dp[i][j] = Math.max(dp[i][j], dp[i - x][j - y] + 1);}}}return dp[m][n];}
}
这一篇博客就到这了,如果你有什么疑问和想法可以打在评论区,或者私信我。
我很乐意为你解答。那么我们下篇再见!
相关文章:
力扣474-一和零(Java详细题解)
题目链接:474. 一和零 - 力扣(LeetCode) 前情提要: 因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。 最近刚学完01背包,所以现在的题解都是以01背包问题为基础再来写的。 如果大家不懂01背包的话&#…...
【话题】量子计算:前沿技术与应用前景深度解析
引言 在当今信息时代,计算能力已成为推动科技进步和社会发展的重要驱动力。随着摩尔定律逐渐接近其物理极限,传统计算机硬件的性能提升面临前所未有的挑战。在此背景下,量子计算作为一种革命性的计算范式,凭借其独特的量子力学属性…...
第11章 32位x86处理器编程架构
第11章 32位x86处理器编程架构 IA-32(INTEL Architecture, 32-bit):INTEL 32位处理器架构简称IA-3,以8086处理器为基础发展起来的。该章重点介绍了IA-32处理器的工作方式和相关技术。 IA-32架构的基本执行环境 寄存器的扩展 32位处理器通用寄存器&am…...
加密软件是什么?有哪些用处呢?
一、加密软件是什么? 加密软件用于对数据进行加密和解密的工具或程序。其主要功能是通过使用加密算法将原始数据转换为密文,以保护数据的机密性和安全性,防止未经授权的访问和泄露。加密软件提供用户友好的界面和操作方式,使用户…...
浅谈C#之任务调度TaskScheduler
一、基本介绍 TaskScheduler 是一个抽象类,用于控制任务的执行方式,特别是它们如何被安排到线程池中的线程上执行。 TaskScheduler 负责将 Task 对象排队并决定何时、以何种方式执行这些任务。 二、TaskScheduler的作用 调度任务:将任务分配…...
SQL server 日常运维命令
一、基础命令 查看当前数据库的版本 SELECT VERSION;查看服务器部分特殊信息 select SERVERPROPERTY(Nedition) as Edition --数据版本,如企业版、开发版等,SERVERPROPERTY(Ncollation) as Collation --数据库字符集,SERVERPROPERTY(Nservername) as Serve…...
基于协同过滤算法+SpringBoot+Vue+MySQL的商品推荐系统
系统展示 用户前台界面 管理员后台界面 系统背景 当前的网络技术,软件技术等都具备成熟的理论基础,市场上也出现各种技术开发的软件,这些软件都被用于各个领域,包括生活和工作的领域。随着电脑和笔记本的广泛运用,以及…...
VSCode中latex文件(Misplaced alignment tab character .LaTeX
Misplaced alignment tab character &.LaTeX 先给出参考文章1 Misplaced alignment tab character &.LaTeX 把bib文件中的 &改为 and 。删除原有的bbl文件、重新运行 选择这个运行 这个错误在overleaf上并没有遇到、在vscode上遇到了 方法二就是把 &改为…...
如何给电脑设置静态IP地址:详细步骤与指南
在日常生活和工作中,我们经常需要使用电脑连接到网络。通常情况下,电脑会自动获取IP地址,但有时候,由于特定的网络需求或配置,我们可能需要手动为电脑设置静态IP地址。本文将详细介绍如何在Windows和Mac操作系统中为电…...
【Mysql】系统服务启动访问报错问题处理:this is incompatible with sql_mode=only_full_group_by
一、背景: 本来已经正常运行的平台,突然有一天由于对服务器进行部分操作迁移,发现jar可以正常启动,但是访问功能一直报错,监控后台日志后,发现了问题: 报错的具体信息如下: Caused…...
安装oh-my-zsh后报错zsh: command not found: conda问题解决
zsh: command not found: conda问题解决 一、问题介绍与环境介绍 系统为macOS Sonoma 14.5 所用终端为zsh 主要问题:安装了oh-my-zsh之后conda命令在终端中不可用。 二、原因分析 终端中zsh的可访问的程序一般放在/bin, /usr/bin, /usr/local/bin,~/bi…...
避免 PyCharm 将该 Python 脚本作为测试运行
为了避免 PyCharm 将该 Python 脚本作为测试运行(即 pytest 自动捕获),你可以做以下几步来确保该脚本作为普通的 Python 程序执行,而不是作为 pytest 运行。 解决方案: 1. 确保文件名不以 test_ 开头: P…...
【Sqlite】.NET Framework使用Sqlite的注意事项
注意:NuGet引入System.Data.SQLite.Core不要引入System.Data.SQLite 注意:局域网共享链接 正常链接Data Source\\BAT-OCV\SqliteDB\batOCV.db;Version3;PoolingTrue;Max Pool Size100; 局域网链接Data Source\\\BAT-OCV\SqliteDB\batOCV.db;Version3;P…...
2024下《系统集成项目管理工程师》50个高频考点汇总!值得收藏
11月软考已经迫在眉睫,准备考系统集成的小伙伴们开始准备了吗? 这里给大家整理了50个高频考点,涵盖全书80%重点,先把这个存下!再慢慢看书,边看书边背这个,事半功倍。 1、信息安全的基本要素有&…...
Java 远程调用接口(RMI)
Java Remote Method Invocation (RMI) 概述 Java 的 Remote Method Invocation (RMI) 是一种允许 Java 程序调用远程对象的方法。这种方法类似于本地调用,但目标对象实际位于远程 JVM(Java 虚拟机)中。RMI 实现了分布式计算,允许…...
torch.squeeze()
在深度学习中经常会遇见这个函数,现在来说一下这个函数的用法,其实很简单的。 函数作用 函数的作用就是:挤压size为1的维度,挤压也就是remove。如果size不是1的话,那就没变化。 使用说明 在使用的时候,…...
COD论文笔记 BiRefNet
本质还是一个 U 型编码器解码器结构的分割模型。 我可以考虑将©和(d)结合,即对解码器的输入不进行 patchify,同时在各个阶段引入梯度参考信息 最近的相关工作,中间监督、额外先验(频率,梯度,边缘等)取得不错效果 作者观察到…...
表单项标签简单学习
目录 1. 单选框 radio 编辑编辑编辑编辑 2. 复选框 checkbox 编辑编辑编辑 3. 隐藏域 hidden 4. 多行文本框 textarea 编辑编辑 5. 下拉框 select 编辑编辑 6. 选择头像编辑编辑 <!DOCTYPE html> <html lang"en"> <h…...
固态硬盘和机械硬盘区别?固态硬盘和机械硬盘哪个好?
在当今数据时代,硬盘作为电脑里的存储设备在我们的生活和工作中扮演着十分重要的角色。随着存储技术的进步,市场上出现了两种主流硬盘:固态硬盘和机械硬盘。它们各有优劣,那么二者究竟有什么区别?我们又该如何选择呢&a…...
QQ频道机器人零基础开发详解(基于QQ官方机器人文档)[第三期]
QQ频道机器人零基础开发详解(基于QQ官方机器人文档)[第三期] 第三期介绍:频道模块之频道成员 目录 QQ频道机器人零基础开发详解(基于QQ官方机器人文档)[第三期]第三期介绍:频道模块之频道成员获取子频道在线成员数获取频道成员列表获取频道身份组成员列…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
Docker、Wsl 打包迁移环境
电脑需要开启wsl2 可以使用wsl -v 查看当前的版本 wsl -v WSL 版本: 2.2.4.0 内核版本: 5.15.153.1-2 WSLg 版本: 1.0.61 MSRDC 版本: 1.2.5326 Direct3D 版本: 1.611.1-81528511 DXCore 版本: 10.0.2609…...
用 FFmpeg 实现 RTMP 推流直播
RTMP(Real-Time Messaging Protocol) 是直播行业中常用的传输协议。 一般来说,直播服务商会给你: ✅ 一个 RTMP 推流地址(你推视频上去) ✅ 一个 HLS 或 FLV 拉流地址(观众观看用)…...
RKNN开发环境搭建2-RKNN Model Zoo 环境搭建
目录 1.简介2.环境搭建2.1 启动 docker 环境2.2 安装依赖工具2.3 下载 RKNN Model Zoo2.4 RKNN模型转化2.5编译C++1.简介 RKNN Model Zoo基于 RKNPU SDK 工具链开发, 提供了目前主流算法的部署例程. 例程包含导出RKNN模型, 使用 Python API, CAPI 推理 RKNN 模型的流程. 本…...
