当前位置：网站首页>＃yyds干货盘点＃解决名企真题：小招喵跑步

＃yyds干货盘点＃解决名企真题：小招喵跑步

2022-07-20 12:25:00 【51CTO】

1.描述：

描述

小招喵喜欢在数轴上跑来跑去，假设它现在站在点n处，它只会3种走法，分别是：1.数轴上向前走一步，即n=n+1 2.数轴上向后走一步,即n=n-1 3.数轴上使劲跳跃到当前点的两倍，即n=2*n现在小招喵在原点，即n=0，它想去点x处，快帮小招喵算算最快的走法需要多少步？

输入描述：

小招喵想去的位置x

输出描述：

小招喵最少需要的步数

示例1

输入：

输出：

2.代码实现：

       
       import java.util.*;
       
public class Main {
       
    public static void main(String[] args){
       
        Scanner sc = new Scanner(System.in);
       
        int x = sc.nextInt();
       
        System.out.println(solve(x));
       
    }
       
    public static int solve(int x){
       
        if(x<2&&x>=0){     
       
          return x;
       
        }
       
        if(x < 0){
       
            x = -x;
       
        }
       
        int[] dp=new int[x+1];
       
        dp[0]=0;
       
        dp[1]=1;
       
        for(int i=2;i<=x;i++){
       
            if(i%2==0){
       
                dp[i]=dp[i/2]+1;
       
            }else{
       
                dp[i]=Math.min(dp[i-1], 1 + dp[(i + 1) / 2])+1;
       
            }
       
        }
       
        return dp[x];
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.