780 Reaching Points

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)

166 Fraction to Recurring Decimal

326 Power of Three

Last modified 2yr ago

Copy link

Contents

780. Reaching Points

1. Question

2. Implementation

3. Time & Space Complexity

780. Reaching Points​

1. Question

2. Implementation

3. Time & Space Complexity

780. Reaching Points