Easy

题目描述

给你一个由 n 个字符组成的字符串 s，每个字符不是 ‘X’ 就是 ‘O’。

一次操作定义为选中 s 的三个连续字符并将它们转换为 ‘O’。注意，如果字符已经是 ‘O’，它将保持不变。

返回将 s 中所有字符都转换为 ‘O’ 所需的最少操作次数。

示例 1：

输入：s = "XXX"
输出：1
解释：XXX -> OOO
我们选择所有的 3 个字符，然后一次操作将它们转换。

示例 2：

输入：s = "XXOX"
输出：2
解释：XXOX -> OOOX -> OOOO
第一次操作，我们选择前 3 个字符，将它们转换为 'O'。
然后我们选择后 3 个字符，将它们转换，使得最终字符串全都是 'O'。

示例 3：

输入：s = "OOOO"
输出：0
解释：s 中没有需要转换的 'X'。

约束：

  • 3 <= s.length <= 1000
  • s[i] 是 ‘X’ 或 ‘O’

提示：

  • 找到每次需要考虑的最小子字符串
  • 尽可能延迟操作

解题思路

这是一道经典的贪心问题。我们需要将字符串中所有的 ‘X’ 转换为 ‘O’，每次操作可以将连续的三个字符转换为 ‘O’。

核心思路： 采用贪心策略，从左到右扫描字符串。当遇到第一个 ‘X’ 时，我们必须进行一次操作来消除它。由于每次操作影响连续的三个字符，最优策略是：

  1. 从当前遇到的第一个 ‘X’ 开始，选择它和后面两个字符进行操作
  2. 这样可以确保当前的 ‘X’ 被转换，同时可能将后面的 ‘X’ 一起转换
  3. 跳过已经处理的位置，继续寻找下一个需要处理的 ‘X’

算法步骤：

  1. 使用指针 i 从左到右遍历字符串
  2. 当遇到 ‘X’ 时，执行一次操作（操作计数加1）
  3. 跳过接下来的两个位置（因为这次操作已经覆盖了三个连续字符）
  4. 继续寻找下一个 ‘X’

这种贪心策略的正确性在于：每当我们遇到 ‘X’ 时，我们必须用某次操作来覆盖它，而最早进行操作不会影响最终结果。

时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int minimumMoves(string s) {
        int moves = 0;
        int i = 0;
        
        while (i < s.length()) {
            if (s[i] == 'X') {
                moves++;
                i += 3;  // 跳过这次操作覆盖的三个字符
            } else {
                i++;
            }
        }
        
        return moves;
    }
};

class Solution:
    def minimumMoves(self, s: str) -> int:
        moves = 0
        i = 0
        
        while i < len(s):
            if s[i] == 'X':
                moves += 1
                i += 3  # 跳过这次操作覆盖的三个字符
            else:
                i += 1
        
        return moves

public class Solution {
    public int MinimumMoves(string s) {
        int moves = 0;
        int i = 0;
        
        while (i < s.Length) {
            if (s[i] == 'X') {
                moves++;
                i += 3;  // 跳过这次操作覆盖的三个字符
            } else {
                i++;
            }
        }
        
        return moves;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var minimumMoves = function(s) {
    let moves = 0;
    let i = 0;
    
    while (i < s.length) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(1)

其中 n 是字符串的长度。算法只需要遍历字符串一次，每次遇到 ‘X’ 时跳过三个位置，因此时间复杂度是线性的。空间复杂度为常数级别，只使用了几个变量存储状态。

相关题目