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 …...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
