0780-到达终点

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给定四个整数 sx , sy ，tx 和 ty，如果通过一系列的 转换 可以从起点 (sx, sy) 到达终点 (tx, ty)，则返回 true，否则返回 false。

从点 (x, y) 可以 转换 到 (x, x+y) 或者 (x+y, y)。

示例 1:

**输入:** sx = 1, sy = 1, tx = 3, ty = 5
**输出:** true
**解释:** 可以通过以下一系列 **转换** 从起点转换到终点：
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

示例 2:

**输入:** sx = 1, sy = 1, tx = 2, ty = 2 
**输出:** false

示例 3:

**输入:** sx = 1, sy = 1, tx = 1, ty = 1 
**输出:** true

提示:

  • 1 <= sx, sy, tx, ty <= 109

方法一：反向计算

如果从 (\textit{sx}, \textit{sy}) 开始正向计算，则可能的情况非常多，会超出时间限制。注意到 sx}, \textit{sy}, \textit{tx}, \textit{ty 都是正整数，因此对于给定的状态 (\textit{tx}, \textit{ty})，只有当 tx} \ne \textit{ty 时才存在上一个状态，且上一个状态唯一，可能的情况如下：

  • 如果 tx} = \textit{ty，不存在上一个状态，状态 (\textit{tx}, \textit{ty}) 即为起点状态；

  • 如果 tx} > \textit{ty，则上一个状态是 (\textit{tx} - \textit{ty}, \textit{ty})；

  • 如果 tx} < \textit{ty，则上一个状态是 (\textit{tx}, \textit{ty} - \textit{tx})。

因此可以从 (\textit{tx}, \textit{ty}) 开始反向计算，判断是否可以到达状态 (\textit{sx}, \textit{sy})。当 tx} > \textit{sx}, \textit{ty} > \textit{sy}, \textit{tx} \ne \textit{ty 三个条件同时成立时，执行反向操作，每一步操作更新 (\textit{tx}, \textit{ty}) 的值，直到反向操作的条件不成立。

由于每一步反向操作一定是将 tx 和 ty 中的较大的值减小，因此当 tx} > \textit{ty 时可以直接将 tx 的值更新为 tx} \bmod \textit{ty，当 tx} < \textit{ty 时可以直接将 ty 的值更新为 ty} \bmod \textit{tx。

当反向操作的条件不成立时，根据 tx 和 ty 的不同情况分别判断是否可以从起点转换到终点。

  • 如果 tx} = \textit{sx 且 ty} = \textit{sy，则已经到达起点状态，因此可以从起点转换到终点。

  • 如果 tx} = \textit{sx 且 ty} \ne \textit{sy，则 tx 不能继续减小，只能减小 ty，因此只有当 ty} > \textit{sy 且 (\textit{ty} - \textit{sy}) \bmod \textit{tx} = 0 时可以从起点转换到终点。

  • 如果 ty} = \textit{sy 且 tx} \ne \textit{sx，则 ty 不能继续减小，只能减小 tx，因此只有当 tx} > \textit{sx 且 (\textit{tx} - \textit{sx}) \bmod \textit{ty} = 0 时可以从起点转换到终点。

  • 如果 tx} \ne \textit{sx 且 ty} \ne \textit{sy，则不可以从起点转换到终点。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        while sx < tx != ty > sy:
            if tx > ty:
                tx %= ty
            else:
                ty %= tx
        if tx == sx and ty == sy:
            return True
        elif tx == sx:
            return ty > sy and (ty - sy) % tx == 0
        elif ty == sy:
            return tx > sx and (tx - sx) % ty == 0
        else:
            return False
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy && tx != ty) {
            if (tx > ty) {
                tx %= ty;
            } else {
                ty %= tx;
            }
        }
        if (tx == sx && ty == sy) {
            return true;
        } else if (tx == sx) {
            return ty > sy && (ty - sy) % tx == 0;
        } else if (ty == sy) {
            return tx > sx && (tx - sx) % ty == 0;
        } else {
            return false;
        }
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public bool ReachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy && tx != ty) {
            if (tx > ty) {
                tx %= ty;
            } else {
                ty %= tx;
            }
        }
        if (tx == sx && ty == sy) {
            return true;
        } else if (tx == sx) {
            return ty > sy && (ty - sy) % tx == 0;
        } else if (ty == sy) {
            return tx > sx && (tx - sx) % ty == 0;
        } else {
            return false;
        }
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy && tx != ty) {
            if (tx > ty) {
                tx %= ty;
            } else {
                ty %= tx;
            }
        }
        if (tx == sx && ty == sy) {
            return true;
        } else if (tx == sx) {
            return ty > sy && (ty - sy) % tx == 0;
        } else if (ty == sy) {
            return tx > sx && (tx - sx) % ty == 0;
        } else {
            return false;
        }
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool reachingPoints(int sx, int sy, int tx, int ty) {
    while (tx > sx && ty > sy && tx != ty) {
        if (tx > ty) {
            tx %= ty;
        } else {
            ty %= tx;
        }
    }
    if (tx == sx && ty == sy) {
        return true;
    } else if (tx == sx) {
        return ty > sy && (ty - sy) % tx == 0;
    } else if (ty == sy) {
        return tx > sx && (tx - sx) % ty == 0;
    } else {
        return false;
    }
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var reachingPoints = function(sx, sy, tx, ty) {
    while (tx > sx && ty > sy && tx != ty) {
        if (tx > ty) {
            tx %= ty;
        } else {
            ty %= tx;
        }
    }
    if (tx === sx && ty === sy) {
        return true;
    } else if (tx === sx) {
        return ty > sy && (ty - sy) % tx === 0;
    } else if (ty === sy) {
        return tx > sx && (tx - sx) % ty === 0;
    } else {
        return false;
    }
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func reachingPoints(sx, sy, tx, ty int) bool {
    for tx > sx && ty > sy && tx != ty {
        if tx > ty {
            tx %= ty
        } else {
            ty %= tx
        }
    }
    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
    }
}

复杂度分析

  • 时间复杂度：O(\log \max(\textit{tx}, \textit{ty}))，其中 tx 和 ty 是终点值。反向计算的过程与辗转相除法相似，时间复杂度是 O(\log \max(\textit{tx}, \textit{ty}))。

  • 空间复杂度：O(1)。

 Comments
On this page
0780-到达终点