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

代码随想录第四十五天

代码随想录第四十五天

    • Leetcode 70. 爬楼梯
    • Leetcode 322. 零钱兑换
    • Leetcode 279. 完全平方数

Leetcode 70. 爬楼梯

题目链接: 爬楼梯
自己的思路:之前是用斐波那契做的,但是现在学了完全背包,可以将m=2拓展的更大一点,我们可以将楼顶n设为背包的容量,将m设为物品的容量,我们每次选物品,而且物品可以重复,问可以有多少种不同的选法,而且这种是要考虑顺序的问题的,所以和之前的组合总和其实是一个题目!!!!!

正确思路:

代码:

class Solution {public int climbStairs(int n) {//物品的数量int m=2;int[] dp= new int[n+1];dp[0] = 1;for (int j=0;j<=n;j++){  //遍历背包for (int i=1;i<=m;i++){  //遍历物品if (j>=i) dp[j]+=dp[j-i];}}return dp[n];}
}

Leetcode 322. 零钱兑换

题目链接: 零钱兑换
自己的思路:想不到!!!!

正确思路:这个题可以看做是一个完全背包问题,因为里面的钱是可以任意取重复个的!动规五部曲:1、dp数组的含义:dp[j]表示的是当总金额为j时组成总金额的钱币的最小数量!2、递推公式:我们拿当第i个钱币来算,如果我们不选这个钱币,那么就是dp[j]情况,那么如果选的话就是dp[j-coins[i]]+1,所以说取两者的最小值;3、dp数组初始化:dp[0]肯定是0,主要是其他的我们要初始化为什么,因为我们是求min值,所以我们应该将他们都初始化为Integer的最大值;4、遍历顺序:由于这道题是求最小的数量,所以先遍历背包和先遍历物品其实是一样的;5、打印dp数组:主要是用于debug!!!

代码:

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];for (int i =0;i<dp.length;i++){dp[i] = Integer.MAX_VALUE;}dp[0] = 0;for (int i=0;i<coins.length;i++){for (int j=coins[i];j<=amount;j++) {//当dp[m]有效的时候,才可以向后更新,不然没有意义if (dp[j-coins[i]]!=Integer.MAX_VALUE){dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);}}}return (dp[amount]==Integer.MAX_VALUE)?-1:dp[amount];}
}

Leetcode 279. 完全平方数

题目链接: 完全平方数
自己的思路:和上一个题基本一样,怪自己懒得思考!!!!

正确思路:只是改变了一下循环中的参数的定义,其他基本都是不变的,这个题一定可以由完全平方数组成,所以我们初始化的时候非零的索引初始化为n,因为dp[n]最大是n!!!
代码:

class Solution {public int numSquares(int n) {int[] dp = new int[n+1];for (int i =0;i<dp.length;i++){dp[i]=n;}dp[0]=0;for (int i =1;i*i<=n;i++){for (int j=i*i;j<=n;j++){if (dp[j-i*i]!=n){dp[j]=Math.min(dp[j],dp[j-i*i]+1);}}}return dp[n];}
}

相关文章:

代码随想录第四十五天

代码随想录第四十五天 Leetcode 70. 爬楼梯Leetcode 322. 零钱兑换Leetcode 279. 完全平方数 Leetcode 70. 爬楼梯 题目链接: 爬楼梯 自己的思路:之前是用斐波那契做的&#xff0c;但是现在学了完全背包&#xff0c;可以将m2拓展的更大一点&#xff0c;我们可以将楼顶n设为背包…...

Vue Baidu Map--自定义点图标bm-marker

自定义点图标 将准备好的图标放到项目中 使用import引入&#xff0c; 并在data中进行声明 <script> import mapIconRed from ./vue-baidu-map/img/marker_red_sprite.png export default {data() {return {mapIconRed,}}, } </script>在<bm-marker>中加入参…...

ZooKeeper的基本概念

集群角色 通常在分布式系统中&#xff0c;构成一个集群的每一台机器都有自己的角色&#xff0c;最典型的集群模式就是Master/Slave模式(主备模式)。在这种模式中&#xff0c;我们把能够处理所有写操作的机器称为Master机器&#xff0c;把所有通过异步复制方式获取最新数据&…...

SpringBoot复习:(51)默认情况下DataSource是怎么创建出来的,是什么类型的?

DataSource是通过DataSourceAutoConfiguration创建的&#xff0c;这个类代码如下&#xff1a; 可以看到DataSourceAutoConfiguration有个静态内部类PooledDataSourceConfiguration,在这个类上有个Import注解&#xff0c;导入了DataSourceConfiguration.Hikari这个类&#xff0…...

Python+Selenium自动化测试环境搭建步骤(selenium环境搭建)

一、自动化简介 1.自动化测试概念&#xff1a; 是把以人为驱动的测试转化为机器执行的一种过程&#xff0c;它是一种以程序测试程序的过程 2.自动化测试分类&#xff1a; 一般IT上所说的自动化测试是指功能自动化测试&#xff0c;通过编码的方式用一段程序来测试一个软件的功…...

实现简单纯Canvas文本输入框,新手适用

文章目录 概要效果技术细节代码 概要 Canvas上面提供输入&#xff1a; 一、最简单可能是用dom渲染一个input,覆盖在图形上面进行文本编辑&#xff0c;编辑完再把内容更新到图形.这样简单&#xff0c;但是缺点也明显&#xff0c;就是它不是真正绘制在canvas上面&#xff0c;没…...

React构建的JS优化思路

背景 之前个人博客搭建时&#xff0c;发现页面加载要5s才能完成并显示 问题 React生成的JS有1.4M&#xff0c;对于个人博客服务器的带宽来说&#xff0c;压力较大&#xff0c;因此耗费了5S的时间 优化思路 解决React生成的JS大小&#xff0c;因为我用的是react-router-dom…...

vim键盘图

国外&#xff1a;http://www.viemu.com/a_vi_vim_graphical_cheat_sheet_tutorial.html&#xff0c;原创&#xff0c;有SVG图&#xff0c;有分步骤的图。 国内翻译&#xff1a;[https://blog.csdn.net/qq_41052753/article/details/101031847 有几个配色&#xff0c;很高清&…...

【实战】十一、看板页面及任务组页面开发(一) —— React17+React Hook+TS4 最佳实践,仿 Jira 企业级项目(二十三)

文章目录 一、项目起航&#xff1a;项目初始化与配置二、React 与 Hook 应用&#xff1a;实现项目列表三、TS 应用&#xff1a;JS神助攻 - 强类型四、JWT、用户认证与异步请求五、CSS 其实很简单 - 用 CSS-in-JS 添加样式六、用户体验优化 - 加载中和错误状态处理七、Hook&…...

深入源码分析kubernetes informer机制(三)Resync

[阅读指南] 这是该系列第三篇 基于kubernetes 1.27 stage版本 为了方便阅读&#xff0c;后续所有代码均省略了错误处理及与关注逻辑无关的部分。 文章目录 为什么需要resyncresync做了什么 为什么需要resync 如果看过上一篇&#xff0c;大概能了解&#xff0c;client数据主要通…...

FL Studio 21最新for Windows-21.1.0.3267中文解锁版安装激活教程及更新日志

FL Studio 21最新版本for Windows 21.1.0.3267中文解锁版是最新强大的音乐制作工具。它可以与所有类型的音乐一起创作出令人惊叹的音乐。它提供了一个非常简单且用户友好的集成开发环境&#xff08;IDE&#xff09;来工作。这个完整的音乐工作站是由比利时公司 Image-Line 开发…...

HTML详解连载(4)

HTML详解连载&#xff08;4&#xff09; 专栏链接 [link](http://t.csdn.cn/xF0H3)下面进行专栏介绍 开始喽CSS定义书写位置示例注意 CSS引入方式内部样式表&#xff1a;学习使用 外部演示表&#xff1a;开发使用代码示例行内样式代码示例 选择器作用基础选择器标签选择器举例特…...

STM32 LL库+STM32CubeMX--点亮板载LED

一、前期准备 硬件&#xff1a;STM32F103C8T6开发板调试工具&#xff1a;DAPLink(本次使用)或USB-TTL开发环境&#xff1a;STM32CubeMX、Keil、Vscode(可选)板载LED&#xff1a;PC13(低电平点亮) 二、STM32CubeMX配置 1.选择芯片型号&#xff1a; 2.配置外设时钟&#xff1a;…...

【HBZ分享】ES的评分score机制的原理

score类型 基础评分boost&#xff0c;默认2.2&#xff0c;逆向文档频率值(IDF)&#xff1a;表示该词再文档中(ES中)出现的次数越多&#xff0c;表示越不重要&#xff0c;评分越低关键词在文档中出现的频率(TF)&#xff1a;表示该词在文档中出现的频率&#xff0c;频率越高表示…...

函数递归专题(案例超详解一篇讲通透)

函数递归 前言1.递归案例:案例一&#xff1a;取球问题案例二&#xff1a;求斐波那契额数列案例三&#xff1a;函数实现n的k次方案例四&#xff1a;输入一个非负整数&#xff0c;返回组成它的数字之和案例五&#xff1a;元素逆置案例六&#xff1a;实现strlen案例七&#xff1a;…...

leetcode-413. 等差数列划分(java)

等差数列划分 leetcode-413. 等差数列划分题目描述双指针 上期经典算法 leetcode-413. 等差数列划分 难度 - 中等 原题链接 - 等差数列划分 题目描述 如果一个数列 至少有三个元素 &#xff0c;并且任意两个相邻元素之差相同&#xff0c;则称该数列为等差数列。 例如&#xff0…...

从零开始学习 Java:简单易懂的入门指南之MAth、System(十二)

常见API&#xff0c;MAth、System 1 Math类1.1 概述1.2 常见方法1.3 算法小题(质数)1.4 算法小题(自幂数) 2 System类2.1 概述2.2 常见方法 1 Math类 1.1 概述 tips&#xff1a;了解内容 查看API文档&#xff0c;我们可以看到API文档中关于Math类的定义如下&#xff1a; Math类…...

人工智能原理概述 - ChatGPT 背后的故事

大家好&#xff0c;我是比特桃。如果说 2023 年最火的事情是什么&#xff0c;毫无疑问就是由 ChatGPT 所引领的AI浪潮。今年无论是平日的各种媒体、工作中接触到的项目还是生活中大家讨论的热点&#xff0c;都离不开AI。其实对于互联网行业来说&#xff0c;自从深度学习出来后就…...

【Linux】以太网协议——数据链路层

链路层解决的问题 IP拥有将数据跨网络从一台主机送到另一台主机的能力&#xff0c;但IP并不能保证每次都能够将数据可靠的送到对端主机&#xff0c;因此IP需要上层TCP为其提供可靠性保证&#xff0c;比如数据丢包后TCP可以让IP重新发送数据&#xff0c;最终在TCP提供的可靠性机…...

Neo4j之MATCH基础

1】基本匹配和返回&#xff1a;查找所有节点和关系&#xff0c;返回节点的标签和属性。 MATCH (n) RETURN n;2】条件筛选&#xff1a;查找所有名为 "Alice" 的人物节点。 MATCH (person:Person {name: Alice}) RETURN person;3】关系查询&#xff1a;查找所有和 &q…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...