周赛总结

[lighteningzhang]

• [ ] 总结每周周赛

[lighteningzhang]

第三十八场双周赛

第四题没思路

第三题

苦思map怎么排序，学下别人的方法(vector套map)：

class Solution {
public:
    int countSubstrings(string s, string t) {
        int n = s.size(), m = t.size();
        int mlen = min(n, m);
        vector<unordered_map<string, int>> ms(mlen + 1), mt(mlen + 1);
        for (int len = 1; len <= mlen; ++len) {
            for (int i = 0; i + len - 1 < n; ++i)
                ms[len][s.substr(i, len)]++;
            for (int j = 0; j + len - 1 < m; ++j)
                mt[len][t.substr(j, len)]++;
        }
        int ans = 0;
        for (int i = 1; i <= mlen; ++i) {
            for (auto [a, ca] : ms[i])
                for (auto [b, cb] : mt[i]) {
                    int diff = 0;
                    for (int j = 0; j < i; ++j) {
                        diff += a[j] != b[j];
                        if (diff > 1)
                            break;
                    }
                    if (diff == 1)
                        ans += ca * cb;
                }
        }
        return ans;
    }
};

[lighteningzhang]

第213场周赛

A了三道常规题，且三道题都费了些劲 第四题更加暴露了问题，我对于全排列这类的题还是缺乏总结

周赛只是对部分知识的检测，每次遇到问题需要复盘并系统总结，不然做周赛就失去了原有的价值

以下是第四题的一些基础：

1. 全排列
2. 康托展开和逆展开
3. 排列数的计算方法
4. 相关题目 第k个排列 https://leetcode-cn.com/problems/permutation-sequence/ 长度为 n 的开心字符串中字典序第 k 小的字符串 https://leetcode-cn.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/

[lighteningzhang]

第213场周赛

A了三道常规题，且三道题都费了些劲 第四题更加暴露了问题，我对于全排列这类的题还是缺乏总结

周赛只是对部分知识的检测，每次遇到问题需要复盘并系统总结，不然做周赛就失去了原有的价值

以下是第四题的一些基础：

1. 全排列
2. 康托展开和逆展开
3. 排列数的计算方法
4. 相关题目 第k个排列 https://leetcode-cn.com/problems/permutation-sequence/ 长度为 n 的开心字符串中字典序第 k 小的字符串 https://leetcode-cn.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/

第三题dp解法

class Solution {
public:
    int countVowelStrings(int n) {
        vector<int>dp(5);
        for (int i = 0; i <= n; i ++) {
            for (int j = 4; j >= 0; j --) {
                if (!i) {
                    dp[j] = 1;
                    continue;
                }
                for (int k = j - 1; k >=0; k --) {
                        dp[j] += dp[k];
                }
            }
        }
        return dp[4];
    }
};