LeetCode [1041] Robot Bounded In Circle

 1041. Robot Bounded In Circle

Medium

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. 1 <= instructions.length <= 100
2. instructions[i] is in {'G', 'L', 'R'}

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { 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; } }

YMSF

火星上有一辆小车车， 你在地球上给它发了一段指令， 比如上上下下左左右右左， 小车最后会停留在离出发点左边一格的位置。 问题，你能不能找到一个最短sub指令能够让小车停留在与执行完所有指令的相同地方？

我的解法：

我用了presum去解这个问题， 我首先把问题分解成了一维问题， 然后向他解释清楚原理以后实现了二维的解法： 时空复发度： 都是O（N）

follow up：

如果指令集特别大怎么办？ 你能够想出一种数据结构存储它么？

我回答了 bit存储 面试官表示不满意，最后我也没能回答出来。 面试官告诉我是一种很简单的结构， 我一定是今天面试太多了， 所以脑袋卡壳了。但是我想了两天也没明白是什么数据结构。。。。。

在两个方向上 （上下，左右）用两个int来存，例如上a++，下a--，左的话b++，右的话b--

指令集特别大的时候，用hashmap，因为所有方向上的操作都是与顺序无关的

我觉得好像不用什么数据结构，两个坐标变量就可以了，最后+-累加，算出实际的offset

我还是不能理解怎么把空间复杂度降低到只用两个指针

对， 我当时代码就是这么写， 可是好像还是没有答到点子上。 之后复盘， 感觉自己当时着急了， 应该继续追问需求。 不应该着急说自己思路

这样不对吧，跟顺序是有关系的吧。比如上上左左，跟下下左左，里面这两个左左，就是不同的方向

我想了下，是不是类似利口要另四以：

        // direction的值 0, 1, 2, 3 分别表示 北，东(右)，南，西(左)

        // 对应的单位位移数组move为：{0, 1}, {1, 0}, {0, -1}, {-1, 0}, 注意这里是坐标系的值

        vector<vector<int>> d = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}};

          右对应的实际方向是： direction = (direction + 1) % 4;

          左对应的实际方向是：direction = (direction + 3) % 4;

然后这个实际方向可以用上面的++a, --a, ++b, --b来抵消

如果你能有一个sub指令集从（3，3） 走到（5，5）， 那么是不是说明你从（0，0）出发的话，你就可以通过同样的指令集走到（2，2）？ 任何一个offset等于终点减去起点的距离的sub指令集都可以满足题目所述条件。