LEETCODE 780. Reaching Points 解题思路分析

题目大意：

到达终点

从点 (x, y) 可以转换到 (x, x+y)  或者 (x+y, y)。

给定一个起点 (sx, sy) 和一个终点 (tx, ty)，如果通过一系列的转换可以从起点到达终点，则返回 True ，否则返回 False。

示例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

注意:

• sx, sy, tx, ty 是范围在 [1, 10^9] 的整数。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=780

解题思路分析：

按照题目的定义，对于任意一个点，都存在2种移动的可能， (x, x+y)  或者 (x+y, y)，这实际上可以想象成是一棵二叉树，从二叉树的顶点开始找某个子节点，每次都要分别遍历2种情况，因此我们需要遍历完整棵树才能判断目标节点是否存在于树的分支中。

但是我们可以反过来想，如果从目标节点向上找根节点，那么就会只存在一条线路，这样会大大减少搜索次数。判断一个节点的父节点很容易，比如节点(5, 8), 它的父节点一定是(5, 3), 原因很简单，当前节点的x和y值，要么等于父节点对应的x和y的值，要么是父节点x和y值之和，对于节点(5, 8)，它的父节点有两种可能，(5, 3)是一种合理解((5, 3) -> (5, 5+3))，而另一种是(-3, 8)是不合理解((-3, 8) -> (-3+8, 8)), 不合理的原因在于节点坐标不能是负数。

这样一来，我们从目标节点开始向上遍历，每次找到当前节点的父节点，父节点的计算方式即上文提到的，x和y中较小的一方不变，而较大的一方需要减去较小的一方来得到父节点。例如： (5, 8) -> (5, 3) -> (2, 3) -> (2, 1) -> (1, 1)，当找到根节点时，返回true，当x或者y的其中一方小于根节点时仍未找到返回false。

解题时，其实我只思考到了这里，感觉已经可以完美通过所有case，但是万万没想到居然TLE超时了。超时的原因在于，当目标节点的x和y相差非常大时，比如(1, 99999999999)。每次找父节点都是用较大的y值减去1，如果根节点是(1, 1)，仍然需要循环99999999999次才行。

题目做到这里，俨然已经成为一道数学题目，试想，我们不断尝试用ty减去tx，设法得到sx，也就是：ty – n* tx = sy，如果n是整数的话，说明我们在用ty减去n个tx之后，正好等于sy，如果此时tx也恰好等于sx，那么就可以说明我们可以从目标节点移动到根节点。推导一下：

因为： ty - n* tx = sy
所以： n = (ty - sy) / tx

如果n不是整数，或者此时tx不等于sx，那么我们需要将ty减去n个tx，注意n不是整数，我们要为n取整（例：6.7应该等于6）。即：

// 因为
n = (ty - sy) / tx;
ty = ty - n * tx;
// 所以
ty = ty - (ty - sy) / tx * tx;

更改完ty值之后，再循环操作以上步骤，直到循环结束即可。

实现代码：

public boolean reachingPoints(int sx, int sy, int tx, int ty) {
    while(tx>=sx && ty>=sy){
        if(tx>ty){
            if((tx- sx) % ty == 0 && ty==sy) return true;
            tx=tx-tx/ty*ty;
        }
        else {
            if((ty- sy) % tx == 0 && tx==sx) return true;
            ty=ty-ty/tx*tx;
        }
    }
    return false;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Reaching Points.

Memory Usage: 33.1 MB, less than 12.50% of Java online submissions for Reaching Points.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-780-reaching-points-解题思路分析/