2023年7月19日每日一题--874. 模拟行走机器人

leetcode链接：
https://leetcode.cn/problems/walking-robot-simulation/

题目分析

尝试通过HashMap的方法来解决此问题，经历了，但是最终未通过

方案一

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int result = 0;
        int direction = 400; // 定义机器人的前进方向。取余数：0：北   1：东  2：南  3：西
        // 此处的数值为什么设置为400? 因为 -1%4 的答案为 -1。为了完成此问题，如果你做到一直递减400次，我认了
        int[] reboot = new int[2]; // 记录机器人所在的位置 (x,y)

        HashMap<Integer, List<Integer>> xHashMap = new HashMap<>();
        HashMap<Integer, List<Integer>> yHashMap = new HashMap<>();

        for (int[] obstacle : obstacles) {
            if (xHashMap.containsKey(obstacle[0])) {
                List<Integer> list = xHashMap.get(obstacle[0]);
                list.add(obstacle[1]);
                xHashMap.replace(obstacle[0], list);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(obstacle[1]);
                xHashMap.put(obstacle[0], list);
            }
            if (yHashMap.containsKey(obstacle[1])) {
                List<Integer> list = yHashMap.get(obstacle[1]);
                list.add(obstacle[0]);
                yHashMap.replace(obstacle[1], list);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(obstacle[0]);
                yHashMap.put(obstacle[1], list);
            }
        }

        for (Map.Entry<Integer, List<Integer>> tem : xHashMap.entrySet()) {
            tem.getValue().sort(((o1, o2) -> (o1 - o2)));
        }
        for (Map.Entry<Integer, List<Integer>> tem : yHashMap.entrySet()) {
            tem.getValue().sort(((o1, o2) -> (o1 - o2)));
        }

        for (int command : commands) {
            if (command < 0) { // 此时机器人进行转向操作
                direction = command == -1 ? direction + 1 : direction - 1;
            } else { // 此时机器人尝试前进
                int temp = direction % 4;
                switch (direction % 4) {
                    case 0 : // y++
                        if (xHashMap.containsKey(reboot[0])) {
                            reboot[1] = selectIndex(reboot[1], command, xHashMap.get(reboot[0]));
                        } else {
                            reboot[1] += command;
                        }
                        break;
                    case 1 : // x++
                        if (yHashMap.containsKey(reboot[1])) {
                            reboot[0] = selectIndex(reboot[0], command, yHashMap.get(reboot[1]));
                        } else {
                            reboot[0] += command;
                        }
                        break;
                    case 2 : // y--
                        if (xHashMap.containsKey(reboot[0])) {
                            reboot[1] = selectIndex(reboot[1], -1 * command, xHashMap.get(reboot[0]));
                        } else {
                            reboot[1] -= command;
                        }
                        break;
                    case 3 : // x--
                        if (yHashMap.containsKey(reboot[1])) {
                            reboot[0] = selectIndex(reboot[0], -1 * command, yHashMap.get(reboot[1]));
                        } else {
                            reboot[0] -= command;
                        }
                        break;
                }

                if ((reboot[0] * reboot[0] + reboot[1] * reboot[1]) > result) {
                    result = reboot[0] * reboot[0] + reboot[1] * reboot[1];
                }
            }
        }
        return result;
    }
    /**
     * 找到满足条件的数值
     * @param index 开始的起点
     * @param l 向走的步数
     * @param list 障碍所在的坐标
     * @return
     */
    private static int selectIndex(int index, int l, List<Integer> list) {
        if (l > 0) {
            if (index >= list.get(list.size() - 1) || (index + l) < list.get(0)) {
                return index + l;
            }

            int i = 0;
            for (; index > list.get(i); i++) {
            }

            if (index + l > list.get(i)) {
                return list.get(i) - 1;
            }
            return index + l;
        } else {
            if (index <= list.get(0) || (index + l) > list.get(list.size() - 1)) {
                return index + l;
            }

            int i = list.size() - 1;
            for (; index < list.get(i); i--) {
            }

            if (index + l < list.get(i)) {
                return list.get(i) + 1;
            }
            return index + l;
        }
    }
}

结果

解答错误
42 / 48 个通过测试用例

方案二

官方题解

https://leetcode.cn/problems/walking-robot-simulation/solution/mo-ni-xing-zou-ji-qi-ren-by-leetcode-sol-41b8/

感觉好 狗🐕

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        int px = 0, py = 0, d = 1;
        Set<Integer> set = new HashSet<Integer>();
        for (int[] obstacle : obstacles) {
            set.add(obstacle[0] * 60001 + obstacle[1]);
        }
        int res = 0;
        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++) {
                    if (set.contains((px + dirs[d][0]) * 60001 + py + dirs[d][1])) {
                        break;
                    }
                    px += dirs[d][0];
                    py += dirs[d][1];
                    res = Math.max(res, px * px + py * py);
                }
            }
        }
        return res;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/walking-robot-simulation/solution/mo-ni-xing-zou-ji-qi-ren-by-leetcode-sol-41b8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。