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


    题目

    874. 模拟行走机器人

    题解思路

    • 初始方向朝y轴正方向,遇到指令command == -1 则向右转, 若为 -2 则向左转

    1. 定义方向[-1,0]、[0,1]、[1,0]、[0,-1] 分别为朝x轴负方向, y轴正方向, x轴正方向,y轴负方向
    2. 初始方向为[0,1], 若向右转 则方向变为[-1,0]、若向左转方向变为[1,0]。
    3. 若向右转则不断 向右递加, 向左转则向左递减
    4. 同时建立集合set 存储有障碍的点。(set集合查询时间复杂度为o(1))

    代码

    C++

    class Solution {
    public:
        int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
            int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
            int sx = 0, sy = 0, res = 0, d = 1;
            set<pair<int, int>> mp;
            for(int i = 0; i < obstacles.size(); ++i){
                pair<int, int> t(obstacles[i][0], obstacles[i][1]);
                mp.insert(t);
            }
            for (int c : commands){
                if (c < 0){
                    d += c == -1 ? 1 : -1;
                    d %= 4;
                    if (d < 0){
                        d += 4;
                    }
                }else{
                    for (int i = 0; i < c; ++i){
                        int nx = sx + dirs[d][0];
                        int ny = sy + dirs[d][1];
                        pair<int, int> t(nx, ny);
                        if (mp.count(t)){
                            break;
                        }
                        res = max(res, nx * nx + ny * ny);
                        sx = nx;
                        sy = ny;
                    }
                }
                
            } 
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    Python

    class Solution:
        def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
            dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
            sx, sy = 0, 0
            d = 1
            res = 0
            mp = set([tuple(i) for i in obstacles])
            for c in commands:
                if c < 0:
                    d += 1 if c == -1 else -1
                    d %= 4
                else:
                    for i in range(c):
                        if tuple([sx + dirs[d][0], sy + dirs[d][1]]) in mp:
                            break
                        else:
                            sx += dirs[d][0]
                            sy += dirs[d][1]
                            res = max(res, sx*sx + sy * sy)
            return res 
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
  • 相关阅读:
    Yaml语法学习
    组装式应用为何成为十二大技术趋势
    无人监测站相关配置
    accelerate 分布式技巧实战--部署ChatGLM-6B(三)
    GO语言gin框架实战-04-websocket链接
    juc面试题总结
    Flink快速入门
    STM32 从0开始系统学习2
    功率谱分析笔记-------脑电相关
    C. RationalLee(贪心+思维)
  • 原文地址:https://blog.csdn.net/qq_39225746/article/details/131817907