2833. 距离原点最远的点

题目描述

给你一个长度为 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' 和 '_' 组成

解法

方法一：贪心

遇到字符 '_' 时，我们可以选择向左或向右移动，而题目需要我们求出离原点最远的点，因此，我们可以先进行一次遍历，贪心地把所有的 '_' 都移到左边，求出此时离原点最远的点，再进行一次遍历，贪心地把所有的 '_' 都移到右边，求出此时离原点最远的点，最后取两次遍历中的最大值即可。

进一步地，我们只需要统计出字符串中 'L'、'R' 的个数之差，再加上 '_' 的个数即可。

时间复杂度 $O(n)$，其中 $n$ 为字符串的长度。空间复杂度 $O(1)$。

Python3JavaC++GoTypeScript

class Solution:
    def furthestDistanceFromOrigin(self, moves: str) -> int:
        return abs(moves.count("L") - moves.count("R")) + moves.count("_")

class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        return Math.abs(count(moves, 'L') - count(moves, 'R')) + count(moves, '_');
    }

    private int count(String s, char c) {
        int cnt = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == c) {
                ++cnt;
            }
        }
        return cnt;
    }
}

class Solution {
public:
    int furthestDistanceFromOrigin(string moves) {
        auto cnt = [&](char c) {
            return count(moves.begin(), moves.end(), c);
        };
        return abs(cnt('L') - cnt('R')) + cnt('_');
    }
};

func furthestDistanceFromOrigin(moves string) int {
    count := func(c string) int { return strings.Count(moves, c) }
    return abs(count("L")-count("R")) + count("_")
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

function furthestDistanceFromOrigin(moves: string): number {
    const count = (c: string) => moves.split('').filter(x => x === c).length;
    return Math.abs(count('L') - count('R')) + count('_');
}

2833. 距离原点最远的点

题目描述

解法

方法一：贪心

评论