```java
class Solution {
    public int minMoves(int sx, int sy, int tx, int ty) {
        int ans = 0;
        
        // 从终点向起点逆向推导
        while (tx > sx || ty > sy) {
            // 如果逆向过程中某个坐标小于起点,说明不可能到达
            if (tx < sx || ty < sy) {
                return -1;
            }
            ans++;
            
            // 处理两个坐标相等的情况
            if (tx == ty) {
                // 只有当起始点有一个坐标为0时,才能从(0, k)到达(k, k)或从(k, 0)到达(k, k)
                if (sx == 0) {
                    tx = 0;
                } else if (sy == 0) {
                    ty = 0;
                } else {
                    return -1;
                }
                continue;
            }
            
            // 保证 tx > ty,便于统一处理
            if (tx < ty) {
                int temp = tx;
                tx = ty;
                ty = temp;
                temp = sx;
                sx = sy;
                sy = temp;
            }
            
            // 核心逆向逻辑
            if (tx > ty * 2) {
                // 如果tx远大于ty,上一步只能是翻倍操作
                if (tx % 2 != 0) {
                    return -1;
                }
                tx /= 2;
            } else {
                // 否则上一步是加法操作,减去较小的那个数
                tx -= ty;
            }
        }
        
        return (tx == sx && ty == sy) ? ans : -1;
    }
}
```

核心思路:逆向思维

这道题正着走很难判断,但从终点往起点倒推就会变得清晰。

· 逆向操作的确定性:正向移动是加上 max(x,y),逆向就是看当前的 (tx, ty) 可能是从哪个前驱状态变来的。当 tx > ty 时,最后一步只可能是两种操作之一:要么是 tx 翻倍,要么是 tx 加上 ty。
· 贪心判断:如果 tx > ty*2,说明 tx 远大于 ty,此时 tx 只能是通过翻倍得到的(否则如果只是加了一次 ty,不可能变得这么大),所以直接让 tx 减半。其他情况则用减法还原。
· 边界与异常:逆向中如果 tx 或 ty 小于起点坐标,说明走过头了,返回 -1。tx == ty 是特殊情况,需要单独处理,只有当起点坐标为 0 时才有可能。

复杂度 O(log(max(tx, ty))),主要消耗在每次将较大的数减半或大幅缩小上。

 

Logo

汇聚全球AI编程工具,助力开发者即刻编程。

更多推荐