解题思路

给定长度为 $n$ 的 01 串 $s=s_1s_2\ldots s_n$，要求对每个位置 $i$，统计在它左侧（下标 $< i$）与 $s_i$ 不同的字符个数。 我们可以采用前缀计数的方法：

1. 定义两个变量 cnt0 和 cnt1，分别记录当前已遍历字符中 '0' 和 '1' 的个数。

2. 对每个位置 $i$：

   • 若 $s_i='0'$，则左侧与它不同的字符即为所有已出现的 '1'，即 $a_i = \text{cnt1}$；
   • 若 $s_i='1'$，则 $a_i = \text{cnt0}$。

3. 将对应的计数器自增：若 $s_i='0'$，则 cnt0++；若 $s_i='1'$，则 cnt1++。

这种方法只需一次扫描，时间复杂度 $O(n)$，空间复杂度 $O(1)$。

算法步骤

1. 初始化 cnt0=0, cnt1=0，并准备数组 ans 长度为 $n$。

2. 从 $i=1$ 到 $n$ 依次遍历：

   1. 如果 $s_i='0'$，则 ans[i]=cnt1，同时 cnt0++；
   2. 否则 ans[i]=cnt0，同时 cnt1++。

3. 输出 ans 数组。

复杂度分析

• 时间复杂度：遍历一次字符串，进行常数次操作，故为 $O(n)$。
• 空间复杂度：只使用常数个额外变量与输出数组，故为 $O(n)$。

代码实现

Python

def count_diff(s):
    n = len(s)
    ans = [0] * n
    cnt0, cnt1 = 0, 0
    for i, ch in enumerate(s):
        if ch == '0':
            ans[i] = cnt1      # 左侧所有 '1'
            cnt0 += 1          # 更新 '0' 计数
        else:
            ans[i] = cnt0      # 左侧所有 '0'
            cnt1 += 1          # 更新 '1' 计数
    return ans

if __name__ == '__main__':
    T = int(input().strip())
    for _ in range(T):
        n = int(input().strip())
        s = input().strip()
        res = count_diff(s)
        print(' '.join(map(str, res)))

Java

import java.util.Scanner;

public class Main {
    // 计算每个位置左侧与当前字符不同的数量
    static int[] countDiff(String s) {
        int n = s.length();
        int[] ans = new int[n];
        int cnt0 = 0, cnt1 = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '0') {
                ans[i] = cnt1;  // 左侧所有 '1'
                cnt0++;         // 更新 '0' 计数
            } else {
                ans[i] = cnt0;  // 左侧所有 '0'
                cnt1++;         // 更新 '1' 计数
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            String s = sc.next();
            int[] res = countDiff(s);
            for (int i = 0; i < n; i++) {
                System.out.print(res[i] + (i+1<n ? " " : ""));
            }
            System.out.println();
        }
        sc.close();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 计算每个位置左侧与当前字符不同的数量
vector<int> countDiff(const string &s) {
    int n = s.size();
    vector<int> ans(n);
    int cnt0 = 0, cnt1 = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            ans[i] = cnt1;  // 左侧所有 '1'
            cnt0++;         // 更新 '0' 计数
        } else {
            ans[i] = cnt0;  // 左侧所有 '0'
            cnt1++;         // 更新 '1' 计数
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        string s;
        cin >> n >> s;
        vector<int> res = countDiff(s);
        for (int i = 0; i < n; i++) {
            cout << res[i] << (i+1<n ? ' ' : '\n');
        }
    }
    return 0;
}

题目内容

牛牛拥有一个长度为$n$的$01$串$s$=“$s_1s_2...s_n$”(下标从$1$开始)。

对于每个位置$i(1≤i≤n)$，定义：

• $a_i$为在$i$左侧(即下标$＜i$的位置)中，字符与$s_i$不同的元素个数。

  请你输出整个序列{$a_1,a_2,...a_n$}

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤100)$代表数据组数,每组测试数据描述如下:

在第一行输入一个整数$n(1≤n≤10^3)$，表示字符串长度。

在第二行输入一个长度为$n$,仅由字符'$0$'和'$1$'组成的字符串$s$,表示初始字符串。

输出描述

于每组测试数据，新起一行，按顺序输出$n$个整数$a_1,a_2,...,a_n$相邻整数之间用一个空格分隔。

样例1

输入

2
4
1101
5
01010

输出

0 0 2 1
0 1 1 2 2

说明

对于第一组测试数据：

• 位置$1$：左侧无字符，$a_1=0$；
• 位置2：左侧只有'$1$'，与$s_2$='$1$'相同，$a_2=0$；
• 位置3：$s_3$='$0$'左侧有两个'$1$'，故$a_3=2$:
• 位置4：$s_4$='$1$'，左侧有一个'$0$'，故$a_4=1$。