Reaching Points问题

---

Contact me

Blog -> https://cugtyt.github.io/blog/index

Email -> cugtyt@qq.com

GitHub -> Cugtyt@GitHub

---

问题描述（题目来源）：

A move consists of taking a point (x, y) and transforming it to either (x, x+y) or (x+y, y).

Given a starting point (sx, sy) and a target point (tx, ty), return True if and only if a sequence of moves exists to transform the point (sx, sy) to (tx, ty). Otherwise, return False.

Examples:

Input: sx = 1, sy = 1, tx = 3, ty = 5

Output: True

Explanation:

One series of moves that transforms the starting point to the target is:

(1, 1) -> (1, 2) (1, 2) -> (3, 2) (3, 2) -> (3, 5)

Input: sx = 1, sy = 1, tx = 2, ty = 2 Output: False

Input: sx = 1, sy = 1, tx = 1, ty = 1 Output: True

Note: sx, sy, tx, ty will all be integers in the range [1, 10^9].

我们先写下最笨的方法：

def reachingPoints(self, sx, sy, tx, ty):
    if tx < sx or ty < sy or tx == ty:
        return False

    if tx == sx and ty == sy:
        return True

    return self.reachingPoints(sx + sy, sy, tx, ty) or self.reachingPoints(
        sx, sx + sy, tx, ty)

首先是如果目标比起点还小，肯定不可能，如果tx和ty相等也不行，因为更新是(x, y)到(x+y, y)或(x, x + y)。然后是成功的条件，对应相等。下面就是更新当前的x和y。

基本逻辑差不多了，但是问题是慢和容易栈溢出，因此暴力的方法不行。

我们假设成功时更新了n次，每次的x和y记作Xi和Yi，i从1到n，那么最后一步就是：

Xn = tx, Yn = ty

这里我们假设tx < ty, 那么：

Xn-1 = tx, Yn-1 = ty - tx

如果tx加了m次，那么在加tx的第一次就是：

Xn-m = tx, Yn-m = ty - m * tx

这里可以做一个转换，就是Yn-m = ty % tx，n-m这个时候tx是最大的。

这样我们就把这个问题转化到了从(sx,sy)到(tx, ty % tx)，同理，我们可以继续做下去，把问题转化为从(x,y)到(tx % (ty % tx), ty % tx)。因为 小数 % 大数 = 小数，因此可以把问题(tx, ty % tx)写为(tx % ty, ty % tx)。

下面是网上的一个答案：

def reachingPoints(sx, sy, tx, ty):
    if sx > tx or sy > ty:
        return False
    if sx == tx and (ty - sy) % sx == 0:
        return True
    if sy == ty and (tx - sx) % sy == 0:
        return True
    return reachingPoints(sx, sy, tx % ty, ty % tx)

值得注意的是中间的两个判断条件，不能写if sx == tx and sy == ty: return True，因为可能%运算出现0，这样就容易让第一个判断返回。

这里使用了递归，来看下不是递归的方法：

def reachingPoints(sx, sy, tx, ty):
    while sx < tx and sy < ty:
        tx, ty = tx % ty, ty % tx
    return sx == tx and (ty - sy) % sx == 0 or sy == ty and (tx - sx) % sy == 0

主要做的是把递归里面的转化放到while里面，直接计算最终的tx和ty，最后的判断条件和上面的中间判断是一致的。