LeetCode-780 到达终点

简介: LeetCode-780 到达终点

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/reaching-points

题目描述

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

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

 

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

 

提示:

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

解题思路

很有趣的一道逆向思维题,如果正向来判断(sx, sy)到达(tx, ty)必然是十分困难的,如果是单次相加,那么时间复杂度会超出,如果是相乘,那么被乘数是无法确定的。但是如果从(tx, ty)反推回(sx, sy)是十分容易的,因为没必要关注中间相减的过程,直接使用取模运算就可以看出从(tx, ty)可以到达(sx, sy),如果使用单次相减就会超时。

逆推过程中,当x和y相等的时候,那么坐标就无法进行变换了,因为下一次逆推的结果坐标中会出现0,不符合题意,所以在x和y不相等的时候,同时,x和y分别都比sx,sy大的时候,将大的那个值对小的那个取模,逆推回去,在最终无法变换时进行状态的判断。

如果(x,y)等于(sx,sy)很显然,可以到达(sx,sy),如果x == sx,那么此时可以操作的坐标仅仅就是y,需要判断sy是否可以通过相加n个x等于了y,此时将y-sy对x取模,判断是否等于0就可以了,不能使用y对x取模判断余数为sy这种方法,因为如果sy可以被x整除,会产生错误的判断。同理,对于y == sy的情况也一样,如果x和y都不等于sx和sy,那么x和y无法达到sx和sy。

代码展示

 

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

运行结果

 

相关文章
|
Java Maven
java修改当前项目的maven仓库地址为国内
修改当前项目的maven仓库地址为国内
|
存储
File操作 - list()/listFiles()与目录过滤器
File操作 - list()/listFiles()与目录过滤器
343 0
|
11月前
|
Java 应用服务中间件 Linux
【Docker容器化技术】docker安装与部署、常用命令、容器数据卷、应用部署实战、Dockerfile、服务编排docker-compose、私有仓库
本文主要讲解了Docker的安装与部署、常用命令、容器数据卷、应用部署实战、Dockerfile、服务编排docker-compose、私有仓库以及Docker容器虚拟化与传统虚拟机比较。
12262 39
【Docker容器化技术】docker安装与部署、常用命令、容器数据卷、应用部署实战、Dockerfile、服务编排docker-compose、私有仓库
|
4月前
|
传感器 安全 物联网
【HarmonyOS 5】鸿蒙分布式协同应用开发详解
为什么需要分布式协同应用? 首先是因为当今社会,围绕电子产品生态,人们迫切希望,周边的电子设备可以协同操作。例如手机,手表,电视机,汽车,甚至是各种家电产品。 从2015年到如今,手机和pc等老牌电子产品的设备数趋于稳定,其他IoT设备稳步增长。可见人均所拥有的的电子产品的个数,在迅速增加。
160 0
|
10月前
|
应用服务中间件 Linux 网络安全
nginx安装部署ssl证书,同时支持http与https方式访问
为了使HTTP服务支持HTTPS访问,需生成并安装SSL证书,并确保Nginx支持SSL模块。首先,在`/usr/local/nginx`目录下生成RSA密钥、证书申请文件及自签名证书。接着,确认Nginx已安装SSL模块,若未安装则重新编译Nginx加入该模块。最后,编辑`nginx.conf`配置文件,启用并配置HTTPS服务器部分,指定证书路径和监听端口(如20000),保存后重启Nginx完成部署。
3040 8
|
12月前
|
Java 关系型数据库 MySQL
mysql5.7 jdbc驱动
遵循上述步骤,即可在Java项目中高效地集成MySQL 5.7 JDBC驱动,实现数据库的访问与管理。
2179 1
|
存储 JavaScript
vue项目中页面跳转传参的方法
vue项目中页面跳转传参的方法
|
Python
Python reStructuredText风格注释详解
reStructuredText风格注释是Python代码注释的一种标准化格式,它提供了一种规范的注释格式,使得代码更加易读、易于维护。reStructuredText风格注释使用两个等号来包围注释标题,并按照一定规范编写。通过使用reStructuredText风格注释,我们可以为代码提供清晰的文档和说明,使得代码更加易读、易于维护。
460 2
|
消息中间件 算法 NoSQL
两年CRUD,二本毕业,备战两个月面试阿里,侥幸拿下offer定级P6
本文素材来自一位关注我一年多的铁粉 对于很多没有学历优势的人来说,面试大厂是非常困难的,这对我而言,也是一样,出身于二本,原本以为就三点一线的生活度过一生,直到生活上的变故,才让我有了新的想法和目标,因此我这个二本渣渣也奋斗了起来,竟拿下了阿里P6岗。今天分享这波面经,主要是希望能够激励到同样被学历所困扰的技术人,能够对职业生涯和技术规划有一个参考价值,感谢!
两年CRUD,二本毕业,备战两个月面试阿里,侥幸拿下offer定级P6
|
JavaScript
vue3表格编辑(数据回显)和删除功能实现
vue3表格编辑(数据回显)和删除功能实现
273 1