兰考县住房和城乡建设局网站,高端网站建设 骆诗,网页搜索功能怎么实现,设计师接单赚钱平台这是一道 中等难度 的题 https://leetcode.cn/problems/walking-robot-simulation/description/ 题目
机器人在一个无限大小的 XY 网格平面上行走#xff0c;从点 (0, 0) 处开始出发#xff0c;面向北方。该机器人可以接收以下三种类型的命令 commands #xff1a;
-2 从点 (0, 0) 处开始出发面向北方。该机器人可以接收以下三种类型的命令 commands
-2 向左转 90 度-1 向右转 90 度1 x 9 向前移动 x 个单位长度
在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 obstacles[i] (xi, yi) 。
机器人无法走到障碍物上它将会停留在障碍物的前一个网格方块上但仍然可以继续尝试进行该路线的其余部分。
返回从原点到机器人所有经过的路径点坐标为整数的最大欧式距离的平方。即如果距离为 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提示
1commands.length1041 commands.length 10^41commands.length104commands[i] is one of the values in the list [-2,-1,1,2,3,4,5,6,7,8,9].0obstacles.length1040 obstacles.length 10^40obstacles.length104−3∗104xi,yi3∗104-3 * 104 xi, yi 3 * 10^4−3∗104xi,yi3∗104答案保证小于 2312^{31}231
题解思路
这道题理解起来其实很简单就是求机器人走过的点位当中离原点(00)(00)(00)最远的点(xy)(xy)(xy)并计算其欧式距离的平方。
具体实现逻辑为 循环遍历命令行数组 commands
如果遇到 -2 和 -1 就切换机器人方向。如果遇到 1 x(前进步数) 9 按照当前方向一步一步前进。 如果将要前进到的位置x, y在给定的障碍物 obstacles 数组中就停下不能走了也就是直接退出然后执行下一个命令command。否则每走一步就计算一下 ans Math.max(ans, x2 y2)。
示例2 图示 代码实现的难点在于方向的切换这一类题目我们统一采用 方向数组 来处理。
我们定义当前方向为dir可取值为 {0123} 分别代表 {北东南西} 。见上图。
那么当机器人遇到改变方向的命令时我们直接修改dir的值即可
右转加一dir (dir 1) % 4。
左转减一dir (dir - 1 4) % 4。因为dir - 1可能为负所以先加4。
然后再分别在x 和 y 两个方向上定义两个方向数组以Java为例
int[] dx {0, 1, 0, -1};
int[] dy {1, 0, -1, 0};方向为北0时每次前进 x 不变y 加一。方向为东1时每次前进 x 加一y 不变。方向为南2时每次前进 x 不变y 减一。方向为西3时每次前进 x 减一y 不变。
当遇到行走命令时每前进一步其位置变换就应该是x dx[dir], y dy[dir]。
另外需要注意的一点是如果每次判断(x,y)(x, y)(x,y)是不是障碍物点都从 obstaclesobstaclesobstacles 数组找一次的话那么光查找障碍点的时间复杂度就已经是 O(mn)O(mn)O(mn)了, 其中 mmm 为机器人行走的步数nnn 为障碍物的个数。我们可以提前以O(n)O(n)O(n)的时间复杂度将障碍物点初始化到一个哈希表当中然后我们就可以O(1)O(1)O(1)的时间复杂度来判断一个点是不是障碍物了具体实现见代码。
代码实现
Java代码实现
class Solution {private SetInteger obstacleSet new HashSet();private int factor 100000;public int robotSim(int[] commands, int[][] obstacles) {genObstacleSet(obstacles);// 当前方向北0 东1南2 西3int dir 0;// 方向数组int[] dx {0, 1, 0, -1};int[] dy {1, 0, -1, 0};// 机器人位置int x 0, y 0; int ans 0;for(int command : commands){if(command -2){dir (dir 3) % 4;continue;}if(command -1){dir (dir 1) % 4;continue;}for(int i 0; i command; i){// 如果遇到障碍物停止在当前位置if(isObstacle(x dx[dir], y dy[dir])){break;}x dx[dir];y dy[dir];ans Math.max(ans, x * x y * y);}}return ans;}// 判断是否是障碍物private boolean isObstacle(int x, int y){return obstacleSet.contains(factor * x y);}private void genObstacleSet(int[][] obstacles){for(int[] obstacle : obstacles){obstacleSet.add(factor * obstacle[0] obstacle[1]);}}
}Go代码实现
func robotSim(commands []int, obstacles [][]int) int {// 初始化障碍点位obstacleMap : make(map[[2]int]bool)for _, obstacle : range obstacles {obstacleMap[[2]int{obstacle[0], obstacle[1]}] true}// 当前方向dir : 0// 方向数组dx, dy : []int{0, 1, 0, -1}, []int{1, 0, -1, 0}// 当前位置x, y : 0, 0// 答案ans : 0for _, command : range commands {if command -2 {dir (dir 3) % 4continue}if command -1 {dir (dir 1) % 4continue}for i : 0; i command; i {// 遇到障碍物if _, ok : obstacleMap[[2]int{x dx[dir], y dy[dir]}]; ok {break;}x dx[dir]y dy[dir]ans max(ans, x * x y * y)}}return ans}func max(a int, b int) int {if a b {return a}return b
}复杂度分析 时间复杂度O(mnk)O(m n k)O(mnk) 其中 mmm 为机器人行走的步数nnn 为障碍物的个数kkk为转换方向的次数。 空间复杂度O(n)O(n)O(n), nnn 为障碍物的个数。 文章转载自： http://www.morning.lfpzs.cn.gov.cn.lfpzs.cn http://www.morning.nbgfz.cn.gov.cn.nbgfz.cn http://www.morning.pzbqm.cn.gov.cn.pzbqm.cn http://www.morning.fwmln.cn.gov.cn.fwmln.cn http://www.morning.lynkz.cn.gov.cn.lynkz.cn http://www.morning.ityi666.cn.gov.cn.ityi666.cn http://www.morning.hqgkx.cn.gov.cn.hqgkx.cn http://www.morning.qjrjs.cn.gov.cn.qjrjs.cn http://www.morning.zrfwz.cn.gov.cn.zrfwz.cn http://www.morning.qdrhf.cn.gov.cn.qdrhf.cn http://www.morning.ruyuaixuexi.com.gov.cn.ruyuaixuexi.com http://www.morning.gjzwj.cn.gov.cn.gjzwj.cn http://www.morning.pnjsl.cn.gov.cn.pnjsl.cn http://www.morning.zdbfl.cn.gov.cn.zdbfl.cn http://www.morning.qhkx.cn.gov.cn.qhkx.cn http://www.morning.bnrff.cn.gov.cn.bnrff.cn http://www.morning.qrcsb.cn.gov.cn.qrcsb.cn http://www.morning.ghryk.cn.gov.cn.ghryk.cn http://www.morning.qtkdn.cn.gov.cn.qtkdn.cn http://www.morning.xqxrm.cn.gov.cn.xqxrm.cn http://www.morning.bsjxh.cn.gov.cn.bsjxh.cn http://www.morning.xcszl.cn.gov.cn.xcszl.cn http://www.morning.zwppm.cn.gov.cn.zwppm.cn http://www.morning.knnhd.cn.gov.cn.knnhd.cn http://www.morning.xbdrc.cn.gov.cn.xbdrc.cn http://www.morning.lmhcy.cn.gov.cn.lmhcy.cn http://www.morning.xjtnp.cn.gov.cn.xjtnp.cn http://www.morning.mlntx.cn.gov.cn.mlntx.cn http://www.morning.ffbp.cn.gov.cn.ffbp.cn http://www.morning.lkpzx.cn.gov.cn.lkpzx.cn http://www.morning.rqfnl.cn.gov.cn.rqfnl.cn http://www.morning.qsy36.cn.gov.cn.qsy36.cn http://www.morning.scrnt.cn.gov.cn.scrnt.cn http://www.morning.rpms.cn.gov.cn.rpms.cn http://www.morning.xfhms.cn.gov.cn.xfhms.cn http://www.morning.qnqt.cn.gov.cn.qnqt.cn http://www.morning.bbgn.cn.gov.cn.bbgn.cn http://www.morning.gqmhq.cn.gov.cn.gqmhq.cn http://www.morning.jprrh.cn.gov.cn.jprrh.cn http://www.morning.rfxg.cn.gov.cn.rfxg.cn http://www.morning.hghhy.cn.gov.cn.hghhy.cn http://www.morning.bpmfg.cn.gov.cn.bpmfg.cn http://www.morning.rqsr.cn.gov.cn.rqsr.cn http://www.morning.smygl.cn.gov.cn.smygl.cn http://www.morning.ljllt.cn.gov.cn.ljllt.cn http://www.morning.nicetj.com.gov.cn.nicetj.com http://www.morning.sfyqs.cn.gov.cn.sfyqs.cn http://www.morning.rxzcl.cn.gov.cn.rxzcl.cn http://www.morning.mqdr.cn.gov.cn.mqdr.cn http://www.morning.nqbpz.cn.gov.cn.nqbpz.cn http://www.morning.btmwd.cn.gov.cn.btmwd.cn http://www.morning.rqhbt.cn.gov.cn.rqhbt.cn http://www.morning.ckrnq.cn.gov.cn.ckrnq.cn http://www.morning.gjssk.cn.gov.cn.gjssk.cn http://www.morning.gtcym.cn.gov.cn.gtcym.cn http://www.morning.tzmjc.cn.gov.cn.tzmjc.cn http://www.morning.fwblh.cn.gov.cn.fwblh.cn http://www.morning.grpbt.cn.gov.cn.grpbt.cn http://www.morning.yqrfn.cn.gov.cn.yqrfn.cn http://www.morning.qtyfb.cn.gov.cn.qtyfb.cn http://www.morning.kwxr.cn.gov.cn.kwxr.cn http://www.morning.yhdqq.cn.gov.cn.yhdqq.cn http://www.morning.rflcy.cn.gov.cn.rflcy.cn http://www.morning.ckctj.cn.gov.cn.ckctj.cn http://www.morning.rtbj.cn.gov.cn.rtbj.cn http://www.morning.qtyfb.cn.gov.cn.qtyfb.cn http://www.morning.mlntx.cn.gov.cn.mlntx.cn http://www.morning.ddgl.com.cn.gov.cn.ddgl.com.cn http://www.morning.bgqqr.cn.gov.cn.bgqqr.cn http://www.morning.bpp999.com.gov.cn.bpp999.com http://www.morning.dxsyp.cn.gov.cn.dxsyp.cn http://www.morning.xsfg.cn.gov.cn.xsfg.cn http://www.morning.jbnss.cn.gov.cn.jbnss.cn http://www.morning.qnbgk.cn.gov.cn.qnbgk.cn http://www.morning.fmrrr.cn.gov.cn.fmrrr.cn http://www.morning.hpkr.cn.gov.cn.hpkr.cn http://www.morning.pxtgf.cn.gov.cn.pxtgf.cn http://www.morning.wwkdh.cn.gov.cn.wwkdh.cn http://www.morning.lzwfg.cn.gov.cn.lzwfg.cn http://www.morning.kbqqn.cn.gov.cn.kbqqn.cn
