我在采访中遇到一个问题，关于一个能后退一步或移动两倍于当前距离的人。把每一个动作看作一个单独的动作，找出他从x到y的最小动作。
import java.util.*;
import java.io.*;
public class Main
{
public static int Solve(int x,int y)
{
if(x==0)
{
return Integer.MAX_VALUE;
}
else if(x==y)
{
return 0;
}
else if(x==1)
{
return 1+Solve(x*2,y);
}
return Math.min(1+Solve(x*2,y),1+Solve(x-1,y));
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int x=sc.nextInt();
int y=sc.nextInt();
int z=Solve(x,y);
System.out.print(z);
}
}
2条答案
按热度按时间jvlzgdj91#
这是一个无限循环。解（x2，y）会停在什么地方？
假设所有这些都只在一个轴上（1d），因为您定义了int x和int y。假设我们有x和y，如果y-x是正的，那意味着我们必须前进。如果y-x是奇数，假设是7，这意味着我们必须向前走8步（42），然后向后走1步。给我们5步。所以我们得走了
所以7+1=8，我们向前走8步，走两步，然后再走一步回来。如果是偶数，那就意味着我们可以一直往前走！所以
如果y-x是负数，这意味着我们必须回去。唯一的办法是后退一步（x-1），所以那就是
你可以写代码。我喜欢你的代码的递归方面，但是如果它是1d的话，那就太过分了。
6ljaweal2#
不确定这里是否需要基于递归的解决方案。
这里有两个子问题：
计数向后移动时
from >= to否则，计数会向前移动，并考虑差异出现的情况to - from是奇怪的：然后需要一个额外的向前移动和一个后退。这可以通过三元运算符来解决：