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

You are given a string s consisting of n characters which are either 'X' or 'O'.

A move is defined as selecting three consecutive characters of s and converting them to 'O'. Note that if a move is applied to the character 'O', it will stay the same.

Return the minimum number of moves required so that all the characters of s are converted to 'O'.

最近的动力就是早点学完早点打游戏

• 思路：贪心

局部最优：每次从以’X’字符为首的位置转换，使每次转换包含的’X’字符数量最多

全局最优：字符串中’X’字符总数一定，因此转换的总次数最少

• 实现：遍历整个字符串，如果当前字符为’X’，那么进行转换，指针后移三位；如果当前字符为’O’，那么指针后移一位

class Solution {
    public int minimumMoves(String s) {
        int res = 0;
        int i = 0;
        while (i < s.length()){
            char c = s.charAt(i);
            if (c == 'O'){
                i++;
            }else{
                res++;
                i += 3;
            }
        }
        return res;
    }
}

。复杂度

• 时间复杂度：O ( n )
• 空间复杂度：O ( 1 )