距离原点最远的点

标签: 字符串 计数

难度: Easy

给你一个长度为 n 的字符串 moves ，该字符串仅由字符 'L'、'R' 和 '_' 组成。字符串表示你在一条原点为 0 的数轴上的若干次移动。

你的初始位置就在原点（0），第 i 次移动过程中，你可以根据对应字符选择移动方向：

  • 如果 moves[i] = 'L' 或 moves[i] = '_' ，可以选择向左移动一个单位距离
  • 如果 moves[i] = 'R' 或 moves[i] = '_' ，可以选择向右移动一个单位距离

移动 n 次之后，请你找出可以到达的距离原点 最远 的点，并返回 从原点到这一点的距离 。

示例 1：

输入：moves = "L_RL__R"
输出：3
解释：可以到达的距离原点 0 最远的点是 -3 ，移动的序列为 "LLRLLLR" 。

示例 2：

输入：moves = "_R__LL_"
输出：5
解释：可以到达的距离原点 0 最远的点是 -5 ，移动的序列为 "LRLLLLL" 。

示例 3：

输入：moves = "_______"
输出：7
解释：可以到达的距离原点 0 最远的点是 7 ，移动的序列为 "RRRRRRR" 。

提示：

  • 1 <= moves.length == n <= 50
  • moves 仅由字符 'L'、'R' 和 '_' 组成

Submission

运行时间: 22 ms

内存: 16.1 MB

class Solution:
    def furthestDistanceFromOrigin(self, moves: str) -> int:
        moveNum, spaceNum = 0, 0
        for char in moves:
            if char == 'L' :
                moveNum += 1
            elif char == 'R' :
                moveNum -= 1
            else :
                spaceNum += 1
        return abs(moveNum)+spaceNum

Explain

该题解的核心思路是通过计算所有可控字符 'L' 和 'R' 的净移动方向，并统计所有自由的移动选项 '_' 的数量。每个 'L' 让位置增加 1，每个 'R' 让位置减少 1，从而计算出在不考虑 '_' 时的净位置。然后，为了达到最远距离，所有的 '_' 都应该朝向离原点距离更远的方向移动。因此，最远距离是净位置的绝对值加上所有 '_' 的数量。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def furthestDistanceFromOrigin(self, moves: str) -> int:
        moveNum, spaceNum = 0, 0  # 初始化计数器：moveNum 用于记录净移动距离（左+1，右-1），spaceNum 用于记录 '_' 的数量
        for char in moves:  # 遍历每个字符以更新计数器
            if char == 'L':
                moveNum += 1  # 对于 'L'，增加移动距离
            elif char == 'R':
                moveNum -= 1  # 对于 'R'，减少移动距离
            else:
                spaceNum += 1  # 对于 '_'，增加自由移动的计数
        return abs(moveNum) + spaceNum  # 返回最远距离：净移动的绝对值加上自由移动的次数

Explore

字符 '_' 在题设中被定义为自由移动选项，意味着其可以根据需要向左或向右移动，以最大化距离原点的远离程度。其不被记录为具体的左移或右移，是因为其灵活性允许在最终计算总移动距离时，根据其他已确定的移动('L' 或 'R')的净结果，决定其最优的移动方向。这种处理方式使得在任何给定的净移动位置基础上，可以通过增加所有 '_' 的数量来达到最远的可能距离。

当 'L' 和 'R' 的数量完全相等时，净移动距离（moveNum）为零。在这种情况下，所有的 '_' 仍然可以自由移动，且为了最大化距离，它们应该全部向同一方向移动（无论是左还是右）。因此，即使 'L' 和 'R' 相抵消，通过将所有的 '_' 加到最远距离计算中，仍然可以确保得到正确的最远距离，即 '_' 的总数。

是的，当 `moveNum` 为零时，意味着 'L' 和 'R' 之间的移动完全抵消，此时处于原点。为了达到最远距离，所有的 '_' 应当在同一个方向上执行（全部向左或全部向右），这样可以确保在原点的基础上以最大程度增加距离，使总移动距离等于 '_' 的数量。

如果输入字符串全为 '_'，这意味着没有任何确定的左移或右移，因此净移动距离（moveNum）为零。在这种情况下，所有的 '_' 都可以自由选择向左或向右移动。为了实现最远距离，所有的 '_' 将被统一在同一方向上移动（全部向左或全部向右）。因此，输出的最远距离将等于 '_' 的总数。