LeetCode----到达终点

题目描述

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

示例:

输入: sx = 1, sy = 1, tx = 3, ty = 5
输出: True

解释:

可以通过以下一系列转换从起点转换到终点：
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

输入: sx = 1, sy = 1, tx = 2, ty = 2
输出: False

输入: sx = 1, sy = 1, tx = 1, ty = 1
输出: True

思路

每次有 2 个选择，如果从起点往前走，就是一个二叉树，后面结果越来越多
既然给定了终点（虽然不一定有给定起点），但是倒着走回去只有一条路
当往回走的过程中，点都小于起点坐标，说明一定不会经过给定起点

代码

class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        if(sx == tx && sy == ty) return true;
        if(sx > tx || sy > ty) return false;
        if(tx > ty) {
            tx -= ty;                              // 先走一步再说
            tx -= tx-ty > sx ? (tx-sx)/ty*ty : 0;  // 如果 2 者差值太大，会导致栈溢出，那就跨一大步，省去不必要递归
        } else {
            ty -= tx;
            ty -= ty-tx > sy ? (ty-sy)/tx*tx : 0;
        }
        return reachingPoints(sx, sy, tx, ty);
    }
}

LeetCode----到达终点

原文：https://www.cnblogs.com/qq188380780/p/11645842.html