代码随想录day44 45 46
这部分的题目主要介绍了完全背包的内容;
主要考虑了两种情况,求组合数还是排列数
先遍历背包,再遍历物品,得到的就是组合数,也就是有顺序
for (int j = 0; j <= amount; j++) { // 遍历背包容量for (int i = 0; i < coins.size(); i++) { // 遍历物品if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];}
}
先遍历物品,再遍历背包,得到的就是有顺序的,物品会从序号从小到大出现
for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量dp[j] += dp[j - coins[i]];}
}
纯背包问题不需要考虑顺序。
另外还有一个点,求最小值,dp数组初始化都要为遍历过程中取不到的大值,一般为INT_MAX
518零钱兑换
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]];cout<<dp[j]<<endl;}}return dp[amount];}
};
//组合数 不需要考虑顺序 所以先遍历物品
377组合数IV
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<unsigned int>dp(target+1,0);dp[0]=1;for(int j=1;j<=target;j++){for(int i=0;i <nums.size();i++){if(j>=nums[i])dp[j]=dp[j]+dp[j-nums[i]];}}return dp[target];}
};
70爬楼梯
class Solution {
public:int climbStairs(int n) {vector<int> dp(n + 1, 0);dp[0] = 1;for (int i = 1; i <= n; i++) { // 遍历背包for (int j = 1; j <= m; j++) { // 遍历物品if (i - j >= 0) dp[i] += dp[i - j];}}return dp[n];}
};
322零钱兑换
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int>dp(amount+1,amount+2);dp[0]=0;for(int i=1;i<dp.size();i++){for(int coin:coins){if(i-coin>=0)dp[i]=min(dp[i],dp[i-coin]+1);}}return dp[amount]==amount+2?-1:dp[amount];}
};
279完全平方数
class Solution {
public:int numSquares(int n) {vector<int>dp(n+1,n+2);dp[0]=0;dp[1]=1;for(int i=2;i<=n;i++){for(int j=1;j*j<=i;j++){dp[i]=min(dp[i],dp[i-j*j]+1);}}return dp[n];}
};
139单词拆分
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool>dp(s.size()+1);dp[0]=true;for(int i=1;i<=s.size();i++){for (int j = 0; j < i; j++){string word = s.substr(j, i - j);if (wordSet.find(word) != wordSet.end() && dp[j]) {dp[i] = true;}}}return dp[s.size()];}
};
相关文章:
代码随想录day44 45 46
这部分的题目主要介绍了完全背包的内容; 主要考虑了两种情况,求组合数还是排列数 先遍历背包,再遍历物品,得到的就是组合数,也就是有顺序 for (int j 0; j < amount; j) { // 遍历背包容量for (int i 0; i <…...
一探Linux下的七大进程状态
文章目录 一、前言二、操作系统学科下的进程状态1、运行状态2、阻塞状态3、挂起状态 三、Linux下的7种进程状态1、运行状态R2、浅度睡眠状态S3、深度睡眠状态D一场有趣的官司 4、停止状态T5、进程跟踪状态t6、死亡状态X7、僵死状态Z —— 两个特殊进程① 僵尸进程② 孤儿进程 四…...
香港站群服务器为什么适合seo优化?
香港站群为什么适合seo优化?本文主要从以下四点出发进行原因阐述。 1.香港站群服务器的优势 2.香港站群服务器与国内服务器的对比 3.多IP站群服务器的优势 4.香港站群服务器在SEO优化中的注意事项 1.香港站群服务器的优势 香港站群服务器是为了满足企业SEO优化需求而提供…...
虚拟机内搭建CTFd平台搭建及CTF题库部署,局域网内机器可以访问
一、虚拟机环境搭建 1、安装docker、git、docker-compose ubuntu: sudo apt-get update #更新系统 sudo apt-get -y install docker.io #安装docker sudo apt-get -y install git #安装git sudo apt-get -y install python3-pip #安装pip3 sudo pip install dock…...
qq录屏怎么弄?手把手教会你!
“有没有人知道qq怎么录屏呀,听说qq可以录屏,刚好最近需要录制屏幕,就想用qq去录,但是找了很久,都没找到,有人知道吗,谢谢了。” 在如今数字化时代,屏幕录制已成为广泛使用的工具。…...
一文读懂c++语言
一文读懂C语言 C的发展C的设计目标C的特性C的挑战 C的发展 C是一种通用的、高级的编程语言,它是C语言的扩展。C由Bjarne Stroustrup于1983年首次引入,并在之后的几十年中不断发展壮大。C被广泛应用于各种领域,包括系统开发、游戏开发、嵌入式…...
BERT数据处理,模型,预训练
代码来自李沐老师《动手学pytorch》 在数据处理时,首先执行以下代码 def load_data_wiki(batch_size, max_len):"""加载WikiText-2数据集"""num_workers d2l.get_dataloader_workers()data_dir d2l.download_extract(wikitext-2, w…...
Oracle将与Kubernetes合作推出DevOps解决方案!
导读Oracle想成为云计算领域的巨头,但它不是推出自己品牌的云DevOps软件,而是将与CoreOS在Kubernetes端展开合作。七年前,Oracle想要成为Linux领域的一家重量级公司。于是,Oracle主席拉里埃利森(Larry Ellison…...
微服务与Nacos概述-4
限流规则配置 每次服务重启后 之前配置的限流规则就会被清空因为是内存态的规则对象,所以就要用到Sentinel一个特性ReadableDataSource 获取文件、数据库或者配置中心是限流规则 依赖:spring-cloud-alibaba-sentinel-datasource 通过文件读取限流规则…...
Streamlit 讲解专栏(九):深入探索布局和容器
文章目录 1 前言2 st.sidebar - 在侧边栏增添交互元素2.1 将交互元素添加至侧边栏2.2 示例:在侧边栏添加选择框和单选按钮2.3 特殊元素的注意事项 3 st.columns - 并排布局多元素容器3.1 插入并排布局的容器3.2 嵌套限制 4 st.tabs - 以选项卡形式布局多元素容器4.1…...
使用cloud-int部署nginx
参考 azure创建虚拟机,创建虚拟机注意入站端口规则开放80端口,高级中使用自定义数据,初始化虚拟机,安装nginx 连接CLI,验证是否安装成功 访问虚拟机IP查看是否部署成功 参考文档: https://learn.microsoft.com/zh-cn…...
定量分析计算51单片机复位电路工作原理 怎么计算单片机复位电容和电阻大小
下面画出等效电路图 可以知道单片机内必然有一个电阻RX,为了简化分析,我们假设他是线性电阻(不带电容,电感的支路) 还有一个基础知识: 电容器的充电放电曲线: 还需要知道电容电压的变化是连续…...
消息队列相关面试题
巩固基础,砥砺前行 。 只有不断重复,才能做到超越自己。 能坚持把简单的事情做到极致,也是不容易的。 面试题 项目上用过消息队列吗?用过哪些?当初选型基于什么考虑的呢? 面试官心理分析 第一࿰…...
33 | 美国总统数据分析
在这个数据分析项目中,利用Pandas等Python库对美国2020年7月22日至2020年8月20日期间的超过75万条捐赠数据进行了深入的探索和分析。通过这一分析,他们揭示了这段时间内美国选民对总统候选人的偏好和捐款情况。以下是对文章中的主要步骤和内容的进一步描述: 数据集处理: 作…...
每日一题之常见的排序算法
常见的排序算法 排序是最常用的算法,常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、希尔排序和归并排序。除此之外,还有桶排序、堆排序、基数排序和计数排序。 1、冒泡排序 冒泡排序就是把小的元素往前放或大的元素往后放,比较…...
JVM 类加载和垃圾回收
JVM 1. 类加载1.1 类加载过程1.2 双亲委派模型 2. 垃圾回收机制2.1 死亡对象的判断算法2.2 垃圾回收算法 1. 类加载 1.1 类加载过程 对应一个类来说, 它的生命周期是这样的: 其中前 5 步是固定的顺序并且也是类加载的过程,其中中间的 3 步我们都属于连接…...
C++ 多线程
C 多线程 多线程是多任务处理的一种特殊形式,多任务处理允许让电脑同时运行两个或两个以上的程序 一般情况下,两种类型的多任务处理:基于进程和基于线程 基于进程的多任务处理是程序的并发执行基于线程的多任务处理是同一程序的片段的并发…...
深入理解JVM之.intern()的用法
intern只在常量池里记录首次出现的实例引用 来看一段代码 public class RuntimeConstantPoolOOM {public static void main(String[] args) {String str1 new StringBuilder("计算机").append("软件").toString();System.out.println(str1.intern() st…...
idea报“Could not autowire. No beans of ‘UserMapper‘ type found. ”错解决办法
原因和解决办法 1.原因 idea具有检测功能,接口不能直接创建bean的,需要用动态代理技术来解决。 2.解决办法 1.修改idea的配置 1.点击file,选择setting 2.搜索inspections,找到Spring 3.找到Spring子目录下的Springcore 4.在Springcore的子目录下…...
QEMU源码全解析35 —— Machine(5)
接前一篇文章:QEMU源码全解析34 —— Machine(4) 本文内容参考: 《趣谈Linux操作系统》 —— 刘超,极客时间 《QEMU/KVM》源码解析与应用 —— 李强,机械工业出版社 特此致谢! 上回书说到有3…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
