LeetCode.874-走路机器人模拟(Walking Robot Simulation)

这是悦乐书的第335次升级，第360篇原创

01 看题和准备

今天详情的是LeetCode算法题中Easy级别的第205题（顺位题号是874）。网格上的机器人从点（0,0）开始并朝北。机器人可以接收三种可能类型的命令之一：

• -2：向左转90度。

• -1：向右转90度。

• 1 <= x <= 9：向前移动x个单位。

少量网格方块是障碍物。第i个障碍位于网格点（obstacles[i][0]，obstacles[i][1]）。假如机器人遇到障碍点，机器人将停留在障碍点前一个网格方格上（但依然会继续执行剩下的指令。）返回机器人从原点开始的最大欧氏距离的平方。例如：

输入：commands = [4，-1,3]，obstacles = []
输出：25
说明：机器人位于（3,4）,3×3 + 4×4 = 25。

输入：commands = [4，-1,4，-2,4]，obstacles = [[2,4]]
输出：65
说明：从（0,0）开始先向北走到（4,0），而后向右，此时朝东，往前走4步，但是在（2,4）遇到了障碍点，所以只能走到（1,4），而不是（4,4），在点（1,4）向左转，此时朝北，向前走4部，到达点（1,8），在（1,8）的平方和最大。

注意：

• 0 <= commands.length <= 10000

• 0 <= barriers.length <= 10000

• -30000 <=障碍物[i] [0] <= 30000

• -30000 <=障碍物[i] [1] <= 30000

• 答案保证小于2 ^ 31。

02 解题

题目中有几个地方需要先解释下：

• 机器人的朝向。初始时，机器人是朝北的，根据题目给的例子1，可以推算出，机器人的朝向和上北下南的方向一致。以（0,0）为原点看，向北就是指向y轴的正方向，向东就是指向x轴的正方向，另外两个方向同理。

• 欧氏距离的平方。其实就是x坐标值和y坐标值的平方和，即X x X + Y x Y之和。

• 机器人前进的方向。既然机器人有朝向的概念，那么其前进的方向也就包含了四个方向，上下左右，那么机器人前进的方向就具备了周期性，以4为周期。

在理解上面这些信息后，再来看这道题，会清晰很多。根据题目的详情，commands数组中会遇到3种指令，-2时左转，-1时右转，剩下就是前进多少步了，但是前进的时候需要判断此方向上有没有障碍物，所以我们需要先将表示障碍物的二维数组解决一下，使用HashSet来存储，这样每次只要要判断HashSet中能否包含障碍点就可，而不必去遍历判断。

在机器人可能前进的四个方向上，我们定义一个二维数组，来表示四个方向，此处我们按照上右下左顺时针的方向来定义，你也可以从其余方向开始，只需后面计算周期的时候能够匹配就行。

在执行前进n步的指令时，我们是以1为单位前进，每执行一步就判断一次障碍点。在执行完前进指令后，需要进行比较最大值，最后输出结果值就可。

public int robotSim(int[] commands, int[][] obstacles) {    int x = 0, y = 0, max = 0, index = 0;    // 将障碍点初始化进HashSet中，以字符串的形式    Set<String> set = new HashSet<String>();    for (int[] arr : obstacles) {        set.add(arr[0]+"-"+arr[1]);    }    // 四个方向，上右下左，index的取值范围是[0,3]    int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};    for (int n : commands) {        if (n == -1) {            index++;            // 右转四次后会回到原点            if (index == 4) {                index = 0;            }        } else if (n == -2) {            index--;            // 左转一次相当于右转3次            if (index == -1) {                index = 3;            }        } else {            // 前进n步，只需此方向上不包含障碍点            while (n-- > 0 && !set.contains((x+directions[index][0])+                    "-"+(y+directions[index][1]))) {                x += directions[index][0];                y += directions[index][1];            }        }        max = Math.max(max, x*x+y*y);    }    return max;}

03 小结

算法专题目前已连续日更超过六个月，算法题文章205+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是一律内容，假如大家有什么好的解法思路、建议或者者其余问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！