1. 困于环中的机器人 - Robot Bounded In Circle

【数组】

Problem Link

在无限的平面上,机器人最初位于 (0, 0) 处,面朝北方。机器人可以接受下列三条指令之一:

  • "G":直走 1 个单位
  • "L":左转 90 度
  • "R":右转 90 度

机器人按顺序执行指令 instructions,并一直重复它们。

只有在平面中存在环使得机器人永远无法离开时,返回 true。否则,返回 false

Example:

示例 1:

输入:"GGLLGG"
输出:true
解释:
机器人从 (0,0) 移动到 (0,2),转 180 度,然后回到 (0,0)。
重复这些指令,机器人将保持在以原点为中心,2 为半径的环中进行移动。

示例 2:

输入:"GG"
输出:false
解释:
机器人无限向北移动。

示例 3:

输入:"GL"
输出:true
解释:
机器人按 (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ... 进行移动。

提示:

  1. 1 <= instructions.length <= 100
  2. instructions[i]{'G', 'L', 'R'}

Analysis

使用数组 pos[4] = {Up, Right, Down, Left}​ 代表当前位置与初始位置的相对关系

使用 dir 记录当前方向

  • R: $(dir + 1) % 4$
  • L: $(dir - 1) % 4$
  • G: $pos[dir]++$

Solution 【数组】 ( 2ms)

执行用时: 2 ms, 在Robot Bounded In Circle的Java提交中击败了68.78% 的用户

内存消耗: 33.8 MB, 在Robot Bounded In Circle的Java提交中击败了100.00% 的用户

 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
36
37
38
39
40
41
42
class Solution {
    public boolean isRobotBounded(String instructions) {
        /* 使用数组pos[4] = {Up, Right, Down, Left} 代表当前位置与初始位置的相对关系
         * 使用 dir 记录当前方向 
         *   - R: (dir + 1) % 4
         *   - L: (dir - 1) % 4
         *   - G: pos[dir]++
         * 由于每次转向为 90°, 因此以一串指令为周期,仅在第1, 2, 4周期结束时到达初始位置可判断无法离开
         */
        int dir = 0;
        int[] pos = new int[4];
        char[] cs = instructions.toCharArray();
        for (int j = 0; j < 4; j++) {
            for (char c : cs) {
                switch(c) {
                    case 'R':
                        dir = (dir + 1) % 4;
                        break;
                    case 'L':
                        dir = (dir + 3) % 4;
                        break;
                    case 'G':
                        pos[dir]++;
                        break;
                    default:
                        throw new IllegalStateException();
                }

            }
            if (pos[0] == pos[2] && pos[1] == pos[3]) {
                return true;
            }
        }
        if (pos[0] == pos[2] && pos[1] == pos[3]) {
            return true;
        } else {
            return false;
        }
        
    }
}

复杂度分析

时间:$O(N)$

空间:$O(1)$