DeepSeek LeetCode 3609. 到达目标点的最小移动次数 Python3实现

pythonclass Solution:def minMoves(self, sx: int, sy: int, tx: int, ty: int) - int:ans 0# 从终点向起点逆向推导while tx sx or ty sy:# 如果逆向过程中某个坐标小于起点说明不可能到达if tx sx or ty sy:return -1ans 1# 处理两个坐标相等的情况if tx ty:# 只有当起始点有一个坐标为0时才能从(0,k)或(k,0)到达(k,k)if sx 0:tx 0elif sy 0:ty 0else:return -1continue# 保证 tx ty便于统一处理if tx ty:tx, ty ty, txsx, sy sy, sx# 核心逆向逻辑if tx ty * 2:# 如果 tx 远大于 ty上一步只能是翻倍操作if tx % 2 ! 0:return -1tx // 2else:# 否则上一步是加法操作减去较小的那个数tx - tyreturn ans if tx sx and ty sy else -1核心思路逆向思维 贪心这道题正着推导很难因为每次都有两种选择。但从终点向起点反向推导就会变得非常清晰1. 逆向操作的确定性· 正向操作(x, y) → (xy, y) 或 (x, xy)· 逆向操作如果 tx ty最后一步只能是· 翻倍(tx//2, ty)前提是 tx 为偶数且 tx//2 ! ty但这里直接减半即可· 加法(tx-ty, ty)2. 贪心优化当 tx ty * 2 时tx 远大于 ty此时最后一步不可能是加法因为加法只会增加 ty不可能让 tx 变得这么大所以一定是翻倍操作直接让 tx 减半。其他情况则用减法还原。3. 特殊情况处理· tx ty 时只能从 (0, k) 或 (k, 0) 到达否则无解· 逆向过程中如果 tx sx 或 ty sy说明走过头了返回 -14. 坐标交换为了统一处理始终保证 tx ty如果 tx ty 就交换两个坐标同时交换起点坐标。时间复杂度O(log(max(tx, ty)))每次循环都会将较大的数大幅缩小减半或减去较小数效率极高。示例验证pythonsol Solution()print(sol.minMoves(1, 1, 3, 5)) # 输出: 4print(sol.minMoves(1, 1, 2, 2)) # 输出: 3print(sol.minMoves(2, 1, 3, 7)) # 输出: -1