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

一和零（leetcode 474

news 来源：原创 2025/8/7 16:47:20

leetcode系列

文章目录

一、核心操作
二、外层配合操作
三、核心模式代码
总结

本题是一个01背包问题，只是背包是一个二维数组的背包，分别为0的个数不能超过m，1的个数不能超过n，而物品就是题目中的字符串，其容量为0和1的个数，而价值就是1，本题要在给定的背包容量中，使得价值尽可能的高，也就是尽可能多的拿字符串

一、核心操作

dp[i][j]代表0的个数不超过i，1的个数不超过j的情况下，字符串的最大数量
递推公式：当本次拿取的字符串不超过背包容量时，可以比较是不拿这个字符串的的总共数量多，还是拿这个字符串的总共数量多，即比较dp[i][j]和dp[i-zero][j-one]+1；如果超过了背包容量那就不用比较了，直接就不用动了（因为是滚动数组，每一次都直接在上一层的基础上更新）
初始化：由于个数是从0开始的，都初始化为0就可以
遍历顺序：两个都是从后往前，只有这样才不会重复放入字符串

提示：小白个人理解，如有错误敬请谅解！

二、外层配合操作

每次都从字符串数组中拿取一个，统计这个字符串0和1的数量，然后根据这个来更新本层的数据

三、核心模式代码

代码如下：

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 zero=0;int one=0;for(auto & s :str){if(s=='0')zero++;else one++;}for(int i=m;i>=zero;i--){for(int j=n;j>=one;j--){dp[i][j]=max(dp[i][j],dp[i-zero][j-one]+1);}}}return dp[m][n];}
};

总结

其实按照标准的01背包来看，此题应该用一个三维数组，但是三维数组对资源占用太大了，代码如下：

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<vector<int>>> dp (strs.size(),vector<vector<int>>(m+1,vector<int>(n+1,0)));vector<int> zero;vector<int> one;for(string str : strs){int zeroNum=0;int oneNum=0;for(char s : str){if(s=='0')zeroNum++;else oneNum++;}one.push_back(oneNum);zero.push_back(zeroNum);}if(zero[0]<=m && one[0]<=n){for(int j=zero[0];j<=m;j++){for(int k=one[0];k<=n;k++){dp[0][j][k]=1;}}}for(int i=1;i<strs.size();i++){for(int j=0;j<=m;j++){for(int k=0;k<=n;k++){if(j<zero[i] || k<one[i])dp[i][j][k]=dp[i-1][j][k];else dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-zero[i]][k-one[i]]+1);}}}return dp[strs.size()-1][m][n];}
};

一和零（leetcode 474

leetcode系列文章目录一、核心操作二、外层配合操作三、核心模式代码总结本题是一个01背包问题，只是背包是一个二维数组的背包，分别为0的个数不能超过m，1的个数不能超过n，而物品就是题目中的字符串，其容量为0和1的…...

编程日记 2025/8/7 16:47:20

注：机翻，未校。 vim terminal “raw” mode Vim 终端 “raw” 模式 1. 原始模式与已处理模式的区别 We know vim puts the terminal in “raw” mode where it receives keystrokes as they are typed, opposed to “cooked” mode where the command…...

编程日记 2025/8/7 16:44:29

利用Linux的I2C子系统和i2c-tools工具集写出的对I2C设备AP3216C读写的应用程序

前言由于NXP官方提供的BSP里已经包含了其片上I2C控制器的驱动并接入到了Linux的I2C子系统，所以我们可以直接去写与I2C有关的应用程序了。在本篇博文中我们用两种方式对I2C设备AP3216C进行读写操作。第一种：直接利用Linux的I2C子系统对I2C设备AP3216…...

编程日记 2025/8/7 16:46:19

springCloud集成tdengine(原生和mapper方式) 其二原生篇

mapper篇请看另一篇文章一、引入pom文件 <dependency><groupId>com.taosdata.jdbc</groupId><artifactId>taos-jdbcdriver</artifactId><version>3.5.3</version></dependency>二、在nacos中填…...

编程日记 2025/8/7 1:51:07

gralloc usage flags

下面这些示例主要说明了 gralloc usage flags 在图像处理和多媒体应用中如何影响性能和正确性。让我们逐个详细分析每个问题的根因和修复方案，并深入解析 gralloc 标志对缓存管理和数据流的影响。 ✅ Example 1: 长曝光快照耗时异常 📌 问题描述…...

编程日记 2025/8/7 16:44:29

RIP路由欺骗攻击与防御实验详解

一、基础网络配置 1. 路由器R1配置 interface GigabitEthernet0/0/0ip address 192.1.2.254 255.255.255.0 ! interface GigabitEthernet0/0/1ip address 192.1.3.254 255.255.255.0 ! router rip 1version 2network 192.1.2.0network 192.1.3.0 2. 路由器R2配置 interface…...

编程日记 2025/8/6 19:18:16

在 Linux下使用 Python 3.11 和 FastAPI 搭建带免费证书的 HTTPS 服务器

在当今数字化时代，保障网站数据传输的安全性至关重要。HTTPS 协议通过使用 SSL/TLS 加密技术，能够有效防止数据在传输过程中被窃取或篡改。本教程将详细介绍如何在 Ubuntu 22.04 系统上，使用 Python 3.11 和 FastAPI 框架搭建一个带有免费 SS…...

编程日记 2025/8/7 16:38:02

[QMT量化交易小白入门]-三十五、如何将聚宽策略信号转为QMT实盘交易

本专栏主要是介绍QMT的基础用法，常见函数，写策略的方法，也会分享一些量化交易的思路，大概会写100篇左右。 QMT的相关资料较少，在使用过程中不断的摸索，遇到了一些问题，记录下来和大家一起沟通，共同进步。文章目录相关阅读一、聚宽模拟运行：构建交易策略的基础在聚宽…...

编程日记 2025/8/7 16:43:15

国思RDIF低代码快速开发框架 v6.2版本发布

1、平台介绍国思RDIF企业级低代码开发平台，给用户和开发者最佳的框架平台方案，为企业快速构建跨平台、企业级的应用提供强大支持。致力于解决企业信息化项目交付难、实施效率低、开发成本高的问题。能帮助企业快速构建美观易用、架构专业、安全可控的企…...

编程日记 2025/8/7 16:44:03

学习笔记 ASP.NET Core Web API 8.0部署到iis

一.修改配置文件修改Program.cs配置文件将 if (app.Environment.IsDevelopment()) {app.UseSwagger();app.UseSwaggerUI(); }修改为 app.UseSwagger(); app.UseSwaggerUI(); 二.安装ASP.NET Core Runtime 8.0.14 文件位置https://dotnet.microsoft.com/en-us/download/do…...

编程日记 2025/8/7 5:35:35

【Linux】信号：产生信号

🔥个人主页：Quitecoder 🔥专栏：linux笔记仓目录 01.信号信号处理简单理解信号的发送和保存由软件产生的信号由硬件（异常）产生的信号 01.信号进程信号是操作系统提供的一种异步通知机制，用于…...

编程日记 2025/8/2 19:14:25

单片机自学总结

自从工作以来，一直努力耕耘单片机，至今，颇有收获。从51单片机，PIC单片机，直到STM32，以及RTOS和Linux，几乎天天在搞:51单片机，STM8S207单片机，PY32F003单片机，…...

编程日记 2025/8/7 16:38:35

Idea集成docker通过ca加密实现镜像打包

Idea集成docker实现镜像打包_ideadocker镜像打包-CSDN博客之前通过这种方式虽然可以实现idea通过maven打jar包的同时把docker镜像也进行打包，但是这种方式存在很大漏洞，就是服务器的2375端口大开，任何人拿着idea通过这种方式都可以连…...

编程日记 2025/8/7 16:36:37

【Prometheus】prometheus标签替换label_replace，动态修改生成标签，增强查询的灵活性和表达能力

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全…...

编程日记 2025/8/7 16:39:41

蓝桥杯之暴力回溯

文章目录数字接龙小u的最大连续移动次数问题在蓝桥杯中，十分喜欢考察对于网格的回溯的问题，对于这类的问题，常常会使用到这个DFS和BFS进行考察，不过无论怎么考察，都只是会在最基础的模本的基础上，根据这个…...

编程日记 2025/8/7 16:39:42

在K8S中挂载 Secret 到 Pod

在 Kubernetes 里，把 Secret 挂载到 Pod 中有两种主要方式：作为卷挂载和作为环境变量挂载。下面为你提供相应的代码示例。作为卷挂载 Secret 将 Secret 作为卷挂载到 Pod 时，Secret 的每个键会成为挂载目录下的一个文件，文件内…...

编程日记 2025/8/7 16:41:04

LINUX网络编程API原型详细解析

1. 网络体系 1.1. 简介网络采用分而治之的方法设计，将网络的功能划分为不同的模块，以分层的形式有机组合在一起。每层实现不同的功能，其内部实现方法对外部其他层次来说是透明的。每层向上层提供服务，同时使用下层提供…...

编程日记 2025/8/7 16:34:14

Android 13 Launcher3最近任务列表“全部清除“按钮位置优化实战

一、问题背景与实现难点在Android 13横屏设备开发中，系统默认将最近任务列表的"全部清除"按钮布局在屏幕左侧，这与用户习惯的底部布局存在明显差异。相较于Android 8.1时代SystemUI模块的实现，Android 13将相关逻辑迁移至Launche…...

编程日记 2025/8/7 16:36:14

docker最新源，及遇到问题+处理

目前国内可用Docker镜像源汇总（截至2025年3月） - CoderJia 遇到问题： Error response from daemon: Get "https://registry-1.docker.io/v2/": dial tcp: lookup registry-1.docker.io on [::1]:53: read udp [::1]:13287->[:…...

编程日记 2025/8/4 23:58:03

Python简单爬虫实践案例

学习目标能够知道Web开发流程能够掌握FastAPI实现访问多个指定网页知道通过requests模块爬取图片知道通过requests模块爬取GDP数据能够用pyecharts实现饼图能够知道logging日志的使用一、基于FastAPI之Web站点开发 1、基于FastAPI搭建Web服务器 # 导入FastAPI模…...

编程日记 2025/8/7 1:50:54

统信UOS中使用Vscode编程

写在前面：统信UOS其实就是套壳的Linux系统，所以有问题如果搜不到解决方法，可以参考Linux下的解决方法。 1.环境配置 Vscode : 1.85.0 Vscode就直接下载安装就行，然后安装插件：Volar、中文汉化包 node：18…...

编程日记 2025/8/4 14:55:11

C#从入门到精通（1）

目录第一章 C#与VS介绍第二章第一个C#程序 （1）C#程序基本组成 1.命名空间 2.类 3.Main方法 4.注释 5.语句 6.标识符及关键字 （2）程序编写规范 1.代码编写规则 2.程序命名方法 3.元素命名规范第三章变量 &…...

编程日记 2025/8/3 11:31:57

openharmony中hilog实证记录说明(3.1和5.0版本)

每次用这个工具hilog都有一些小用法记不清，需要花一些时间去查去分析使用方法，为了给丰富多彩的生活留出更多的时间，所以汇总整理共享来了，它来了它来了~~~~~~~~~ 开始是想通过3.1来汇总的，但实际测试发现openharmony…...

编程日记 2025/8/6 18:43:35

飞书设计智能字段：通过“字段类型”添加AI功能列

在飞书多维表格中，通过“字段类型”添加AI功能列的核心逻辑是将AI模型能力与结构化数据结合，实现自动化内容生成与信息处理。以下是具体操作步骤及关键要点，结合实际应用场景说明： 一、基础操作步骤创建多维表格登录飞书&#x…...

编程日记 2025/8/2 20:01:02

Cannot find module @rollup/rollup-win32-x64-msvc

方法1 在package.json中添加postinstall: "scripts": {"postinstall": "node -e \"const { platform } process; if (platform win32) { require(child_process).execSync(npm install rollup/rollup-win32-x64-msvc, { stdio: inherit });…...

编程日记 2025/8/5 16:16:11

Docker和Dify学习笔记

文章目录 1 docker学习1.1 基本命令使用1.1.1 docker ps查看当前正在运行的镜像1.1.2 docker stop停止容器1.1.3 docker compose容器编排1.1.4 docker网络[1] 进入到容器里面敲命令[2] docker network ls[3] brige网络模式下容器访问宿主机的方式 2 Dify的安装和基础使用2.1 下…...

编程日记 2025/8/7 5:12:42

【AIGC】Win10系统极速部署Docker+Ragflow+Dify

【AIGC】WIN10仅3步部署DockerRagflowDify 一、 Docker快速部署1.F2进入bios界面，按F7设置开启VMX虚拟化技术。保存并退出。2.打开控制面板配置开启服务3.到官网下载docker安装包，一键安装（全部默认勾选） 二、 RagFlow快速部署1.确…...

编程日记 2025/8/2 20:59:45

Oracle ASM 磁盘组冗余策略

Oracle ASM 磁盘组冗余策略 1. 外部冗余（External Redundancy）2. 普通冗余（Normal Redundancy）3. 高冗余（High Redundancy）关键注意事项如何选择合适的策略？ Oracle ASM（Automatic S…...

编程日记 2025/8/3 7:32:20

C++ 数据结构

C++ 数据结构概述 C++作为一种强大的编程语言，在软件开发领域有着广泛的应用。数据结构作为C++编程中不可或缺的一部分，它决定了程序的性能和效率。本文将详细介绍C++中的常见数据结构，包括其定义、特点以及在实际应用中的使用方法。常见数据结构 1. 数组数组是一种…...

编程日记 2025/8/5 17:58:58

Unity NodeCanvas AI使用笔记

扩展: 1. 输入输出参数限制，增加描述，根据接口判断类型限制 2.选择节点，遍历节点，行为节点 3.行为节点行为执行的时候有互斥关系，加入一个queue，最后执行 4.NodeCanvas的参数传参可以由上个节点传到下个节…...

编程日记 2025/8/3 10:30:07

(* IOB = “FORCE“ *) 的使用分享

在Xilinx FPGA设计中，IOBFORCE是一个与输入输出块（IOB）相关的属性设置。这个设置主要用于控制逻辑是否被推入到IOB（Input/Output Block）中，即FPGA芯片边缘的I/O引脚附近的专用硬件资源。使用IOB属性可以帮助…...

编程日记 2025/8/7 12:11:21

【大语言模型_7】利用ragas框架评测rag系统指标

一、介绍 ragas是一个用来评估RAG系统的框架，允许不在依赖人工注释的情况下，通过一套指标评估检索模块和生成模块的性能及其质量。二、准备数据准备：需要准备评估数据集，数据集格式如下 [{"question": "安全智…...

编程日记 2025/8/4 8:04:57

adb常用的命令

1. 查看adb版本 adb version 2. 将apk安装包安装到手机/模拟器上 adb install apk路径 3. 获取apk包名和界面名包名（package）：决定程序的唯一性界面名（activity）：一个界面界面名，对应一个界面…...

编程日记 2025/8/6 12:48:30

手动集成sqlite的方法

注意到sqlite有backup方法（https://www.sqlite.org/backup.html）。也注意到android中sysroot下，没有sqlite3的库，也没有相关头文件。如果要使用 sqlite 的backup，那么就需要手动集成sqlite代码到项目中。可以如下操…...

编程日记 2025/8/5 7:37:09

自然语言处理（NLP）技术

人工智能（Artificial Intelligence，AI）是一种模拟人类智能思维过程的技术，它在现代科技中的应用非常广泛，涉及诸多领域，如自然语言处理、计算机视觉、机器学习、数据分析等。以下是人工智能在现代科技中的应…...

编程日记 2025/8/3 17:16:18

【GPT入门】第25课掌握 LangChain：链式调用的奥秘、特性与使用示例

【GPT入门】第25课掌握 LangChain：链式调用的奥秘、特性与使用示例语法解释各部分性质链式调用的性质调用方式注意事项语法解释你给出的代码 is_duplicated_chain (check_duplicated | model | parser) 运用了 LangChain 里的链式调用语法。在 LangChain 中&a…...

编程日记 2025/8/7 14:36:37

机器学习之DBSCAN算法详解

文章目录引言1. DBSCAN算法概述2.DBSCAN算法的基本概念2.1 ε-邻域2.2 核心点（Core Point）2.3 边界点（Border Point）2.4 噪声点（Noise Point）2.5 直接密度可达（Directly Density-Reachable&…...

编程日记 2025/8/6 8:54:15

借助vite来优化前端性能

Vite 是一个现代化的前端构建工具，凭借其基于原生 ES 模块的开发服务器和高效的构建能力，可以显著优化前端性能。一、开发环境优化 1.快速启动与热更新 Vite 利用浏览器对 ES 模块的原生支持，在开发环境中无需打包，直接按需加载…...

编程日记 2025/8/5 16:04:35

[工控机安全] 使用DriverView快速排查不可信第三方驱动（附详细图文教程）

导语： 在工业控制领域，设备驱动程序的安全性至关重要。第三方驱动可能存在兼容性问题、安全漏洞甚至恶意代码，威胁设备稳定运行。本文将手把手教你使用 DriverView工具，高效完成工控机驱动安全检查，精准识别可疑驱动&a…...

编程日记 2025/8/2 16:45:27

Execution failed for task ‘:path_provider_android:compileDebugJavaWithJavac‘.

What went wrong: Execution failed for task ‘:path_provider_android:compileDebugJavaWithJavac’. Could not resolve all files for configuration ‘:path_provider_android:androidJdkImage’. Failed to transform core-for-system-modules.jar to match attributes {…...

编程日记 2025/8/6 20:09:07

文章目录

一、核心操作

二、外层配合操作

三、核心模式代码

总结

相关文章：