Google
780 Reaching Points

1. Question

A move consists of taking a point(x, y)and transforming it to either(x, x+y)or(x+y, y).
Given a starting point(sx, sy)and a target point(tx, ty), returnTrueif and only if a sequence of moves exists to transform the point(sx, sy)to(tx, ty). Otherwise, returnFalse.
1
Examples:
2
Input: sx = 1, sy = 1, tx = 3, ty = 5
3
4
Output: True
5
6
Explanation:
7
8
One series of moves that transforms the starting point to the target is:
9
(1, 1) -> (1, 2)
10
(1, 2) -> (3, 2)
11
(3, 2) -> (3, 5)
12
13
Input: sx = 1, sy = 1, tx = 2, ty = 2
14
15
Output: False
16
17
Input: sx = 1, sy = 1, tx = 1, ty = 1
18
19
Output: True
Copied!
Note:
  • sx, sy, tx, tywill all be integers in the range[1, 10^9].

2. Implementation

(1) BFS (TLE)
1
class Solution {
2
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
3
if (sx > tx || sy > ty) {
4
return false;
5
}
6
7
Queue<int[]> queue = new LinkedList<>();
8
queue.add(new int[] {sx, sy});
9
10
while (!queue.isEmpty()) {
11
int size = queue.size();
12
13
for (int i = 0; i < size; i++) {
14
int[] curPoint = queue.remove();
15
int x = curPoint[0], y = curPoint[1];
16
17
if (x == tx && y == ty) {
18
return true;
19
}
20
21
if (x + y <= tx) {
22
queue.add(new int[] {x + y, y});
23
}
24
25
if (x + y <= ty) {
26
queue.add(new int[] {x, x + y});
27
}
28
}
29
}
30
return false;
31
}
32
}
Copied!
(2) Math
思路:看解析
1
class Solution {
2
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
3
while (sx < tx && sy < ty) {
4
if (tx > ty) {
5
tx %= ty;
6
}
7
else {
8
ty %= tx;
9
}
10
}
11
12
if (sx == tx) {
13
return (ty - sy) % sx == 0;
14
}
15
else if (sy == ty) {
16
return (tx - sx) % sy == 0;
17
}
18
else {
19
return false;
20
}
21
}
22
}
Copied!

3. Time & Space Complexity

Math: 时间复杂度O(max(tx, ty)), 空间复杂度O(1)