【每日一题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)$，那么如果机器人位于原点时，一定产生了环；不位于原点时，需要考虑此时机器人的方向，当机器人不朝北时，一定会产生环

    • 当机器人朝向为北时，每执行一遍指令，会向北移动$(x,y)$，那么一定不会回到原点，不会产生环
    • 当机器人朝向为东时，执行第二遍遍指令，坐标会向移动$(y,-x)$，执行第三遍遍指令，坐标会向移动$(-x,-y)$，执行第四遍遍指令，坐标会向移动$(-y,x)$，因此最终一定回到原点，会产生环
    • 当机器人朝向为南时，再执行一遍指令，会向南移动$(x,y)$，那么一定回到原点，会产生环
    • 当机器人朝向为西时，执行第二遍遍指令，坐标会向移动$(-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$