On the shoulders of giants.

biweekly-contest-13

加密数字

给你一个非负整数 num ,返回它的「加密字符串」。

加密的过程是把一个整数用某个未知函数进行转化,你需要从下表推测出该转化函数:

示例 1:

输入:num = 23
输出:"1000"

示例 2:

输入:num = 107
输出:"101100"

提示:

  • 0 <= num <= 10^9
题解

能很容易看出来的规律是:除零外,其它 n 递增时, f(n) 先是固定位数的二进制数递增,然后再是二进制位数递增,模拟即可。(存在更“简单”的规律)

时间复杂度:\( O(\log n) \)

class Solution {
public:
    void toTrans(int num, string& ans, int& len) {
        if(num == 0) return;
        toTrans(num / 2, ans, len);
        ans += (num % 2 ? "1" : "0");
        len--;
    }
    string encode(int num) {
        if(num == 0) return "";
        int a = 2, sum = 1, len = 1;
        while((long long)sum + a <= num) {
            sum += a;
            a *= 2;
            len++;
        }
        int now = num - sum;
        string ret = "";
        toTrans(now, ret, len);
        while(len--) ret = "0" + ret;
        return ret;
    }
};

最小公共区域

给你一些区域列表 regions ,每个列表的第一个区域都包含这个列表内所有其他区域。

很自然地,如果区域 X 包含区域 Y ,那么区域 X  比区域 Y 大。

给定两个区域 region1 和 region2 ,找到同时包含这两个区域的 最小 区域。

如果区域列表中 r1 包含 r2 和 r3 ,那么数据保证 r2 不会包含 r3 。

数据同样保证最小公共区域一定存在。

示例 1:

输入:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
输出:"North America"

提示:

  • 2 <= regions.length <= 10^4
  • region1 != region2
  • 所有字符串只包含英文字母和空格,且最多只有 20 个字母。
题解

建立一颗树(可能是森林),然后判断是否有最近公共祖先。

时间复杂度:\(O(nm\log (n+m))\) , n 为列表个数,m 为每个列表平均地区个数。

class Solution {

    int n = 0, vis[10005], ans, f[10005];
    string id[10005];
    vector<int> g[10005];
    map<string, int> hash;
       
public:
    
    int getID(string name) {
        if(hash.find(name) == hash.end()) {
            hash[name] = ++n; 
            id[n] = name;
        }
        return hash[name];
    }
    
    void step(int x) {
        while(x != -1) {
            if(vis[x]) {
                ans = x;
                break;
            }
            vis[x] = 1;
            x = f[x];
        }
    }
    
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        
        memset(f, -1, sizeof(f));
        
        for(auto region : regions) {
            int x = getID(region[0]);
            int m = region.size();
            for(int i = 1; i < m; i++) {
                g[x].push_back(getID(region[i]));
                f[getID(region[i])] = x;
            }
        }
        
        step(getID(region1));
        step(getID(region2));
        
        return id[ans];
    }
};

近义词句子

给你一个近义词表 synonyms 和一个句子 text , synonyms 表中是一些近义词对 ,你可以将句子 text 中每个单词用它的近义词来替换。

请你找出所有用近义词替换后的句子,按 字典序排序 后返回。

示例 1:

输入:
synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]],
text = "I am happy today but was sad yesterday"
输出:
["I am cheerful today but was sad yesterday",
"I am cheerful today but was sorrow yesterday",
"I am happy today but was sad yesterday",
"I am happy today but was sorrow yesterday",
"I am joy today but was sad yesterday",
"I am joy today but was sorrow yesterday"]

提示:

  • 0 <= synonyms.length <= 10
  • synonyms[i].length == 2
  • synonyms[0] != synonyms[1]
  • 所有单词仅包含英文字母,且长度最多为 10
  • text 最多包含 10 个单词,且单词间用单个空格分隔开。
题解

有同义词的列表具有传递性,所以先合并有同义词的列表,然后把新单词列表按字典序排序,然后在文本串中枚举每个能用同义词代替的单词。

时间复杂度:“有点子复杂!”

class Solution {
public:
    int num[10], pos[10], count = 0, id[10];
    vector<vector<string>> nowSynonyms;
    vector<string> nowText;
    vector<string> result;

    void dfs(int dep) {
        for(int i = 0; i < nowSynonyms[num[dep]].size(); i++) {
            id[dep] = i;
            if(dep != count - 1) dfs(dep + 1);
            else {
                string s = "";
                for(int p = 0, k = 0; k <= count; k++, p++) {
                    while(p != pos[k]) {
                        if(s != "") s += " ";
                        s += nowText[p++];
                    }
                    if(k != count) {
                        if(s != "") s += " ";
                        s += nowSynonyms[num[k]][id[k]];
                    }
                }
                result.push_back(s);
            }
        }
    }

    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
        int n = synonyms.size();
        map<string, int> h;
        bool vis[n];

        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; i++) {
            if(vis[i]) continue;
            set<string> tmp1;
            tmp1.insert(synonyms[i][0]);
            tmp1.insert(synonyms[i][1]);
            for(int j = i + 1; j < n; j++) {
                for(auto synonym : tmp1) {
                    if(synonym != synonyms[j][0] && synonym != synonyms[j][1])
                        continue;
                    tmp1.insert(synonyms[j][0]);
                    tmp1.insert(synonyms[j][1]);
                    vis[j] = 1;
                    break;
                }
            }
            vector<string> tmp2;
            for(auto synonym : tmp1) tmp2.push_back(synonym);
            sort(tmp2.begin(), tmp2.end());
            nowSynonyms.push_back(tmp2);
            // cout << nowSynonyms.size() << " : " << endl;
            for(auto synonym : tmp2) {
                // cout << synonym << endl;
                h[synonym] = nowSynonyms.size() - 1;
            }
        }

        for(int i = 0; i < text.size(); i++) {
            string s = "";
            while(text[i] && text[i] != ' ') s += text[i++];
            nowText.push_back(s);
        }

        // for(auto s : nowText) cout << s << endl;

        for(int i = 0; i < nowText.size(); i++) {
            if(h.find(nowText[i]) == h.end()) continue;
            num[count] = h[nowText[i]];
            pos[count++] = i;
        }
        pos[count] = nowText.size();

        if(count == 0) result.push_back(text);
        else dfs(0);

        return result;
    }
};

不相交的握手

偶数 个人站成一个圆,总人数为 num_people 。每个人与除自己外的一个人握手,所以总共会有 num_people / 2 次握手。

将握手的人之间连线,请你返回连线不会相交的握手方案数。

由于结果可能会很大,请你返回答案  10^9+7 后的结果。

示例 1:

输入:num_people = 2
输出:1

示例 2:

输入:num_people = 4
输出:2
解释:总共有两种方案,第一种方案是 [(1,2),(3,4)] ,第二种方案是 [(2,3),(4,1)] 。

示例 3:

输入:num_people = 6
输出:5

示例 4:

输入:num_people = 8
输出:14

提示:

  • 2 <= num_people <= 1000
  • num_people % 2 == 0
题解

动态规划:设 dp[x] 为有 x 对人时的方案数,特别地 dp[0] = 1

  • 第一个人可以与第二个人牵手,剩下的组合牵手,dp[0] * dp[n – 1]
  • 第一个人可以与第四个人牵手,剩下的组合牵手,dp[1] * dp[n – 2]
  • 第一个人可以与第六个人牵手,剩下的组合牵手,dp[2] * dp[n – 3]
  • ……
  • \(dp_n = \sum dp_i * dp_{n-i}\)

时间复杂度:\(O(n^2)\)

class Solution {
public:
    int numberOfWays(int num_people) {
        int dp[num_people / 2 + 1], mod = 1E9 + 7;
        dp[0] = dp[1] = 1;
        for(int i = 2; i <= num_people / 2; i++) {
            long long sum = 0;
            for(int j = 0; j < i; j++) {
                sum = (sum + 1ll * dp[j] * dp[i - 1 - j]) % mod;
            }
            dp[i] = sum % mod;
        }
        return dp[num_people / 2];
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注