526互联

[LeetCode] 874. Walking Robot Simulation

发布时间 2023-07-19 06:58:02作者: CNoodle

A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot can receive a sequence of these three possible types of commands:

  • -2: Turn left 90 degrees.
  • -1: Turn right 90 degrees.
  • 1 <= k <= 9: Move forward k units, one unit at a time.

Some of the grid squares are obstacles. The ith obstacle is at grid point obstacles[i] = (xi, yi). If the robot runs into an obstacle, then it will instead stay in its current location and move on to the next command.

Return the maximum Euclidean distance that the robot ever gets from the origin squared (i.e. if the distance is 5, return 25).

Note:

  • North means +Y direction.
  • East means +X direction.
  • South means -Y direction.
  • West means -X direction.

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: The robot starts at (0, 0):
1. Move north 4 units to (0, 4).
2. Turn right.
3. Move east 3 units to (3, 4).
The furthest point the robot ever gets from the origin is (3, 4), which squared is 32 + 42 = 25 units away.

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: The robot starts at (0, 0):
1. Move north 4 units to (0, 4).
2. Turn right.
3. Move east 1 unit and get blocked by the obstacle at (2, 4), robot is at (1, 4).
4. Turn left.
5. Move north 4 units to (1, 8).
The furthest point the robot ever gets from the origin is (1, 8), which squared is 12 + 82 = 65 units away.

Example 3:

Input: commands = [6,-1,-1,6], obstacles = []
Output: 36
Explanation: The robot starts at (0, 0):
1. Move north 6 units to (0, 6).
2. Turn right.
3. Turn right.
4. Move south 6 units to (0, 0).
The furthest point the robot ever gets from the origin is (0, 6), which squared is 62 = 36 units away.

Constraints:

  • 1 <= commands.length <= 104
  • commands[i] is either -2, -1, or an integer in the range [1, 9].
  • 0 <= obstacles.length <= 104
  • -3 * 104 <= xi, yi <= 3 * 104
  • The answer is guaranteed to be less than 231.

模拟行走机器人。

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

-2 ：向左转 90 度
-1 ：向右转 90 度
1 <= x <= 9 ：向前移动 x 个单位长度
在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点  obstacles[i] = (xi, yi) 。

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

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

注意：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/walking-robot-simulation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是模拟。这一类的题，如果没做过，一下子很难想出来方向和坐标是怎么控制的。这里我把障碍物的坐标转换成了字符串，方便判断。同时我也将四个方向以 「北，东，南，西」的顺序存在 dirs 数组里。其余思路参见代码，应该不难懂。

时间O(m+n) - 把 m 个障碍物坐标放入 hashset + 遍历 n 个 commands

空间O(n)

Java实现

 1 class Solution {
 2     public int robotSim(int[] commands, int[][] obstacles) {
 3         int res = 0;
 4         int x = 0;
 5         int y = 0;
 6         int direction = 0;
 7         // north, east, south, west
 8         int[][] dirs = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 9         
10         Set<String> set = new HashSet<>();
11         for (int[] ob : obstacles) {
12             set.add(ob[0] + "," + ob[1]);
13         }
14 
15         for (int c : commands) {
16             // turn left
17             if (c == -2) {
18                 direction = (direction == 0) ? 3 : direction - 1;
19             }
20             // turn right
21             else if (c == -1) {
22                 direction = (direction == 3) ? 0 : direction + 1;
23             } else {
24                 while (c-- > 0 && !set.contains((x + dirs[direction][0]) + "," + (y + dirs[direction][1]))) {
25                     x += dirs[direction][0];
26                     y += dirs[direction][1];
27                 }
28                 res = Math.max(res, x * x + y * y);
29             }
30         }
31         return res;
32     }
33 }
34 // Time Complexity, O(m + n)
35 // O(m) - add all the obstacles into hashset
36 // O(n) - go over all the commands

 

LeetCode 题目总结