java面试题,上楼梯有多少种方式
java面试题,上楼梯有多少种方式
题目:一个小孩上一个N级台阶的楼梯,他可以一次走1阶、2阶或3阶,那么走完N阶有多少种方式。
很自然的想法是使用递归:
public class Test04 {
public static int countWays(int n) {
if(n < 0) {
return 0;
}
else if(n == 0) {
return 1;
}
else {
return countWays(n - 1) + countWays(n - 2) + countWays(n - 3);
}
}
public static void main(String[] args) {
System.out.println(countWays(5)); // 13
// 11111, 1112, 1121, 1211, 122, 131, 113, 23, 221, 2111, 212, 32, 311
}
}
然而,这里的递归是一个头递归,也就是说要先递归再回溯(编译器无法将其优化为一个循环结构),而且是将三个递归的结果进行合并,这样的话算法的运行时间呈指数增长(渐近时间复杂度为O(3^N))。可以利用动态规划的思想对递归进行优化,其代码如下所示:
public class Test04 {
public static int countWaysDP(int n) {
int[] map = new int[n + 1];
for (int i = 0; i < map.length; i++) {
map[i] = -1;
}
return countWaysDP(n, map);
}
private static int countWaysDP(int n, int[] map) {
if (n < 0) {
return 0;
}
else if (n == 0) {
return 1;
}
else if (map[n] > -1) {
return map[n];
}
else {
map[n] = countWaysDP(n - 1, map) + countWaysDP(n - 2, map)
countWaysDP(n - 3, map);
return map[n];
}
}
public static void main(String[] args) {
System.out.println(countWaysDP(5)); // 13
// 11111, 1112, 1121, 1211, 122, 131, 113, 23, 221, 2111, 212, 32, 311
}
}
相关文章:
java面试题,上楼梯有多少种方式
java面试题,上楼梯有多少种方式 题目:一个小孩上一个N级台阶的楼梯,他可以一次走1阶、2阶或3阶,那么走完N阶有多少种方式。 很自然的想法是使用递归: public class Test04 { public static int countWays(int n) {…...
8.HTTP工作原理
HTTP是什么 HTTP工作原理 HTTP协议的请求类型和响应状态码 总结 1.HTTP是什么 HTTP超文本传输协议就是在一个网络中上传下载文件的一套规则 2.HTTP工作原理 HTTP超文本传输协议的本质是TCP通信,链接—>请求—>响应—>断开 3.HTTP协议的请求类型和响应状…...
环境部署的学习笔记(Docker)
1 前言 在现场测试时,常常需要在现场机器上搭建开发环境,此时使用容器会是一个比较方便的途径; 2 常见的容器技术 2.1 Docker⭐️31k:目前使用最为广泛的容器技术 2.2 Nix⭐️13.8k:镜像文件占用会比Docker少 Chat…...
Navicat在分辨率不同的屏幕窗口显示大小不一致问题解决
1.主屏幕为2560*1600分辨率,能够显示较多数据连接 2.在第二屏幕分辨率低,字体变大,显示内容变少 解决办法: 1.右击navicat图标-属性 2.选择【兼容性】-在兼容性页面中选择**“更改高DPI设置”** 3…勾选“高DPI缩放替代”&a…...
通过代码搞明白JAVA中值传递和引用传递
public static void main(String[] args) {Map a new HashMap();a.put("a", 1);System.out.println(a "我在main中的值");aaa(a);System.out.println(a "我在main中的值");bbb(a);System.out.println(a "我在main中的值");int b …...
ambari 开启hdfs回收站机制
hdfs回收站类似于我们常用的windows中的回收站,被删除的文件会被暂时存储于此,和回收站相关的参数有两个: fs.trash.interval:默认值为0 代表禁用回收站,其他值为回收站保存文件时间,单位为分钟 fs.trash…...
服务器数据恢复—服务器重装系统导致逻辑卷发生改变的数据恢复案例
服务器数据恢复环境: 某品牌linux操作系统服务器,服务器中有4块SAS接口硬盘组建一组raid5阵列。服务器中存放的数据有数据库、办公文档、代码文件等。 服务器故障&检测: 服务器在运行过程中突然瘫痪,管理员对服务器进行了重装…...
软件工程之架构设计
从公众号转载,关注微信公众号掌握更多技术动态 --------------------------------------------------------------- 一、架构设计的目的 1.什么是复杂的软件项目 复杂的软件项目通常有两个特点: 需求不确定 技术复杂 技术的复杂性主要体现在四个方面…...
oracle java.sql.SQLException: Invalid column type: 1111
1.遇到的问题 org.mybatis.spring.MyBatisSystemException: nested exception is org.apache.ibatis.type.TypeException: Could not set parameters for mapping: ParameterMapping{propertyuuid, modeIN, javaTypeclass java.lang.String, jdbcTypenull, numericScalenull, r…...
Mac 浏览器下载的文件名总是「乱码」
如果可以实现记得点赞分享,谢谢老铁~ 本文所说的方法是在出现文件名乱码情况下,如何恢复文件名的正确中文名称,并非一劳永逸地避免乱码的出现。这是由于下载文件名称乱码的出现,往往是系统、浏览器、网站三方面因素共…...
Redis Reactor事件驱动模型源码
前置学习:Redis server启动源码-CSDN博客 1、Redis服务器启动的时候就会就一直在轮询。 // 运行事件处理器,一直到服务器关闭为止 aeSetBeforeSleepProc(server.el,beforeSleep); aeMain(server.el);// 服务器关闭,停止事件循环 aeDeleteEven…...
cv2.error: OpenCV(4.7.0)
运行hsv脚本报错: cv2.error: OpenCV(4.7.0) D:\a\opencv-python\opencv-python\opencv\modules\imgproc\src\color.cpp:182: error: (-215:Assertion failed) !_src.empty() in function cv::cvtColor 解决方案: 这个错误信息是在使用OpenCV的cvtColor函…...
10.vue3项目(十):spu管理页面的sku的新增和修改
目录 一、sku静态页面的搭建 1.思路分析 2.代码实现 3.效果展示...
Java LeetCode篇-深入了解二叉树经典解法(三种方式实现:获取二叉树的最大深度)
🔥博客主页: 【小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍ 文章目录 1.0 对称二叉树 1.1 判断对称二叉树实现思路 1.2 代码实现:判断对称二叉树 2.0 二叉树的最大深度 2.1 使用递归实现获取二叉树的最大深度思路 2.2 代码实…...
Image Segmentation Using Deep Learning: A Survey
论文标题:Image Segmentation Using Deep Learning:A Survey作者:发表日期:阅读日期 :研究背景:scene understanding,medical image analysis, robotic perception, video surveillance, augmented reality, and image…...
可视化开源编辑器Swagger Editor本地部署并实现远程访问管理编辑文档
最近,我发现了一个超级强大的人工智能学习网站。它以通俗易懂的方式呈现复杂的概念,而且内容风趣幽默。我觉得它对大家可能会有所帮助,所以我在此分享。点击这里跳转到网站。 文章目录 Swagger Editor本地接口文档公网远程访问1. 部署Swagge…...
Java TCP协议实现一对一聊天与UDP协议实现群聊案例
JavaTCP协议实现一对一聊天与UDP协议实现群聊案例 1.TCP协议实现一对一聊天 1.1服务端运行结果 1.2客服端运行结果 1.3代码汇总 服务端 package twentyone;import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.…...
【从0配置JAVA项目相关环境1】jdk + VSCode运行java + mysql + Navicat + 数据库本地化 + 启动java项目
从0配置JAVA项目相关环境 写在最前面一、安装Java的jdk环境1. 下载jdk2. 配置jdk3. 配置环境变量 二、在vscode中配置java运行环境1. 下载VSCode2. 下载并运行「Java Extension Pack」 三、安装mysql1.官网下载MySQL2.开始安装如果没有跳过安装成功 3.配置MySQL Server4.环境变…...
人工智能_机器学习053_支持向量机SVM目标函数推导_SVM条件_公式推导过程---人工智能工作笔记0093
然后我们再来看一下支持向量机SVM的公式推导情况 来看一下支持向量机是如何把现实问题转换成数学问题的. 首先我们来看这里的方程比如说,中间的黑线我们叫做l2 那么上边界线我们叫l1 下边界线叫做l3 如果我们假设l2的方程是上面这个方程WT.x+b = 0 那么这里 我们只要确定w和…...
二叉树的前、中和后序遍历的递归与迭代实现
1. 前序遍历 1.1 递归 /*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? null : right)* }*/ /*** param …...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
