【刷题日记】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. 到达终点
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
