C++刷题实战（Dictionaries and Hashmaps)

Hash Tables: Ransom Note

思路1：剔除note中重复元素，查找note和magazine中每个元素数量，比较

部分测试超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void checkMagazine(vector<string> magazine, vector<string> note) {
    //set<string> myM;
    set<string> myN;
    for(const auto& n:note){
        myN.insert(n);
    }

    for(const auto& n:myN){
        auto resM=count(begin(magazine),end(magazine),n);
        auto resN=count(begin(note),end(note),n);
        if(resN>resM){
            cout <<"No"<<endl;
            return;
        }
    }
    cout <<"Yes"<<endl;
}

思路2：用map存储magazine，遍历note元素，找到map中的对应值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Complete the checkMagazine function below.
void checkMagazine(vector<string> magazine, vector<string> note) {
    unordered_map<string,int> mapM;
    for(const auto& m:magazine){
        if(mapM.find(m)==mapM.end()){
                mapM.insert(pair<string,int>(m,1));
        }else{
            mapM[m]++;
        }
    }
    for(const auto& n:note){
        
        auto res=mapM.find(n);
        if(res==mapM.end()){
            cout <<"No"<<endl;   
            return;
        }else if(res->second==0){
            cout <<"No"<<endl;
            return;
        }
        mapM[n]--;
    }
    cout <<"Yes"<<endl;

}

构建计数map

1
2
3
4
5
6
7
8
unordered_map<string,int> mapM;
for(const auto& m:magazine){
	if(mapM.find(m)==mapM.end()){
		mapM.insert(pair<string,int>(m,1));
	}else{
		mapM[m]++;
	}
}

Two Strings

思路：若s1和s2同时包含从a到z任意一个字符则有公共子串，否则没有

1
2
3
4
5
6
7
8
string twoStrings(string s1, string s2) {
for(auto c : "abcdefghijklmnopqrstuvwxyz"){
    if(s1.find_first_of(c)!=std::string::npos&&s2.find_first_of(c)!=std::string::npos){
        return "YES";
    }
}
return "NO";
}

s1.find_first_of(c)!=std::string::npos

Sherlock and Anagrams

思路：找出包含相同元素的字串数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int sherlockAndAnagrams(string s) {
    int ret = 0;
    size_t len = s.length();

    unordered_map<string, int> rec;
    for (size_t ilen = 1; ilen < len; ilen++)
    {//ilen用来递增每次切分的字串长度
        for (size_t i = 0; i <= len - ilen; i++)
        {//i用来递增每次切分字串的起始位置
            string curr = s.substr(i, ilen);
            std::sort(curr.begin(), curr.end());//通过排序使得乱序的字串一致
            rec[curr]++;//将相同的字串存入字典
        }
        
        //
        for (auto &r : rec)
            if (r.second > 1)
                ret += r.second * (r.second - 1) / 2;//遍历字典增加记录
        rec.clear();
    }
    return ret;
}

string curr = s.substr(i, ilen);

Count Triplets

找等比数列个数

思路：一次遍历：找到前三个构成等比数列的元素（a1,a,2,a3)和他们重复次数(c1,c2,c3)（因为已经排序，所以顺序找下去就行），这三个元素构成等比数列的个数=c1c2c3。之后，每次保留a2，a3和c2，c3作为前两个元素（a1，a2），找新的下一个构成等比数列的元素（新的a3），和它的重复次数（新的c3）。直到a3是最后一个元素。或a3不构成等比数列，则把a3设为a1重新开始。

思路2：也是一次遍历，先把arrA存入hashmap，key为arrA的值，value是重复次数。这样只需要遍历遍map，通过判断key为m mXr 和 mXrXr的value是否存在就可以确保等比数列的构成。（有错）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
long countTriplets(vector<long> arr, long r) {
    long count=0;
    size_t len=arr.size();
    if(r==1){
        return len*(len-1)*(len-2)/3/2;
    }
   unordered_map<long,long> mapA;
    for(const auto& a:arr){
        if(mapA.find(a)==mapA.end()){
            mapA.insert(pair<long,long>(a,1));
        }else{
            mapA[a]++;
        }
    }    
    auto m = mapA.begin();
    while(m!=mapA.end()){
        if(mapA.count(m->first*r)!=0&&mapA.count(m->first*r*r)!=0){
            count+=mapA[m->first]*mapA[m->first*r]*mapA[m->first*r*r];
        }
        m++;
    }

       cout << count <<endl;
   return count;
}

思路3： 按照作者的意思，作者进行个对arr的遍历，建立两个字典，假设三元组为(A，B，C)，两个字典分别是指对于B来说A已经存在了，以及对于C来说（A，B）的组合已经准备好了。
每个字典里面放的并不是实值，而是对于未来三元组的一个可能性的预测，在遍历每个A的同时让B与C的线性空间不断减小，是一个非常有意思的解决思路。 

1
2
3
4
5
6
7
8
9
10
11
12
long countTriplets(vector<long> arr, long r) {
    long res=0;
      
    unordered_map<long,long> mapA,mapB;

    for(const auto& a:arr){
        if(mapB.count(a)) res+=mapB[a];
        if(mapA.count(a)) mapB[a*r]+=mapA[a];
        mapA[a*r]++;
    }
    return res;
}

Frequency Queries

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
vector<int> freqQuery(vector<vector<int>> queries) {
   int q;
    int type;
    int current_count;
    vector<int> query;
    vector<int> query_results;
    unordered_map<long, int> count_map;
    unordered_map<int, long> frequency_map;
    
    q = queries.size();
    
    for(int i =0 ; i < q ;i++){
        query = queries[ i ];
        type = query[0];
        switch(type){
            case 1:
                frequency_map[count_map[ query[1] ]]--;
                count_map[ query[1] ]++;
                frequency_map[count_map[ query[1] ]]++;
                break;
            case 2:
                current_count = count_map[ query[1] ];
                if(current_count > 0){
                    frequency_map[current_count]--;
                    count_map[ query[1] ]--;
                    frequency_map[count_map[ query[1] ]]++;
                }
                break;
            case 3:
                query_results.push_back(( frequency_map[query[1]] > 0 )? 1:0); 
                break;
            default:
                break;
        }        
    }
    return query_results;
}