-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path1041.java
More file actions
113 lines (112 loc) · 4.52 KB
/
Copy path1041.java
File metadata and controls
113 lines (112 loc) · 4.52 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
// 1041. Robot Bounded In Circle
//
// On an infinite plane, a robot initially stands at (0, 0) and faces north. Note that:
//
// The north direction is the positive direction of the y-axis.
// The south direction is the negative direction of the y-axis.
// The east direction is the positive direction of the x-axis.
// The west direction is the negative direction of the x-axis.
// The robot can receive one of three instructions:
//
// "G": go straight 1 unit.
// "L": turn 90 degrees to the left (i.e., anti-clockwise direction).
// "R": turn 90 degrees to the right (i.e., clockwise direction).
// The robot performs the instructions given in order, and repeats them forever.
//
// Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.
//
//
//
// Example 1:
//
// Input: instructions = "GGLLGG"
// Output: true
// Explanation: The robot is initially at (0, 0) facing the north direction.
// "G": move one step. Position: (0, 1). Direction: North.
// "G": move one step. Position: (0, 2). Direction: North.
// "L": turn 90 degrees anti-clockwise. Position: (0, 2). Direction: West.
// "L": turn 90 degrees anti-clockwise. Position: (0, 2). Direction: South.
// "G": move one step. Position: (0, 1). Direction: South.
// "G": move one step. Position: (0, 0). Direction: South.
// Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (0, 2) --> (0, 1) --> (0, 0).
// Based on that, we return true.
// Example 2:
//
// Input: instructions = "GG"
// Output: false
// Explanation: The robot is initially at (0, 0) facing the north direction.
// "G": move one step. Position: (0, 1). Direction: North.
// "G": move one step. Position: (0, 2). Direction: North.
// Repeating the instructions, keeps advancing in the north direction and does not go into cycles.
// Based on that, we return false.
// Example 3:
//
// Input: instructions = "GL"
// Output: true
// Explanation: The robot is initially at (0, 0) facing the north direction.
// "G": move one step. Position: (0, 1). Direction: North.
// "L": turn 90 degrees anti-clockwise. Position: (0, 1). Direction: West.
// "G": move one step. Position: (-1, 1). Direction: West.
// "L": turn 90 degrees anti-clockwise. Position: (-1, 1). Direction: South.
// "G": move one step. Position: (-1, 0). Direction: South.
// "L": turn 90 degrees anti-clockwise. Position: (-1, 0). Direction: East.
// "G": move one step. Position: (0, 0). Direction: East.
// "L": turn 90 degrees anti-clockwise. Position: (0, 0). Direction: North.
// Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (-1, 1) --> (-1, 0) --> (0, 0).
// Based on that, we return true.
//
//
// Constraints:
//
// 1 <= instructions.length <= 100
// instructions[i] is 'G', 'L' or, 'R'.
//
// Runtime 3 ms Beats 10.28%
// Memory 40.8 MB Beats 19.54%
class Solution {
private int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public boolean isRobotBounded(String instructions) {
// line 70 - 73 themselves can pass 104 / 117 test cases
// multiple replaceAll and indexOf might not be cheap
instructions = instructions.replaceAll("RL", "");
instructions = instructions.replaceAll("LR", "");
if (instructions.indexOf("L") == -1 && instructions.indexOf("R") == -1) return false;
int x = 0;
int y = 0;
int direction = 0;
for (int i = 0; i < instructions.length(); i++) {
char c = instructions.charAt(i);
if (c == 'R') {
direction = (direction + 1) % 4;
} else if (c == 'L') {
direction = (direction + 3) % 4;
} else {
x = x + directions[direction][0];
y = y + directions[direction][1];
}
}
return (x == 0 && y == 0) || direction != 0;
}
}
// Runtime 0 ms Beats 100%
// Memory 40.6 MB Beats 66.7%
class Solution {
private int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public boolean isRobotBounded(String instructions) {
int x = 0;
int y = 0;
int direction = 0;
for (int i = 0; i < instructions.length(); i++) {
char c = instructions.charAt(i);
if (c == 'R') {
direction = (direction + 1) % 4;
} else if (c == 'L') {
direction = (direction + 3) % 4;
} else {
x = x + directions[direction][0];
y = y + directions[direction][1];
}
}
return (x == 0 && y == 0) || direction != 0;
}
}