【Day 32 】2023-03-17 - 657. 机器人能否返回原点

[azl397985856]

657. 机器人能否返回原点

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/robot-return-to-origin/

前置知识

• 模拟

  题目描述

  
  在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。

移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。

注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

 

示例 1:

输入: "UD" 输出: true 解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。

示例 2:

输入: "LL" 输出: false 解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。

[JiangyanLiNEU]

• T = O(N) N=len(moves)
• S = O(1)

  class Solution:
  def judgeCircle(self, moves: str) -> bool:
      past = defaultdict(int)
      for m in moves:
          past[m] += 1
      return past['U'] == past['D'] and past['L'] == past['R']

[huifeng248]

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        arrs = []
        for move in moves:
            if move == "U":
                arrs.append([-1, 0])
            elif move == "D":
                arrs.append([1,0])
            elif move == "L":
                arrs.append([0, -1])
            elif move =="R":
                arrs.append([0, 1])
        print(arrs)
        row, col = 0, 0
        for pos in arrs:
            r_delta, col_delta = pos
            row += r_delta
            col += col_delta
        print([row, col])
        return [row, col] == [0, 0]

# time complexity: O(N)
# space complexity: O(1)

[Yufanzh]

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        # simulation problem
        # starting (0,0)
        x = 0
        y = 0
        for move in moves:
            if move == "U":
                y += 1
            if move == "D":
                y -= 1
            if move == "L":
                x -= 1
            if move == "R":
                x += 1
        return x == 0 and y == 0

[GuitarYs]

class Solution: def judgeCircle(self, moves: str) -> bool:

simulation problem

    # starting (0,0)
    x = 0
    y = 0
    for move in moves:
        if move == "U":
            y += 1
        if move == "D":
            y -= 1
        if move == "L":
            x -= 1
        if move == "R":
            x += 1
    return x == 0 and y == 0

[JasonQiu]

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        trajectory = {"U": 0, "D": 0, "L": 0, "R": 0}
        for m in moves:
            trajectory[m] += 1
        return trajectory["U"] == trajectory["D"] and trajectory["L"] == trajectory["R"]

Time: O(n) Space: O(1)

[kofzhang]

思路

统计每个字母出现的次数，上下相同，左右相同就能回来。

复杂度

时间复杂度：O(n) 空间复杂度：O(1)

代码

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        c = Counter(moves)
        return c['R']==c['L'] and c['U']==c['D']

[954545647]

/**
 * @param {string} moves
 * @return {boolean}
 */
var judgeCircle = function (moves) {
  const list = moves.split("")
  const map = {
    "L": 0,
    "R": 0,
    "U": 0,
    "D": 0
  }
  for (const dir of moves) {
    map[dir] = map[dir] + 1;
  }
  const leftVal = map["L"];
  const rightVal = map["R"];
  const upVal = map["U"];
  const downVal = map["D"];
  return leftVal === rightVal && upVal === downVal
};

[NorthSeacoder]

/**
 * @param {string} moves
 * @return {boolean}
 */
var judgeCircle = function(moves) {
    let x = 0;
    let y = 0;
    for (let i = 0; i < moves.length; i++) {
        const cur = moves[i];
        switch (cur) {
            case 'U':
                x++;
                break;
            case 'D':
                x--;
                break;
            case 'L':
                y--;
                break;
            case 'R':
                y++;
                break;
        }
    }
    return x === 0 && y === 0;
};

• TC:O(n)
• SC:O(1)

[duke-github]

思路

分别记录上下左右的移动距离 比较上下左右的移动距离是否相当

复杂度

时间复杂度O(n) 空间复杂度O(1)

代码

public boolean judgeCircle(String moves) {
        int[] ans = new int['U'+1];
        for(char c:moves.toCharArray()){
            ans[c]++;
        }
        return ans['L']==ans['R']&&ans['U']==ans['D'];
    }

[wwewwt]

思路

定义初始坐标x=0,y=0；相应的操作对应x，y坐标的增减： R：x+1 ，L：x-1 ，U：y+1 ，D：y-1 特殊情况分析：机器人走的步数如果是奇数，则肯定回不到原点，所以可以快速排除这类情况（理论上占一半）

复杂度

时间复杂度O(n)，空间复杂度O(1)

代码

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        if len(moves)%2 == 1:
            return False

        x = 0
        y = 0
        for i in moves:
            if i == 'R':
                x = x + 1
            elif i == 'L':
                x = x - 1
            elif i == 'U':
                y = y + 1
            elif i == 'D':
                y = y -1

        return x==0 and y==0

[yfu6]

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

[Abby-xu]

class Solution: def judgeCircle(self, moves: str) -> bool: return moves.count('U')==moves.count('D') and moves.count('R')==moves.count('L') if len(moves)%2 == 0 else False

[zpbc007]

思路

回到原点，x、y 都为 0

代码

function judgeCircle(moves: string): boolean {
    const { x, y } = moves.split('').reduce<{ x: number; y: number }>(
        (position, action) => {
            if (action === 'U') {
                position.y++
            }
            if (action === 'D') {
                position.y--
            }
            if (action === 'R') {
                position.x++
            }
            if (action === 'L') {
                position.x--
            }

            return position
        },
        { x: 0, y: 0 },
    )

    return x === 0 && y === 0
}

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[X1AOX1A]

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x_move = {"U": 0, "D": 0, "L": -1, "R": 1}
        y_move = {"U": 1, "D": -1, "L": 0, "R": 0}
        x_axis = 0
        y_axis = 0
        for move in moves:
            x_axis += x_move[move]
            y_axis += y_move[move]
        return x_axis==0 and y_axis==0

• 时间复杂度：O(N)，N = len(moves)
• 空间复杂度：O(1)

[wangqianqian202301]

思路

往上走的步数和往下走的相同 向左的和向右的步数相同

代码

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        udlrHash = {'U':0, 'D':0, 'L':0, 'R':0}
        for c in moves:
            udlrHash[c] = udlrHash[c] + 1
        return udlrHash['U'] == udlrHash['D'] and udlrHash['L'] == udlrHash['R']

复杂度

O(n) O(1)

[jackgaoyuan]

func judgeCircle(moves string) bool {
    up, left := 0, 0
    for _, v := range moves {
        if v == 85 {
            up ++
        } else if v == 68 {
            up--
        } else if v == 76 {
            left++
        } else {
            left--
        }
    }
    return up == 0 && left == 0
}

[linlizzz]

思路

U和D的次数一致并且L和R的次数一致就能回到原点，否则失败

代码

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        return moves.count('U') == moves.count('D') and moves.count('L') == moves.count('R')

复杂度分析

T(n) = O(n), n为动作长度

S(n) = O(1)

[aoxiangw]

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        origin = {"X":0, "Y":0}
        for move in moves:
            if move == "U":
                origin["X"] += 1
            elif move == "D":
                origin["X"] -= 1
            elif move == "L":
                origin["Y"] -= 1
            elif move == "R":
                origin["Y"] += 1
        return origin['X'] == 0 and origin['Y'] == 0

[bookyue]

TC: O(n)
SC: O(1)

    public boolean judgeCircle(String moves) {
        int vertical = 0;
        int horizontal = 0;
        for (char move : moves.toCharArray()) {
            switch (move) {
                case 'U' -> vertical++;
                case 'D' -> vertical--;
                case 'L' -> horizontal++;
                case 'R' -> horizontal--;
            }
        }

        return vertical == 0 && horizontal == 0;
    }

[snmyj]

class Solution {
public:
    bool judgeCircle(string moves) {
        int dx = 0,dy = 0;
        for (int i = 0; i < moves.size(); i++){
            if (moves[i] == 'R') dx += 1;
            if (moves[i] == 'L') dx -= 1;
            if (moves[i] == 'U') dy += 1;
            if (moves[i] == 'D') dy -= 1;
        }
        if (dx == 0 && dy == 0) return true;
        else return false;
    }
};

[Jetery]

class Solution {
public:
    bool judgeCircle(string moves) {
        int x = 0, y = 0;
        for (char c : moves) {
            if (c == 'U') y += 1;
            else if (c == 'D') y -= 1;
            else if (c == 'L') x -= 1;
            else if (c == 'R') x += 1;
        }
        return x == 0 && y == 0;
    }
};

[chocolate-emperor]

class Solution {
public:

    bool judgeCircle(string moves) {
        int x = 0, y = 0;
        int l = moves.length();
        for(int i = 0; i<l ; i++){
            if(moves[i]=='U'){
                y+=1;
            }else if(moves[i]=='D'){
                y-=1;
            }else if(moves[i]=='R'){
                x+=1;
            }else{
                x-=1;
            }
        }    
        return (x==0 && y==0);
    }
};

[csthaha]

/**
 * @param {string} moves
 * @return {boolean}
 */
var judgeCircle = function(moves) {
    let x = 0;
    let y = 0;

    for(let item of moves) {
        switch(item) {
            case "R":
            case "L":
                if(item === 'R') {
                    x++;
                } else {
                    x--;
                }
                break;
            case "U":
            case "D":
                if(item === 'U') {
                    y++;
                } else {
                    y--;
                }
                break;
        }
    }

    return x === 0 && y === 0
};

[Fuku-L]

思路

遍历给定的字符串，如果是 R或L，则修改rl，如果是 U或D，则修改ud。 最后判断 rl==0 && ud == 0。

代码

class Solution {
    public boolean judgeCircle(String moves) {
        int rl = 0;
        int ud = 0;
        for(char ch: moves.toCharArray()){
            if('R' == ch){
                rl--;
            } else if('L' == ch){
                rl++;
            } else if('U' == ch){
                ud--;
            } else if('D' == ch){
                ud++;
            }
        }
        return rl==0 && ud == 0;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[AstrKing]

思路

简而言之，左右和上下的次数要一样才能回到原点，我们就根据这个思路走下去即可

代码

class Solution {
    public boolean judgeCircle(String moves) {
        int x = 0, y = 0;
        for(char move: moves.toCharArray()) {
            if(move == 'R') {
                x++;
            } else if(move == 'L') {
                x--;
            } else if(move == 'U') {
                y++;
            } else if(move == 'D') {
                y--;
            }
        }
        return x == 0 && y == 0;
    }
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

[airwalkers]

class Solution {
    public boolean judgeCircle(String moves) {
        int i = 0, j = 0;
        for (char ch: moves.toCharArray()) {
            if (ch == 'U') {
                i++;
            } else if (ch == 'D') {
                i--;
            } else if (ch == 'L') {
                j--;
            } else {
                j++;
            }
        }
        return i==0 && j==0;
    }
}

[Meisgithub]

class Solution {
public:
    bool judgeCircle(string moves) {
        int x = 0, y = 0;
        for (char dir : moves)
        {
            if (dir == 'U')
            {
                y += 1;
            }
            else if (dir == 'D')
            {
                y -= 1;
            }
            else if (dir == 'L')
            {
                x -= 1;
            }
            else
            {
                x += 1;
            }
        }
        // cout << x << ' ' << y << endl;
        return x == 0 && y == 0;
    }
};

[xb798298436]

var judgeCircle = function (moves) { let p = [0, 0]; for (let i = 0; i < moves.length; i++) { if (moves[i] === "U") p[0] += 1; if (moves[i] === "D") p[0] -= 1; if (moves[i] === "L") p[1] -= 1; if (moves[i] === "R") p[1] += 1; } return p[0] === 0 && p[1] === 0; };

[Lrwhc]

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

[FireHaoSky]

思路：

"""
令U为y-1,D为y+1,L为x-1,R为x+1
"""

代码：python

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        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

复杂度分析：

"""
时间复杂度：O(n)
空间复杂度：O(1)

"""

[yingchehu]

Code

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x, y = 0, 0
        for step in moves:
            if step == 'R':
                x += 1
            elif step == 'L':
                x -= 1
            elif step == 'U':
                y += 1
            else:
                y -= 1
        return x == 0 and y == 0

複雜度

Time: O(N) Space: O(1)

[harperz24]

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x = 0
        y = 0
        for move in moves:
            match move:
                case "U":
                    y += 1
                case "D":
                    y -= 1
                case "L":
                    x -= 1
                case "R":
                    x += 1
        return x == 0 and y == 0

[Bochengwan]

思路

模拟

代码

class Solution {
    public boolean judgeCircle(String moves) {
        int x = 0;
        int y = 0;
        int length = moves.length();
        for(int i = 0; i < length; i++) {
            char move = moves.charAt(i);
            if (move == 'U') {
                y++;
            } else if (move == 'D') {
                y--;
            } else if (move == 'R') {
                x++;
            } else if (move == 'L') {
                x--;
            }
        }
        return x == 0 && y == 0;

    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[wangzh0114]

代码

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;
    }
};

复杂度分析

• TC:O(N)
• SC:O(1)

[jiujingxukong]

解题思路

图问题：UD是y轴的上下移动，LR是x轴的左右移动，看最终x，y坐标是否都是0

解题代码

/**
 * @param {string} moves
 * @return {boolean}
 */
var judgeCircle = function (moves) {
  let pos = [0, 0];
  for (let i of moves) {
    switch (i) {
      case "U":
        pos[1] += 1;
        break;
      case "D":
        pos[1] -= 1;
        break;
      case "L":
        pos[0] -= 1;
        break;
      case "R":
        pos[0] += 1;
    }
  }
  return pos[0] === 0 && pos[1] === 0;
};

复杂度分析

TC：O（n）,n为字符串长度。 SC：O（1）。

[tzuikuo]

思路

上=下 左=右，就能返回

代码

class Solution {
public:
    bool judgeCircle(string moves) {
        int n=moves.size();
        int r=0,l=0,u=0,d=0;
        for(int i=0;i<n;i++){
            if(moves[i]=='R') r++;
            if(moves[i]=='L') l++;
            if(moves[i]=='U') u++;
            if(moves[i]=='D') d++;
        }
        if(r==l&&u==d) return true;
        else return false;
    }
};

复杂度分析

• 时间：O(N)
• 空间：O(1)

[xiaoq777]

class Solution {
    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 -= 1;
                    break;
                case 'D':
                    y += 1;
                    break;
                case 'L':
                    x -= 1;
                    break;
                case 'R':
                    x += 1;
            }
        }
        if(x == 0 && y == 0) {
            return true;
        }
        return false;
    }
}

[Hughlin07]

class Solution {

public boolean judgeCircle(String moves) {
    int x = 0, y = 0;
    for(char move: moves.toCharArray()) {
        if(move == 'R') {
            x++;
        } else if(move == 'L') {
            x--;
        } else if(move == 'U') {
            y++;
        } else if(move == 'D') {
            y--;
        }
    }
    return x == 0 && y == 0;
}

}

Time: O(n)

Space: O(1)

[RestlessBreeze]

code

class Solution {
public:
    bool judgeCircle(string moves) {
        int a = 0;
        int b = 0;
        for (auto& c : moves)
        {
            switch (c)
            {
                case 'L':
                    a--;
                    break;
                case 'R':
                    a++;
                    break;
                case 'U':
                    b++;
                    break;
                case 'D':
                    b--;
                    break;
                default:
                    break;
            }
        }
        return a == 0 && b == 0;
    }
};

[huizsh]

func judgeCircle(moves string) bool {
    x, y := 0, 0
    for _, move := range moves {
        if move == 'R' {
            x++
        } else if move == 'L' {
            x--
        } else if move == 'U' {
            y++
        } else if move == 'D' {
            y--
        }
    }
    return x == 0 && y == 0
}

[joemonkeylee]

思路

做两个变量表示xy轴 控制加减

代码

    public bool JudgeCircle(string moves) {
        int stepX = 0;
        int stepY = 0;

        foreach (char c in moves.ToCharArray())
        {
            if (c == 'L')
            {
                stepX--;
            }
            else if (c == 'R')
            {
                stepX++;
            }
            else if (c == 'D')
            {
                stepY--;
            }
            else if (c == 'U')
            {
                stepY++;
            }
        }
        return stepX == 0 && stepY == 0;
    }

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[kangliqi1]

public boolean judgeCircle(String moves) { int x = 0, y = 0; for(char move: moves.toCharArray()) { if(move == 'R') { x++; } else if(move == 'L') { x--; } else if(move == 'U') { y++; } else if(move == 'D') { y--; } } return x == 0 && y == 0; }

[Lydia61]

657.机器人能否回到原点

思路

位图

代码

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        position = 0+0j
        move_map = {
            'L': -1,
            'R': 1,
            'U': 1j,
            'D': -1j
        }

        for m in moves:
            position += move_map[m]

        return not position

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[bingzxy]

思路

使用数组记录位置，模拟移动

代码

class Solution {
    public boolean judgeCircle(String moves) {
        int[] pos = new int[2];
        for (char c : moves.toCharArray()) {
            if (c == 'U') {
                pos[1]++;
            } else if (c == 'D') {
                pos[1]--;
            } else if (c == 'L') {
                pos[0]--;
            } else {
                pos[0]++;
            }
        }
        return pos[0] == 0 && pos[1] == 0;
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[CruiseYuGH]

思路

关键点

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        start=[0,0]
        for move in moves:
            if move == "R":
                start[0]+=1
            elif move == "L":
                start[0]-=1
            elif move == "U":
                start[1]+=1
            elif move == "D":
                start[1]-=1

        return start==[0,0]

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

[DrinkMorekaik]

const judgeCircle => moves => {
  const map = {
    U: [0, 1],
    D: [0, -1],
    R: [1, 1],
    L: [1, -1]
  }
  const recodeArr = [0, 0]
  for (const i of moves) {
    recodeArr[map[i][0]] += map[i][1]
  }
  return recodeArr[0] === 0 && recodeArr[1] === 0
};

[SoSo1105]

class Solution: def judgeCircle(self, moves: str) -> bool: start=[0,0] for move in moves: if move == "R": start[0]+=1 elif move == "L": start[0]-=1 elif move == "U": start[1]+=1 elif move == "D": start[1]-=1

    return start==[0,0]

[sye9286]

思路

用两个变量表示 X 和 Y 轴，最后如果 XY 均为 0 则表示回到原点。

代码

/**
 * @param {string} moves
 * @return {boolean}
 */
var judgeCircle = function(moves) {
    let X = 0, Y = 0;
    for (let c of moves) {
        if (c === 'L') X -= 1;
        if (c === 'R') X += 1;
        if (c === 'U') Y += 1;
        if (c === 'D') Y -= 1;
    }
    return X === 0 && Y === 0;
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[jmaStella]

思路

up的次数和down的次数相等，left 次数和right的次数相等，回到原点，如果不是泽没有

代码

   public boolean judgeCircle(String moves) {
        int x = 0;
        int y = 0;

        for(int i=0; i<moves.length(); i++){
            char m = moves.charAt(i);
            if(m == 'U'){
                y +=1;
            }else if(m == 'D'){
                y-= 1;
            }else if(m == 'L'){
                x -= 1;
            }else{
                x +=1;
            }
        }

        return x==0 && y==0;
    }

复杂度

O(N) O(1)

[lp1506947671]

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