【数学】【C++算法】780. 到达终点

作者推荐

视频算法专题

本文涉及知识点

数学

LeetCode780. 到达终点

给定四个整数 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

数学

看起来很简单:
{ t x − = t y t x > t y / / t y − = t x t x < t y / / 非法 o t h e r / / \begin{cases} tx -= ty & tx > ty // ty -= tx & tx < ty // 非法 & other // \end{cases} {tx=tytx>ty//ty=txtx<ty//非法other//
这样极端情况下,时间复杂度会达到O(10^9)。
tx = 1 ,ty = 109
可以用 tx = tx %ty ,加速。
如果tx < sx,判断 : (sx - tx)^ ty 是否等于,如果是:tx = sx并退出迭代,否则死循环。此时:tx > ty,不会改变ty,改变tx会死循环。

可以用另外一个方法:
tx -= ty,到不小于等于sx且>=ty,然后在减一。必须>=ty ,否则tx成为负数。
结束迭代的条件:
一,tx < sx或ty<sy。无法到达终点。
二,txsx 且 ty == sy ,能够到达终点。
三,tx
sx,ty > sy,继续。
四,ty==sy,tx > sx ,继续。

代码

核心代码

class Solution {
public:
	bool reachingPoints(int sx, int sy, int tx, int ty) {
		while ((sx <= tx) && (sy <= ty))
		{
			if ((sx == tx) && (sy == ty))
			{
				return true;
			}
			if (tx < ty)
			{
				const int cnt = (ty - max(sy+1,tx)) / tx;
				ty -= (cnt + 1) * tx;
			}
			else
			{
				const int cnt = (tx - max(sx + 1, ty)) / ty;
				tx -= (cnt + 1) * ty;
			}
		}
		return false;
	}
};

测试用例



template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	vector<int> nums, changeIndices;
	{
		Solution sln;
		auto res = sln.reachingPoints(1, 1, 3, 5);
		Assert(true, res);
	}
	{
		Solution sln;
		auto res = sln.reachingPoints(1, 1, 2, 2);
		Assert(false, res);
	}
	
	{
		Solution sln;
		auto res = sln.reachingPoints(1, 5, 19, 5);
		Assert(false, res);
	}

}

优化前版本

class Solution {
public:
	bool reachingPoints(int sx, int sy, int tx, int ty) {
		while ((sx < tx) || (sy < ty))
		{
			if ((sx > tx) || (sy > ty))
			{
					break;
			}
			if (tx < ty)
			{
				ty = ty % tx;
				if ((ty < sy) && (0 == (sy - ty) % tx))
				{
					ty = sy;
					break;
				}
			}
			else
			{
				tx = tx % ty;
				if ((tx < sx) && (0 == (sx - tx) % ty))
				{
					tx = sx;
					break;
				}
			}
		}
		return (sx == tx) && (sy == ty);
	}
};

2023年6月

class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
while (true)
{
if ((sx == tx) && (sy == ty))
{
return true;
}
if (tx > ty)
{
int iNum = min(tx / ty - 1, (tx - sx) / ty);
iNum = max(1, iNum);
tx -= tyiNum;
if (tx < sx)
{
return false;
}
}
else
{
int iNum = min((ty - sy) / tx, ty / tx - 1);
iNum = max(1, iNum);
ty -= tx
iNum;
if (ty < sy)
{
return false;
}
}
}
return false;
}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/453519.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Go语言中的锁与管道的运用

目录 1.前言 2.锁解决方案 3.管道解决方案 4.总结 1.前言 在写H5小游戏的时候&#xff0c;由于需要对多个WebSocket连接进行增、删、查的管理和对已经建立连接的WebSocket通过服务端进行游戏数据交换的需求。于是定义了一个全局的map集合进行连接的管理&#xff0c;让所有…

Netty架构详解

文章目录 概述整体结构Netty的核心组件逻辑架构BootStrap & ServerBootStrapChannelPipelineFuture、回调和 ChannelHandler选择器、事件和 EventLoopChannelHandler的各种ChannelInitializer类图 Protocol Support 协议支持层Transport Service 传输服务层Core 核心层模块…

操作系统内功篇:硬件结构之CPU是如何运行的?

本文分5个小结&#xff0c;分别是图灵机工作方式&#xff0c;冯诺依曼结构&#xff0c;总线线路位宽和CPU位宽&#xff0c;程序执行的基本过程&#xff0c; a12的具体执行过程。 一 图灵机的工作方式 图灵机由纸带&#xff0c;读写头组成。读写头上有一些部件例:存储单元&#…

嵌入式驱动学习第三周——linux内核链表

前言 在 Linux 内核中使用最多的数据结构就是链表了&#xff0c;其中就包含了许多高级思想。 比如面向对象、类似C模板的实现、堆和栈的实现。 嵌入式驱动学习专栏将详细记录博主学习驱动的详细过程&#xff0c;未来预计四个月将高强度更新本专栏&#xff0c;喜欢的可以关注本博…

智能指针的讲解

1.为什么要智能指针 首先我们分析一段代码&#xff1a; 1、如果p1这里new 抛异常会如何&#xff1f; 2、如果p2这里new 抛异常会如何&#xff1f; 3、如果div调用这里又会抛异常会如何&#xff1f; int div() {int a, b;cin >> a >> b;if (b 0)throw invalid_ar…

CVE-2024-2074 SpringBoot迷你天猫商城Mini-Tmall sql注入漏洞分析

漏洞简介 Mini-Tmall是一个基于Spring Boot的迷你天猫商城。Mini-Tmall在20231017版本及之前存在一个严重的漏洞&#xff0c;攻击者可以利用该漏洞通过远程执行特定操作来注入恶意SQL语句&#xff0c;从而获取敏感信息或控制数据库。此漏洞影响文件?rtmall/admin/user/1/1的一…

下载API文档

在线看&#xff1a;Overview (Java SE 17 & JDK 17) 离线下载&#xff1a;Java Development Kit 17 Documentation

Python 单元测试

本篇为Python的单元测试的方法及示例 目录 概念 结果 示例 对函数进行测试 创建函数文件 创建测试文件 测试结果 对类进行测试 创建待测试类 创建测试文件 文档测试 创建函数 进行测试 总结 概念 用来对一个函数、一个类或者一个模块来进行正确性校验工作 结果 …

为什么选择线上展览馆,搭建线上展览馆要注意什么

引言&#xff1a; 线上展览馆是一种利用互联网技术&#xff0c;将实体展览馆的展示内容以数字化形式呈现出来的在线观展方式。它打破了时间和空间的限制&#xff0c;使得更多的人可以随时随地参观展览&#xff0c;领略文化的魅力。 一、线上展览馆的优势 1.成本效益高&#x…

【安卓】Android开发入门 你的第一个apk应用

本文介绍如何写一个入门的安卓apk应用, 以嵌套一个网页为例。 开发ide&#xff1a;Android studio 语言&#xff1a;Kotlin tips: 最好别下载新版本的 Android studio &#xff0c;因为新版的界面有所改动 遇到问题去网上搜 新手刚入门可能界面都找不到在哪里&#xff1b;其次…

05-延迟任务精准发布文章-黑马头条

延迟任务精准发布文章 1)文章定时发布 2)延迟任务概述 2.1)什么是延迟任务 定时任务&#xff1a;有固定周期的&#xff0c;有明确的触发时间延迟队列&#xff1a;没有固定的开始时间&#xff0c;它常常是由一个事件触发的&#xff0c;而在这个事件触发之后的一段时间内触发…

银河麒麟V10SP3操作系统-网络时间配置

1、动态网络配置 打开终端&#xff0c;以网口 eth0 为例&#xff1a; nmcli conn add connection.id eth0-dhcp type ether ifname eth0 ipv4.method auto其中“eth0-dhcp”为连接的名字&#xff0c;可以根据自己的需要命名方便记忆和操作 的名字&#xff1b;“ifname eth0”…

Realsense 相机SDK学习(一)——librealsense使用方法及bug解决(不使用Ros)

一.介绍 realsense相机是一个intel开发出来的一款深度相机&#xff0c;我之前使用他来跑过slam&#xff0c;也配置过他的驱动&#xff0c;在此附上realsense的相机驱动安装方法&#xff1a;Ubuntu20.04安装Intelrealsense相机驱动&#xff08;涉及Linux内核降级&#xff09; …

redis-操作数据库

0 序言 一个Redis服务器可以包含多个数据库。在默认情况下&#xff0c;Redis服务器在启动时将会创建16个数据库&#xff1a;这些数据库都使用号码进行标识&#xff0c;其中第一个数据库为0号数据库&#xff0c;第二个数据库为1号数据库&#xff0c;而第三个数据库则为2号数据库…

Leetcode101对称的二叉树

如何去检查对称&#xff1f; 思路是check(n1->left,n2->right)&&check(n1->right,n2->left) 直接手算这题&#xff0c;该懂就懂了&#xff01; /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* Tre…

【一】【设计模式】类关系UML图

1. 继承&#xff08;Generalization&#xff09; 继承是对象间的一种层次关系&#xff0c;允许子类继承并扩展父类的功能。 UML线&#xff1a;带有空心箭头的直线&#xff0c;箭头指向基类&#xff08;父类&#xff09;。 class Parent {public void parentMethod() {System.…

Python网络基础爬虫-python基本语法

文章目录 逻辑语句if,else,elifforwhile异常处理 函数与类defpassclass 逻辑语句 熟悉C/C语言的人们可能很希望Python提供switch语句&#xff0c;但Python中并没有这个关键词&#xff0c;也没有这个语句结构。但是可以通过if-elif-elif-…这样的结构代替&#xff0c;或者使用字…

哈密顿算子的计算公式及一些常用公式总结

目录 哈密顿算子的定义式如下&#xff1a; 梯度定义&#xff1a; 散度定义&#xff1a; 旋度定义&#xff1a; 常用的一些公式&#xff1a; 注意文中字母上面没有→的是标量&#xff0c;有→的都表示矢量 哈密顿算子的定义式如下&#xff1a; 快速了解哈密顿算符&#xff…

同步整流芯片 支持12V降5V 24V降5V 24V降12V 降压芯片 H4122

惠海H4122降压恒压芯片的工作原理&#xff1a; 主要是通过内部电路和算法来控制和调节输出电压&#xff0c;使其保持恒定。 输入电压&#xff1a;芯片接收一个较高的输入电压&#xff0c;如12V、24V或36V。 开关电源转换器&#xff1a;芯片内部通常包含一个或多个开关电源转…

Linux 安装Nginx (Nginx-1.25.4)

一、下载Nginx安装包 1.服务器联网的情况下&#xff0c;使用wget命令把Nginx安装包下载到/usr/local/目录中&#xff0c;如果没有wget命令&#xff0c;需要先安装&#xff1a;yum install -y wget cd /usr/local wget -c https://nginx.org/download/nginx-1.25.4.tar.gz ng…