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),3x3 + 4x4 = 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+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!


作者:小川94,发布于:2019/05/16
原文:https://www.cnblogs.com/xiaochuan94/p/10873500.html