https://leetcode.com/problems/robot-bounded-in-circle/
On an infinite plane, a robot initially stands at
(0, 0) and faces north. The robot can receive one of three instructions:"G": go straight 1 unit;"L": turn 90 degrees to the left;"R": turn 90 degress to the right.
The robot performs the
instructions given in order, and repeats them forever.
Return
true if and only if there exists a circle in the plane such that the robot never leaves the circle.
Example 1:
Input: "GGLLGG" Output: true Explanation: The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0). When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.
Example 2:
Input: "GG" Output: false Explanation: The robot moves north indefinitely.
Example 3:
Input: "GL" Output: true Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...
Note:
1 <= instructions.length <= 100instructions[i]is in{'G', 'L', 'R'}
https://leetcode.com/problems/robot-bounded-in-circle/discuss/290856/JavaC%2B%2BPython-Let-Chopper-Help-Explain
Starting at the origin and face north
after one sequence of
(0,1),after one sequence of
instructions,- if chopper return to the origin, he's in an obvious circle.
- if chopper finishes with face not towards north,
it will get back to the initial status in another one or three sequences.
Explanation
(x,y) is the location of chopper.d[i] is the direction he is facing.i = (i + 1) % 4 will turn righti = (i + 3) % 4 will turn leftCheck the final status after
instructions.Complexity
Time
Space
O(N)Space
O(1) public boolean isRobotBounded(String ins) {
int x = 0, y = 0, i = 0, d[][] = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}};
for (int j = 0; j < ins.length(); ++j)
if (ins.charAt(j) == 'R')
i = (i + 1) % 4;
else if (ins.charAt(j) == 'L')
i = (i + 3) % 4;
else {
x += d[i][0]; y += d[i][1];
}
return x == 0 && y == 0 || i > 0;
}
When instructions end, if the robot is back to (0,0) or is not facing north (which guarantees it will come back to 0, 0 for another 1 or 3 rounds)
https://leetcode.com/problems/robot-bounded-in-circle/discuss/291358/A-bad-problem-although-it-is-easy
This problem is easy. Just return true if the final position does not change or the facing direction is different from the beginning.
However, this problem is tricky. And I don't think a tricky problem can test or improve a developer's programming skill.
I find more and more tricky problems recently. I feel it is not a good trend if LeetCode goes deeper into it.
https://leetcode.com/problems/robot-bounded-in-circle/discuss/291191/ChineseC%2B%2B-O(n)
题意：一个机器人在原点
(0,0)，默认方向朝北，按下面三个指令行动。G朝当前方向前进一步L左转90度R右转90度
机器人然后按顺序执行一串指令，并且可以重复执行下去。
问机器人是否会在一个固定路线转圈？
问机器人是否会在一个固定路线转圈？
思路：既然机器人是重复执行这串指令，若在固定路线转圈，则肯定是重复若干次后，回到了原点。
否则路线肯定不能固定。
否则路线肯定不能固定。
接下来看什么时候可以回到原点。
如果第一次执行完一串指令后，就在原点，则可以保证是固定路线。
否则继续分析。
如果第一次执行完一串指令后，就在原点，则可以保证是固定路线。
否则继续分析。
执行完一串指令后，不在原点，假设此时新的方向是
如果
dir。如果
dir不是北方，则一定可以回到原点。
证明如下：
如果
如果
dir指向南方，则下一次执行完，机器人就回到原点（方向选择180度，180度镜像）。如果
dir指向东方或西方，则第四次执行完，机器人就回到原点（方向选择90度，90度镜像）。
所以，为了简单起见，只需要让机器人重复执行四次指令串，然后判断是否在原点即可。
当然，也可以直接执行一次，判断方向是不是北方。
当然，也可以直接执行一次，判断方向是不是北方。
https://blog.csdn.net/fuxuemingzhu/article/details/92128721
我们一定知道，这个题不能用暴力解法。机器人的路径最终被圆包括的充分条件是机器在一些指令之后回到原点。由于指令是循环的，题目只给出了部分指令。那么对于该部分指令的要求是，机器人回到了原点或者不再原点且不面向北。
回到原点很好理解，那么不再原点且不面向北是什么意思呢？
如果题目中的指令结束之后，机器人不在原点，那么说明它相对原点移动了一个向量v。机器人在指令结束后的位置成为了新的原点，题目说机器人的初始状态时是面向北的，那么如果在新的原点上仍然面向北，那么一定还会继续向第一次一样相对新的原点移动相同的向量v，此时机器人距原点的向量是2v。
那么为什么不面向北就一定能回到原点呢？这是由于在新的原点新的方向上再次接受相同指令后，机器人移动新向量的长度为|向量v|、方向和v成90度或者180度；多次指令的结果叠加就会抵消第一次移动的v。
思路：有2种情况会形成循环
1. 经过一个周期回到原点
2. 经过一个周期没有回到原点，但是方向变了（经过若干个循环后一定会回到原点）
