Open azl397985856 opened 2 years ago
时间复杂度:O(N) 空间复杂度:O(1)
def judgeCircle(moves):
x, y, n = 0,0, len(moves)
for i in range(n):
if moves[i] =='U':
y+=1
elif moves[i] =='D':
y-=1
elif moves[i] =='R':
x-=1
elif moves[i] =='L':
x+=1
return x == 0 and y ==0
遍历方向对冲
var judgeCircle = function(moves) {
let x = y = 0;
const a = moves.split('');
for(let i = 0;i < a.length; i++){
if(a[i] === 'L'){
x -= 1;
}else if(a[i] === 'R'){
x += 1;
}else if(a[i] === 'D'){
y -= 1;
}else if(a[i] === 'U'){
y += 1;
}
}
return x === 0 && y === 0
};
模拟移动过程
class Solution {
public boolean judgeCircle(String moves) {
char[] ch = moves.toCharArray();
int x = 0, y = 0;
for (char c : ch) {
if (c == 'R') {
++x;
}
if (c == 'L') {
--x;
}
if (c == 'U') {
++y;
}
if (c == 'D') {
--y;
}
}
return x == 0 && y == 0;
}
}
title: "Day 32 657. 机器人能否返回原点" date: 2021-10-11T08:54:59+08:00 tags: ["Leetcode", "c++", "vector"] categories: ["91-day-algorithm"] draft: true
在二维平面上,有一个机器人从原点 (0, 0) 开始。给出它的移动顺序,判断这个机器人在完成移动后是否在 (0, 0) 处结束。
移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R(右),L(左),U(上)和 D(下)。如果机器人在完成所有动作后返回原点,则返回 true。否则,返回 false。
注意:机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次,“L” 将始终向左移动等。此外,假设每次移动机器人的移动幅度相同。
示例 1:
输入: "UD"
输出: true
解释:机器人向上移动一次,然后向下移动一次。所有动作都具有相同的幅度,因此它最终回到它开始的原点。因此,我们返回 true。
示例 2:
输入: "LL"
输出: false
解释:机器人向左移动两次。它最终位于原点的左侧,距原点有两次 “移动” 的距离。我们返回 false,因为它在移动结束时没有返回原点。
- 1、模拟题,简单解法
class Solution {
public:
bool judgeCircle(string m) {
if(m.size() % 2 != 0) return false;
vector<int> s(2, 0);
for(char ch : m)
{
switch (ch)
{
case 'U' : s[0]++;break;
case 'D' : s[0]--;break;
case 'L' : s[1]++;break;
case 'R' : s[1]--;break;
}
}
return s[0] == 0 && s[1] == 0;
}
};
时间复杂度:O(n),遍历
空间复杂度:O(1)
func judgeCircle(moves string) bool {
length := len(moves)
x, y := 0, 0
for i := 0; i < length; i++ {
switch moves[i] {
case 'U': y--
case 'D': y++
case 'L': x--
case 'R': x++
}
}
return x==0 && y==0
}
https://leetcode-cn.com/problems/robot-return-to-origin/
UD为一个pair,LR为一个pair,遇到U时UD++,D时--,以此类推。 看最后结果是否UD == 0 && LR== 0。
class Solution {
public boolean judgeCircle(String moves) {
int UD = 0;
int LR = 0;
for(int i = 0; i < moves.length(); i++) {
char c = moves.charAt(i);
if(c == 'U') {
UD++;
} else if(c == 'D'){
UD--;
} else if(c == 'L') {
LR++;
} else if(c == 'R') {
LR--;
}
}
return UD == 0 && LR == 0;
}
}
O(n)
O(1)
class Solution {
public boolean judgeCircle(String moves) {
int x = 0;
int y = 0;
for (char c: moves.toCharArray()) {
if (c == 'R') x++;
if (c == 'L') x--;
if (c == 'U') y++;
if (c == 'D') y--;
}
return x == 0 && y == 0;
}
}
思路
根据字符串对原点坐标进行+或者-,如果最后坐标为原点,返回真 代码
class Solution {
public:
bool judgeCircle(string moves) {
int n = moves.size();
transform(moves.begin(), moves.end(),moves.begin(),::towlower);
vector<int> o{ 0, 0 };
for (int i = 0; i < n;i++)
{
if (moves[i]=='u')
{
o[1]++;
}
else if (moves[i] == 'd')
{
o[1]--;
}
else if (moves[i] == 'l')
{
o[0]--;
}
else if (moves[i] == 'r')
{
o[0]++;
}
}
if (o[0] == 0 && o[1] == 0)
{
return true;
}
else
return false;
}
};
复杂度分析 时间复杂度:O(n) 空间复杂度:O(1)
设置2个变量,记录上下移动 和 左右移动。最终回到原点的话 这2个变量必然保持不变。
java
class Solution {
public boolean judgeCircle(String moves) {
int upDoen = 0;
int leftRight = 0;
for(int i = 0; i < moves.length(); i++){
char c = moves.charAt(i);
if(c == 'R'){
leftRight++;
}else if(c == 'L'){
leftRight--;
}else if(c == 'U'){
upDoen++;
}else if(c == 'D'){
upDoen--;
}
}
if(upDoen == 0 && leftRight == 0){
return true;
}
return false;
}
}
时间复杂度:O(n)遍历一遍字符串 空间复杂度:O(1)没有用额外空间
按题意模拟机器人行动轨迹
class Solution:
def judgeCircle(self, moves: str) -> bool:
start = [0, 0]
for m in moves:
if m == 'U':
start[0] += 1
elif m == 'D':
start[0] -= 1
elif m == 'L':
start[1] -= 1
elif m == 'R':
start[1] += 1
return start == [0, 0]
class Solution:
def judgeCircle(self, moves: str) -> bool:
x = y = 0 #坐标 x, y = 0
for move in moves:
if move == "U":
y -= 1
elif move == "L":
x -= 1
elif move == "R":
x += 1
else:
y += 1
if x == 0 and y == 0:
return True
else:
return False
Time: O(n) Space: O(1)
class Solution:
def judgeCircle(self, moves: str) -> bool:
col = 0
row = 0
for m in moves:
if m == 'U':
row -=1
elif m == 'D':
row +=1
elif m == 'L':
col -=1
elif m == 'R':
col +=1
if col == 0 and row == 0:
return True
return False
one loop no extra space
用一个哈希表来记录 U/D/L/R 的出现次数, 然后 返回原点的条件是 U 和 D 的次数相同 并且 L 和 R 的次数相同
import collections
class Solution:
def judgeCircle(self, moves: str) -> bool:
counts = collections.defaultdict(int)
for m in moves:
counts[m] += 1
return counts['U'] == counts['D'] and counts['L'] == counts['R']
时间复杂度: O(N) 遍历数组的复杂度
空间复杂度: O(1) 哈希表的复杂度
class Solution:
def judgeCircle(self, moves: str) -> bool:
position = [0,0]
for m in moves:
if m == 'R':
position[0] += 1
elif m == 'L':
position[0] -= 1
elif m == 'U':
position[1] += 1
elif m == 'D':
position[1] -= 1
return position == [0,0]
Follow the order
Time: O(N)
Space: O(1)
Initialize an array to stand for the position. Iterate through the string to record all the moves. Update position.
class Solution {
public boolean judgeCircle(String moves) {
int[] init = {0, 0};
for (int i = 0; i < moves.length(); ++i) {
if (moves.charAt(i) == 'R') {
init[1]++;
}
else if (moves.charAt(i) == 'L') {
init[1]--;
}
else if (moves.charAt(i) == 'U') {
init[0]--;
}
else {
init[0]++;
}
}
if (init[0] == 0 && init[1] == 0) {
return true;
}
return false;
}
}
class Solution(object):
def judgeCircle(self, moves):
"""
:type moves: str
:rtype: bool
"""
return ((moves.count("L")==moves.count("R")) and (moves.count("U")==moves.count("D")))
time and memory: O(1)
class Solution(object):
def judgeCircle(self, moves):
x = y = 0
for move in moves:
if move == 'U': y -= 1
elif move == 'D': y += 1
elif move == 'L': x -= 1
elif move == 'R': x += 1
return x == y == 0
class Solution {
public boolean judgeCircle(String moves) {
int x = 0;
int y = 0;
for (char c : moves.toCharArray()) {
if (c == 'U') y++;
if (c == 'D') y--;
if (c == 'L') x++;
if (c == 'R') x--;
}
return x == 0 && y == 0;
}
}
时间复杂度:O(n) 空间复杂度:O(1)
思路
用map存储次数
代码
class Solution {
public boolean judgeCircle(String moves) {
HashMap<Character,Integer> map = new HashMap();
map.put('U',0);
map.put('D',0);
map.put('R',0);
map.put('L',0);
char[] chars = moves.toCharArray();
for (int i = 0; i < moves.length(); i++) {
map.put(chars[i],map.getOrDefault(chars[i],0) + 1);
}
if (map.get('U').intValue() == map.get('D').intValue() && map.get('R').intValue() == map.get('L').intValue()){
return true;
}
return false;
}
}
复杂度
时间复杂度:O(N)
空间复杂度:O(1)
思路
用x y记录坐标
代码
class Solution {
public boolean judgeCircle(String moves) {
int x = 0,y = 0;
char[] chars = moves.toCharArray();
for(int i = 0;i < moves.length(); i++){
if(chars[i] == 'R') x++;
if(chars[i] == 'L') x--;
if(chars[i] == 'U') y++;
if(chars[i] == 'D') y--;
}
return x==0 && y==0;
}
}
复杂度
时间复杂度:O(N)
空间复杂度:O(1)
模拟题,按照指令模拟机器人的移动坐标即可。
class Solution {
public:
bool judgeCircle(string moves) {
return judgeCircle(moves, 0, 0, 0);
}
bool judgeCircle(string& moves, int cur, int x, int y) {
if (cur == moves.size()) return x == 0 && y == 0;
char move = moves[cur];
if (move == 'U') x--;
else if (move == 'D') x++;
else if (move == 'L') y--;
else y++;
return judgeCircle(moves, cur + 1, x, y);
}
};
class Solution {
public:
bool judgeCircle(string moves) {
int x = 0, y = 0;
for (const auto move : moves) {
if (move == 'U') x--;
else if (move == 'D') x++;
else if (move == 'L') y--;
else y++;
}
return x == 0 && y == 0;
}
};
const judgeCircle = (moves) => {
let up = 0, down = 0, left = 0, right = 0;
for (let i = 0; i < moves.length; i++) {
switch (moves[i]) {
case 'U':
up++;
down--;
break;
case 'D':
down++;
up--;
break;
case 'L':
left++;
right--;
break;
case 'R':
right++;
left--;
break;
default:
break;
}
}
return up === down && down === left && left === right && right === 0;
};
只需要最后判断这个机器人的坐标是否是 0,0,即 L === R && U === D
/**
* @param {string} moves
* @return {boolean}
*/
// 只需要最后的起始点相同: L === R && U === D 就回到了原点
var judgeCircle = function(moves) {
const obj = {
"R": 0,
"L": 0,
"U": 0,
"D": 0
}
for (const move of moves) obj[move]++
return obj["R"] === obj["L"]
&& obj["U"] === obj["D"]
};
时间复杂度:O(N)
空间复杂度:O(1) 只需要存放几个方向变量
只需要判断LR的个数是否相等,UD的个数是否相等即可
const obj = {
"R": 0,
"L": 0,
"U": 0,
"D": 0
};
for (const move of moves) {
obj[move]++
}
return obj["R"] === obj["L"] && obj["U"] === obj["D"]
时间复杂度:O(n)
空间复杂度:O(1)
https://leetcode-cn.com/problems/robot-return-to-origin/
模拟
class Solution:
def judgeCircle(self, moves: str) -> bool:
# time |s|
# space 1
# imitation
# 写法一
startPos = [0, 0]
for direct in moves:
if direct == 'U':
startPos[1] += 1
elif direct == 'D':
startPos[1] -= 1
elif direct == 'L':
startPos[0] -= 1
elif direct == 'R':
startPos[0] += 1
if (startPos[0] == 0) and (startPos[1] == 0):
return True
else:
return False
class Solution:
def judgeCircle(self, moves):
"""
:type moves: str
:rtype: bool
"""
# 写法二
return moves.count('L') == moves.count('R') and moves.count('U') == moves.count('D')
class Solution {
public boolean judgeCircle(String moves) {
int horizontal = 0, vertical = 0;
for (char c: moves.toCharArray()) {
if (c == 'U') {
vertical--;
} else if (c == 'D') {
vertical++;
} else if (c == 'L') {
horizontal--;
} else if (c == 'R') {
horizontal++;
}
}
return horizontal == 0 && vertical == 0;
}
}
class Solution {
public boolean judgeCircle(String moves) {
int row = 0;
int col = 0;
for (char c : moves.toCharArray()) {
if (c == 'U') {
row--;
} else if (c == 'D') {
row++;
} else if(c == 'L') {
col--;
} else {
col++;
}
}
return row == 0 && col == 0;
}
}
Time: O(N)\ Space: O(1)
class 机器人能否返回原点_657 { public boolean judgeCircle(String moves) { int x = 0, y = 0; for(int i = 0; i < moves.length(); i++) { switch(moves.charAt(i)){ case 'U': y++;break; case 'D': y--;break; case 'L': x++;break; case 'R': x--;break; } } return x==0 && y==0; } }
模拟,用x、y分别记录机器人的横竖坐标
var judgeCircle = function(moves) {
let x = 0
let y = 0
for (const p of moves) {
switch (p) {
case 'U':
y += 1
break;
case 'D':
y += -1
break;
case 'L':
x += -1
break;
case 'R':
x += 1
break;
}
}
return x === 0 && y === 0
};
时间复杂度 O(n) 空间复杂度 O(1)
Language: Java
public boolean judgeCircle(String moves) {
int upDown = 0;
int leftRight = 0;
for (char c : moves.toCharArray()) {
switch (c) {
case 'U':
upDown++;
break;
case 'D':
upDown--;
break;
case 'L':
leftRight++;
break;
case 'R':
leftRight--;
break;
default:
break;
}
}
return upDown == 0 && leftRight == 0;
}
根据题意进行移动。
class Solution {
public:
bool judgeCircle(string moves) {
int x=0, y=0;
for(int i = 0; i < moves.length(); i++) {
if(moves[i] == 'L') x--;
if(moves[i] == 'R') x++;
if(moves[i] == 'U') y++;
if(moves[i] == 'D') y--;
}
if(x==0&&y==0)
return true;
return false;
}
};
Time:O(n) Space:O(1)
模拟横竖坐标移动
class Solution:
def judgeCircle(self, moves: str) -> bool:
x = y = 0
for m in moves:
if m == 'U':
y += 1
elif m == 'D':
y -= 1
elif m == 'L':
x -= 1
elif m == 'R':
x += 1
return True if x == 0 and y == 0 else False
复杂度
用x,y模拟坐标系,遍历字符串判断
var judgeCircle = function(moves) {
let x=y=0;
for(let i = 0; i < moves.length; i++){
const s = moves.charAt(i);
if(s.toLocaleUpperCase() == 'R'){
x -= 1;
}
if(s.toLocaleUpperCase() == 'L'){
x += 1;
}
if(s.toLocaleUpperCase() == 'U'){
y += 1;
}
if(s.toLocaleUpperCase() == 'D'){
y -= 1;
}
}
return x==0&&y==0;
};
class Solution {
public boolean judgeCircle(String moves) {
if (moves == null || moves.length() == 0) return true;
char[] cs = moves.toCharArray();
if (cs.length % 2 == 1) return false; // 移动奇数次时,回不到原点
int hori = 0, vert = 0; // 水平和垂直方向
for (char c : cs) {
switch(c) {
case 'R': hori++;break;
case 'L': hori--;break;
case 'U': vert++;break;
case 'D': vert--;
}
}
return hori == 0 && vert == 0;
}
}
657. 机器人能否返回原点
https://leetcode-cn.com/problems/robot-return-to-origin/
只需按指令模拟机器人移动的坐标即可。起始时机器人的坐标为 (0,0)(0,0)(0,0),在遍历完所有指令并对机器人进行移动之后,判断机器人的坐标是否为 (0,0)(0,0)(0,0) 即可
class Solution(object):
def judgeCircle(self, moves):
x = y = 0
for move in moves:
if move == 'U': y -= 1
elif move == 'D': y += 1
elif move == 'L': x -= 1
elif move == 'R': x += 1
return x == y == 0
用 X表示 L、R 操作动作 +1,-1、最后看是否为0、上下同样
var judgeCircle = function(moves) {
let x = y =0
for(let move of moves){
move = move.toLocaleUpperCase();
if(move== "U") y++
else if(move =="D") y--
else if(move == "L") x++
else if(move == "R") x--
}
return x==0 && y ==0
};
模拟,用两个变量来表示当前坐标,根据指令对坐标进行加和减
语言:JavaScript
var judgeCircle = function(moves) {
let x = 0, y = 0;
moves.split('').forEach(i=>{
if (i === 'U') {
y += 1;
} else if (i === 'D') {
y -= 1;
} else if (i === 'L') {
x -= 1;
} else if (i === 'R') {
x += 1;
}
})
return (x === 0 && y === 0)
};
C++
class Solution {
public:
bool judgeCircle(string moves) {
int x = 0, y = 0;
for (char &s: moves) {
if (s == 'U') y++;
if (s == 'D') y--;
if (s == 'L') x--;
if (s == 'R') x++;
}
return x == 0 && y == 0;
}
};
public boolean judgeCircle(String moves) {
if (moves == null || moves.length() == 0) {
return true;
}
int upAndDown = 0;
int leftAndRight = 0;
char[] arr = moves.toCharArray();
for (char c : arr) {
switch (c) {
case 'R':
leftAndRight++;
break;
case 'L':
leftAndRight--;
break;
case 'U':
upAndDown++;
break;
case 'D':
upAndDown--;
break;
default:
return false;
}
}
return upAndDown == 0 && leftAndRight == 0;
}
var judgeCircle = function(moves) {
var h = 0, v = 0;
for (var i = 0; i < moves.length; i++) {
var move = moves[i];
if (move === 'R') h++;
if (move === 'L') h--;
if (move === 'D') v++;
if (move === 'U') v--;
}
return h === 0 && v === 0;
};
时间:O(n) 空间:O(1)
var judgeCircle = function(moves) { let map={}; moves=moves.split(''); moves.forEach((ele)=>{ map[ele]=map[ele]?++map[ele]:1 }) let res1=0,res2=0; if(map['D']||map['U']){ res1=map['D']-map['U'] } if(map['R']||map['L']){ res2=map['R']-map['L'] } return res1===0&&res2===0 };
Count the number of times on each direction. If Count(L) == Count(R), and Count(U) == Count(D), we know that the robot can go back to its origin
class Solution {
public:
bool judgeCircle(string moves) {
map<char, int> counter;
for (char c : moves)
counter[c]++;
return (counter['L'] == counter['R']) && (counter['U'] == counter['D']);
}
};
O(n), need to process each point once
O(1), just need to store the count of 4 directions.
class Solution {
public boolean judgeCircle(String moves) {
int x = 0;
int y = 0;
for (int i = 0; i < moves.length(); i++) {
if (moves.charAt(i) == 'U') {
y += 1;
} else if (moves.charAt(i) == 'D') {
y -= 1;
} else if (moves.charAt(i) == 'L') {
x -= 1;
} else if (moves.charAt(i) == 'R') {
x += 1;
}
}
return x == 0 && y == 0;
}
}
官方解题思路
Python3 Code
class Solution:
def judgeCircle(self, moves: str) -> bool:
x = y = 0
for move in moves:
if move == 'R': x += 1
if move == 'L': x -= 1
if move == 'U': y += 1
if move == 'D': y -= 1
return x == 0 and y == 0
复杂度
class Solution {
public boolean judgeCircle(String moves) {
int dx = 0, dy = 0;
for (char c : moves.toCharArray()) {
if (c == 'U') {
dy++;
}
if (c == 'D') {
dy--;
}
if (c == 'L') {
dx--;
}
if (c == 'R') {
dx++;
}
}
return dx == 0 && dy == 0;
}
}
class Solution:
def judgeCircle(self, moves: str) -> bool:
up_down = 0
left_right = 0
for m in moves:
if m == 'U':
up_down += 1
elif m == 'D':
up_down -= 1
elif m == 'L':
left_right += 1
elif m == 'R':
left_right -= 1
return up_down == left_right == 0
模拟。
class Solution {
public:
bool judgeCircle(string moves) {
int x = 0, y = 0;
for (const auto& move: moves) {
if (move == 'U') {
y--;
}
else if (move == 'D') {
y++;
}
else if (move == 'L') {
x--;
}
else if (move == 'R') {
x++;
}
}
return x == 0 && y == 0;
}
};
思路: 上下左右模拟 class Solution: def judgeCircle(self, moves: str) -> bool: x=0 y=0 for mov in moves: if mov == "U": y -=1 if mov == "D": y +=1 if mov == "L": x -=1 if mov == "R": x +=1 return x == y == 0 时间复杂度 O(n) 空间复杂度 O (1)
Explanation
Python
class Solution:
def judgeCircle(self, moves: str) -> bool:
m = [0, 0]
d = {"L": (-1, 0), "R": (1, 0), "U": (0, -1), "D": (0, 1)}
for i in moves:
m[0] += d[i][0]
m[1] += d[i][1]
return m == [0, 0]
Complexity:
O(N)
O(1)
遍历一次
public boolean judgeCircle(String moves) {
int a =0;
int b =0;
for (int i = 0; i < moves.length(); i++) {
if(moves.charAt(i)=='L'){
a--;
}
if(moves.charAt(i)=='R'){
a++;
}
if(moves.charAt(i)=='U'){
b++;
}
if(moves.charAt(i)=='D'){
b--;
}
}
return a == 0 && b == 0;
}
T:O(N) S:O(1)
col,row横纵坐标
class Solution:
def judgeCircle(self, moves: str) -> bool:
if moves == None:
return True
row = 0
col = 0
for move in moves:
if move == 'U':
col += 1
if move == 'D':
col -= 1
if move == 'L':
row -= 1
if move == 'R':
row += 1
if row == 0 and col == 0:
return True
return False
时间:O(n) 空间:O(1)
var judgeCircle = function(moves) { let x = 0, y = 0; moves.split('').forEach(i=>{ if (i === 'U') { y += 1; } else if (i === 'D') { y -= 1; } else if (i === 'L') { x -= 1; } else if (i === 'R') { x += 1; } })
return (x === 0 && y === 0)
};
657. 机器人能否返回原点
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/robot-return-to-origin/
前置知识
题目描述
移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R(右),L(左),U(上)和 D(下)。如果机器人在完成所有动作后返回原点,则返回 true。否则,返回 false。
注意:机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次,“L” 将始终向左移动等。此外,假设每次移动机器人的移动幅度相同。
示例 1:
输入: "UD" 输出: true 解释:机器人向上移动一次,然后向下移动一次。所有动作都具有相同的幅度,因此它最终回到它开始的原点。因此,我们返回 true。
示例 2:
输入: "LL" 输出: false 解释:机器人向左移动两次。它最终位于原点的左侧,距原点有两次 “移动” 的距离。我们返回 false,因为它在移动结束时没有返回原点。