Hard
题目描述
给定四个整数 sx, sy, tx, ty，表示无限大2D网格上的两个点 (sx, sy) 和 (tx, ty)。
你从 (sx, sy) 开始。
在任何点 (x, y)，定义 m = max(x, y)。你可以：
- 移动到
(x + m, y)，或者 - 移动到
(x, y + m)
返回到达 (tx, ty) 所需的最小移动次数。如果不可能到达目标，返回 -1。
示例 1：
输入：sx = 1, sy = 2, tx = 5, ty = 4
输出：2
解释：
最优路径是：
移动 1：max(1, 2) = 2。将 y 坐标增加 2，从 (1, 2) 移动到 (1, 2 + 2) = (1, 4)。
移动 2：max(1, 4) = 4。将 x 坐标增加 4，从 (1, 4) 移动到 (1 + 4, 4) = (5, 4)。
因此，到达 (5, 4) 的最小移动次数是 2。
示例 2：
输入：sx = 0, sy = 1, tx = 2, ty = 3
输出：3
示例 3：
输入：sx = 1, sy = 1, tx = 2, ty = 2
输出：-1
解释：无法使用允许的移动从 (1, 1) 到达 (2, 2)。因此答案是 -1。
约束条件：
0 <= sx <= tx <= 10^90 <= sy <= ty <= 10^9
解题思路
这道题的关键是采用逆向思维，从目标点 (tx, ty) 反推到起始点 (sx, sy)。
核心观察：
- 从
(x, y)只能移动到(x + max(x,y), y)或(x, y + max(x,y)) - 逆向操作：从
(x, y)只能来自(x - max(x,y), y)或(x, y - max(x,y)) - 由于我们要减去较大值，必须保证减法后坐标非负
算法步骤：
- 从
(tx, ty)开始逆向推导 - 每次选择较大的坐标进行减法操作
- 如果较大坐标至少是较小坐标的2倍，可以通过除法快速计算步数
- 否则，进行单步减法操作
- 重复直到到达
(sx, sy)或无法继续
优化技巧：
当一个坐标远大于另一个时（例如 tx » ty），我们不需要逐步减 ty，而是可以直接计算需要多少步将 tx 减到接近 ty 的程度。具体地，如果 tx >= 2*ty，那么可以进行 (tx - ty) // ty 次减法操作。
边界情况：
- 如果目标点小于起始点，无法到达
- 如果陷入循环（坐标差值太小无法继续减少），返回 -1
代码实现
class Solution {
public:
int minMoves(int sx, int sy, int tx, int ty) {
int moves = 0;
while (tx > sx || ty > sy) {
if (tx > ty) {
if (ty <= sy) {
// 如果 ty <= sy，我们只能通过减 tx 来接近目标
if ((tx - sx) % ty == 0) {
moves += (tx - sx) / ty;
return moves;
} else {
return -1;
}
}
// 如果 tx >= 2*ty，可以快速计算步数
if (tx >= 2 * ty) {
moves += (tx - ty) / ty;
tx %= ty;
} else {
tx -= ty;
moves++;
}
} else {
if (tx <= sx) {
// 如果 tx <= sx，我们只能通过减 ty 来接近目标
if ((ty - sy) % tx == 0) {
moves += (ty - sy) / tx;
return moves;
} else {
return -1;
}
}
// 如果 ty >= 2*tx，可以快速计算步数
if (ty >= 2 * tx) {
moves += (ty - tx) / tx;
ty %= tx;
} else {
ty -= tx;
moves++;
}
}
}
return (tx == sx && ty == sy) ? moves : -1;
}
};
class Solution:
def minMoves(self, sx: int, sy: int, tx: int, ty: int) -> int:
moves = 0
while tx > sx or ty > sy:
if tx > ty:
if ty <= sy:
# 如果 ty <= sy，我们只能通过减 tx 来接近目标
if (tx - sx) % ty == 0:
moves += (tx - sx) // ty
return moves
else:
return -1
# 如果 tx >= 2*ty，可以快速计算步数
if tx >= 2 * ty:
moves += (tx - ty) // ty
tx %= ty
else:
tx -= ty
moves += 1
else:
if tx <= sx:
# 如果 tx <= sx，我们只能通过减 ty 来接近目标
if (ty - sy) % tx == 0:
moves += (ty - sy) // tx
return moves
else:
return -1
# 如果 ty >= 2*tx，可以快速计算步数
if ty >= 2 * tx:
moves += (ty - tx) // tx
ty %= tx
else:
ty -= tx
moves += 1
return moves if tx == sx and ty == sy else -1
public class Solution {
public int MinMoves(int sx, int sy, int tx, int ty) {
int moves = 0;
while (tx > sx || ty > sy) {
if (tx > ty) {
if (ty <= sy) {
// 如果 ty <= sy，我们只能通过减 tx 来接近目标
if ((tx - sx) % ty == 0) {
moves += (tx - sx) / ty;
return moves;
} else {
return -1;
}
}
// 如果 tx >= 2*ty，可以快速计算步数
if (tx >= 2 * ty) {
moves += (tx - ty) / ty;
tx %= ty;
} else {
tx -= ty;
moves++;
}
} else {
if (tx <= sx) {
// 如果 tx <= sx，我们只能通过减 ty 来接近目标
if ((ty - sy) % tx == 0) {
moves += (ty - sy) / tx;
return moves;
} else {
return -1;
}
}
// 如果 ty >= 2*tx，可以快速计算步数
if (ty >= 2 * tx) {
moves += (ty - tx) / tx;
ty %= tx;
} else {
ty -= tx;
moves++;
}
}
}
return (tx == sx && ty == sy) ? moves : -1;
}
}
var minMoves = function(sx, sy, tx, ty) {
if (sx === tx && sy === ty) return 0;
let moves = 0;
while (tx > sx || ty > sy) {
if (tx > ty) {
if (ty <= sy) {
if (sy === ty) {
moves += Math.floor((tx - sx) / ty);
tx = tx % ty || ty;
} else {
return -1;
}
} else {
moves++;
tx -= ty;
}
} else {
if (tx <= sx) {
if (sx === tx) {
moves += Math.floor((ty - sy) / tx);
ty = ty % tx || tx;
} else {
return -1;
}
} else {
moves++;
ty -= tx;
}
}
}
return sx === tx && sy === ty ? moves : -1;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(log(max(tx, ty))) - 类似辗转相除法的复杂度 |
| 空间复杂度 | O(1) - 只使用常数额外空间 |