新手怎么学做网站/河北百度代理公司
目录
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. 零钱兑换 总结: 474. 一和零 这道题和前面的思路一样,就是需要将背包扩展到二维。 class Solution { public:int findMaxForm(vector<string>& strs, int m, int n) {vector&l…...

MongoDB创建和查询视图(一)
目录 限制和注意事项 应用两种方式创建视图 本文整理mongodb的官方文档,介绍mongodb的视图创建和查询。 Mongodb中,允许使用两种方式来创建视图。 //使用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)覆盖优化 - 附代码
智能优化算法应用:基于卷积优化算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于卷积优化算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.卷积优化算法4.实验参数设定5.算法结果6.…...

项目中日期封装
官网:Moment.js 中文网项目中安装:npm install moment --save封装:创建一个.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 定义 在编程中,需要接收用户输入的数据,就可以使用键盘输入语句来获取。Input.java , 需要一个 扫描器(对象), 就是 Scanner .2 步骤 导入该类的所在包package, java.util.*创建该类对象(声明变…...

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

Linux的账号及权限管理
一.管理用户账号 1.1 用户账户的分类 1.1.1 用户账号的分类 超级用户:(拥有至高无上的权利) root用户是Linux操作系统中默认的超级用户账号,对本主机拥有最高的权限,系统中超级用户是唯一的。普通用户: …...

Flink 状态管理与容错机制(CheckPoint SavePoint)的关系
一、什么是状态 无状态计算的例子: 例如一个加法算子,第一次输入235那么以后我多次数据23的时候得到的结果都是5。得出的结论就是,相同的输入都会得到相同的结果,与次数无关。 有状态计算的例子: 访问量的统计&#x…...

CSS中更加高级的布局手段——定位之绝对定位
定位: - 定位指的就是将指定的元素摆放到页面的任意位置,通过定位可以任意的摆放元素 - 通过position属性来设置元素的定位 -可选值: static: [sttik] 默认值,元素没有开启定位 relative: [relətiv] 开启元素…...

SQL server 数据库练习题及答案(练习3)
一、编程题 公司部门表 department 字段名称 数据类型 约束等 字段描述 id int 主键,自增 部门ID name varchar(32) 非空,唯一 部门名称 description varchar(1024) …...

太绝了!这个食堂服务,戳中了打工人的心巴!
在当今数字化时代,科技的迅猛发展已经渗透到我们生活的方方面面,其中餐饮行业也不例外。食堂作为人们日常生活中不可或缺的一部分,其管理和运营也需要紧跟科技潮流。 智慧收银系统的引入,旨在提高食堂的效率、准确性和服务水平&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接口任意文件读取漏洞(附漏洞检测脚本)
免责声明 文章中涉及的漏洞均已修复,敏感信息均已做打码处理,文章仅做经验分享用途,切勿当真,未授权的攻击属于非法行为!文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直接或者间接的…...

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

c语言例题7
以下程序中,主函数调用了LineMax函数,实现在N行M列的二维数组中,找出每一行上的最大值。请填空。 #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驱动
🐱作者:一只大喵咪1201 🐱专栏:《Linux驱动》 🔥格言:你只管努力,剩下的交给时间! 目录 🏀最基本的驱动框架⚽驱动程序框架⚽编程 🏀LED驱动⚽配置GPIO⚽编程…...

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

[C#]Parallel使用
一、 Parallel的使用 1、Parallel.Invoke2、Parallel.For3、Parallel.Foreach二、 Parallel中途退出循环和异常处理 1、当我们使用到Parallel,必然是处理一些比较耗时的操作,当然也很耗CPU和内存,如果我们中途向停止,怎么办呢&…...

docker container 指定gpu设备
1, 在yaml中 Turn on GPU access with Docker Compose | Docker Docs Example of a Compose file for running a service with access to 1 GPU device: services:test:image: nvidia/cuda:12.3.1-base-ubuntu20.04command: nvidia-smideploy:resources:reserva…...

时间Date
你有没有思考过时间问题: 前端为什么可以直接看见时间格式的数据 后端怎么接受的数据,怎么处理的 一般来说:前端传输来数据都是时间格式的字符串,那么后端需要能够解析时间格式的字符串,归功于JSONFormat ,可以解析…...

前端---css 选择器
1. css 选择器的定义 css 选择器是用来选择标签的,选出来以后给标签加样式。 2. css 选择器的种类 标签选择器类选择器层级选择器(后代选择器)id选择器组选择器伪类选择器 3. 标签选择器 根据标签来选择标签,以标签开头,此种选择器影响范…...

【MybatisPlus快速入门】(2)SpringBoot整合MybatisPlus 之 标准数据层开发 代码示例
目录 1 标准CRUD使用2 新增3 删除4 修改5 根据ID查询6 查询所有7 MyBatis-Plus CRUD总结 之前我们已学习MyBatisPlus在代码示例与MyBatisPlus的简介,在这一节中我们重点学习的是数据层标准的CRUD(增删改查)的实现与分页功能。代码比较多,我们一个个来学习…...

如何将自建的ElasticSearch注册成一个服务
ES 服务管理 注册ES服务 创建一个 Elasticsearch 服务配置文件。 sudo vim /etc/systemd/system/elasticsearch.service 将以下内容复制到 elasticsearch.service 文件中: [Unit] Descriptionelasticsearch Afternetwork.target[Service] Typeforking Useresa…...

360勒索病毒:了解最新变种.360,以及如何保护您的数据
导言: 随着科技的飞速发展,网络安全威胁也在不断演变,.360 勒索病毒成为近期备受关注的一种恶意软件。本文91数据恢复将介绍如何恢复被.360 勒索病毒加密的数据文件,并提供一些建议,帮助你预防这种威胁。 如果您在面对…...

vue使用ElementUI搭建精美页面入门
ElementUI简直是css学得不好的同学的福音 ElementUI官网: Element - The worlds most popular Vue UI framework 安装 在vue文件下,用这个命令去安装Element UI。 npm i element-ui -S step1\先切换到vue的目录下去,注意这里面的WARN不是…...

【C->Cpp】深度解析#由C迈向Cpp(2)
目录 (一)缺省参数 全缺省参数 半缺省参数 缺省参数只能在函数的声明中出现: 小结: (二)函数重载 函数重载的定义 三种重载 在上一篇中,我们从第一个Cpp程序为切入,讲解了Cpp的…...

WPS中如何根据身份证号生成出生日期并排序
1. wps中如何根据身份证号导出出生日期并排序 1.1 wps中建一张表 1.2 使用转日期格式导出出生日期 DATE(VALUE(MID(C2,7,4)),VALUE(MID(C2,11,2)),VALUE(MID(C2,13,2)))MID(C2, 7, 4):这部分从单元格 C2 中提取文本字符串,从第7个字符开始提取长度为4的…...