【入门篇】小游戏——多语言求解版
题目链接
样例说明
样例中：
-
小明的第一次操作是查询，我们可以得到字符串 “010011” 中第一次出现 ‘1’ 的位置为 2 。
-
小明的第二次操作将下标为 2的字符反转，此时字符串变为 “000011” 。
-
小明的第三次操作是查询，我们可以得到字符串 “000011” 中第一次出现 ‘1’
的位置为 5 。 -
小明的第四次操作是将下标为 6 的字符反转，此时字符串变为 “000010”
-
小明的第五次操作是查询，我们可以得到字符串 “000010” 中第一次出现 ‘1’ 的位置为 5 。
理解了！从程序设计学生的角度来看，我们可以通过一些简单而高效的方式来处理这个问题。我们先理清问题的要点，找出最直接的求解方式，然后给出代码实现。
问题要点总结
-
字符串更新和查询：我们有一个初始的二进制字符串
s，需要进行q次操作。- 操作1：查询字符串中第一次出现
'1'的位置。 - 操作2：反转指定位置上的字符（从
'0'变为'1'，或者从'1'变为'0'）。
- 操作1：查询字符串中第一次出现
-
高效求解的关键：
- 对于 操作1，直接遍历字符串查找第一个
'1'会比较低效，特别是在字符串很长且查询次数较多的情况下。 - 对于 操作2，我们只需要在原字符串上更新指定位置的值。
- 对于 操作1，直接遍历字符串查找第一个
思路
- 初始化阶段：先将字符串转换为一个列表，方便后续更新字符。
- 查询操作：每次查询我们可以从当前字符串的头部开始查找第一个
'1'，如果找到了，就返回其位置。如果没有找到，返回-1。 - 更新操作：直接对字符串中指定位置的字符进行反转，之后查询操作可以直接利用更新后的字符串。
具体步骤：
-
初始化：
- 将输入字符串
s转换为列表，方便修改。 - 找到字符串中第一个
'1'的位置，并记录。
- 将输入字符串
-
操作1：直接输出记录的第一个
'1'的位置。 -
操作2：反转指定位置的字符，并更新
first_one_index（如果该位置是'1'或'0'）。
算法设计
- 将字符串转换为列表，以便快速修改。
- 遍历字符串一次，记录第一个
'1'的位置。 - 对于操作1，直接返回
first_one_index。 - 对于操作2，更新指定位置，并根据需要调整
first_one_index。
代码实现
Python 实现：
import os
import sys
# 请在此输入您的代码
# 获取n,q,s
n,q=map(int,input().split(" "))
s=input()
result=[]
for _ in range(q):
temp_q=input()
if int(temp_q[0])==1:
# 就开始查找第一次1出现的位置
result.append(int(s.find("1"))+1) #记得转化成1开始的下标
else:
user_position=int(temp_q.split(" ")[1])-1 #转换成下标
change_number=abs(1-int(s[user_position]))
s=s[0:user_position]+str(change_number)+s[user_position+1:]
for _ in range(len(result)):
print(result[_])
代码解释
-
输入部分：
- 首先通过
map(int, input().split(" "))获取了两个整数n和q，表示字符串长度和操作次数。 - 接着获取字符串
s，并初始化一个result列表，用来存储查询操作的结果。
- 首先通过
-
循环处理每一个操作：
- 对于每一个操作，判断操作类型。
- 如果操作类型是
1（查询操作），则用find()方法查找字符串中第一次出现1的位置，记得加1转化成 1-based 索引，并存入result列表。 - 如果操作类型是
2（反转操作），则获取指定的下标，将该位置字符反转（使用abs(1-int(...))，实现0与1的切换），然后将反转后的字符串拼接起来。
-
输出结果：
- 最后通过遍历
result列表，输出所有查询操作的结果。
- 最后通过遍历
其他版本
其他版本都使用了相似的思路：
- 查询操作：直接通过字符串查找第一次出现
'1'的位置，记得转换为 1-based 索引。 - 反转操作：反转字符串中指定位置的字符，并更新字符串。
C 版本实现
#include <stdio.h>
#include <string.h>
int main() {
int n, q;
scanf("%d %d", &n, &q);
char s[n + 1];
scanf("%s", s);
int result[q]; // 用于存储查询操作的结果
int resultIndex = 0;
// 处理每个操作
for (int i = 0; i < q; i++) {
int op;
scanf("%d", &op);
if (op == 1) { // 查询操作
// 查找第一个 '1' 的位置
char* first_one = strchr(s, '1'); // 找到第一个 '1'
if (first_one != NULL) {
result[resultIndex++] = first_one - s + 1; // 1-based 索引
} else {
result[resultIndex++] = -1;
}
} else if (op == 2) { // 反转操作
int x;
scanf("%d", &x);
x--; // 转换为0-based索引
s[x] = (s[x] == '1') ? '0' : '1'; // 反转字符
}
}
// 输出查询结果
for (int i = 0; i < resultIndex; i++) {
printf("%d\n", result[i]);
}
return 0;
}
C++ 版本实现
#include <iostream>
#include <string>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
string s;
cin >> s;
int result[q]; // 用于存储查询操作的结果
int resultIndex = 0;
// 处理每个操作
for (int i = 0; i < q; i++) {
int op;
cin >> op;
if (op == 1) { // 查询操作
size_t pos = s.find('1');
if (pos != string::npos) {
result[resultIndex++] = pos + 1; // 1-based 索引
} else {
result[resultIndex++] = -1;
}
} else if (op == 2) { // 反转操作
int x;
cin >> x;
x--; // 转换为0-based索引
s[x] = (s[x] == '1') ? '0' : '1'; // 反转字符
}
}
// 输出查询结果
for (int i = 0; i < resultIndex; i++) {
cout << result[i] << endl;
}
return 0;
}
Java 版本实现
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入n和q
int n = scanner.nextInt();
int q = scanner.nextInt();
// 输入字符串
StringBuilder s = new StringBuilder(scanner.next());
// 用于存储查询结果
List<Integer> result = new ArrayList<>();
// 处理每个操作
for (int i = 0; i < q; i++) {
int op = scanner.nextInt();
if (op == 1) { // 查询操作
int pos = s.indexOf("1");
if (pos != -1) {
result.add(pos + 1); // 1-based 索引
} else {
result.add(-1);
}
} else if (op == 2) { // 反转操作
int x = scanner.nextInt() - 1; // 转换为0-based索引
char currentChar = s.charAt(x);
s.setCharAt(x, (currentChar == '1') ? '0' : '1'); // 反转字符
}
}
// 输出查询结果
for (int res : result) {
System.out.println(res);
}
scanner.close();
}
}
解释：
- C: 使用
strchr()函数查找第一个'1'的位置，如果找到了就输出其位置（转换为 1-based 索引），否则输出-1。 - C++: 使用
find()方法查找字符串中第一次出现'1'的位置，处理和 C 类似。 - Java: 使用
indexOf("1")方法查找字符串中第一次出现'1'的位置，处理逻辑与 C/C++ 相同。