题解

记 zero 和 one为 最后一个 0/1 的下标 ，初始值为 -1。

遍历字符串，每次记录 1 和 0 的最新下标，并将其不同字符的最后一个下标加入答案。

AC代码

• Python

  T = int(input()) 
  for _ in range(T):
      n = int(input())
      s = input()
      zero, one = -1, -1
      ans = []
      for i in range(n):
          if s[i] == '1':
              ans.append(zero)
              one = i + 1
          else:
              ans.append(one)
              zero = i + 1
      print(' '.join(map(str, ans)))
  

• C++

  #include <iostream>
  #include <vector>
  #include <string>
  
  using namespace std;
  
  int main() {
      int T;
      cin >> T;
  
      while (T--) {
          int n;
          cin >> n;
          string s;
          cin >> s;
  
          int zero = -1, one = -1;
          vector<int> ans(n);
  
          for (int i = 0; i < n; ++i) {
              if (s[i] == '1') {
                  ans[i] = zero;
                  one = i + 1;
              } else {
                  ans[i] = one;
                  zero = i + 1;
              }
          }
  
          for (int i = 0; i < n; ++i) {
              cout << ans[i];
              if (i < n - 1) {
                  cout << " ";
              }
          }
          cout << endl;
      }
  
      return 0;
  }
  

• Java

  import java.util.Scanner;
  
  public class Main {
      public static void main(String[] args) {
          Scanner scanner = new Scanner(System.in);
          int T = scanner.nextInt();
          scanner.nextLine();
  
          for (int t = 0; t < T; t++) {
              int n = scanner.nextInt();
              scanner.nextLine();
              String s = scanner.nextLine();
  
              int zero = -1, one = -1;
              int[] ans = new int[n];
  
              for (int i = 0; i < n; i++) {
                  if (s.charAt(i) == '1') {
                      ans[i] = zero;
                      one = i + 1;
                  } else {
                      ans[i] = one;
                      zero = i + 1;
                  }
              }
  
              for (int i = 0; i < n; i++) {
                  System.out.print(ans[i]);
                  if (i < n - 1) {
                      System.out.print(" ");
                  }
              }
              System.out.println();
          }
  
          scanner.close();
      }
  }
  

题目描述

小红拥有一个长度为 $n$ 的 01 串，现在他想知道，对于每个字符，在它前面的最近的不同字符的下标是多少。

输入描述

本题为多组测试数据，第一行输入一个正整数 $T$（$1 \leq T \leq 100$），代表测试数据组数。对于每组测试数据，第一行输入一个正整数 $n$（$1 \leq n \leq 1000$），代表初始 01 串的长度。第二行输入一个长度为 $n$ 的 01 串，代表初始字符串。

输出描述

对于每组测试数据，输出一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，其中 $a_i$ 代表初始字符串中第 $i$ 个位置的字符前面，最近的不同字符的下标是 $a_i$。特殊的，如果前面不存在不同字符，则输出 $-1$ 表示不存在。

样例输入

1
4
1101

样例输出

-1 -1 2 3