Biweekly Contest 13

加密数字

class Solution {
public:
    string encode(int num) {
        string ans;
        string tmp;
        num++;
        while (num) {
            tmp.push_back(num % 2 == 0 ? '0' : '1');
            num >>= 1;
        }
        for (int i = tmp.size() - 2; i >= 0; i--) {
            ans.push_back(tmp[i]);
        }
        return ans;
    }
};

最小公共区域

class Solution {
public:
    map<string, string>maps;
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        vector<string>v1, v2;
        for(int i = 0; i < regions.size(); ++i){//建立并查集
            string fa = regions[i][0];
            for(int j = 1; j < regions[i].size(); ++j){
                maps[regions[i][j]] = fa;
            }
        }
		//将region1与region2的所有父结点对应放到v1与v2中。
		//然后寻找v1与v2第1个相交的元素
        v1.push_back(region1);
        v2.push_back(region2);
        string tmp = region1;
        while(maps.find(tmp) != maps.end()){
            tmp = maps[tmp];
            v1.push_back(tmp);
        }
        tmp = region2;
        while(maps.find(tmp) != maps.end()){
            tmp = maps[tmp];
            v2.push_back(tmp);
        }
        for(int i = 0; i < v1.size(); ++i){
            if(find(v2.begin(), v2.end(), v1[i]) != v2.end()){
                return v1[i];
            }
        }
        return "";
    }
};

近义词句子

vector<string>res, words;
string tmp;
vector<vector<string>>v(15);
void generate(int idx, int n){//DFS生成句子
    if(idx >= n){
        tmp.clear();
        for(int i = 0; i < n; ++i){
            if(i == 0){
                tmp.append(words[i]);
            }
            else{
                tmp.append(" ");
                tmp.append(words[i]);
            }
        }
        res.push_back(tmp);
        return;
    }
    for(auto str:v[idx]){
        words.push_back(str);
        generate(idx + 1, n);
        words.pop_back();
    }
}

class Solution {
public:
    vector<string> generateSentences(vector<vector<string>>& sy, string text) {
        set<string>sets[15];
        for(int i = 0; i < 15; ++i){//全局变量需要重置，不然执行结果与本地不相同
            v[i].clear();
        }
        res.clear();
        words.clear();
        int idx = 0, cnt = -1;
        vector<string>sen;
        for(int i = 0; i < sy.size(); ++i){//根据同义词组，将同义的放到同一个set中
            if(i == 0){
                ++cnt;
                idx =cnt;
            }
            else{
                idx = -1;
                for(int j = 0; j <= cnt; ++j){
                    if(sets[j].find(sy[i][0]) != sets[j].end() || sets[j].find(sy[i][1]) != sets[j].end()){
                        idx = j;
                    }
                }
                if(idx == -1){
                    ++cnt;
                    idx = cnt;
                }
            }
            for(auto str:sy[i]){
                sets[idx].insert(str);
            }
        }
        istringstream s(text);
        string str;
        while(s >> str){//句子拆成单词
            sen.push_back(str);
        }
        for(int i = 0; i < sen.size(); ++i){
            bool flag = false;
            for(int j = 0; j <= cnt; ++j){
                if(sets[j].find(sen[i]) != sets[j].end()){//如果同义词组中找到该词，则将该同义词组中所有元素放到v[i]中
                    flag = true;
                    for(auto iter :sets[j]){
                        v[i].push_back(iter);
                    }
                    break;
                }
            }
            if(!flag){
                v[i].push_back(sen[i]);
            }
        }
        generate(0, sen.size());//DFS生成句子
        return res;
    }
};

不相交的握手

class Solution {
public:
    int h[1001];
    int numberOfWays(int num_people) {
        int n = num_people / 2;
        h[0] = 1;
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j < i; ++j)
                h[i] = (h[i] + 1ll * h[j] * h[i - 1 - j]) % 1000000007;
        return h[n];
    }
};