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

力扣刷题记录(18)LeetCode:474、518、377、322

 

目录

474. 一和零

518. 零钱兑换 II 

377. 组合总和 Ⅳ 

 322. 零钱兑换

 总结:


474. 一和零

 

这道题和前面的思路一样,就是需要将背包扩展到二维。

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 s:strs){int oneNum=0,zeroNum=0;for(auto c:s){if(c=='0')  zeroNum++;else if(c=='1') 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];}
};

518. 零钱兑换 II 

 

每个硬币可以无限制取,完全背包问题。先确定dp[i]表示的含义,i表示背包容量,dp[j]表示该容量有多少种方法。再确定递推公式,dp[j]+=dp[j-coins[i]];。最后确定遍历顺序,因为每个硬币都可以无限制取,所以j的遍历顺序应该为正序。

注意:在01背包中为了防止元素重复取,采用倒序

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount+1,0);dp[0]=1;for(int i=0;i<coins.size();i++){for(int j=coins[i];j<=amount;j++){dp[j]+=dp[j-coins[i]];}}return dp[amount];}
};


377. 组合总和 Ⅳ 

 

 这题和上题的区别在于这题是排列,上题是组合。组合问题先遍历物品后遍历背包容积,排列问题先遍历背包容积后遍历物品。进入循环里面思考一下就明白了怎么回事了。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target+1,0);dp[0]=1;//遍历背包容积for(int j=0;j<=target;j++){//遍历物品for(int i=0;i<nums.size();i++){if(j<nums[i] || dp[j]>INT_MAX-dp[j-nums[i]])   continue;dp[j]+=dp[j-nums[i]];}}return dp[target];}
};

 322. 零钱兑换

 

这题的不同之处在于求最小硬币个数,初始化的时候注意初始化为最大值。

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount+1,INT_MAX);dp[0]=0;for(int i=0;i<coins.size();i++){for(int j=coins[i];j<=amount;j++){//如果dp[j-coins[i]]==INT_MAX,将超出int的范围if(dp[j-coins[i]]!=INT_MAX)dp[j]=min(dp[j],dp[j-coins[i]]+1);}}if(dp[amount]==INT_MAX) return -1;return dp[amount];}
};

 总结:

01背包问题和完全背包问题的主要区别是元素是否可以无限制取。

在解决问题的方式上,如果是求组合就先遍历物品再遍历背包容积,如果是求排列就先遍历背包容积再遍历物品。

相关文章:

力扣刷题记录(18)LeetCode:474、518、377、322

目录 474. 一和零 518. 零钱兑换 II 377. 组合总和 Ⅳ 322. 零钱兑换 总结&#xff1a; 474. 一和零 这道题和前面的思路一样&#xff0c;就是需要将背包扩展到二维。 class Solution { public:int findMaxForm(vector<string>& strs, int m, int n) {vector&l…...

MongoDB创建和查询视图(一)

目录 限制和注意事项 应用两种方式创建视图 本文整理mongodb的官方文档&#xff0c;介绍mongodb的视图创建和查询。 Mongodb中&#xff0c;允许使用两种方式来创建视图。 //使用db.createCollection()来创建视图 db.createCollection("<viewName>",{"…...

paddle 53 基于PaddleClas2.5训练自己的数据(训练|验证|推理|c++ 部署)

项目地址:https://github.com/PaddlePaddle/PaddleClas 文档地址:https://paddleclas.readthedocs.io/zh-cn/latest/tutorials/install.html paddleclas的最新项目已经不适应其官网的使用案例(训练、验证、推理命令均不适用),为此博主对其进行命令重新进行修改。同时padd…...

智能优化算法应用:基于卷积优化算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于卷积优化算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于卷积优化算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.卷积优化算法4.实验参数设定5.算法结果6.…...

项目中日期封装

官网&#xff1a;Moment.js 中文网项目中安装&#xff1a;npm install moment --save封装&#xff1a;创建一个.js文件 // 日期、时间封装 import moment from moment moment.locale("zh-cn"); const formatTime {getTime: (date) > {return moment().format(YY…...

7.仿若依后端系统业务实践

目录 概述项目实践mybatis 反向生成代码有覆盖问题解决pom.xmlbootstrap.ymlapplication.ymlmaven测试各种校验问题实践单个属性校验级联属性校验接口实体类测试结果自定义关联属性校验接口...

java:4-9键盘输入

文章目录 键盘输入.1 定义.2 步骤.3 演示 键盘输入 .1 定义 在编程中&#xff0c;需要接收用户输入的数据&#xff0c;就可以使用键盘输入语句来获取。Input.java , 需要一个 扫描器(对象), 就是 Scanner .2 步骤 导入该类的所在包package, java.util.*创建该类对象(声明变…...

制作自己的 Docker 容器

软件开发最大的麻烦事之一&#xff0c;就是环境配置。用户必须保证操作系统的设置&#xff0c;各种库和组件的安装&#xff0c;只有它们都正确&#xff0c;软件才能运行。docker从根本上解决问题&#xff0c;软件安装的时候&#xff0c;把原始环境一模一样地复制过来。 以 koa-…...

Linux的账号及权限管理

一.管理用户账号 1.1 用户账户的分类 1.1.1 用户账号的分类 超级用户&#xff1a;&#xff08;拥有至高无上的权利&#xff09; root用户是Linux操作系统中默认的超级用户账号&#xff0c;对本主机拥有最高的权限&#xff0c;系统中超级用户是唯一的。普通用户&#xff1a; …...

Flink 状态管理与容错机制(CheckPoint SavePoint)的关系

一、什么是状态 无状态计算的例子&#xff1a; 例如一个加法算子&#xff0c;第一次输入235那么以后我多次数据23的时候得到的结果都是5。得出的结论就是&#xff0c;相同的输入都会得到相同的结果&#xff0c;与次数无关。 有状态计算的例子&#xff1a; 访问量的统计&#x…...

CSS中更加高级的布局手段——定位之绝对定位

定位&#xff1a; - 定位指的就是将指定的元素摆放到页面的任意位置,通过定位可以任意的摆放元素 - 通过position属性来设置元素的定位 -可选值&#xff1a; static&#xff1a; [sttik] 默认值&#xff0c;元素没有开启定位 relative&#xff1a; [relətiv] 开启元素…...

SQL server 数据库练习题及答案(练习3)

一、编程题 公司部门表 department 字段名称 数据类型 约束等 字段描述 id int 主键&#xff0c;自增 部门ID name varchar(32) 非空&#xff0c;唯一 部门名称 description varchar(1024) …...

太绝了!这个食堂服务,戳中了打工人的心巴!

在当今数字化时代&#xff0c;科技的迅猛发展已经渗透到我们生活的方方面面&#xff0c;其中餐饮行业也不例外。食堂作为人们日常生活中不可或缺的一部分&#xff0c;其管理和运营也需要紧跟科技潮流。 智慧收银系统的引入&#xff0c;旨在提高食堂的效率、准确性和服务水平&am…...

围栏中心点

后端返回的数据格式是 [{height: 0,lat: 30.864277169098443,lng:114.35252972024682}{height: 1,lat: 30.864277169098443,lng:114.35252972024682}.........]我们要转换成 33.00494857612568,112.53886564762979;33.00307854503083,112.53728973842954;33.00170296814311,11…...

【go-zero】simple-admin框架 整合ent mysql批量插入 | ent批量插入mysql

一、完整流程 我们需要通过goctls快速生成一个RPC项目 【go-zero】simple-admin 开篇:进击 go-zero 二开框架 simple-admin 加速 go-zero 开发 之 rpc项目快速创建(更新中~) https://ctraplatform.blog.csdn.net/article/details/130087729 1、RPC项目 1.1、.proto synta…...

漏洞复现-泛微OA xmlrpcServlet接口任意文件读取漏洞(附漏洞检测脚本)

免责声明 文章中涉及的漏洞均已修复&#xff0c;敏感信息均已做打码处理&#xff0c;文章仅做经验分享用途&#xff0c;切勿当真&#xff0c;未授权的攻击属于非法行为&#xff01;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直接或者间接的…...

Flink CDC 1.0至3.0回忆录

Flink CDC 1.0至3.0回忆录 一、引言二、CDC概述三、Flink CDC 1.0&#xff1a;扬帆起航3.1 架构设计3.2 版本痛点 四、Flink CDC 2.0&#xff1a;成长突破4.1 DBlog 无锁算法4.2 FLIP-27 架构实现4.3 整体流程 五、Flink CDC 3.0&#xff1a;应运而生六、Flink CDC 的影响和价值…...

c语言例题7

以下程序中&#xff0c;主函数调用了LineMax函数&#xff0c;实现在N行M列的二维数组中&#xff0c;找出每一行上的最大值。请填空。 #define N 3 #define M 4 void LineMax(int x[N][M]) { int i,j,p; for(i0; i<N;i) { p0; for(j1; j<M;j) …...

【Linux驱动】最基本的驱动框架 | LED驱动

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《Linux驱动》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 目录 &#x1f3c0;最基本的驱动框架⚽驱动程序框架⚽编程 &#x1f3c0;LED驱动⚽配置GPIO⚽编程…...

前端---表单提交

1. 表单属性设置 <form>标签 表示表单标签&#xff0c;定义整体的表单区域 action属性 设置表单数据提交地址method属性 设置表单提交的方式&#xff0c;一般有“GET”方式和“POST”方式, 不区分大小写 2. 表单元素属性设置 name属性 设置表单元素的名称&#xff0c…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...