解题思路
这是一个查找字符串中第一个只出现一次的字符的问题。我们可以使用哈希表来记录每个字符的出现次数,然后再遍历字符串找到第一个只出现一次的字符。关键点如下:
-
字符计数:
- 使用一个哈希表(或数组)来记录每个字符的出现次数。
-
查找第一个只出现一次的字符:
- 再次遍历字符串,找到第一个计数为1的字符。
-
输入输出优化:
- 由于输入数据量较大,使用快速的输入输出方法。
代码
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int main() {
int T;
cin >> T;
cin.ignore(); // 忽略换行符
vector<char> results;
for (int t = 0; t < T; t++) {
string s;
getline(cin, s); // 使用getline读取整行
unordered_map<char, int> charCount;
// 统计字符出现次数
for (char c : s) {
charCount[c]++;
}
// 查找第一个只出现一次的字符
for (char c : s) {
if (charCount[c] == 1) {
results.push_back(c);
break;
}
}
}
// 输出结果
for (char result : results) {
cout << result << endl;
}
return 0;
}
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(reader.readLine());
StringBuilder results = new StringBuilder();
for (int t = 0; t < T; t++) {
String s = reader.readLine();
HashMap<Character, Integer> charCount = new HashMap<>();
// 统计字符出现次数
for (char c : s.toCharArray()) {
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}
// 查找第一个只出现一次的字符
for (char c : s.toCharArray()) {
if (charCount.get(c) == 1) {
results.append(c).append("\n");
break;
}
}
}
// 输出结果
System.out.print(results.toString());
}
}
import sys
from collections import defaultdict
def first_unique_character():
input = sys.stdin.read
data = input().splitlines()
T = int(data[0])
results = []
for i in range(1, T + 1):
s = data[i]
char_count = defaultdict(int)
# 统计字符出现次数
for c in s:
char_count[c] += 1
# 查找第一个只出现一次的字符
for c in s:
if char_count[c] == 1:
results.append(c)
break
# 输出结果
print("\n".join(results))
if __name__ == "__main__":
first_unique_character()
算法及复杂度
- 算法:使用哈希表统计字符出现次数
- 时间复杂度:,每个字符串遍历两次
- 空间复杂度:,字符集大小固定(ASCII范围)