【逆向思维】力扣780-到达终点

摘要: 逆向思维

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们看一个逆向思维解决的问题。在文章 逆向思维 中，我们汇总了一些逆向思维的问题，可以参考。

$1 题目

• 780. 到达终点

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

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

提示:

1 <= sx, sy, tx, ty <= 1e9

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

$2 题解

算法: 逆向思维

正常地研究如何从 (sx, sy) 走到 (tx, ty)，想破头也想不出来。但是如果研究如何从 (tx, ty) 走到 (sx, sy)，则会比较容易思路。

我们来看一下寻找从 (sx, sy) 走到 (tx, ty) 的路径为什么难。

假设当前走到了 (x, y)，因为 (x, y) 正向走一步有两种可能性，一种是 (x, x + y)，另一种是 (x + y, y)。但是此时我们并不知道哪一条可以走到 (tx, ty)，可能某一条能走到，可能两条都能走到，也可能两条都走不到，必须得两条都得走一遍才能知道。那这个时间复杂度就受不了了。

如果研究从 (tx, tx) 走到 (sx, sy) 的路径，假设当前走到了 (x, y)，某个点反向走到 (x, y) 也有两种可能性，一种是从 (x, x + y) 走到 (x, y)，另一种是从 (x + y, y) 走到 (x, y)。但由于我们是要走到 (sx, sy) 而不是 (tx, ty)，因此我们没必要清楚是从哪一点走到 (x, y) 的，只需要关心从 (x, y) 反向走一步能走到哪个点。

由于不论是 (x, x + y), (x + y, y) 中的哪一点走到的 (x, y)，都是较大的数要变小，也就是 x + y 要变成 x 或 y。因此对于 (x, y) 来说

• x > y: 反向走一步走到 (x - y, y)
• x < y: 反向走一步走到 (x, y - x)
• x = y: 如果 (x, y) 不是 (sx, sy)，则无法反向走到 (sx, sy)

这样当我们在 (x, y) 往 (sx, sy) 走的时候，只有一种选择，这样就可以接受了。

当 x 远大于 y 或者 y 远大于 x 的时候，可以通过模运算一次性完成多步。

代码(C++)

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        if(sx > tx || sy > ty)
            return false;
        if(sx == tx && sy == ty)
            return true;
        int x = tx, y = ty;
        while(sx < x && sy < y)
        {
            if(x > y)
            {
                x = x % y;
                if(x == 0)
                    x = y;
            }
            else if(x < y)
            {
                y = y % x;
                if(y == 0)
                    y = x;
            }
            if(x == y)
                break;
        }
        if(sx == x && sy == y)
            return true;
        if(sx == x && ((y - sy) % x == 0))
            return true;
        if(((x - sx) % y == 0) && sy == y)
            return true;
        return false;
    }
};

---