Easy

题目描述

给你一个长度为 n 的字符串 moves，该字符串仅由字符 'L'、'R' 和 '_' 组成。字符串表示你在数轴上从原点 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' 和 '_' 组成

关键提示：

  • 在最优解中，所有的 '_' 都会被替换为相同的字符
  • 将所有 '_' 字符替换为出现次数最多的字符

解题思路

解题思路

这道题的关键在于理解如何最大化距离原点的距离。

首先分析移动规律：

  • 'L' 必须向左移动，位置 -1
  • 'R' 必须向右移动，位置 +1
  • '_' 可以选择向左或向右移动

为了使最终位置距离原点最远，我们需要让所有可选择的移动（即 '_'）都朝同一个方向移动。

策略分析：

  1. 统计固定的左移次数（'L' 的个数）和右移次数（'R' 的个数）
  2. 统计可选择的移动次数（'_' 的个数）
  3. 计算当前的净移动：net = rightCount - leftCount
  4. 为了最大化距离，所有 '_' 都应该朝着能增大绝对值的方向移动

具体实现：

  • 如果 net >= 0（当前偏向右边），所有 '_' 都向右移动
  • 如果 net < 0（当前偏向左边），所有 '_' 都向左移动
  • 最终距离 = |net + wildcardCount| 或 |net - wildcardCount|

更简洁的表达：最远距离 = |net| + wildcardCount，因为无论当前净移动是正是负，我们都可以通过合理安排 '_' 的方向来增加绝对值。

代码实现

class Solution {
public:
    int furthestDistanceFromOrigin(string moves) {
        int leftCount = 0, rightCount = 0, wildcardCount = 0;
        
        for (char move : moves) {
            if (move == 'L') {
                leftCount++;
            } else if (move == 'R') {
                rightCount++;
            } else {
                wildcardCount++;
            }
        }
        
        int net = rightCount - leftCount;
        return abs(net) + wildcardCount;
    }
};

class Solution:
    def furthestDistanceFromOrigin(self, moves: str) -> int:
        left_count = moves.count('L')
        right_count = moves.count('R')
        wildcard_count = moves.count('_')
        
        net = right_count - left_count
        return abs(net) + wildcard_count

public class Solution {
    public int FurthestDistanceFromOrigin(string moves) {
        int leftCount = 0, rightCount = 0, wildcardCount = 0;
        
        foreach (char move in moves) {
            if (move == 'L') {
                leftCount++;
            } else if (move == 'R') {
                rightCount++;
            } else {
                wildcardCount++;
            }
        }
        
        int net = rightCount - leftCount;
        return Math.Abs(net) + wildcardCount;
    }
}

var furthestDistanceFromOrigin = function(moves) {
    let leftCount = 0;
    let rightCount = 0;
    let wildcardCount = 0;
    
    for (let char of moves) {
        if (char === 'L') {
            leftCount++;
        } else if (char === 'R') {
            rightCount++;
        } else {
            wildcardCount++;
        }
    }
    
    return Math.abs(leftCount - rightCount) + wildcardCount;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历一次字符串统计各字符数量
空间复杂度O(1)只使用了常数个变量存储计数信息

相关题目