当前位置: 首页 > 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…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...