程序员的算法趣题:Q15 走楼梯(Java版)

2024-02-19 13:59

本文主要是介绍程序员的算法趣题:Q15 走楼梯(Java版),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目说明

A从底部上楼梯时,B从该楼梯的顶部往下走。
每次不一定只走 1 级,最多可以一次跳过 3 级(即直接前进 4 级)。
但无论走多少级,1 次移动所需时间不变。
两人同时开始走,求共有多少种“两人最终同时停在同一级”的情况
(假设楼梯宽度足够,可以相互错开,不会撞上。另外,同时到达同一级时视为结束)。

思路1

1.A上楼,一次走1~4级台阶;B下楼,一次走1~4级台阶
2.用双重循环罗列出A和B这一步所走的台阶数的所有可能性
3.当A所在的台阶级数比B所在的台阶级数大时,结束递归(A和B已经错过了)
4.A和B处在同一级时,正确答案+1

代码1

public static void main(String[] args) {// A的起点:0级台阶// B的起点:10级台阶// 每一步可以走的最大台阶数:4System.out.println(move(0, 10, 4));
}
/*** A从a出发上楼;B从b出发下楼。* 统计同时到达同一级台阶的走法有多少种* @param a     A所处的级数* @param b     B所处的级数* @param max   一步最多移动的级数* @return      正确答案的个数*/
public static int move(int a, int b, int max) {if (a > b) return 0;if (a == b) return 1; // 到达相同台阶,正确答案+1int count = 0;// 双重循环罗列了A和B这一步的所有可能性for (int i = 1; i <= max; i++) {     // 这一步:A上楼走的台阶数for (int j = 1; j <= max; j++) { // 这一步:B下楼走的台阶数count += move(a + i, b - j, max);}}return count;
}

代码1优化版(时间性能)

此种递归方式随着递归层级变多,耗时较大。(实测30层台阶,耗时5300ms+。优化后耗时10ms~20ms,粗略计算时间性能提升200+倍)
可以采用“内存化”的方法,把计算过的数据存入map中,下次计算同样的递归时,直接从map中获取结果,避免重复计算,进而提示时间效率。

// 键:a,b 值:move(a,b)的结果(说明:a和b表示具体的数字)
public static Map<String,Integer> hmap = new HashMap<>();
public static void main(String[] args) {long start = System.currentTimeMillis(); // 当前系统时间 ms值System.out.println(move(0, 30, 4));long end = System.currentTimeMillis(); // 当前系统时间 ms值System.out.println((end-start)+" ms"); // 30级 5425 ms ==> 10 ms
}
public static int move(int a, int b, int max) {if (a > b) return 0;if (a == b) return 1;// 如果map中已经计算过该结果,则直接获取即可if(hmap.containsKey(a+","+b)) return hmap.get(a+","+b);int count = 0;for (int i = 1; i <= max; i++) {for (int j = 1; j <= max; j++) {count += move(a + i, b - j, max);}}// 将本次计算结果存入map,下次需要重复计算时直接去map中拿结果hmap.put(a+","+b, count); return count;
}

思路2

1.A走“偶数”步到达B的情况就是我们想要的结果(“偶数”步意味着一定存在某一级台阶到达A、B两点的步数相同)
2.动态规划:第n步时,站在t级台阶的情况数量,取决于前一步(第n-1步)时(t-4)到(t-1)四级台阶的情况数量之和

示意图
走楼梯

Q15走楼梯
补充说明:空白区域的值为0

代码2

public static void main(String[] args) {int N = 10;     // 最高台阶级数(B所在的台阶级数)int STEPS = 4;  // 一步最多走几级台阶int[] arr = new int[N + 1];     // [0,N] 算上辅助计算的起点(A点),共N+1个元素arr[0] = 1;     // 辅助计算的值。可以理解为:走0步时,到达起点(A点)的情况只有这一种int count = 0;  // 统计正确答案的数量// i表示走的步数,一共N级台阶,最大不超过N步// 举例:当i=3时,arr[10]的值表示走3步到达第10级台阶(B点)有几种走法,从示意图可知有6种走法for(int i = 1; i <= N ; i ++){// 计算走了i步时,到达各级台阶的走法有多少种for(int j = N; j >= i; j --){   // 从最后一级依次往前计算(后面的值是前面4个元素的旧值,所以需要从后往前计算)arr[j] = 0;                 // 清除当前位置的旧值for(int k = 1; k <= STEPS; k ++){     // 表示(j-1) ~ (j-4) 前4个元素arr[j] += j-k < 0 ? 0 : arr[j-k]; // 如果下标为负,避免下标越界,直接赋值为0}}arr[i-1] = 0; // 清除之前位置的旧值(走i步,则最少站在i级台阶上,之前台阶上的数据要清空)System.out.println(Arrays.toString(arr)); // 查看每一步到达各级台阶的情况if(i%2 == 0) count += arr[N]; // 偶数步到达B级台阶(B点)的步数要计入正确答案,可以参考示意图}System.out.println("count = " + count); // 201
}

结果

201

这篇关于程序员的算法趣题:Q15 走楼梯(Java版)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/724883

相关文章

SpringBoot中四种AOP实战应用场景及代码实现

《SpringBoot中四种AOP实战应用场景及代码实现》面向切面编程(AOP)是Spring框架的核心功能之一,它通过预编译和运行期动态代理实现程序功能的统一维护,在SpringBoot应用中,AO... 目录引言场景一:日志记录与性能监控业务需求实现方案使用示例扩展:MDC实现请求跟踪场景二:权限控制与

Java NoClassDefFoundError运行时错误分析解决

《JavaNoClassDefFoundError运行时错误分析解决》在Java开发中,NoClassDefFoundError是一种常见的运行时错误,它通常表明Java虚拟机在尝试加载一个类时未能... 目录前言一、问题分析二、报错原因三、解决思路检查类路径配置检查依赖库检查类文件调试类加载器问题四、常见

Java注解之超越Javadoc的元数据利器详解

《Java注解之超越Javadoc的元数据利器详解》本文将深入探讨Java注解的定义、类型、内置注解、自定义注解、保留策略、实际应用场景及最佳实践,无论是初学者还是资深开发者,都能通过本文了解如何利用... 目录什么是注解?注解的类型内置注编程解自定义注解注解的保留策略实际用例最佳实践总结在 Java 编程

Java 实用工具类Spring 的 AnnotationUtils详解

《Java实用工具类Spring的AnnotationUtils详解》Spring框架提供了一个强大的注解工具类org.springframework.core.annotation.Annot... 目录前言一、AnnotationUtils 的常用方法二、常见应用场景三、与 JDK 原生注解 API 的

Java controller接口出入参时间序列化转换操作方法(两种)

《Javacontroller接口出入参时间序列化转换操作方法(两种)》:本文主要介绍Javacontroller接口出入参时间序列化转换操作方法,本文给大家列举两种简单方法,感兴趣的朋友一起看... 目录方式一、使用注解方式二、统一配置场景:在controller编写的接口,在前后端交互过程中一般都会涉及

Java中的StringBuilder之如何高效构建字符串

《Java中的StringBuilder之如何高效构建字符串》本文将深入浅出地介绍StringBuilder的使用方法、性能优势以及相关字符串处理技术,结合代码示例帮助读者更好地理解和应用,希望对大家... 目录关键点什么是 StringBuilder?为什么需要 StringBuilder?如何使用 St

使用Java将各种数据写入Excel表格的操作示例

《使用Java将各种数据写入Excel表格的操作示例》在数据处理与管理领域,Excel凭借其强大的功能和广泛的应用,成为了数据存储与展示的重要工具,在Java开发过程中,常常需要将不同类型的数据,本文... 目录前言安装免费Java库1. 写入文本、或数值到 Excel单元格2. 写入数组到 Excel表格

Java并发编程之如何优雅关闭钩子Shutdown Hook

《Java并发编程之如何优雅关闭钩子ShutdownHook》这篇文章主要为大家详细介绍了Java如何实现优雅关闭钩子ShutdownHook,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 目录关闭钩子简介关闭钩子应用场景数据库连接实战演示使用关闭钩子的注意事项开源框架中的关闭钩子机制1.

Maven中引入 springboot 相关依赖的方式(最新推荐)

《Maven中引入springboot相关依赖的方式(最新推荐)》:本文主要介绍Maven中引入springboot相关依赖的方式(最新推荐),本文给大家介绍的非常详细,对大家的学习或工作具有... 目录Maven中引入 springboot 相关依赖的方式1. 不使用版本管理(不推荐)2、使用版本管理(推

Java 中的 @SneakyThrows 注解使用方法(简化异常处理的利与弊)

《Java中的@SneakyThrows注解使用方法(简化异常处理的利与弊)》为了简化异常处理,Lombok提供了一个强大的注解@SneakyThrows,本文将详细介绍@SneakyThro... 目录1. @SneakyThrows 简介 1.1 什么是 Lombok?2. @SneakyThrows