金华正规网站建设总部,app软件开发app定制开发价格,上传wordpress到服务器,内蒙古呼和浩特市网络公司文章目录 Walking Robot Simulation 模拟行走机器人问题描述#xff1a;分析代码哈希 Tag Walking Robot Simulation 模拟行走机器人
问题描述#xff1a;
机器人在一个无限大小的 XY 网格平面上行走#xff0c;从点 (0, 0) 处开始出发#xff0c;面向北方。该机器人可以… 文章目录 Walking Robot Simulation 模拟行走机器人问题描述分析代码哈希 Tag Walking Robot Simulation 模拟行走机器人
问题描述
机器人在一个无限大小的 XY 网格平面上行走从点 (0, 0) 处开始出发面向北方。该机器人可以接收以下三种类型的命令 commands
-2 向左转 90 度 -1 向右转 90 度 1 x 9 1 x 9 1x9 向前移动 x 个单位长度 在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 o b s t a c l e s [ i ] ( x i , y i ) obstacles[i] (x_i, y_i) obstacles[i](xi,yi)。
机器人无法走到障碍物上它将会停留在障碍物的前一个网格方块上但仍然可以继续尝试进行该路线的其余部分。
返回从原点到机器人所有经过的路径点坐标为整数的最大欧式距离的平方。即如果距离为 5 则返回 25 1 c o m m a n d s . l e n g t h 1 0 4 c o m m a n d s [ i ] i s o n e o f t h e v a l u e s i n t h e l i s t [ − 2 , − 1 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] 0 o b s t a c l e s . l e n g t h 1 0 4 − 3 ∗ 1 0 4 x i , y i 3 ∗ 1 0 4 答案保证小于 2 31 1 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 10^4\\ -3 * 10^4 xi, yi 3 * 10^4\\ 答案保证小于 2^{31} 1commands.length104commands[i]isoneofthevaluesinthelist[−2,−1,1,2,3,4,5,6,7,8,9]0obstacles.length104−3∗104xi,yi3∗104答案保证小于231
分析 模拟问题属于看上去很简单但是做起来处处是坑。 这个问题中可以移动的范围可以看做是一个二维直角坐标系。起始点是原点[0,0],这个移动范围是不受边界限制的它不同于一般的矩阵有行列大小限制。
唯一受到的限制就是obstacle而且移动的方向是4向上下左右。
最简单的方式就是在每次移动时确定要移动的方向然后移动C步每移动一步需要判断是否遇到obstacle如果遇到就需要在obstacle之前停止。
如果是普通的判断坐标是否是obstacle就需要遍历O(N)的长度而command的次数是 1 0 4 10^4 104所以整体来看这个算法很可能TLE. 所以需要在某个环节进行加速很明显只能在判断的环节进行加速。 加速的方式有几种目标就是缩短判断的时间复杂度最常见的就是HashMap。 移动的过程中一定是有x或者y保持不变 只要每次判断移动的nx,ny是否是obstacle所以时间复杂度基本可以达到O(1). 当然预处理hashmap 的时间复杂度也大概需要 O ( N ) O(N) O(N)整体的时间复杂度 O ( N M ∗ C ) O(NM*C) O(NM∗C).
代码 哈希
public int robotSim(int[] commands, int[][] obstacles) {int[][] dirs {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};int px 0, py 0, d 1;SetInteger set new HashSetInteger();for (int[] obstacle : obstacles) {set.add(obstacle[0] * 60001 obstacle[1]);}int res 0;for (int c : commands) {if (c 0) {d c -1 ? 1 : -1;d % 4;if (d 0) {d 4;}} else {for (int i 0; i c; i) {if (set.contains((px dirs[d][0]) * 60001 py dirs[d][1])) {break;}px dirs[d][0];py dirs[d][1];res Math.max(res, px * px py * py);}}}return res;}时间复杂度 O ( N M ∗ C ) O(NM*C) O(NM∗C)
空间复杂度 O ( M ) O(M) O(M)
Tag
Array
Simulation
