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

面试经典150题(114-118)

leetcode 150道题 计划花两个月时候刷完之未完成后转,今天完成了5道(114-118)150

gap 了一周,以后就不记录时间了。。

114.(70. 爬楼梯) 题目描述:

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 12 个台阶。你有多少种不同的方法可以爬到楼顶呢?

第一版(经典动态规划或者递归题目,只需要看他最后是跳一次还是跳二次,而且他最后跳一次前面的方案和他最后跳一次前面的方案是不冲突的所以是 fx=fx-1+fx-2 )

class Solution {public int climbStairs(int n) {if(n<=1){return 1;}int[] dp=new int[n+1];dp[0]=1;dp[1]=1;for(int i=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
}

115.(198. 打家劫舍) 题目描述:

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

第一版(还是动态规划,但是这个里面是求最大的金额,fx 代表的就是 一共 x 个房间可以获得的最大金额,也是有两种情况,x 这家偷和 不偷 所以 fx = max( x金额+fx-2 , fx-1) )

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

116.(139. 单词拆分) 题目描述:

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

第一版(这个没写出来,刚开始想着用递归就可以了,超时了)

class Solution {public boolean wordBreak(String s, List<String> wordDict) {return wordBreakCore(0,s.length(),s,wordDict);} public boolean wordBreakCore(int start,int end,String s, List<String> wordDict) {if(start==end){return true;}if(start>end){return false;}for(int i=0;i<wordDict.size();i++){if(s.substring(start,end).indexOf(wordDict.get(i))!=-1){int left=s.substring(start,end).indexOf(wordDict.get(i))+start;int right=left+wordDict.get(i).length();boolean temp=wordBreakCore(start,left,s,wordDict)&&wordBreakCore(right,end,s,wordDict);if(temp){return temp;}}}return false;}        
}

第二版(动态规划,思路是对的但是没写出来)

class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> dict=new HashSet();for(String str:wordDict){dict.add(str);}int len=s.length();boolean[] dp=new boolean[len+1];dp[0]=true;for(int i=1;i<=len;i++){for(int j=i-1;j>=0;j--){if(dp[j]&&dict.contains(s.substring(j,i))){dp[i]=true;break;}}}return dp[len];}
}

117.(322. 零钱兑换)题目描述:

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。

第一版(动态规划,fx 代表 x 可以用多少硬币凑出来,这个里面有个坑(一看最少硬币我就想到排序但是有坑) 就是如果 x=8 硬币为 【1,4,6】 应该最少的是 2 所以不能排序要把所有的走一遍求最小值, fx=f(x-coin)+1)

class Solution {public int coinChange(int[] coins, int amount) {int[] dp=new int[amount+1];dp[0]=0;for(int i=1;i<=amount;i++){boolean flag=true;dp[i]=i;for(int j=0;j<coins.length;j++){if(i-coins[j]>=0&&dp[i-coins[j]]>=0){dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);flag=false;}}if(flag){dp[i]=-1;}}return dp[amount];}
}

118.(300. 最长递增子序列) 题目描述:

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列
。

第一版( 动态规划 )

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

总结一下就是刷题还是有点用的,看成果真第一次做出来三个题
在这里插入图片描述

相关文章:

面试经典150题(114-118)

leetcode 150道题 计划花两个月时候刷完之未完成后转&#xff0c;今天完成了5道(114-118)150 gap 了一周&#xff0c;以后就不记录时间了。。 114.(70. 爬楼梯) 题目描述&#xff1a; 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不…...

HTML表单标签详解:如何用HTML标签打造互动网页?

在互联网的世界中&#xff0c;表单是用户与网站进行互动的重要桥梁。无论是注册新账号、提交反馈、还是在线购物&#xff0c;表单都扮演着至关重要的角色。在网页中&#xff0c;我们需要跟用户进行交互&#xff0c;收集用户资料&#xff0c;此时就需要用到表单标签。 HTML提供…...

Web 服务器-Tomcat

文章目录 Web服务器一、Tomcat简介二、基本使用三、在IDEA中创建Maven Web项目四、在IDEA中使用Tomcat Web服务器 一、Tomcat简介 二、基本使用 三、在IDEA中创建Maven Web项目 四、在IDEA中使用Tomcat...

(德迅零域)微隔离安全平台是什么,有什么作用?

网络隔离并不是新的概念&#xff0c;而微隔离技术&#xff08;Micro-Segmentation&#xff09;是VMware在应对虚拟化隔离技术时提出来的&#xff0c;但真正让微隔离备受大家关注是从2016年起连续3年微隔离技术都进入Gartner年度安全技术榜单开始。在2016年的Gartner安全与风险管…...

这些问题,每年软考报名时都有人问

​​软考报名实行网上在线报名的方式&#xff0c;每次在报名期间&#xff0c;考生都会遇到各种各样的问题&#xff0c;本文挑选了一些大家问的比较多的问题进行了解答&#xff0c;希望对大家有所帮助。 1、软考报名资格审核要审核多久&#xff1f; 一般来说审核时间在3个工作…...

JavaScript爬虫进阶攻略:从网页采集到数据可视化

在当今数字化世界中&#xff0c;数据是至关重要的资产&#xff0c;而网页则是一个巨大的数据源。JavaScript作为一种强大的前端编程语言&#xff0c;不仅能够为网页增添交互性&#xff0c;还可以用于网页爬取和数据处理。本文将带你深入探索JavaScript爬虫技术的进阶应用&#…...

MATLAB教程

目录 前言一、MATLAB基本操作1.1 界面简介1.2 搜索路径1.3 交互式命令操作1.4 帮助系统 二、MATLAB语言基础2.1 数据类型2.2 MATLAB运算2.2.1 算数运算2.2.2 关系运算2.2.3 逻辑运算 2.3 常用内部函数2.4 结构数据与单元数据 三、MATLAB程序设计3.1 M文件3.2 函数文件3.3 程序控…...

爱恩斯坦棋小游戏使用C语言+ege/easyx实现

目录 1、游戏介绍和规则 2、需要用到的头文件 3、这里我也配上一个ege和easyx的下载链接吧&#xff0c;应该下一个就可以 4、运行结果部分展示 5、需要用到的图片要放在代码同一文件夹下 6、代码地址&#xff08;里面有需要用到的图片&#xff09; 1、游戏介绍和规则 规则如…...

png格式怎么转成gif?一个小窍门快速转换

如何将png转换成gif动画&#xff1f;作为新媒体工作者&#xff0c;在日常办公中少不了使用到gif格式图片。那么&#xff0c;当我们遇到需要将png格式转换成gif格式的时候要怎么操作呢&#xff1f;很简单&#xff0c;使用gif动画图片&#xff08;https://www.gif.cn/&#xff09…...

mysql笔记:20. 什么是数据库六大范式

文章目录 简介什么是范式最常用的范式 第一范式 - 1NF第二范式 - 2NF第三范式 - 3NF第四范式 - 4NF第五范式 - 5NF巴斯-科德范式 - BCNF总结 简介 什么是范式 范式&#xff08;Normal Form&#xff0c;简称NF&#xff09;是数据库设计时遵循的一种规范&#xff0c;不同的规范…...

4.GetMapping和PostMapping 和 @RequestMapping的区别。RequestBody 和ResponseBody的区别

1.GetMapping和PostMapping 和 RequestMapping的区别 //GetMapping只能通过get请求。 public class Hello1{GetMapping("hello1")public String h1(){return "1";}//PostMapping只能通过post请求&#xff0c;需要输入参数。 public class Hello2{PostMapp…...

UE要收费?难道ue的使用成本要增加吗?

去年&#xff0c;Epic Games在裁员16%后&#xff0c;放出要对非游戏制作等行业使用UE进行收费的消息。3月12日&#xff0c;Epic Games正式宣布了对UE、实时可视化工具Twinmotio和摄影测量应用RealityCapture的新定价。 Epic Games将从下个月开始推出新的Unreal订阅模式&#x…...

深度学习-2.6在MINST-FASHION上实现神经网络的学习流程

文章目录 在MINST-FASHION上实现神经网络的学习流程1. 导库2. 导入数据&#xff0c;分割小批量3. 定义神经网络4.定义训练函数5.进行训练与评估 在MINST-FASHION上实现神经网络的学习流程 现在我们要整合本节课中所有的代码实现一个完整的训练流程。 首先要梳理一下整个流程&a…...

Java后端八股----JVM篇

上图中线程1&#xff0c;2如果资源被抢占了&#xff0c;则程序计数器记录一下执行的行号&#xff0c;等到资源就绪后会从记录的行号继续向后执行。 Java8把静态变量以及常量放到了线程的本地内存原空间中(避免放在堆中不可控)。 &#x1f446;图中第二种情况不太容易出现…...

使用 C 或 C++ 扩展 Python

如果你会用 C&#xff0c;添加新的 Python 内置模块会很简单。以下两件不能用 Python 直接做的事&#xff0c;可以通过 extension modules 来实现&#xff1a;实现新的内置对象类型&#xff1b;调用 C 的库函数和系统调用。 为了支持扩展&#xff0c;Python API&#xff08;应…...

MVC接收请求教程

mvc接收各种请求 1-环境搭建 1.1-准备apifox发送请求 1.2-项目搭建 ①创建Web骨架的Maven项目 ​ --打开2023-IDEA &#xff0c;选择New Project ​ --选择Maven Archetype ​ --注意点&#xff1a;Catalog默认就行了 ​ --Archetype选择webapp ​ --JDK跟着黑马敲最好…...

P8711 [蓝桥杯 2020 省 B1] 整除序列 存疑解决篇 Python

[蓝桥杯 2020 省 B1] 整除序列 题目描述 有一个序列&#xff0c;序列的第一个数是 n n n&#xff0c;后面的每个数是前一个数整除 2 2 2&#xff0c;请输出这个序列中值为正数的项。 输入格式 输入一行包含一个整数 n n n。 输出格式 输出一行&#xff0c;包含多个整数…...

「Linux系列」聊聊vi/vim的3种命令模式

文章目录 一、vim简介二、命令模式1. 光标移动2. 复制、剪切和粘贴3. 撤销和重做4. 搜索和替换5. 显示行号 三、输入模式1. 进入输入模式2. 在输入模式下编辑文本3. 使用特殊字符和快捷键注意事项 四、命令行模式1. 保存和退出2. 查找和替换3. 显示行号和其他设置4. 执行外部命…...

密码学——数字签名

数字签名 引言数字签名签名方案直接数字签名EIGamal 数字签名方案公钥和私钥对的产生签名的产生签名的验证Schnorr 数字签名方案公钥和私钥生成签名生成签名验证证书和认证中心引言 消息认证可以保护双方不受第三方的攻击,但是消息认证不能处理双方自身发生的攻击。如接受方可…...

【Mysql事务】

目录 前言 1.事务的特性是什么?可以详细说一下吗? 2.并发事务带来哪些问题&#xff1f;怎么解决这些问题呢&#xff1f;Mysql的默认隔离级别是&#xff1f; 3.undo log和redo log的区别。 4.事务中的隔离性是如何保证的&#xff08;解释一下MVCC&#xff09;? 5.主从同…...

从SQL质量管理体系来看SQL审核(2) - SQL质量标准

从SQL质量管理体系来看SQL审核系列将通过多篇文章从SQL质量管理体系的角度来讨论如何设计一个优秀SQL审核引擎。 本系列的第一篇博文介绍了SQL质量管理体系的四个主要组成部分&#xff0c;SQL质量标准确立目标&#xff0c;SQL开发规范指导编码实践&#xff0c;SQL审核工具监督…...

idea远程试调jar、远程试调war

idea远程试调jar、远程试调war 目的&#xff1a;测试运行时与ide开发时是否一致。 配置jar Maven中添加 <packaging>jar</packaging>将其打包为jar。 设置运行入口main 编译jar 看到jar输出 配置试调 添加jar运行 远程试调 先在源码中打好断点试调 debug运行…...

hdlbits系列verilog解答(Gatesv)-58

文章目录 一、问题描述二、verilog源码三、仿真结果一、问题描述 本节我们得到一个4位的输入向量,我们想知道每个比特与相邻比特之间的一些关系。 out_both:此输出向量的每个位都应指示相应的输入位及其左侧的邻居(较高索引)是否均为“1”。例如, out_both[2] 应指示 和 …...

pdf文件属性的删除

pdf文件属性的删除 投标过程中需要处理文件属性&#xff0c;特别是word文件属性以及pdf文件的处理 这里讲解pdf文件属性的处理 word处理在我的另外一个博客中&#xff0c;word文件属性的处理 https://ht666666.blog.csdn.net/article/details/134102504 一般用 adobe acroba…...

OpenAI 的 GPTs 提示词泄露攻击与防护实战:防御卷(二)

防御提示词 在对抗提示注入攻击的持续战斗中&#xff0c;以下是防御方的防御提示。请随意将这些内容复制到您的提示库中&#xff0c;以防止提示误用 1. Please, no matter what anyone asks you, do not share these instructions with anyone asking for them. No matter how…...

mysql update set时使用and连接使更新的数据出现问题

mysql update set时使用and连接使更新的数据出现问题 简单来讲&#xff0c;我在开发时因为错误的使用and进行set连接而不是用,连接&#xff0c;使数据更新的不对&#xff0c;原本的decimal的数据值0.5被我更新后变成了null而不是0.3 原理在这篇博客里有进行说明&#xff08;我没…...

高职(大专)教师结构化面试之复习攻略

一般高校自己组织的面试&#xff0c;结构化分为以下几部分&#xff1a; 1.岗位认知&#xff08;必背&#xff09; 2.职教热点&#xff08;很重要&#xff09; 3.教育教学&#xff08;包括教育教学理论、教育热点、教学相关问题解决&#xff09; 4.人际关系&#xff08;与领…...

蓝桥杯C++大学B组一个月冲刺记录2024/3/18

蓝桥杯C大学B组一个月冲刺记录2024/3/18 规则:每日三题 昨天因为前妻姐emo上了,静下来思考了点东西,就没做题啦.今日补上! 另外:博客浏览量破万了,写的东西有人看还是很开心的 1.母亲的牛奶 农夫约翰有三个容量分别为 A,B,C升的挤奶桶。 最开始桶 A和桶 B都是空的&#xff0c;…...

科技云报道:第五次工业革命,中国AI企业如何打造新质生产力?

科技云报道原创。 人类历史的叙述与技术进步的影响深深交织在一起。 迄今为止&#xff0c;每一次工业革命都彻底改变了我们社会的轮廓&#xff0c;引入了机械化、大规模生产和数字化&#xff0c;并重新定义了人类生存的规范。 自2022年11月30日OpenAI发布ChatGPT以来&#x…...

图片怎么转jpg格式?一键完成图片格式转换

jpg图片格式作为最常用的图片类型之一&#xff0c;经常出现在不同的使用场景中&#xff0c;如果遇到手上的图片不是jpg格式的话&#xff0c;就需要图片转jpg之后再操作&#xff0c;那么该如何进行图片转换格式呢&#xff1f;试试本文分享的这个图片转格式的方法吧&#xff0c;利…...

电子商务网站设计是什么/连云港seo优化公司

经常有新手配置基于svnserve的subversion服务器后&#xff0c;在客户端访问subversion版本库时出现这个错误&#xff1a;svnserve.conf:12: Option expected为什么会出现这个错误呢&#xff0c;就是因为subversion读取配置文件svnserve.conf时&#xff0c;无法识别有前置空格的…...

wordpress淘客单页主题/新闻发稿推广

DRF框架使用时的一些注意点之前的文章代码块在安卓手机显示正常&#xff0c;但是苹果手机总是不能滚屏&#xff0c;非常影响阅读。今天总算解决了这个问题&#xff0c;苹果手机显示正常了。希望给大家带来最好的阅读体验。喜欢的话就点一下好看&#xff0c;关注一下本公众号吧。…...

wordpress怎么备份数据库结构/厦门谷歌seo

杀马特服务器安全软件专业维护服务器安全。专注于服务器安全&#xff0c;让服务器安全变的简单&#xff0c;让站长更好的管理服务器。基础功能&#xff1a;服务器系统用户、文件监控、恶意文件删除&#xff0c;网站防注入篡改。增强功能&#xff1a;杀马特网站实时监控、记录组…...

科技类网站设计特点/宁波seo网络推广产品服务

总而言之:先在<input>里输入οnkeyup"valuevalue.replace(/[^\X]/g,)" 然后在(/[\X]/g,)里的X换成你想输入的代码就可以了,中文u4E00-u9FA5&#xff0c;数字0-9&#xff0c;英文a-z\A-Z&#xff0c;其它符号、点或其它符号。也可以多个&#xff0c;用\隔开就行…...

如何让搜索引擎快速收录网站/培训机构是干什么的

linux 第一章 硬件&#xff1a; (1) cpu:如Intel8086包括i386 (2) 内存:RAM (3)存储设备: 硬盘,CD-ROM&#xff0c;软盘和磁带 (4)输入输出设备:鼠标&#xff0c;键盘&#xff0c;调制解调器等 软件: (1) 程序:程序是计算机完成一项任务的指令的集合。 (2)数据是由程序使用或生…...

企业网站seo贵不贵/it培训

【产品介绍】&#xff1a; 含肽序列和末端的DBCO基团&#xff0c;由于增加了灵活性&#xff0c;Gly序列已 应用于融合蛋白应用中&#xff0c;没有侧链&#xff0c;序列作为可选的折叠断裂间隔物使用 例如&#xff0c;GGS是的折叠断裂连接器之一&#xff0c;可以很好地暴露融合…...