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

【LeetCode-面试经典150题-day20】

目录

70.爬楼梯

198.打家劫舍

139.单词拆分 

322.零钱兑换 

 300.最长递增子序列


 

70.爬楼梯

题意:

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

提示:

  • 1 <= n <= 45

【输入样例】n=2

【输出样例】2

解题思路:

1. 明确当爬到第一阶台阶的时候,只有一种做法,就是这一步爬1个台阶;爬到第二阶台阶的时候有两种做法,就是走2个1台阶或1次2台阶。

2.当你要爬到第n阶台阶的时候,你有两种选择,一种选择是最后一步走1个台阶,意味着你的爬法=走到n-1个台阶的爬法;第二种选择是最后一步走2个台阶,意味着你的爬法=走到n-2个台阶的爬法;所有走到n阶的爬法应该是走到n-1+走到n-2

3. 因为n的范围很小,用数组实现,如果要方便直接将num[1]和num[2]的值先赋值好的话,初始化不要写new int[n],不然需要先判断n是否大于1,是否大于2.

class Solution {public int climbStairs(int n) {int[] num=new int[50];num[1]=1;num[2]=2;for(int i=3;i<=n;i++){num[i] =  num[i-1]+num[i-2];}return num[n];}
}

时间: 击败了100.00%

内存: 击败了39.14%

198.打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

【输入样例】[1,2,3,1]

【输出样例】4

解题思路:

1.定义一个数组count存储打劫到第i家的时候可以获得的最高金额;

2.寻找关系,为了不触动警报的前提下获取最多金额,我们采取隔房打劫的思路,在第i家的时候,如果选择打劫第i家,那么其金额应该是nums[i]+count[i-2];如果不选择打劫第i家,到这里的的金额是count[i-1],要获得最高的金额,就需要比较哪一种做法金额较高;

3. 确定初始值,打劫第一家的时候,没有选择,count[1]=nums[1],打劫第二家也一样,不能触发警报,只能打劫本身count[2]=nums[2],但是,其也可以选择不打劫第二家,打劫第一家,即count[2]=max(nums[2],count[1])

class Solution {public int rob(int[] nums) {int len = nums.length;int[] count = new int[len];count[0] = nums[0];if(len >= 2 )count[1] = Math.max(nums[1],count[0]);for(int i = 2;i<len;++i){count[i] = Math.max(count[i-1],count[i-2]+nums[i]);}return count[len-1];}
}

时间: 击败了100.00%

内存: 击败了67.42%

139.单词拆分 

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

提示:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串 互不相同

【输入样例】s = "leetcode", wordDict = ["leet", "code"]

【输出样例】true

解题思路:

1. 定义数组dp[i],表示字符串长度为i时,是否可以拆解为一个或多个在字典中出现的单词,可以为true,不让为false;

2. dp[0]表示空字符串,此时默认为true

3. 字符串长度为i时,dp[i]的取值依靠什么?假设j<i,dp[j]=true且字符串字串(j,i]存在字典中,则dp[i]为true;

4. 遍历结束时将dp[s.length]return
5. 为了更好的判断字串(j,i]是否在字典中,先将字典转换成set

class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set = new HashSet<String>(wordDict);boolean[] dp = new boolean[s.length()+1];dp[0] = true;for(int i=1;i<=s.length();++i){for(int j=0;j  <i;++j){if(dp[j] && set.contains(s.substring(j,i))){dp[i] = true;break;//j这里不用再遍历了,从下一位i开始}}}return dp[s.length()];}
}

时间: 击败了66.63%

内存: 击败了70.02%

322.零钱兑换 

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

你可以认为每种硬币的数量是无限的。

【输入样例】coins = [1, 2, 5], amount = 11

【输出样例】3

11=5+5+1

解题思路:

1. 定义数组dp[i],表示凑足总额为i所需的最高硬币个数

2. 寻找规律,凑足金额为i-coins[j]的最少个数为dp[i-coins[j]],那么只需要加上一个硬币coins[j]即可获得dp[i],dp[i]取小min(dp[i],dp[i-coins[j]]+1);

3. 数组初始化,凑如总金额为0所需的钱币个数为0,dp[0]=0,其余的dp[i]下标为最大值,因为要进行min操作

class Solution {public int coinChange(int[] coins, int amount) {int max = Integer.MAX_VALUE;int[] dp = new int[amount+1];//初始化数组for(int i = 1; i< amount+1;++i){dp[i] = max;}dp[0] = 0;for(int j = 0;j < coins.length;++j){//从这个钱币开始for(int i = coins[j]; i <=amount; ++i){if(dp[i-coins[j]] != max){dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);}}}return dp[amount] == max ? -1 : dp[amount];}
}

时间: 击败了45.96%

内存: 击败了19.52%

 300.最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

【输入样例】nums = [10,9,2,5,3,7,101,18]

【输出样例】4

[2,3,7,101]

解题思路:

1. 定义数组dp[i],表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

2. 位置i的最长递增子序列等于j从0到i-1各个位置的最长递增子序列+1的最大值

3. dp[i]的默认大小为1,就是只选择本身的情况 

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];int res = 1;for(int i=0;i<nums.length;++i){dp[i] = 1;}for(int i = 1; i < nums.length; ++i){for(int j = 0;j < i; ++j){if(nums[i] > nums[j]){//递增子序列,所以要大才可以计算dp[i] = Math.max(dp[i],dp[j]+1);}res = Math.max(dp[i],res);}}return res;}
}

时间: 击败了25.90%

内存: 击败了15.18%

相关文章:

【LeetCode-面试经典150题-day20】

目录 70.爬楼梯 198.打家劫舍 139.单词拆分 322.零钱兑换 300.最长递增子序列 70.爬楼梯 题意&#xff1a; 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 提示&#xff1a; 1 < n < …...

回归与聚类算法系列②:线性回归

目录 1、定义与公式 2、应用场景 3、特征与目标的关系分析 线性回归的损失函数 为什么需要损失函数 损失函数 ⭐如何减少损失 4、优化算法 正规方程 梯度下降 优化动态图 偏导 正规方程和梯度下降比较 5、优化方法GD、SGD、SAG 6、⭐线性回归API 7、实例&#…...

springBoot:redis使用

需求&#xff1a;查询酒店房间列表 1、引入依赖 <!--redis--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency> 2、配置yml文件 server:port: 80…...

cmake 选择 vs编译器

QQ:2967732156 QQ交流群&#xff1a;622684416 // 编译VS2017版本的Tars&#xff0c; Release版本 // win32 cmake .. -G "Visual Studio 15 2017" -D CMAKE_BUILD_TYPERelease // x64 cmake .. -G "Visual Studio 15 2017 Win64" -D CMAKE_BUILD_…...

项目(智慧教室)第一部分:cubemx配置,工程文件的移植,触摸屏的检测,项目bug说明

第一章&#xff1a;需求与配置 一。项目需求 二。实现外设控制 注意&#xff1a; 先配置引脚&#xff0c;再配置外设。否则会出现一些不可预料的问题 1.时钟&#xff0c;串口&#xff0c;灯&#xff0c;蜂鸣器配置 &#xff08;1&#xff09;RCC配置为外部时钟&#xff0c;修…...

Springboot集成redis--不同环境切换

1.单机配置 spring:redis:mode: singletonhost: 127.0.0.1port: 6379lettuce:pool:max-active: 8 #连接池最大阻塞等待时间&#xff08;使用负值表示没有限制max-idle: 2 #连接池中的最大空闲连接min-idle: 1 #连接池最大阻塞等待时间&#xff08;使用负值表示没有限…...

稀疏数组的实现

文章目录 目录 文章目录 前言 一 什么是稀疏数组? 二 稀疏数组怎么存储数据? 三 稀疏数组的实现 总结 前言 大家好,好久不见了,这篇博客是数据结构的第一篇文章,望大家多多支持! 一 什么是稀疏数组? 稀疏数组&#xff08;Sparse Array&#xff09;是一种数据结构&a…...

表达式语言的新趋势!了解SPEL如何改变开发方式

文章首发地址 SpEL&#xff08;Spring Expression Language&#xff09;是一种表达式语言&#xff0c;由Spring框架提供和支持。它可以在运行时对对象进行解析和计算&#xff0c;用于动态地构建和操作对象的属性、方法和表达式。以下是SpEL的一些特性和功能&#xff1a; 表达式…...

一套成熟的实验室信息管理系统(云LIS源码)ASP.NET CORE

一套成熟的实验室信息管理系统&#xff0c;集前处理、检验、报告、质控、统计分析、两癌等模块为一体的网络管理系统。它的开发和应用将加快检验科管理的统一化、网络化、标准化的进程。 LIS把检验、检疫、放免、细菌微生物及科研使用的各类分析仪器&#xff0c;通过计算机联…...

NPM使用技巧

NPM使用技巧 前言技巧全局模块位置PowerShell报错安装模块冲突 NPM介绍NPM命令使用方法基本命令模块命令查看模块运行命令镜像管理 常用模块rimrafyarn 前言 本文包含NodeJS中NPM包管理器的使用技巧&#xff0c;具体内容包含NPM介绍、NPM命令、常用模块等内容&#xff0c;还包…...

java学习一

目录 Java 与 C 的区别 Java程序是编译执行还是解释执行 编译型语言 解释型语言 Java 与 C 的区别 Java 是纯粹的面向对象语言&#xff0c;所有的对象都继承自 java.lang.Object&#xff0c;C 兼容 C &#xff0c;不但支持面向对象也支持面向过程。Java 通过虚拟机从而实现…...

PV PVC in K8s

摘要 在Kubernetes中&#xff0c;PV&#xff08;Persistent Volume&#xff09;和PVC&#xff08;Persistent Volume Claim&#xff09;是用于管理持久化存储的重要资源对象。PV表示存储的实际资源&#xff0c;而PVC表示对PV的声明性要求。当应用程序需要使用持久化存储时&…...

SAP-PP:基础概念笔记-5(物料主数据的MRP1~4视图)

文章目录 前言一、MRP1视图Base Unit of Measure&#xff08;UoM&#xff09;MRP 组采购组ABC 指示器Plant-Specific Material Status 特定的工厂物料状态MRP 类型 MRP TypeMRP 类型 MRP TypeMaster Production Scheduling(MPS) 主生产计划基于消耗的计划(CBP)再订货点Reorder-…...

【C语言】初阶测试 (带讲解)

目录 ① 选择题 1. 下列程序执行后&#xff0c;输出的结果为( ) 2. 以下程序的输出结果是&#xff1f; 3. 下面的代码段中&#xff0c;执行之后 i 和 j 的值是什么&#xff08;&#xff09; 4. 以下程序的k最终值是&#xff1a; 5. 以下程序的最终的输出结果为&#xff…...

用huggingface.Accelerate进行分布式训练

诸神缄默不语-个人CSDN博文目录 本文属于huggingface.transformers全部文档学习笔记博文的一部分。 全文链接&#xff1a;huggingface transformers包 文档学习笔记&#xff08;持续更新ing…&#xff09; 本部分网址&#xff1a;https://huggingface.co/docs/transformers/m…...

unity 物体至视图中心以及新对象创建位置

如果游戏对象不在视野中心或在视野之外&#xff0c; 一种方法是双击Hierarchy中的对象名称 另一种是选中后按F 新建物体时对象的位置不是在坐标原点&#xff0c;而是在当前屏幕的中心...

船舶稳定性和静水力计算——绘图体平面图,静水力,GZ计算(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

Python 网页爬虫的原理是怎样的?

网页爬虫是一种自动化工具&#xff0c;用于从互联网上获取和提取信息。它们被广泛用于搜索引擎、数据挖掘、市场研究等领域。 网页爬虫的工作原理可以分为以下几个步骤&#xff1a;URL调度、页面下载、页面解析和数据提取。 URL调度&#xff1a; 网页爬虫首先需要一个初始的U…...

python技术面试题合集(二)

python技术面试题 1、简述django FBV和CBV FBV是基于函数编程&#xff0c;CBV是基于类编程&#xff0c;本质上也是FBV编程&#xff0c;在Djanog中使用CBV&#xff0c;则需要继承View类&#xff0c;在路由中指定as_view函数&#xff0c;返回的还是一个函数 在DRF中的使用的就是…...

【linux命令讲解大全】089.使用tree命令快速查看目录结构的方法

文章目录 tree补充说明语法选项列表选项文件选项排序选项图形选项XML / HTML / JSON 选项杂项选项 参数实例 从零学 python tree 树状图列出目录的内容 补充说明 tree 命令以树状图列出目录的内容。 语法 tree [选项] [参数]选项 列表选项 -a&#xff1a;显示所有文件和…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

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…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...