首页 > 代码库 > 求圈子用户数,竟然超过时间限制(TLE)了_1
求圈子用户数,竟然超过时间限制(TLE)了_1
此题关键是查表,关注链与被关注链一定要分开!!
圈子:(A,爱好Y)
#include "GetUserNum.h" #include <vector> #include <map> #include <set> #include <algorithm> using namespace std; typedef struct tagFollowRelation { unsigned int userId;//指定用户 unsigned int followerId;//关注userId的用户 unsigned int hobbyId; }FollowRelation; vector<FollowRelation> followRelationVec; map<unsigned int, vector<unsigned int> > userHobbysMap; set<unsigned int> followingSet; set<unsigned int> followedSet; set<unsigned int> circleSet; void AddUser(unsigned int user_id, unsigned int hobby_num, const unsigned int hobby_array[]) { vector<unsigned int> hobbyArray; for(unsigned int i = 0; i < hobby_num; i++) { hobbyArray.push_back(hobby_array[i]); } userHobbysMap.insert(pair<unsigned int,vector<unsigned int> >(user_id, hobbyArray)); return; } //检测指定的用户是否存在,如果存在继续判断指定的用户是否有指定的爱好,不存在返回-1 int isExistCheck(unsigned int user_id, unsigned int hobby_id) { if(userHobbysMap.count(user_id) == 0) { return -1; } else if(find(userHobbysMap[user_id].begin(), userHobbysMap[user_id].end(), hobby_id) == userHobbysMap[user_id].end()) { return -1; } return 0; } int AddFollowInfo( unsigned int user_id, unsigned int follower_id, unsigned int hobby_id ) { //检测输入参数是否存在 if(isExistCheck(user_id, hobby_id) == -1 || isExistCheck(follower_id, hobby_id) == -1) { return -1; } //follower_id与user_id相同 if(user_id == follower_id) { return -1; } //“user_id、 follower_id、hobby_id”全部相同的关注信息已经存在。 if(!followRelationVec.empty()) { vector<FollowRelation>::iterator iter = followRelationVec.begin(); for(; iter != followRelationVec.end(); iter++) { if(iter->userId == user_id && iter->followerId == follower_id && iter->hobbyId == hobby_id) { return -1; } } } FollowRelation followRelation = {0, 0, 0}; followRelation.userId = user_id; followRelation.followerId = follower_id; followRelation.hobbyId = hobby_id; followRelationVec.push_back(followRelation); return 0; } //A以电影直接或间接关注的所有用户,A是follower,即A关注的 void followingUsers(unsigned int follower_id, unsigned int hobby_id) { unsigned int tempSize = 0; vector<FollowRelation>::iterator iterRela = followRelationVec.begin(); for(;iterRela != followRelationVec.end(); iterRela++) { if(iterRela->followerId == follower_id && iterRela->hobbyId == hobby_id) { followingSet.insert(iterRela->userId); } } if(followingSet.empty()) { return; } while(true) { tempSize = followingSet.size(); set<unsigned int>::iterator iterFollowing = followingSet.begin(); for(;iterFollowing != followingSet.end(); iterFollowing++) { vector<FollowRelation>::iterator iterRela2 = followRelationVec.begin(); for(;iterRela2 != followRelationVec.end(); iterRela2++) { if(iterRela2->followerId == *iterFollowing && iterRela2->hobbyId == hobby_id) { followingSet.insert(iterRela2->userId); } } } if(tempSize == followingSet.size()) { return; } } }
求圈子用户数,竟然超过时间限制(TLE)了_1
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。