题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个由’W’和’B”组成的字符串，w是白色色块，b是黑色色块。再给一个整数 K，要求如果要一个连续 K 个黑色块的子数组，至少要填几次白色快为黑色。

思路分享

代码解答（强烈建议自行解答后再看）

  • 陆爻齐的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int min_oper = INT_MAX;
        int white_count = 0;  // 既是表示窗口内白色块数组，又是表示涂色的次数
        int block_size = blocks.size();
        for (int i = 0; i < block_size; i++) {
            if (blocks[i] == 'W') white_count++;

            if (i < k-1) continue; // 达到窗口大小

            if (white_count < min_oper) min_oper = white_count;

            if (blocks[i-k+1]=='W') white_count--;
        }

        return min_oper;
    }
};
  • 避免分支预测解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int cnt_w = 0;
        for (int i = 0; i < k; i++) {
            cnt_w += blocks[i] & 1;
        }
        int ans = cnt_w;
        for (int i = k; i < blocks.length(); i++) {
            cnt_w += (blocks[i] & 1) - (blocks[i - k] & 1);
            ans = min(ans, cnt_w);
        }
        return ans;
    }
};