780. 到达终点 (Reaching Points)

title: ' 780. 到达终点 (Reaching Points)' date: 2019-01-17 17:10:17 categories: leetcode tags: [leetcode,算法, java]


从点 (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] 的整数。

由于本题按照题目给的思路正向一步一步走下去会存在多种情况,我们可以逆向推导。反推起点,因为这样只存在两种种情况。

  • if : tx > ty then : tx = tx % ty
  • if : ty > tx then : ty = ty % tx

java代码

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

python代码

class Solution:
    def reachingPoints(self, sx, sy, tx, ty):
        """
        :type sx: int
        :type sy: int
        :type tx: int
        :type ty: int
        :rtype: bool
        """
        while tx > sx and ty > sy:
            if tx > ty:
                tx = tx % ty
            else:
                ty = ty % tx
        
        if tx == sx:
             return (ty - sy) % sx == 0
        if ty == sy:
             return (tx - sx) % sy == 0
        return False

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券