​LeetCode解法汇总874. 模拟行走机器人

这篇具有很好参考价值的文章主要介绍了​LeetCode解法汇总874. 模拟行走机器人。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣

描述:

机器人在一个无限大小的 XY 网格平面上行走,从点 (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

提示:

  • 1 <= commands.length <= 104
  • commands[i] is one of the values in the list [-2,-1,1,2,3,4,5,6,7,8,9].
  • 0 <= obstacles.length <= 104
  • -3 * 104 <= xi, yi <= 3 * 104
  • 答案保证小于 231

解题思路:

* 874. 模拟行走机器人

* -2:左转90

* -1:右转90

* 1<=x<=9,移动长度

* 解题思路:

* 首先我们看范围,1 <= commands.length <= 10^4,0 <= obstacles.length <= 10^4。

* 则肯定不能是n*m的复杂度,否则时间会超过。

* 但是commands的遍历肯定是要的,所以我们就想办法解决obstacles,把其变为一个O(1)或者O(lgn)复杂度的查询。

* obstacles按照x轴和y轴分为两个map,key为x或者y坐标,value为这个坐标轴上所有的点,然后进行排序。

* 遍历commands的时候,方向自然不用说,如果遇到了前进或者后退,则判断当前轴距离原点最近的点长度,如果大于command则移动command,否则移动最近长度。文章来源地址https://www.toymoban.com/news/detail-666804.html

代码:

class Solution874
{
public:
    /**
     * 找出比tartget找到有序集合中,比目标值相等或者大的
     * 或者
     * 找到有序集合中,比目标值相等或者小的
     */
    int findIndex(vector<int> *list, int target, bool isBigger)
    {
        int left = 0;
        int right = list->size() - 1;
        int middle;
        int abs = isBigger ? right + 1 : left - 1;
        while (left <= right)
        {
            middle = (left + right) / 2;
            if (isBigger)
            {
                if ((*list)[middle] > target)
                {
                    right = middle - 1;
                    abs = middle;
                }
                else
                {
                    left = middle + 1;
                }
            }
            else
            {
                if ((*list)[middle] < target)
                {
                    abs = middle;
                    left = middle + 1;
                }
                else
                {
                    right = middle - 1;
                }
            }
        }
        return abs;
    }

    /**
     * forward 方向,加或者减
     * value   前进值
     * from    起始值
     */
    void takeStep(map<int, vector<int>> &xMap, map<int, vector<int>> &yMap, int &x, int &y, int forward, int step)
    {

        vector<int> *list;
        int from = 0;
        int *updateValue;
        bool isAdd = forward <= 1;
        if (forward == 0 || forward == 2)
        {
            from = y;
            if (yMap.find(x) == yMap.end())
            {
                y = y + (forward == 0 ? step : step * -1);
                return;
            }
            updateValue = &y;
            list = &(yMap[x]);
        }
        else if (forward == 1 || forward == 3)
        {
            from = x;
            if (xMap.find(y) == xMap.end())
            {
                x = x + (forward == 1 ? step : step * -1);
                return;
            }
            updateValue = &x;
            list = &(xMap[y]);
        }
        int index = findIndex(list, from, isAdd);
        if (index == -1 || index == list->size())
        {
            *updateValue = from + (isAdd ? step : step * -1);
            return;
        }
        // int expect = from + (isAdd ? step : step * -1);//
        int canMove = abs((*list)[index] - from) - 1;
        if (step > canMove)
        {
            *updateValue = from + (isAdd ? canMove : canMove * -1);
        }
        else
        {
            *updateValue = from + (isAdd ? step : step * -1);
        }
    }

    int correctForward(int forward)
    {
        if (forward < 0)
        {
            return 3;
        }
        if (forward > 3)
        {
            return 0;
        }
        return forward;
    }

    int robotSim(vector<int> &commands, vector<vector<int>> &obstacles)
    {
        map<int, vector<int>> xMap;
        map<int, vector<int>> yMap;

        for (vector<int> v : obstacles)
        {
            int x = v[0];
            int y = v[1];
            if (xMap.find(y) == xMap.end())
            {
                xMap[y] = vector<int>();
            }
            xMap[y].push_back(x);

            if (yMap.find(x) == yMap.end())
            {
                yMap[x] = vector<int>();
            }
            yMap[x].push_back(y);
        }
        int max = 0;
        // 排序
        for (auto at = xMap.begin(); at != xMap.end(); at++)
        {
            std::vector<int> &value = at->second;
            sort(value.begin(), value.end());
        }
        for (auto at = yMap.begin(); at != yMap.end(); at++)
        {
            std::vector<int> &value = at->second;
            sort(value.begin(), value.end());
        }
        int forward = 0;
        int x = 0;
        int y = 0;

        for (int i = 0; i < commands.size(); i++)
        {
            int command = commands[i];
            if (command == -2)
            {
                forward = correctForward(forward - 1);
            }
            else if (command == -1)
            {
                forward = correctForward(forward + 1);
            }
            else
            {
                takeStep(xMap, yMap, x, y, forward, command);
            }
            cout << "command:" << command << ",forward:" << forward << ",x:" << x << ",y:" << y << ",value:" << (x * x + y * y) << endl;
            max = std::max(max, x * x + y * y);
        }
        return max;
    }
};

到了这里,关于​LeetCode解法汇总874. 模拟行走机器人的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每日一题(set集合)-874. 模拟行走机器人

    874. 模拟行走机器人 初始方向朝y轴正方向,遇到指令command == -1 则向右转, 若为 -2 则向左转 定义方向[-1,0]、[0,1]、[1,0]、[0,-1] 分别为朝x轴负方向, y轴正方向, x轴正方向,y轴负方向 初始方向为[0,1], 若向右转 则方向变为[-1,0]、若向左转方向变为[1,0]。 若向右转则不断 向右

    2024年02月13日
    浏览(37)
  • 暑期代码每日一练Day3:874. 模拟行走机器人

    题目 874. 模拟行走机器人 分析 这道题就是个简单的模拟 主要有两点考察点: 对 方向数组 的运用 方向数组存储的是各个方向的单位向量,也即: 方向 X Y 向北 0 1 向东 1 0 向南 0 -1 向西 -1 0 存储在数组中,则是方向数组: 我们很容易发现: 我们可以使用一个变量 j 来指示当

    2024年02月16日
    浏览(45)
  • 【LeetCode 算法】Walking Robot Simulation 模拟行走机器人 - 哈希

    机器人在一个无限大小的 XY 网格平面上行走,从点 (0, 0) 处开始出发,面向北方。该机器人可以接收以下三种类型的命令 commands : -2 :向左转 90 度 -1 :向右转 90 度 1 = x = 9 1 = x = 9 1 = x = 9 :向前移动 x 个单位长度 在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位

    2024年02月15日
    浏览(37)
  • 【LeetCode 算法】Walking Robot Simulation 模拟行走机器人 - 二分

    机器人在一个无限大小的 XY 网格平面上行走,从点 (0, 0) 处开始出发,面向北方。该机器人可以接收以下三种类型的命令 commands : -2 :向左转 90 度 -1 :向右转 90 度 1 = x = 9 1 = x = 9 1 = x = 9 :向前移动 x 个单位长度 在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位

    2024年02月11日
    浏览(47)
  • 【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人

    《博主简介》 小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌ 更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍 感谢小伙伴 们点赞、关注! class   Solution :      def   findContentChildren ( self ,  g :  List [ int ],  s

    2024年02月04日
    浏览(52)
  • 【算法-数组-pyhton】模拟行走机器人

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月12日
    浏览(37)
  • leetcode刷题(字符串相加、包含每个查询的最小区间、模拟行走机器人、环形子数组的最大和、满足不等式的最大值、四数之和、树中距离之和)

    目录 1、字符串相加 2、包含每个查询的最小区间 3、模拟行走机器人 4、环形子数组的最大和 5、满足不等式的最大值 6、四数之和 7、 树中距离之和

    2024年02月10日
    浏览(45)
  • ​力扣解法汇总1041. 困于环中的机器人

    https://github.com/September26/java-algorithms 在无限的平面上,机器人最初位于  (0, 0)  处,面朝北方。注意: 北方向  是y轴的正方向。 南方向  是y轴的负方向。 东方向  是x轴的正方向。 西方向  是x轴的负方向。 机器人可以接受下列三条指令之一: \\\"G\\\" :直走 1 个单位 \\\"L\\\" :左转

    2023年04月11日
    浏览(36)
  • 能“出汗”,会“呼吸”的户外行走机器人

    美国亚利桑那州立大学(ASU)科学家研制出了世界上第一个能像人类一样出汗、颤抖和呼吸的户外行走机器人模型。这个机器人名叫ANDI,是一个能模仿人类出汗的热敏“热模型”。 ANDI 身上不仅有可以使它行走的关节,还有其他机器人身上都没有的东西——它浑身上下还有 35

    2024年02月14日
    浏览(25)
  • 论文阅读:四足机器人对抗运动先验学习稳健和敏捷的行走

    论文:Learning Robust and Agile Legged Locomotion Using Adversarial Motion Priors 进一步学习:AMP,baseline方法,TO 介绍了一种新颖的系统,通过使用对抗性运动先验 (AMP) 使四足机器人在复杂地形上实现稳健和敏捷的行走。主要贡献包括为机器人生成AMP数据集,并提出一种教师-学生训练框架

    2024年02月21日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包