DeepSeek LeetCode 3609. 到达目标点的最小移动次数 Rust实现
根据搜索结果,对于 LeetCode 3609 题,目前公开的 Rust 解法信息比较有限。不过我找到了思路相近的题解,可以为你提供实现参考。
3609 题的核心通常是使用逆向思维 + 贪心/模拟,从终点倒推到起点。这里参考类似问题的 C++ 解法逻辑,提供一个 Rust 版本的实现思路:
```rust
impl Solution {
pub fn min_moves(sx: i32, sy: i32, tx: i32, ty: i32) -> i32 {
let mut x = tx;
let mut y = ty;
let mut moves = 0;
while x > sx || y > sy {
if x < sx || y < sy {
return -1;
}
if x > y {
if x <= 2 * y {
x -= y;
} else {
if x % 2 == 1 {
return -1;
}
x /= 2;
}
} else if y > x {
if y <= 2 * x {
y -= x;
} else {
if y % 2 == 1 {
return -1;
}
y /= 2;
}
} else { // x == y
if sx > 0 {
y = 0;
} else {
x = 0;
}
}
moves += 1;
}
if x == sx && y == sy {
moves
} else {
-1
}
}
}
```
💡 思路说明
· 逆向推导:从终点 (tx, ty) 倒推回起点 (sx, sy),因为正推分支太多,倒推时每一步的操作通常是唯一的。
· 贪心策略:倒推时,较大的坐标来自上一步的“加倍”操作。如果 x > y,说明上一步对 x 做了操作,根据 x 和 y 的大小关系决定是回退 x -= y 还是 x /= 2(必须确保 x 是偶数)。y > x 时同理。
· 相等特判:当 x == y 且尚未到达起点时,需要根据起点坐标决定让哪个坐标归零,以继续倒推。
💎 复杂度分析
这个实现的时间复杂度约为 O(log(max(tx, ty))),因为每次循环坐标至少减半或减少,效率很高。
如果这个思路和题目描述有出入,你可以提供具体的移动规则,我能再帮你调整实现。

更多推荐





所有评论(0)