前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >780. 到达终点 (Reaching Points)

780. 到达终点 (Reaching Points)

作者头像
yukong
发布2019-01-28 10:29:20
5940
发布2019-01-28 10:29:20
举报
文章被收录于专栏:yukong的小专栏

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

代码语言:javascript
复制
示例:
输入: 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代码

代码语言:javascript
复制
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代码

代码语言:javascript
复制
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
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.01.17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档