leetcode
leetcode 701 ~ 750
到达终点

到达终点

难度:

标签:

题目描述

代码结果

运行时间: 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)到(tx, ty)的每一步都有两种可能性(增加sx或增加sy),这会导致状态空间的指数级增长,使得问题变得难以处理。而逆向推理则明确每一步的选择,因为每个(tx, ty)点只能通过一种方式从一个更大的点转换而来(要么是(tx - ty, ty),要么是(tx, ty - tx)),从而减少了可能的路径数量,并能更直观地通过减法和模运算来逐步逼近起始点。
🦆
在使用取模操作优化性能的过程中,如何保证每次操作都是朝向正确的方向前进,即确保最终能回到(sx, sy)而不是错过?
取模操作通过减少无效的重复步骤来优化算法性能。在每一步操作中,如果tx > ty,则进行tx %= ty操作,这实际上是将tx减少到小于ty的值,等价于去掉了多个ty,确保了不会跳过任何可能的状态,因为这个过程只是快速实现了多次(tx - ty)操作。同理,ty的处理也是类似的。这种方法确保了我们每一步都是有效地接近目标点(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相等时,我们需检查另一个坐标是否能够通过多次相同的增加操作回达到另一个起点坐标。例如,如果tx等于sx,并且ty大于sy,那么我们需要检查从sy到ty是否可以通过多次添加sx得到。这可以通过`(ty - sy) % sx == 0`来验证,确保ty可以通过减去若干个sx准确达到sy。同理适用于另一个条件。
🦆
如果tx和ty都远大于sx和sy,这种取模方法的效率和普通的递减方法相比有多大的提升?
如果tx和ty远大于sx和sy,递减方法的效率极低,因为它需要逐步一个一个地减去ty或tx,而这可能需要进行数百万次操作。取模方法可以显著减少所需的操作次数,因为它一次性减去了多个ty或tx,直接跳到一个与另一坐标相近的值。这种方法在处理大数时尤其有效,可以将时间复杂度从线性降低到对数级别,显著提高算法的执行速度。

相关问题