HJ94 题解 | #记票统计#

题意分析

• 给你n个字符串，我们定义这些字符串都是合法的，然后，我们另外输入一些字符串，我们需要判断这些统计合法的字符串的具体个数，记录不合法的字符串的个数。

思路分析

• 我们用哈希表存储每个字符串，然后对于输入的字符串，先判断是否是合法的字符串，如果是合法的字符串，然后对应的哈希表自增1，否则非法的投票的个数自增。

写法一 C++法

• 这里我们使用unordered_map来作为哈希表对字符串进行哈希。
• 代码如下
  • 对字符串，我们哈希存储所有的字符串的长度，然后，我们的解题过程都是一重循环进行遍历，所以总的时间复杂度为$O(n)O(n)$
  • 我们需要存储所有的字符串。空间复杂度为$O(\sum len(i))O(\backslash sum\{len(i)\})$

#include<bits/stdc++.h>

using namespace std;
unordered_map<string, bool> vis;
unordered_map<string,int> mp; // 用来记录获得的票数
vector<string> v;
int main(){
    int n;
    while(cin>>n){
        vis.clear();
        v.clear();
        mp.clear();
        for(int i=1;i<=n;i++){
            string s;
            cin>>s;
            vis[s]=true;
            v.push_back(s);
        }
        int m;
        cin>>m;
        int invalid=0;
        while(m--){
            string s;
            cin>>s;
            if(vis[s]){
                mp[s]++;
            }else{
                invalid++;
            }
        }
        for(auto x:v){
            cout<<x<<" : "<<mp[x]<<endl;
        }
        cout<<"Invalid : "<<invalid<<endl;
    }
    return 0;
}

写法二 Python法

• 同理，我们在python中也是利用一些现有的数据结构进行哈希，但是在python我们似乎没有现成的哈希表，所以我们使用字典来模拟，对于每张票，我们先判断是否在字典里面，如果在，那么字典的这个键对应的值自增。
• 代码如下
  • 对字符串，我们用字典存储所有的字符串的长度，然后，我们的解题过程都是一重循环进行遍历，所以总的时间复杂度为$O(n)O(n)$
  • 我们需要存储所有的字符串。空间复杂度为$O(\sum len(i))O(\backslash sum\{len(i)\})$

while True:
    try:
        res={}
        n=int(input())
        arr=input().split()
        m=int(input())
        vote=input().split()
        for x in vote:
            # 如果这个票不是合法的，那么非法票数加1
            if x not in arr:
                res["Invalid"]=res.get("Invalid", 0)+1
            else:
                res[x]=res.get(x,0)+1
        # 循环遍历输出合法得票数的情况
        for name in arr:
            print(name,":",res.get(name,0))
        print("Invalid", ":", res.get("Invalid", 0))
    except:
        break