【刷题日记】780. 到达终点

本次刷题日记的第 28 篇，力扣题为：429. N 叉树的层序遍历 ，困难

一、题目描述：

周六咱们早点来刷每日一题，今天是一个困难题，题目的内容比较少也比较明确，做起来应该不难

那么我们就开始仔细分析一下吧

二、这道题考察了什么思想？你的思路是什么？

查看这道题目，重点信息如下：

• 题目给出 2 个坐标，我们可以通过坐标 1 根据题目中给出的逻辑，转化成 坐标 2 ，如果可以，那么结果就是 true，反之就是 false
• 那么题目中的意思，我们是不是也可以通过坐标 2 按照逻辑，转换成坐标 1 也是可以实现的嘞
• 转换的时候，我们需要注意，(x,y) ，开始转换的时候，只能转换成 (x+y,y) 或者 (x,y+x) ， 而不能是 (x+x,y) ，或者 (x,y+y) ，或者 (x+x,y+y)

那么我们就来推演一下这个题要如何去实现吧

题目给出的示例是：sx = 1, sy = 1, tx = 3, ty = 5

sx = sx  = 1 , sy = sx+sy = 2

sx = sx + sy = 3 , sy = sy = 2

sx = sx = 3, sy = sy + sx = 5

对于这种数字比较小的时候，咱们还比较好推演，当数字大的时候，我们到底是在 sx 上加上 sy ，还是在 sy 上 加上 sx

我们只能对于每一种情况不停的向下加，直到所有路径中，有 1 种路径是可以转换成 tx ，ty 的，那么就是可以的实现的

那么，上述的这种方式，情况实在是太多，当数据量大的时候，就会出现超时的情况，是不符合题目给出的要求的，对于题目给给出的测试用例，是不能完全跑过的

那么，我们也可以将 tx, ty 转成 sx, sy 来看看效果

tx , ty 转成 sx 和 sy 的时候，按照上述逻辑就是 (tx-ty,ty) 或者 (tx,ty -tx)

那么此处就要注意，对于这里的减法，那么肯定是 大数减去小数，才能得到我们期望的正数

开始推演：

tx = 3 , ty = 5

tx = 3, ty = ty -tx = 2

tx = tx - ty = 1 , ty = 2

tx = 1, ty = ty - tx = 1

此时，咱们反推，也是 OK 的，但是我们发现，发推的话，逻辑就比较明确，也没有那么多弯弯绕绕，只需要比较 tx ,ty 谁大，大的减去对方就可以了

但是这里还需要注意的是，只要当我们 tx 或者 ty 减到其中 tx = sx 或者 ty = sy 的时候，那么就不能再减下去了

此时，我们就可以查看 当前的较大的一个数 减去 对应的sx 或者 sy，是对方的倍数，

例如，我们此时不能再往下减了，此时 tx 已经等于 sx，那么我们就可以校验 ty - sy 的结果是否是 tx 的整数倍即可，因为这个时候，只能是 ty 不断的减去 tx 来看是否有机会等于 sy

那这个时候，我们又发现，这其实是一个数学题，我们理清楚思路之后，就可以来编码了，思路如下：

• 咱们使用反向推导，让 tx, ty  减去对方，来查看是否可以转换成 sx, sy

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，此处需要注意，当tx = sx, 或者 ty = sy 的时候，咱们就不能再减下去了，这个时候，就需要校验上述说到的逻辑了

编码如下：

func reachingPoints(sx, sy, tx, ty int) bool {
    // 辗转相除，直到 tx <= sx  或者 ty <= sy
    for tx > sx && ty > sy  {
        if tx > ty {
            tx %= ty
        } else {
            ty %= tx
        }
    }
    // 退出上述条件之后，开始校验 tx，ty 中较大的一个数字是否是否可以被另外一个数字整除
    switch {
    case tx == sx && ty == sy:
        return true
    case tx == sx:
        return ty > sy && (ty-sy)%tx == 0
    case ty == sy:
        return tx > sx && (tx-sx)%ty == 0
    default:
        return false
    }
}

看了上述编码后，逻辑还是非常清晰的吧，xdm 有时间也可以自己推理一下，反着推理确实比正向推理要明确的多

四、总结：

那么本次的空复杂度是 O(1)，这个不难看出，因为我们都没有引入新的空间，那时间复杂度是多少呢，我们可以思考一下，咱本次的时间复杂度，依赖于上述的 for 循环，可是循环的次数是多少呢？

咱们的时间复杂度是 O(n)  , O(log tx) , O(log ty)  还是 O(log max(tx + ty)) 呢？

原题地址：780. 到达终点

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~