算法分析

题目讲述一共有3种移动情况且权重一致

• 从 X 移动到 X−1

• 从 X 移动到 X+1

• 从 X 移动到 2∗X

相当于X 与X - 1,X + 1,2 * X ,各连一条边,从n开始进行bfs到k，dist[k]表示k点到n点的最短距离

时间复杂度 $O(k)$

参考文献

算法提高课

Java 代码

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static int N = 100010;
    static int n;
    static int k;
    static int[] dist = new int[N];
    static int bfs()
    {
        Queue<Integer> q = new LinkedList<Integer>();
        Arrays.fill(dist, -1);
        q.add(n);
        dist[n] = 0;
        while(!q.isEmpty())
        {
            int t = q.poll();
            if(t - 1 >= 0 && dist[t - 1] == -1)
            {
                dist[t - 1] = dist[t] + 1;
                if(t - 1 == k) return dist[t - 1];
                q.add(t - 1);
            }
            if(t + 1 < N && dist[t + 1] == -1)
            {
                dist[t + 1] = dist[t] + 1;
                if(t + 1 == k) return dist[t + 1];
                q.add(t + 1);
            }
            if(t * 2 < N && dist[t * 2] == -1)
            {
                dist[t * 2] = dist[t] + 1;
                if(t * 2 == k) return dist[t * 2];
                q.add(t * 2);
            }
        }
        return  -1;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        k = scan.nextInt();
        System.out.println(bfs());
    }
}