【Day 32 】2024-05-09 - 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，因为它在移动结束时没有返回原点。

[smallppgirl]

思路 模拟 代码

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)

[zhiyuanpeng]

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        if len(moves) % 2 != 0:
            return False
        count = collections.Counter(moves)
        if count["U"] == count["D"] and count["L"]==count["R"]:
            return True
        else:
            return False

[CathyShang]

思路：回到原点说明向左与向右的位移量相等，向上与向下位移量相等。

class Solution {
public:
    bool judgeCircle(string moves) {
        int ud = 0, lr = 0;
        bool ans;
        for(auto& cur : moves){
            if(cur=='L')
                lr += -1;
            else if(cur=='R')
                lr += 1;
            else if(cur=='D')
                ud += -1;
            else if(cur=='U')
                ud += 1;
        }
        ans = (ud==0 && lr==0)? true:false;
        return ans;
    }
};

• Time O(n) 字符串长度
• Space O(1)

[xil324]

class Solution(object):
    def judgeCircle(self, moves):
        """
        :type moves: str
        :rtype: bool
        """
        direction_map = {'L':[0,-1], 'U':[1,0], 'R':[0,1],'D':[-1,0]};
        start = [0, 0]
        for move in moves:
            start[0] += direction_map[move][0]
            start[1] += direction_map[move][1] 
        return start == [0,0]

[lxy1108]

思路

记录坐标x和y，每次移动改变坐标值，最终检查坐标是否位于原点

python3代码

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

复杂度分析

空间复杂度o(1) 时间复杂度o(n) n为moves中move的个数

[Dtjk]

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

[GReyQT]

class Solution {
public:
    bool judgeCircle(string moves) {
        int nums_u = 0;
        int nums_d = 0;
        int nums_l = 0;
        int nums_r = 0;
        for (char c : moves) {
            if (c == 'U') {
                nums_u++;
            } else if (c == 'D') {
                nums_d++;
            } else if (c == 'L') {
                nums_l++;
            } else if (c == 'R') {
                nums_r++;
            }
        }
        if (nums_u == nums_d && nums_l == nums_r) {
            return true;
        } else {
            return false;
        }
    }
};

[Martina001]

简单模拟题，时间复杂度：On 空间复杂度 O1

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

[hillsonziqiu]

代码

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

  for (let i = 0; i < moves.length; i++) {
    const item = moves[i];
    if (item === "U") {
      position.y++;
    }
    if (item === "L") {
      position.x--;
    }
    if (item === "R") {
      position.x++;
    }
    if (item === "D") {
      position.y--;
    }
  }

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

复杂度分析

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