Java实现 LeetCode 780 到达终点（逻辑题）

780. 到达终点

从点 (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

注意:

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

PS：

正规套路应该是递归

但是！！！

他这个题不正规，所以只能反过来想

从结束点找出发点

class Solution {

     public boolean reachingPoints(int sx, int sy, int tx, int ty) {

        while (tx >= sx && ty >= sy) {

            if (tx == ty) break;

            //如果tx>ty  只能是（x+y,y）过来的

            if (tx > ty) {

            	//如果结束点的y大于出发点的y

            	//tx是x+y来的，所以%y，就是求出原x

                if (ty > sy) tx %= ty;

                //反过来的话，起始点和结束点的y已经一致了

                //只需要看加上的是不是y的倍数

                //tx-sx这里就是n多个y，看他%y是不是能全部%掉

                else return (tx - sx) % ty == 0;

            } else {

                if (tx > sx) ty %= tx;

                else return (ty - sy) % tx == 0;

            }

        }

        return (tx == sx && ty == sy);

    }

}

巴特西

Java实现 LeetCode 780 到达终点（逻辑题）

780. 到达终点

最新文章

热门文章