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

本文主要是介绍【数学】【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 <= 10⁹

数学

看起来很简单：
$\begin{cases} tx -= ty & tx > ty // ty -= tx & tx < ty // 非法 & other // \end{cases}$
这样极端情况下，时间复杂度会达到O(10^9)。
tx = 1 ,ty = 10⁹。
可以用 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 ，能够到达终点。
三，txsx,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 -= txiNum;
if (ty < sy)
{
return false;
}
}
}
return false;
}
};

扩展阅读

视频课程

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

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

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