L1-020 帅到没朋友 (20 point(s))

  • 最开始用了 set 但最后一个测试点超时了,想了想这遍历是顺序的,不需要考虑排序,所以用了 unordered_set 就把最后一个测试点给解决了。

    而想了想既然 unordered_set 都可以,那么类似的向量 vector 也应该是可以的,所以就改成向量试了试。但结果发现却超时了。

    故查了查这两个容器的比较。向量是 vector 线性表,而 unordered_set 是hash容器。而在该题后面我用到了多个 find 来搜索朋友圈中是否有该人的存在。

    故在查找效率下,显然 vector 只能线性查找,时间复杂度是 O(n) ,而 unordered_set 根据映射关系时间复杂度是 O(1) 所以前者的超时就可以理解了。

    集合求交集中,vector, set ,unordered_set,的对比试验

  • 写 vector 的 find 函数时报错,所以查了下该容器的 find 怎么写。发现 vector 的 find 不是成员而是静态函数,并且还需要传入容器的起始末尾地址以确定范围。

    写了之后就可以发现整个 find 代码十分冗长,所以还是用回 unordered_set 较好。而且用 vector,还会超时。

    vector中find和find_if的用法

  • 参考了别人的方法,又发现了很多神奇的东西。

    因为题目说了,“K超过1的朋友圈里都至少有2个不同的人” 所以在处理的时候 K == 1 的朋友圈说明只有对象自己,这种朋友圈即不需要读取也不需要处理。固有如下代码。

    for (int i = 0; i < K; ++i) {
    		cin >> id;
    		if (K > 1)
    			mp[id]++;
    }
    

    而在统计了每个人朋友圈的数量后,因为所统计的朋友圈必然包括除自己的其他对象,所以存在一个朋友圈就说明该对象必然有朋友,反之朋友圈数量为 0 的就说明必然没有朋友。

    if (mp[id]++ == 0)
    cout << (flag++ ? " " : "") << id;
    

    可以看到代码对朋友圈数量进行了判断,同时可以看到在判断里面对 mp[id] 进行了 ++ 运算,因为条件 “同一个人可以被查询多次,但只输出一次” 所以为了避免再次查询而输出,所以给这个对象朋友圈 ++ 防止再次输出。

    还有是最后输出 “No one is handsome” ,在打印空格的时候我们用了变量 first 来标记是第一个输出还是第n个输出。所以在后面判断是否有帅哥的时候,我们除了用容器来记录和判断之外,也可以用 first 来判断。

    如果 first == 0 那么必然说明输出为 0 没有帅哥。

    参考代码

  • 再记录一个问题,如果用了 if(K > 1) 来统计,那么就不能够用 while(K--) 来作为循环判断,不然 K-- 会让 if(K > 1) 判断不成立而错误,所以需要改成下面的代码。

    for(int i = 0; i < K; i++)

    可以看到,当循环变量自增自减来循环判断时,不能在其他地方用这个循环变量作为判断依据。判断是静态的,如果用了自增自减显然是动态,会跟事实不符。

// 参考后的精简代码
#include <bits/stdc++.h>
using namespace std;

int main(){
	int N, K, M, first = 0;
	string id;
	map<string, int> Moments;
	
	cin >> N;
	while(N--){
		cin >> K;
		for(int i = 0; i < K; i++){
			cin >> id;
			if(K > 1)
				Moments[id]++;
		}
	}

	cin >> M;
	while(M--){
		cin >> id;
		if(Moments[id]++ == 0)
			cout << (first++ ? " " : "") << id;
	}
	if(first == 0) cout << "No one is handsome";
} 
// unordered_set 20 points
#include <bits/stdc++.h>
using namespace std;

int main(){
	int N, K, M, first = 0;
	vector<unordered_set<string>> Moments;
	 
	// 读取朋友圈 
	cin >> N;
	for(int i = 0; i < N; i++){
		unordered_set<string> tmp;
		string str;
		cin >> K;
		
		while(K--){
			cin >> str;
			tmp.insert(str);
		}
		Moments.push_back(tmp);
	}
	
	// 输出标记 
	set<string> isPrint;
	// 查询 
	cin >> M;
	while(M--){
		bool out = true;
		string str; 
		cin >> str;
		
		// 从每个朋友圈中寻找 
		for(int i = 0; i < N; i++){
			
			// 找到朋友则结束寻找  不输出 
			if(Moments[i].size() > 1 && Moments[i].find(str) != end(Moments[i])){
				out = false;
				break;			
			}
		}
		
		// 遍历完都找不到说明是帅哥 && 该人没有输出过 
		if(out == true && isPrint.find(str) == end(isPrint)){
			cout << (first++ ? " " : "") << str;
			isPrint.insert(str); 
		} 
	}
	
	if(isPrint.size() == 0) cout << "No one is handsome";
} 
// vector 17points 错误示范
#include <bits/stdc++.h>
using namespace std;

int main(){
	int N, K, M, first = 0;
	vector<vector<string>> Moments;
	 
	// 读取朋友圈 
	cin >> N;
	for(int i = 0; i < N; i++){
		vector<string> tmp;
		string id;
		cin >> K;
		
		while(K--){
			cin >> id;
			tmp.push_back(id);
		}
		Moments.push_back(tmp);
	}
	
	// 输出标记 
	vector<string> isPrint;
	// 查询 
	cin >> M;
	while(M--){
		bool out = true;
		string id; 
		cin >> id;
		
		// 从每个朋友圈中寻找 
		for(int i = 0; i < N; i++){
			
			// 找到朋友则结束寻找  不输出 
			if(Moments[i].size() > 1 && 
			find(begin(Moments[i]), end(Moments[i]), id) != end(Moments[i])){
				out = false;
				break;			
			}
		}
		
		// 遍历完都找不到说明是帅哥 && 该人没有输出过 
		if(out == true && 
		find(begin(isPrint), end(isPrint), id) == end(isPrint)){
			cout << (first++ ? " " : "") << id;
			isPrint.push_back(id); 
		} 
	}
	
	if(isPrint.size() == 0) cout << "No one is handsome";
} 
上一篇:PTA L1-020 帅到没朋友(Java)


下一篇:JavaWebDay03(MySQL 约束)020