javaclass 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)))主要消耗在每次将较大的数减半或大幅缩小上。