[LeetCode]657. Robot Return to Origin

657. Robot Return to Origin

There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.

The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after it finishes all of its moves, return true. Otherwise, return false.

Note: The way that the robot is “facing” is irrelevant. “R” will always make the robot move to the right once, “L” will always make it move left, etc. Also, assume that the magnitude of the robot’s movement is the same for each move.

Example 1:

1
2
3
Input: "UD"
Output: true
Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.

Example 2:

1
2
3
Input: "LL"
Output: false
Explanation: The robot moves left twice. It ends up two "moves" to the left of the origin. We return false because it is not at the origin at the end of its moves.

大概解释一下题目:机器人从原来(0,0)开始走,用键盘上下左右键,判断最后机器人是否回到原点。

方案一

思路:判断是否回到原点,就是左右走动的格数要相等,上下走动的格数也要相等,即count(L) == count(R)而且count(U) == count(D),循环遍历,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool judgeCircle(string moves) {
map<char, int> move_map;
for(char item : moves) {
if(move_map.count(item)>0) {
move_map[item] = move_map[item]+1;
} else {
move_map.insert(make_pair(item, 1));
}
}
if ((move_map['U'] == move_map['D']) && (move_map['R'] == move_map['L'])) {
return true;
}
return false;
}
};

result

Runtime: 36 ms, faster than 7.05% of C++ online submissions for Robot Return to Origin.

Memory Usage: 10.3 MB, less than 98.06% of C++ online submissions for Robot Return to Origin.

方案二

用两个堆来匹配,U遇到堆顶是D,则pop,否则push,其他类似:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
bool judgeCircle(string moves) {
stack<char> updown_stack;
stack<char> lr_stack;
for(char item : moves) {
if(item=='U') {
if (!updown_stack.empty() && updown_stack.top()=='D') {
updown_stack.pop();
} else {
updown_stack.push(item);
}
} else if(item=='D') {
if (!updown_stack.empty() && updown_stack.top()=='U') {
updown_stack.pop();
} else {
updown_stack.push(item);
}
} else if(item=='R') {
if (!lr_stack.empty() && lr_stack.top()=='L') {
lr_stack.pop();
} else {
lr_stack.push(item);
}
} else if(item=='L') {
if (!lr_stack.empty() && lr_stack.top()=='R') {
lr_stack.pop();
} else {
lr_stack.push(item);
}
}
}
if (updown_stack.empty() && lr_stack.empty()) {
return true;
}
return false;
}
};

result

Runtime: 20 ms, faster than 64.52% of C++ online submissions for Robot Return to Origin.

Memory Usage: 10.6 MB, less than 28.68% of C++ online submissions for Robot Return to Origin.

方案三

被固定思维所限,其实只要计算左右和上下的次数,用int值来判断就可以,下面这个方案就很好:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
bool judgeCircle(string moves) {
int updown=0;
int lr=0;
for(char item : moves) {
if(item=='U') {
updown++;
} else if(item=='D') {
updown--;
} else if(item=='L') {
lr++;
} else if(item=='R') {
lr--;
}
}
if (updown==0 && lr==0) {
return true;
}
return false;
}
};

result

Runtime: 16 ms, faster than 96.59% of C++ online submissions for Robot Return to Origin.

Memory Usage: 10.3 MB, less than 97.29% of C++ online submissions for Robot Return to Origin.