leetcode
leetcode 551 ~ 600
机器人能否返回原点

机器人能否返回原点

难度:

标签:

题目描述

代码结果

运行时间: 22 ms, 内存: 16.1 MB


/*
 题目思路:
 我们可以通过计算机器人每次移动后的坐标变化来判断它是否回到原点。每次向右(R)移动时,x 坐标加 1,向左(L)移动时,x 坐标减 1;
 向上(U)移动时,y 坐标加 1,向下(D)移动时,y 坐标减 1。如果所有移动结束后,x 和 y 坐标都为 0,那么机器人返回了原点。
 使用 Java Stream API 可以更加简洁地实现坐标的计算。
*/
 
import java.util.stream.*;
 
public class RobotReturnToOriginStream {
    public boolean judgeCircle(String moves) {
        int x = moves.chars().map(c -> c == 'R' ? 1 : c == 'L' ? -1 : 0).sum();
        int y = moves.chars().map(c -> c == 'U' ? 1 : c == 'D' ? -1 : 0).sum();
        return x == 0 && y == 0;
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在这种情况下计数而不是模拟每一步的移动来确定机器人的最终位置?
在这个问题中,我们只关心机器人是否能返回原点,而不关心其具体的移动过程。计算每个方向的移动次数并比较它们能够直接判断机器人是否回到原点,这种方法比模拟每一步的移动更为高效。因为模拟每一步需要追踪机器人的实时坐标,而仅仅计算次数则可以忽略中间过程,直接得到结果,这样可以显著减少计算量和时间复杂度。
🦆
在计算字符出现次数时,使用`str.count()`方法是否会有性能考虑,特别是在`moves`字符串非常长的情况下?
虽然使用`str.count()`是一个直接且简便的方法来统计字符出现的次数,但在性能上有待考虑。对于每个方向字符,`str.count()`都会遍历整个字符串,这导致总的时间复杂度为O(n)。如果`moves`字符串非常长,这种方法可能会导致效率低下。更有效的方法是使用单次遍历,用一个字典或类似的数据结构来计数每个字符的出现,这样可以保证只遍历字符串一次,时间复杂度为O(n),在长字符串情况下更加高效。
🦆
如果输入中包含无效字符(即不是 'R', 'L', 'U', 'D'),此算法是否仍然有效?
在当前的算法实现中,只统计了'R', 'L', 'U', 'D'这四个有效字符的出现次数。如果输入字符串含有其他无关字符,它们不会影响到统计结果,因为这些字符的计数并不会被加入到最终用于比较的计数中。因此,算法仍然有效,可以正确判断机器人是否能返回原点。然而,包含大量无关字符的输入可能会对性能产生影响,因为遍历的成本会增加,尽管它们不影响结果。

相关问题

省份数量

n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

 

示例 1:

输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出:2

示例 2:

输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出:3

 

提示:

  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j]10
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]