讨论/题目交流/🐱 第 13 场夜喵双周赛/
🐱 第 13 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

4 分 - 加密数字
5 分 - 最小公共区域
6 分 - 近义词句子
6 分 - 不相交的握手

展开讨论
力扣 (LeetCode)发起于 2019-11-16
最近编辑于 2019-11-16

赞这次题目质量,第三题是工作中经常碰到的场景「输入联想」,比如各种网站输入框,帮你把形近字和音近字罗列出来构成句子去库里匹配

第一题:

额,这题全靠肉眼识别,n+1n+1 的二进制,去掉第一位就行了

import java.math.*;

class Solution {
    public String encode(int num) {
        return BigInteger.valueOf(num + 1).toString(2).substring(1);
    }
}

第二题:

这题把字符串看成结点,每一行第一个元素是后面所有元素的父亲结点,题目就是求两个结点的最近公共祖先

解法:先分别把两个节点的祖先们求出来,然后再从第一个祖先开始匹配,直到第一次不匹配的上一个祖先就是结果

class Solution {
public:
    vector<string> find(map<string, string> &m, string region) {
        vector<string> p;
        string res = region;
        while (1) {
            p.push_back(res);
            auto it = m.find(res);
            if (it == m.end()) {
                break;
            }
            res = it->second;
        }
        return p;
    }
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        map<string, string> m;
        for (auto& region: regions) {
            for (int i = 1;i < region.size();i++) {
                m[region[i]] = region[0];
            }
        }
        vector<string> p1 = find(m, region1), p2 = find(m, region2);
        
        int i1 = p1.size() - 1;
        int i2 = p2.size() - 1;
        while (true) {
            if (i1 >= 0 && i2 >= 0 && p1[i1] == p2[i2]) {
                i1--;
                i2--;
            } else {
                break;
            }
            
        }
        return p1[i1 + 1];
    }
};

第三题:

先把所有的近义词集合求出来。题目中 AABB 的近义词,如果 AABB 的近义词,AACC 的近义词,那么 AABBCC 都是近义词,这一步如果数据量大需要用到并查集,数据量小,瞎搞搞咯

然后再dfs,把句子中每个词的近义词都拿出来计算一次。。。

import java.util.*;

class Solution {
    private void dfs(Map<String, Set<String>> map, String[] col, List<String> result, int index) {
        if (index == col.length) {
            result.add(String.join(" ", col));
            return;
        }
        if (map.containsKey(col[index])) {
            String s = col[index];
            for (String sub: map.get(col[index])) {
                col[index] = sub;
                dfs(map, col, result, index + 1);
            }
            col[index] = s;
        } else {
            dfs(map, col, result, index + 1);
        }
    }
    public List<String> generateSentences(List<List<String>> synonyms, String text) {
        Map<String, Set<String>> map = new HashMap<>();
        
        for (List<String> synonym: synonyms) {
            Set<String> s1 = map.getOrDefault(synonym.get(0), new HashSet<>());
            Set<String> s2 = map.getOrDefault(synonym.get(1), new HashSet<>());
            if (s1 == s2) {
                continue;
            }
            HashSet<String> ret = new HashSet<>();
            ret.addAll(s1);
            ret.addAll(s2);
            ret.add(synonym.get(0));
            ret.add(synonym.get(1));
            
            for (String sub: ret) {
                map.put(sub, ret);
            }
        }

        String[] col = text.split(" ");
        List<String> result = new ArrayList<>();
        dfs(map, col, result, 0);

        Collections.sort(result);
        return result;
    }
}

第四题:

看到例子,1,1,5,141,1,5,14,明显卡特兰数啊

f(n)=i=0n1f(i)f(ni1)f(n)=\sum_{i=0}^{n-1}f(i)*f(n-i-1)

证明:

假设 nn 无限大,考察点 11

  1. 11 如果跟点 22 连接,那么有 f(n2)f(n-2) 种方法
  2. 11 如果跟点 33 连接,点 22 不管跟啥点连接都会跟 1>1-> 3相交,冲突
  3. 11 如果跟点 44 连接,那么 1>41->4 将空间划成两边,2233 两个点,有 f(2)f(2) 个方法连接,另外一边是 n4n-4 个点,有 f(n4)f(n-4) 个方法连接,那么总方法数是 f(2)f(n4)f(2)*f(n-4)
  4. 。。。
class Solution {
public:
    vector<int> cal;
    void init() {
        if (cal.size() != 0) {
            return;
        }
        cal.push_back(1);
        cal.push_back(1);
        for (int i = 2;i <= 500;i++) {
            int res = 0;
            for (int j = 0;j < i;j++) {
                res += (long long)cal[j] * cal[i - 1 - j] % 1000000007;
                            res %= 1000000007;
            }
            cal.push_back(res);
        }
    }
    int numberOfWays(int num_people) {
        init();
        return cal[num_people / 2];
    }
};
17
展开全部 9 讨论