到达终点
难度:
标签:
题目描述
代码结果
运行时间: 24 ms, 内存: 16.1 MB
/*
题目思路:
从终点 (tx, ty) 逆向推回到起点 (sx, sy)。
每一步可以是 (x, y) 变为 (x-y, y) 或者 (x, y-x)。
我们需要在 tx >= sx 且 ty >= sy 的条件下进行操作。
当 tx == ty 时,说明无法再进行转换,只能返回 false。
使用Java Stream API来简化代码。
*/
import java.util.stream.Stream;
public class Solution {
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
while (tx >= sx && ty >= sy) {
if (tx == sx && ty == sy) return true;
if (tx > ty) {
tx -= ty;
} else {
ty -= tx;
}
}
return false;
}
}
解释
方法:
题解采用的是从终点(tx, ty)向起点(sx, sy)反向推理的方式。考虑到每次变换操作是唯一的,可以逆向单步回溯,从(tx, ty)减少到(sx, sy)。如果在过程中tx>ty,则意味着tx是通过(tx - ty, ty)转换而来;反之,则ty是通过(tx, ty - tx)转换而来。由于直接递减可能导致复杂度过高,因此代码使用取模操作以优化性能,跳过多次直接递减的过程。当其中一个值与起点对应值相等时,只需验证另一个值能否通过若干次指定增加操作变为目标值。
时间复杂度:
O(log(min(tx, ty)))
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在解题策略中选择从终点(tx, ty)向起点(sx, sy)逆向推理,而不是从起点向终点正向推理?
▷🦆
在使用取模操作优化性能的过程中,如何保证每次操作都是朝向正确的方向前进,即确保最终能回到(sx, sy)而不是错过?
▷🦆
题解中提到的终止条件`sx == tx and sy <= ty and (ty - sy) % sx == 0 or sy == ty and sx <= tx and (tx - sx) % sy == 0`具体是如何得出的?
▷🦆
如果tx和ty都远大于sx和sy,这种取模方法的效率和普通的递减方法相比有多大的提升?
▷