机器人能否返回原点

难度: Easy

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

移动顺序由字符串 moves 表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。

如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。

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

示例 1:

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

示例 2:

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

提示:

1 <= moves.length <= 2 * 10⁴
moves 只包含字符 'U', 'D', 'L' 和 'R'

Submission

运行时间: 22 ms

内存: 16.1 MB

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

Explain

该题解通过计算移动序列中每个方向的移动次数来判断机器人是否返回原点。具体来说，只有当向右('R')的移动次数等于向左('L')的移动次数，并且向上('U')的移动次数等于向下('D')的移动次数时，机器人才会回到原点。这是因为每一次向某个方向的移动都需要被相反方向的同等次数的移动来抵消，从而使得最终的位置仍然是 (0, 0)。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        # Count the occurrences of each move direction
        r_count = moves.count('R')
        l_count = moves.count('L')
        u_count = moves.count('U')
        d_count = moves.count('D')
        # Check if the counts of opposite directions are equal
        return r_count == l_count and u_count == d_count

Explore

在这个问题中，我们只关心机器人是否能返回原点，而不关心其具体的移动过程。计算每个方向的移动次数并比较它们能够直接判断机器人是否回到原点，这种方法比模拟每一步的移动更为高效。因为模拟每一步需要追踪机器人的实时坐标，而仅仅计算次数则可以忽略中间过程，直接得到结果，这样可以显著减少计算量和时间复杂度。

虽然使用`str.count()`是一个直接且简便的方法来统计字符出现的次数，但在性能上有待考虑。对于每个方向字符，`str.count()`都会遍历整个字符串，这导致总的时间复杂度为O(n)。如果`moves`字符串非常长，这种方法可能会导致效率低下。更有效的方法是使用单次遍历，用一个字典或类似的数据结构来计数每个字符的出现，这样可以保证只遍历字符串一次，时间复杂度为O(n)，在长字符串情况下更加高效。

在当前的算法实现中，只统计了'R', 'L', 'U', 'D'这四个有效字符的出现次数。如果输入字符串含有其他无关字符，它们不会影响到统计结果，因为这些字符的计数并不会被加入到最终用于比较的计数中。因此，算法仍然有效，可以正确判断机器人是否能返回原点。然而，包含大量无关字符的输入可能会对性能产生影响，因为遍历的成本会增加，尽管它们不影响结果。