【数学】【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 <= 109

数学

看起来很简单:

image.png

这样极端情况下,时间复杂度会达到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 -= 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++**实现。

相关文章
|
1月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
1月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
451 0
高精度算法(加、减、乘、除,使用c++实现)
|
1月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
22 0
|
1月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
1月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
1月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)
|
1月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
1月前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)
|
1月前
|
存储 算法 C++
弗洛伊德(Floyd)算法(C/C++)
弗洛伊德(Floyd)算法(C/C++)
|
1月前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)