【每日一题Day270】LC874模拟行走机器人 | 哈希表+模拟

简介: 【每日一题Day270】LC874模拟行走机器人 | 哈希表+模拟

模拟行走机器人【LC874】

机器人在一个无限大小的 XY 网格平面上行走,从点 (0, 0) 处开始出发,面向北方。该机器人可以接收以下三种类型的命令 commands

  • -2 :向左转 90
  • -1 :向右转 90
  • 1 <= x <= 9 :向前移动 x 个单位长度

在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi)

机器人无法走到障碍物上,它将会停留在障碍物的前一个网格方块上,但仍然可以继续尝试进行该路线的其余部分。

返回从原点到机器人所有经过的路径点(坐标为整数)的最大欧式距离的平方。(即,如果距离为 5 ,则返回 25

注意:

  • 北表示 +Y 方向。
  • 东表示 +X 方向。
  • 南表示 -Y 方向。
  • 西表示 -X 方向。

思路

  • 首先找到左转右转时方向变化的规律
  • 右转时,方向由北->东->南->西
  • 左转时,方向由北<-东<-南<-西
  • 因此可以使用状态压缩表示方向的变化,使用0 1 2 3分别表示北、东、南、西,假设此时方向为dir,那么

image.png

  • 如果没有障碍物,那么向指定方向移动,并求出该位置与原点的距离,判断是否需要更新;否则,停止移动
  • 实现
class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// -1 方向坐标右移,-2方向坐标左移
        // 如何判断在移动过程中是否遇到障碍物,1<= x<=9,将障碍物存储在哈希表中,逐个判断
        // 二维-> 一维 (数据范围:6 * 10^4 *6 * 10^4)
        Set<Integer> obs = new HashSet<>();
        int n = 30000;
        int res = 0, i = 0;
        int x = 0, y = 0;
        for (int[] o : obstacles){
            obs.add(o[0] * n + o[1]);
        }
        for (int c : commands){
            if (c == -1){
                i = (i + 1) % 4;
            }else if (c == -2){
                i = (i + 3) % 4;
            }else{
                int j = 0;
                while (j < c){
                    int newX = x + dirs[i][0], newY = y + dirs[i][1];
                    if (!obs.contains(newX * n + newY)){                        
                        res = Math.max(res, newX * newX + newY * newY);
                        x = newX; 
                        y = newY;
                    }
                    j++;
                }
            }
        }
        return res;
    }
}

image.png

目录
相关文章
|
6月前
|
算法 机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
|
存储 机器人 C++
leetcode 每日一题 874. 模拟行走机器人 c++模拟解法
简单来说就是机器人在一个矩阵上移动 我们要找到一个离原点的一个最大欧式距离的平方
134 0
|
机器学习/深度学习 机器人 Python
蓝桥杯国赛【机器人行走】 Python
蓝桥杯国赛【机器人行走】 Python
174 0
蓝桥杯国赛【机器人行走】 Python
2069. 模拟行走机器人 II : 脑筋急转弯类模拟题
2069. 模拟行走机器人 II : 脑筋急转弯类模拟题
|
机器人 C++
LeetCode 2069. 模拟行走机器人 II(模拟)
LeetCode 2069. 模拟行走机器人 II(模拟)
174 0
LeetCode 2069. 模拟行走机器人 II(模拟)
|
算法 机器人 atlas
逆天机器人 Atlas 再升级:能在乱石中行走,以后送快递交给它就行了
还记得波士顿动力系列(Boston Dynamics)机器人各种花式虐待的视频,其通过各种暴力推倒、拳打脚踢的动作以测试机器人的各种平衡能力以及多地形适应能力。 波士顿动力推出的各种四脚机器人,诸如:Big Dog、Spot、Cheetah 等产品的平衡能力其实已经非常好,基本上能能各种复杂地形轻松自如的行走,当然其平衡能力好的其中一个原因就是采用四脚站立,能更好的支撑身体。
181 0
逆天机器人 Atlas 再升级:能在乱石中行走,以后送快递交给它就行了
|
10天前
|
自然语言处理 算法 机器人
智能电话销售机器人源码搭建部署系统电话机器人源码
智能电话销售机器人源码搭建部署系统电话机器人源码
20 4