我们先来看题目描述给定四个整数 sx , sy tx 和 ty 如果通过一系列的 转换 可以从起点 (sx, sy) 到达终点 (tx, ty) 则返回 true 否则返回 false 。从点 (x, y) 可以 转换 到 (x, xy) 或者 (xy, y) 。示例 1输入: sx 1, sy 1, tx 3, ty 5 输出: true 解释: 可以通过以下一系列转换从起点转换到终点 (1, 1) - (1, 2) (1, 2) - (3, 2) (3, 2) - (3, 5)示例 2输入: sx 1, sy 1, tx 2, ty 2 输出: false示例 3输入: sx 1, sy 1, tx 1, ty 1 输出: true提示:1 sx, sy, tx, ty 109解决方案方法一反向计算思路和算法如果从 (sx,sy) 开始正向计算则可能的情况非常多会超出时间限制。注意到 sx, sy, tx, ty 都是正整数因此对于给定的状态 (tx,ty) 只有当 tx ≠ ty 时才存在上一个状态且上一个状态唯一可能的情况如下如果 tx ty 不存在上一个状态状态 (tx,ty) 即为起点状态如果 tx ty 则上一个状态是 (tx − ty,ty) 如果tx ty 则上一个状态是 (tx,ty − tx) 。因此可以从 (tx,ty) 开始反向计算判断是否可以到达状态 (sx,sy) 。当 tx sx , ty sy , tx ≠ ty 三个条件同时成立时执行反向操作每一步操作更新 (tx,ty) 的值直到反向操作的条件不成立。由于每一步反向操作一定是将 tx 和 ty 中的较大的值减小因此当 tx ty 时可以直接将 tx 的值更新为 tx mod ty当 tx ty 时可以直接将 ty 的值更新为 ty mod tx 。当反向操作的条件不成立时根据 tx 和 ty 的不同情况分别判断是否可以从起点转换到终点。复杂度分析如果 tx sx 且 ty sy 则已经到达起点状态因此可以从起点转换到终点。如果 tx sx 且 ty ≠ sy 则 tx 不能继续减小只能减小 ty 因此只有当 ty sy 且 (ty−sy) mod tx 0 时可以从起点转换到终点。如果 ty sy 且 tx ≠ sx 则 ty 不能继续减小只能减小 tx 因此只有当 tx sx 且 (tx−sx) mod ty 0 时可以从起点转换到终点。如果 tx ≠ sx 且 ty ≠ sy 则不可以从起点转换到终点。代码Python3class Solution: def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) - bool: while sx tx ! ty sy: if tx ty: tx % ty else: ty % tx if tx sx and ty sy: return True elif tx sx: return ty sy and (ty - sy) % tx 0 elif ty sy: return tx sx and (tx - sx) % ty 0 else: return FalseJavaclass Solution { public boolean reachingPoints(int sx, int sy, int tx, int ty) { while (tx sx ty sy tx ! ty) { if (tx ty) { tx % ty; } else { ty % tx; } } if (tx sx ty sy) { return true; } else if (tx sx) { return ty sy (ty - sy) % tx 0; } else if (ty sy) { return tx sx (tx - sx) % ty 0; } else { return false; } } }C#public class Solution { public bool ReachingPoints(int sx, int sy, int tx, int ty) { while (tx sx ty sy tx ! ty) { if (tx ty) { tx % ty; } else { ty % tx; } } if (tx sx ty sy) { return true; } else if (tx sx) { return ty sy (ty - sy) % tx 0; } else if (ty sy) { return tx sx (tx - sx) % ty 0; } else { return false; } } }复杂度分析时间复杂度O(logmax(tx,ty)) 其中 tx 和 ty 是终点值。反向计算的过程与辗转相除法相似时间复杂度是 O(logmax(tx,ty)) 。空间复杂度O(1) 。