题目链接：题目链接
题面：
小王最近得到了一艘神奇的飞船，这艘飞船只有两个脚踏板，分别是油门和刹车，飞船的原始速度 N。
假设飞船的现有速度为 X，每当小王踩一下油门后，就会加速到 X * X。
假设飞船的现有速度为 Y，每当小王踩一下刹车后，飞船速度就会减速到 Y - 1。
这并不神奇，神奇的是飞船会出一道题，如果飞船驾驶员能正确解答这道题，就可以召唤出一条神龙，实现驾驶者的一个愿望。飞船出题的内容是求出踩脚踏板后达到预定的速度 M(0 < M < 400000)的最少次数。
小王特别想有一个女朋友陪他一起遨游太空，你能帮助小王解决这个问题让他召唤出神龙满足有女朋友的愿望吗？
本次挑战需要你至少了解一些 Java 中诸如流程控制、数组、集合或队列的使用。
知识点
- 队列/背包的基本使用
- 广度优先搜索
- 最佳解决方案
初始代码
import java.util.*; public class SpaceShip{ public static int fly(int N,int M){ int ans = 0; //代码编辑区 开始 //代码编辑区 结束 return ans; } public static void main(String[] args) { //测试用例 System.out.printf("从%d 到 %d 最少需要踩:%d 次,正确答案为3次.\n",2,15,fly(2, 15)); System.out.printf("从%d 到 %d 最少需要踩:%d 次,正确答案为5次.\n",5,21,fly(5, 21)); System.out.printf("从%d 到 %d 最少需要踩:%d 次,正确答案为13次.\n",5,30,fly(5, 30)); System.out.printf("从%d 到 %d 最少需要踩:%d 次,正确答案为26次.\n",5,125,fly(5, 125)); System.out.printf("从%d 到 %d 最少需要踩:%d 次,正确答案为78次.\n",5,173010,fly(5, 173010)); System.out.printf("从%d 到 %d 最少需要踩:%d 次,正确答案为752次.\n",11,200000,fly(11, 200000)); System.out.printf("从%d 到 %d 最少需要踩:%d 次,正确答案为2次.\n",52,50,fly(52, 50)); } }
样例说明
输入初始速度 N 和目标速度 M，输出踩脚踏板的最小次数。
如初始速度 N = 2，目标速度为 15，只需依次踩油门、油门、刹车即可达到，最少只需要踩 3 次。
如初始速度 N = 52，目标速度为 50，只需依次踩刹车、刹车即可达到，最少只需要踩 2 次。
刹车与油门可以只踩一种或交替进行踩踏。
题解
考察 Java 队列和 bfs 的使用，当然也可以用动态规划的思想去解决问题，对于初始速度 N 和目标速度 M，需要考虑到下列三种情况。
1 初始速度 N >= 目标速度 M，答案为 N - M，因为小王只能通过踩刹车减速。
2 初始速度 N < 目标速度 M，小王可以通过踩油门或刹车控制速度，使用广搜思想分类讨论，最终得出答案。
参考代码如下：
import java.util.*; public class SpaceShipAns{ // 请勿修改 fly() 的方法名和参数类型 public static int fly(int n,int m){ int ans = 0; //代码编辑区 开始 if(n >= m) { return n - m; } init(); integerList.set(n,0); q.add(new NodeVo(0,n)); while(q.size() > 0) { NodeVo vo = q.peek(); q.poll(); if(integerList.get(vo.getId()) < vo.getT()) { continue; } if(vo.getId() <= 632) { int index = vo.getId() * vo.getId(); int t = vo.getT() + 1; if(integerList.get(index) > t) { integerList.set(index,t); q.add(new NodeVo(t,index)); } } if(vo.getId() > 2) { int index = vo.getId() - 1; int t = vo.getT() + 1; if(integerList.get(index) > t) { integerList.set(index,t); q.add(new NodeVo(t,index)); } } } ans = integerList.get(m); //代码编辑区 结束 return ans; } public static void main(String[] args) { //测试用例 System.out.printf((Objects.equals(3,fly(2, 15)) ? "【√正确】" : "【X错误】") + "从%d 到 %d 最少需要踩:%d 次,正确答案为 3 次\n",2,15,fly(2, 15)); System.out.printf((Objects.equals(5,fly(5, 21)) ? "【√正确】" : "【X错误】") + "从%d 到 %d 最少需要踩:%d 次,正确答案为 2 次\n",5,21,fly(5, 21)); System.out.printf((Objects.equals(13,fly(5, 30)) ? "【√正确】" : "【X错误】") + "从%d 到 %d 最少需要踩:%d 次,正确答案为 13 次\n",5,30,fly(5, 30)); System.out.printf((Objects.equals(26,fly(5, 125)) ? "【√正确】" : "【X错误】") + "从%d 到 %d 最少需要踩:%d 次,正确答案为 26 次\n",5,125,fly(5, 125)); System.out.printf((Objects.equals(78,fly(5, 173010)) ? "【√正确】" : "【X错误】") + "从%d 到 %d 最少需要踩:%d 次,正确答案为 78 次\n",5,173010,fly(5, 173010)); System.out.printf((Objects.equals(752,fly(11, 200000)) ? "【√正确】" : "【X错误】") + "从%d 到 %d 最少需要踩:%d 次,正确答案为 752 次\n",11,200000,fly(11, 200000)); System.out.printf((Objects.equals(2,fly(52, 50)) ? "【√正确】" : "【X错误】") + "从%d 到 %d 最少需要踩:%d 次,正确答案为 2 次\n",52,50,fly(52, 50)); } private static List<Integer> integerList; private static Queue<NodeVo> q; private static class NodeVo implements Comparable<NodeVo>{ private int t; private int id; public NodeVo(int t,int id) { this.t = t; this.id = id; } public int getT() { return t; } public void setT(int t) { this.t = t; } public int getId() { return id; } public void setId(int id) { this.id = id; } @Override public int compareTo(NodeVo other) { return t > other.t ? 1 : 0; } } private static void init() { integerList = new ArrayList<>(); for(int i = 0;i < 500000; i ++) { integerList.add(999999999); } q = new LinkedList<>(); } }
总结
要 AC 本题，必须学会基于队列的 BFS （即广度优先搜索）的算法，从而通过本题。
