推薦朋友 - LintCode

拼多多筆試第三題
除了題目具體方法值得注意外，資料的輸入格外注意

題目

描述
給n個人的朋友名單，告訴你user，請找出user最可能認識的人。（他和user有最多的共同好友且他不是user的朋友）

n <= 500。
好友關系是互相的。（b若出現在a的好友名單中，a一定出現在b的好友名單中）
每個人的好友關系不超過 m 條，m <= 3000。
如果有兩個人和user的共同好友數目一樣，編号更小的那個認為是最可能認識的人。
如果user和所有陌生人都沒有共同好友，輸出-1。

樣例
給出 list = [[1,2,3],[0,4],[0,4],[0,4],[1,2,3]], user = 0, 傳回 4。

解釋：
0和4不是朋友，并且他們有3個共同好友。是以4是0最可能認識的人。

給出 list = [[1,2,3,5],[0,4,5],[0,4,5],[0,5],[1,2],[0,1,2,3]], user = 0, 傳回 4。

解釋：
雖然5和0有3個共同好友，4和0隻有2個共同好友，但是5是0的好友，是以4是0最可能認識的人。

解析

思路: 首先找到不是user朋友的人，再根據user的朋友名單，計算出和user的共同好友數，結果傳回最多共同好友的人。
輸入：

#if 1

#include<iostream>
#include<vector>
#include<map>
#include <algorithm>
using namespace std;

int recommendFriends(vector<vector<int>> &friends, int user) {
	// Write your code here 
	if (friends.empty())
		return -1;
	int num = friends.size();
	//res存放不是user的朋友的人與user共同好友的個數
	map<int, int> res;
	if (friends[user].empty())
		return -1;
	//dic[i]=1表示i是user或者是user的朋友,dic[i]=0表示i不是user的朋友
	vector<int> dic(num, 0);
	dic[user] = 1;
	for (auto c : friends[user])
	{
		dic[c] = 1;
	}
	//找到不是user好友的人
	for (int i = 0; i < num; ++i)
	{
		if (dic[i] == 0)
			res[i] = 0;
	}
	//根據user的好友名單更新res
	for (auto c : friends[user])
	{
		for (auto t : friends[c])
		{
			if (res.find(t) != res.end())
				res[t]++;
		}
	}
	int Max = 0;
	int person = -1;
	//找到有最多共同好友的人
	for (auto c : res)
	{
		if (c.second > Max)
		{
			Max = c.second;
			person = c.first;
		}
	}
	return person;
}


int main()
{
	int N, id;
	string str;
	getline(cin, str);
	stringstream ss(str);
	ss >> N >> id;

	vector<vector<int>> vec;
	//for (int i = 0; i < N; i++)
	//{
	//	vector<int> temp;
	//	int user;
	//	getline(cin, str);
	//	stringstream s(str);
	//	while (s>>user) //以空格進行劃分
	//	{
	//		temp.push_back(user);
	//	}
	//	vec.push_back(temp);
	//}

	while (getline(cin, str)) //其實可都可以不知道行數
	{
		vector<int> temp;
		int user;
		stringstream s(str);
		while (s >> user)
		{
			temp.push_back(user);
		}
		vec.push_back(temp);
	}

	cout << recommendFriends(vec, id) << endl;

	return 0;
}

int test()
{
	//int N,id;
	//cin >> N >> id; //直接輸入使用者數和需要查找的使用者id ; 這樣就會産生換行符

	int N;
	vector<int> in;
	char c;
	while ((c = cin.get()) != '\n')
	{
		cin.unget();
		cin >> N; 
		in.push_back(N);
	}
	
	vector<vector<int>> vec;
	for (int i = 0; i < in[0]; i++)
	{
		vector<int> temp;
		int user;
		
		while ((c=cin.get())!= '\n') //檔案結果沒有換行符了，是以陷入死循環
		{
			cin.unget();
			cin >> user;
			temp.push_back(user);
		}
		if (temp.size()!=0)
		{
			vec.push_back(temp);
		}
		
	}

	cout << recommendFriends(vec, in[1]) << endl;

	return 0;
}


#endif

題目參考：

推薦朋友 - LintCode
HDU - 4039 The Social Network （BFS）

C/C++基本文法學習

STL

C++ primer