LeetCode——1041. 困于环中的机器人

一、题目

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

北方向是y轴的正方向。
南方向是y轴的负方向。
东方向是x轴的正方向。
西方向是x轴的负方向。
机器人可以接受下列三条指令之一：

“G”：直走 1 个单位
“L”：左转 90 度
“R”：右转 90 度
机器人按顺序执行指令 instructions，并一直重复它们。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/robot-bounded-in-circle/description/

二、C++解法

我的思路及代码

考虑三种情况：
①执行完成一次后方向不变且有位移，此时可以走出去
②执行完成一次后方向反向，那么再执行一次后将会回到原点，走不出去
③执行完成一次后方向逆/顺时针改变90度，这样再执行三次也会回到原点，走不出去
综上所述，可以直接模拟4次，若还在原点则说明走不出去返回 true ，其他情况我们就返回 false ，说明可以走出去

class Solution {
public:bool isRobotBounded(string instructions) {int curFace=0;int row = 0,col = 0;for(int i=0;i<4;i++){for(char ch:instructions){switch(ch){case 'G':if(curFace == 0)row++;if(curFace == 1)col++;if(curFace == 2)row--;if(curFace == 3)col--;break;case 'L':if(curFace == 0)curFace = 3;else curFace--;break;case 'R':if(curFace ==3)curFace = 0;else curFace++;break;}}}if(row == 0&&col == 0)return true;return false;}
};

• 时间复杂度：O(n)，其中 n 是 instructions 的长度，需要遍历 instructions 四次
• 空间复杂度：O(1)，只用到常数空间

官方参考代码

class Solution {
public:bool isRobotBounded(string instructions) {vector<vector<int>> direc {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int direcIndex = 0;int x = 0, y = 0;for (char instruction : instructions) {if (instruction == 'G') {x += direc[direcIndex][0];y += direc[direcIndex][1];} else if (instruction == 'L') {direcIndex += 3;direcIndex %= 4;} else {direcIndex++;direcIndex %= 4;}}return direcIndex != 0 || (x == 0 && y == 0);}
};

• 时间复杂度：O(n)，其中 n 是 instructions 的长度，需要遍历 instructions 一次
• 空间复杂度：O(1)，只用到常数空间