本文涉及知识点
数学
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
数学
看起来很简单:
这样极端情况下,时间复杂度会达到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 ,能够到达终点。
三,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
相关下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话 |
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。