距离原点最远的点

难度:

标签:

题目描述

You are given a string moves of length n consisting only of characters 'L', 'R', and '_'. The string represents your movement on a number line starting from the origin 0.

In the i^th move, you can choose one of the following directions:

move to the left if moves[i] = 'L' or moves[i] = '_'
move to the right if moves[i] = 'R' or moves[i] = '_'

Return the distance from the origin of the furthest point you can get to after n moves.

Example 1:

Input: moves = "L_RL__R"
Output: 3
Explanation: The furthest point we can reach from the origin 0 is point -3 through the following sequence of moves "LLRLLLR".

Example 2:

Input: moves = "_R__LL_"
Output: 5
Explanation: The furthest point we can reach from the origin 0 is point -5 through the following sequence of moves "LRLLLLL".

Example 3:

Input: moves = "_______"
Output: 7
Explanation: The furthest point we can reach from the origin 0 is point 7 through the following sequence of moves "RRRRRRR".

Constraints:

1 <= moves.length == n <= 50
moves consists only of characters 'L', 'R' and '_'.

代码结果

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

/*
 * 思路：
 * 1. 使用Java Stream API来处理字符串中的字符。
 * 2. 分别计算可以左移和右移的次数。
 * 3. 计算最大距离为左移计数和右移计数之和。
 */

import java.util.stream.Stream;

public class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        long leftMoves = moves.chars().filter(c -> c == 'L' || c == '_').count();
        long rightMoves = moves.chars().filter(c -> c == 'R' || c == '_').count();
        
        // 最远距离为左移和右移的最大值
        return (int) Math.max(leftMoves, rightMoves);
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

在实现中，你是如何确定将字符 '_' 算作自由移动，而不是记录为具体的左移或右移？

▷

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

🦆

当字符串中的 'L' 和 'R' 数量完全相等时，如何确保仍然能得到正确的最远距离？

▷

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

🦆

程序中的 `moveNum` 为零时，所有的 '_' 操作是否都应该考虑在同一个方向上执行以达到最远距离？

▷

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

🦆

该算法中，如果输入字符串全为 '_' 时，输出的最远距离是如何确定的？

▷

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

距离原点最远的点

题目描述

代码结果

解释

代码细节讲解

相关问题