本文已参与「新人创作礼」活动， 一同敞开创作之路。
874. 模拟行走机器人
来源：力扣（LeetCode）
链接: leetcode.cn/problems/wa…
机器人在一个无限巨细的 XY 网格平面上行走，从点 (0, 0) 处开端出发，面向北方。该机器人能够接纳以下三种类型的指令 commands ：
- -2 ：向左转 90 度
- -1 ：向右转 90 度
- 1 <= x <= 9 ：向前移动 x 个单位长度
在网格上有一些格子被视为妨碍物 obstacles 。第 i 个妨碍物坐落网格点 obstacles[i]=(xi,yi)obstacles[i] = (x_i, y_i) 。
机器人无法走到妨碍物上，它将会停留在妨碍物的前一个网格方块上，但仍然能够继续测验进行该路线的其余部分。
回来从原点到机器人一切通过的路径点（坐标为整数）的最大欧式间隔的平方。（即，如果间隔为 5 ，则回来 25 ）
留意：
- 北表明 +Y 方向。
- 东表明 +X 方向。
- 南表明 -Y 方向。
- 西表明 -X 方向。
示例 1：
输入：commands = [4,-1,3], obstacles = []
输出：25
解说：
机器人开端坐落 (0, 0)：
1. 向北移动 4 个单位，抵达 (0, 4)
2. 右转
3. 向东移动 3 个单位，抵达 (3, 4)
间隔原点最远的是 (3, 4) ，间隔为 32 + 42 = 25
示例 2：
输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出：65
解说：机器人开端坐落 (0, 0)：
1. 向北移动 4 个单位，抵达 (0, 4)
2. 右转
3. 向东移动 1 个单位，然后被坐落 (2, 4) 的妨碍物阻挡，机器人停在 (1, 4)
4. 左转
5. 向北走 4 个单位，抵达 (1, 8)
间隔原点最远的是 (1, 8) ，间隔为 12 + 82 = 65
提示：
- 1<=commands.length<=1041 <= commands.length <= 10^4
-
commands[i]is one of the values in the list [-2,-1,1,2,3,4,5,6,7,8,9]. - 0<=obstacles.length<=1040 <= obstacles.length <= 10^4
- −3∗104<=xi,yi<=3∗104-3 * 10^4 <= xi, yi <= 3 * 10^4
- 答案保证小于 2312^{31}
解法
-
模拟+贪心算法： 模拟机器人走路，这儿需求留意方向
- ( 0, 1) — 北：x不动，y向上一步
- ( 1, 0) — 东：y不动，x向右一步
- ( 0, -1) — 南：x不动，y向下一步
- (-1, 0) — 西：y不动，x向左一步
顺时针方向，先确认方向，然后一步一步走，遇到妨碍就break，如果没有就更新坐标，核算间隔，更新最大间隔；妨碍能够运用哈希表，加快查询速度
代码实现
贪心算法
python实现
class Solution:
def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
if not commands:
return 0
direntions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
cur_x, cur_y = 0, 0
cur_dir = 0
ans = 0
obstacles = set(map(tuple, obstacles))
for cmd in commands:
if cmd == -1:
cur_dir = (cur_dir+1) % 4
elif cmd == -2:
cur_dir = (cur_dir+3) % 4
else:
for i in range(cmd):
nx = cur_x + direntions[cur_dir][0]
ny = cur_y + direntions[cur_dir][1]
if (nx, ny) not in obstacles:
cur_x = nx
cur_y = ny
ans = max(ans, cur_x*cur_x+cur_y*cur_y)
else:
break
return ans
c++实现
class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
/*
( 0, 1) -- 北：x不动，y向上一步
( 1, 0) -- 东：y不动，x向右一步
( 0, -1) -- 南：x不动，y向下一步
(-1, 0) -- 西：y不动，x向左一步
*/
if (commands.size() == 0) return 0;
int cur_x = 0, cur_y = 0, cur_dir = 0;
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
unordered_map<int, unordered_set<int>> obs;
for(auto& iter: obstacles) {
obs[iter[0]].insert(iter[1]);
}
int ans = 0;
for (auto &cmd : commands) {
if (cmd == -1)
cur_dir = (cur_dir+1) % 4; // turn left
else if (cmd == -2)
cur_dir = (cur_dir+3) % 4; // turn right
else { // walk alone
for (int i=0; i<cmd; i++) {
int nx = cur_x + directions[cur_dir].first;
int ny = cur_y + directions[cur_dir].second;
auto iter = obs.find(nx);
if (iter == obs.end() || iter->second.find(ny) == iter->second.end()) {
cur_x = nx;
cur_y = ny;
ans = max(ans, cur_x*cur_x+ cur_y*cur_y);
}
}
}
}
return ans;
}
};
复杂度分析
- 时刻复杂度： O(N+K)O(N+K) 其中 N, K 分别是 commands 和 obstacles 的长度。
- 空间复杂度： O(K)O(K) 用于存储 obstacleSet 而运用的空间
参考
- leetcode.cn/problems/wa…
