解题思路

这是一个查找字符串中第一个只出现一次的字符的问题。我们可以使用哈希表来记录每个字符的出现次数,然后再遍历字符串找到第一个只出现一次的字符。关键点如下:

  1. 字符计数

    • 使用一个哈希表(或数组)来记录每个字符的出现次数。
  2. 查找第一个只出现一次的字符

    • 再次遍历字符串,找到第一个计数为1的字符。
  3. 输入输出优化

    • 由于输入数据量较大,使用快速的输入输出方法。

代码

#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范围)