首页 > 代码库 > 求圈子用户数,竟然超过时间限制(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