南宁网站建设哪家好,做网站的要求,建设银行的网站是什么,龙华营销型网站费用题目 求从坐标零点到坐标点n的最小步数#xff0c;一次只能沿横坐标轴向左或向右移动2或3. 注意:途径的坐标点可以为负数 输入描述 坐标点n 输出描述 输出从坐标零点移动到坐标点n的最小步数 备注 1 n 10^9 示例1: 输入 4 输出 2 说明 从坐标零点移动到4#xff0c;…题目 求从坐标零点到坐标点n的最小步数一次只能沿横坐标轴向左或向右移动2或3. 注意:途径的坐标点可以为负数 输入描述 坐标点n 输出描述 输出从坐标零点移动到坐标点n的最小步数 备注 1 n 10^9 示例1: 输入 4 输出 2 说明 从坐标零点移动到4最小需要两步即右移2再右移2 思路
两种方案
1. 动态规划 n1至少需要两步3 -2 n2, 只需移动一步2 n3, 只需移动1步3 记dp[n]为n的最小步数 那么对于n4时dp[n]min(dp[n-3],dp[n-2])1。 可以用一个队列来模拟实现这个过程 2. 数学 要想步数最小考虑优先走3步对于任意大于1的正整数n记an/3;ba%3 如果b 0,那么只需要走a步即可即全走3步 如果b 2那么只需要走a1步a个3步1个2步 如果b 1那么需要走a-12a1步a-1个3步2个2步 题解
package hwod;import java.util.LinkedList;
import java.util.Scanner;public class TheMinStep {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();System.out.println(minStep(n));}
//动态规划private static int minStep(int n) {if (n 1) return 2;LinkedListInteger queue new LinkedList();queue.addLast(2);queue.addLast(1);queue.addLast(1);for (int i 4; i n; i) {int first queue.pollFirst();int second queue.peekFirst();queue.addLast(Math.min(first, second) 1);}return queue.peekLast();}
// 数学解法private static int minStep2(int n) {if (n 1) return 2;int a n / 3, b n % 3;if (b 0) return a;return a 1;}
}
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
