leetcode
leetcode 1801 ~ 1850
转换字符串的最少操作次数

转换字符串的最少操作次数

难度:

标签:

题目描述

代码结果

运行时间: 23 ms, 内存: 16.0 MB


/*
 * Problem: Given a string 's' composed of 'X' and 'O', determine the minimum number of operations to convert all characters to 'O'.
 * An operation consists of selecting three consecutive characters and converting them to 'O'.
 * 
 * Solution using Java Streams: 
 * 1. Use IntStream to iterate over the string indices and filter only those indices where the character is 'X'.
 * 2. Use a reduction operation to calculate the number of operations by skipping two characters after an operation.
 */

import java.util.stream.IntStream;

public class StreamSolution {
    public int minimumMoves(String s) {
        int[] count = {0};
        IntStream.range(0, s.length())
                 .filter(i -> s.charAt(i) == 'X')
                 .forEach(i -> {
                     count[0]++;
                     for (int j = 0; j < 3 && i + j < s.length(); j++) {
                         s = s.substring(0, i + j) + 'O' + s.substring(i + j + 1);
                     }
                 });
        return count[0];
    }
}

解释

方法:

该题解采用了一种贪心算法。从字符串s的开始到结束扫描,每次遇到'X'时,执行一次操作将这个'X'以及其后的两个字符(如果存在)都转换为'O',因为每次操作都能覆盖三个字符。接着,跳过这三个字符,继续向后扫描。如果字符是'O',则只向后移动一位继续检查。这样的策略确保了每次遇到'X'都以最小代价处理,从而实现将所有字符变为'O'的最少操作次数。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在算法中,遇到'O'时直接跳过而不考虑后续字符会不会形成'XXX',这种做法是否可能错过更优的操作序列?
该算法遇到'O'时直接跳过的策略不会错过更优的操作序列。因为每次遇到'X'时,算法会立即进行操作,覆盖该'X'及其后的两个字符,无论这三个字符的具体组合是什么。这种策略确保了只要有'X'出现,就立即处理,从而避免错过需要操作的机会。此外,跳过'O'只是为了快速移动到下一个可能需要处理的'X',而不影响操作的总数。
🦆
算法在处理如'XXOXX'这样的字符串时,是否会因为第一次操作选择的是前三个字符而不是后三个,导致操作次数增加?
在处理'XXOXX'这样的字符串时,第一次操作选择覆盖前三个字符('XXO'),导致后面的'XX'需要单独再进行一次操作。如果选择覆盖后三个字符('OXX'),同样需要两次操作(一次处理前两个'X',一次处理后两个'X')。因此,无论是选择前三个还是后三个字符进行操作,所需的操作次数都是相同的,这种情况下算法没有导致操作次数增加。
🦆
为什么算法选择每次遇到'X'就执行操作并跳过三个字符?这种贪心策略在哪些情况下是最有效的?
算法之所以每次遇到'X'就执行操作并跳过三个字符,是因为这种策略可以最大化操作的覆盖范围。每次操作可以将连续的三个字符中的所有'X'转换为'O',这样可以确保使用最少的操作次数处理最多的'X'。这种贪心策略在字符串中'X'的分布较为均匀或连续的情况下特别有效,因为它可以快速减少需要处理的'X'数量,降低总操作次数。
🦆
如果字符串长度n不是3的倍数,算法如何确保最后不足三个字符的部分也被正确处理,从而确保所有字符都能转换为'O'?
如果字符串的长度不是3的倍数,算法仍然可以确保所有字符都被正确处理。在遍历字符串时,只要遇到'X',就会执行操作并跳过三个字符。当指针p接近字符串末尾时,即使剩余字符少于三个,算法依然会在遇到'X'时执行操作,覆盖剩余的所有字符(不论是1个还是2个)。因此,无论字符串长度如何,算法都能有效地覆盖并转换所有的'X'。

相关问题