【每日一题Day174】LC1041困于环中的机器人 | 模拟 位运算

困于环中的机器人【LC1041】

在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。注意:

• 北方向 是y轴的正方向。
• 南方向 是y轴的负方向。
• 东方向 是x轴的正方向。
• 西方向 是x轴的负方向。

机器人可以接受下列三条指令之一：

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

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

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

思路

• 首先找到左转右转时方向变化的规律

• 右转时，方向由北->东->南->西
• 左转时，方向由北<-东<-南<-西

     因此可以使用状态压缩表示方向的变化，使用0 1 2 3分别表示北、东、南、西，假设此时方向为dir，那么

• 右转时，方向变为(dir+1)%4
• 左转时，方向变为(dir+3)%4

• 然后判断什么时候会产生环？

    假设第一次执行指令后，机器人的方向为newDir，位置为(x,y)，那么如果机器人位于原点时，一定产生了环；不位于原点时，需要考虑此时机器人的方向，当机器人不朝北时，一定会产生环

1. 当机器人朝向为北时，每执行一遍指令，会向北移动(x,y)，那么一定不会回到原点，不会产生环
2. 当机器人朝向为东时，执行第二遍遍指令，坐标会向移动(y,−x)，执行第三遍遍指令，坐标会向移动(−x,−y)，执行第四遍遍指令，坐标会向移动(−y,x)，因此最终一定回到原点，会产生环
3. 当机器人朝向为南时，再执行一遍指令，会向南移动(x,y)，那么一定回到原点，会产生环
4. 当机器人朝向为西时，执行第二遍遍指令，坐标会向移动(−y,x)，执行第三遍遍指令，坐标会向移动(−x,−y)，执行第四遍遍指令，坐标会向移动(y,−x)，因此最终一定回到原点，会产生环

实现 

class Solution {
    public boolean isRobotBounded(String instructions) {
        int dir = 0;// 0 1 2 3分别表示北、东、南、西
        int[] move = new int[4];// 分别表示在北、东、南、西移动的距离       
        for (char c : instructions.toCharArray()){
            if (c == 'G'){
                move[dir]++;
            }else if (c == 'L'){
                dir = (dir + 1) % 4;
            }else{
                dir = (dir + 3) % 4;
            }
        }
        if ((move[0] == move[2] && move[1] == move[3])|| dir != 0){
            return true;
        }
        return false;
    }
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(C)，C=4