得到目标值的最少行动次数

问题描述

• 将 sourceX, sourceY 转换成 targetX, targetY 最少需要多少次计算，给定两个数字（x, y)，允许以下两种计算：
  1. 同时对两个数加 1，即（x, y) -> (x+1, y+1)
  2. 同时对两个数乘 2，即（x, y) -> (x2, y2)
• 求要将（x, y）转换成（X, Y)，至少需要多次计算，如果不能转换，返回-1

代码实现

public class Solution {

    public static void main(String[] args) {
        System.out.println(new Solution().GetMinCalculateCount(10, 100, 22, 202));
    }

    public long GetMinCalculateCount(long sourceX, long sourceY, long targetX, long targetY) {
        if (sourceX == targetX && sourceY == targetY) {
            return 0;
        }
        if (sourceX <= 0 || sourceY <= 0 || targetX <= 0 || targetY <= 0) {
            return -1;
        }
        Queue<TwoNumber> queue = new LinkedList<>();
        queue.add(new TwoNumber(targetX, targetY, 0));
        while (!queue.isEmpty()) {
            TwoNumber nums = queue.poll();
            if (nums.X == sourceX && nums.Y == sourceY) {
                return nums.times;
            } else {
                if (nums.X % 2 == 1 && nums.Y % 2 == 1) {
                    queue.offer(new TwoNumber(nums.X - 1, nums.Y - 1, nums.times + 1));
                } else {
                    queue.offer(new TwoNumber(nums.X - 1, nums.Y - 1, nums.times + 1));
                    queue.offer(new TwoNumber(nums.X / 2, nums.Y / 2, nums.times + 1));
                }
            }
        }
        return -1;
    }
}

class TwoNumber {
    long X;
    long Y;
    int times;

    public TwoNumber(long X, long Y, int times) {
        this.X = X;
        this.Y = Y;
        this.times = times;
    }
}