Repository navigation
Expand file tree
/
Copy path_3_robot.java
More file actions
165 lines (155 loc) · 5.87 KB
/
Copy path_3_robot.java
File metadata and controls
165 lines (155 loc) · 5.87 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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
package pp.arithmetic.LCP;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
/**
* Created by wangpeng on 2019-10-09.
* LCP 3. 机器人大冒险
* <p>
* 力扣团队买了一个可编程机器人，机器人初始位置在原点(0, 0)。小伙伴事先给机器人输入一串指令command，机器人就会无限循环这条指令的步骤进行移动。指令有两种：
* <p>
* U: 向y轴正方向移动一格
* R: 向x轴正方向移动一格。
* 不幸的是，在 xy 平面上还有一些障碍物，他们的坐标用obstacles表示。机器人一旦碰到障碍物就会被损毁。
* <p>
* 给定终点坐标(x, y)，返回机器人能否完好地到达终点。如果能，返回true；否则返回false。
* <p>
*
* <p>
* 示例 1：
* <p>
* 输入：command = "URR", obstacles = [], x = 3, y = 2
* 输出：true
* 解释：U(0, 1) -> R(1, 1) -> R(2, 1) -> U(2, 2) -> R(3, 2)。
* 示例 2：
* <p>
* 输入：command = "URR", obstacles = [[2, 2]], x = 3, y = 2
* 输出：false
* 解释：机器人在到达终点前会碰到(2, 2)的障碍物。
* 示例 3：
* <p>
* 输入：command = "URR", obstacles = [[4, 2]], x = 3, y = 2
* 输出：true
* 解释：到达终点后，再碰到障碍物也不影响返回结果。
*
* <p>
* 限制：
* <p>
* 2 <= command的长度 <= 1000
* command由U，R构成，且至少有一个U，至少有一个R
* 0 <= x <= 1e9, 0 <= y <= 1e9
* 0 <= obstacles的长度 <= 1000
* obstacles[i]不为原点或者终点
* <p>
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/programmable-robot
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class _3_robot {
public static void main(String[] args) {
_3_robot robot = new _3_robot();
System.out.println(robot.robot("URR", new int[][]{}, 3, 2));
System.out.println(robot.robot("URR", new int[][]{{2, 2}}, 3, 2));
System.out.println(robot.robot("URR", new int[][]{{4, 2}}, 3, 2));
System.out.println(robot.robot("URRURRR", new int[][]{{7, 7}, {0, 5}, {2, 7}, {8, 6}, {8, 7}, {6, 5}, {4, 4}, {0, 3}, {3, 6}}, 4915, 1966));
//优化解题
System.out.println(robot.robot2("URR", new int[][]{}, 3, 2));
System.out.println(robot.robot2("URR", new int[][]{{2, 2}}, 3, 2));
System.out.println(robot.robot2("URR", new int[][]{{4, 2}}, 3, 2));
System.out.println(robot.robot2("URRURRR", new int[][]{{7, 7}, {0, 5}, {2, 7}, {8, 6}, {8, 7}, {6, 5}, {4, 4}, {0, 3}, {3, 6}}, 4915, 1966));
}
/**
* 解题思路：
* 简单直接能出结果，但是提交超时，主要耗时在障碍物的循环判断上，当障碍物太多了就比较耗时了
* 比如这个case：https://leetcode-cn.com/submissions/detail/32424313/testcase/
* <p>
* 优化求解：{@link _3_robot#robot2(String, int[][], int, int)}
*
* @param command
* @param obstacles
* @param x
* @param y
* @return
*/
public boolean robot(String command, int[][] obstacles, int x, int y) {
int index = 0;
int length = command.length();
int SX = 0, SY = 0;
while (true) {
char c = command.charAt(index % length);
if (c == 'U') {
SY++;
} else if (c == 'R') {
SX++;
} else {
break;
}
if (SX == x && SY == y) {
return true;
}
//不考虑内存的话，可以考虑用map保存障碍物位置，本题提交不过x,y太大
if (isInObstacles(SX, SY, obstacles) || SX > x || SY > y) {
break;
}
index++;
}
return false;
}
private boolean isInObstacles(int x, int y, int[][] obstacles) {
if (obstacles.length == 0) return false;
for (int i = 0; i < obstacles.length; i++) {
if (x == obstacles[i][0] && y == obstacles[i][1]) {
return true;
}
}
return false;
}
/**
* 解题思路：
* 1、鉴于指令是不断走循环的，先算出一个循环内横向走的坐标xx和纵向走的坐标yy，后续的可以通过规则落到第一圈的坐标上
* 2、利用map将一个循环走的坐标保存下来==>xx+"_"+yy,true
* 3、计算走到目标坐标需要的循环次数，映射到第一圈中是否包含该坐标
* 4、同理，循环障碍物，看映射到第一圈中是否包含该坐标
*
* 映射规则：x ==> x - circle * xx
* <p>
* 执行用时 : 3 ms, 在所有 Java 提交中击败了69.76%的用户
* 内存消耗 :36 MB, 在所有 Java 提交中击败了100.00%的用户
*
* @param command
* @param obstacles
* @param x
* @param y
* @return
*/
public boolean robot2(String command, int[][] obstacles, int x, int y) {
int xx = 0, yy = 0;
Map<String, Boolean> set = new HashMap<>();
set.put(xx + "_" + yy, true);
//1
for (char c : command.toCharArray()) {
switch (c) {
case 'U':
yy++;
break;
case 'R':
xx++;
break;
}
//2
set.put(xx + "_" + yy, true);
}
//3
int circle = Math.min(x / xx, y / yy);
if (!set.getOrDefault((x - circle * xx) + "_" + (y - circle * yy), false)) return false;
//4
for (int[] item : obstacles) {
if (item.length < 2) continue;
if (item[0] > x || item[1] > y) continue;
circle = Math.min(item[0] / xx, item[1] / yy);
if (set.getOrDefault((item[0] - circle * xx) + "_" + (item[1] - circle * yy), false)) return false;
}
return true;
}
}