Skip to content

第 311 场周赛

比赛链接

A 最小偶倍数

如果 n 是 2 的倍数，则 \(lcm(n,2) = n\)，否则 \(lcm(n,2) = n*2\)

1
2
3
4
5
6
class Solution {
public:
    int smallestEvenMultiple(int n) {
        return n % 2 == 0 ? n : n * 2;
    }
};

1
2
3
class Solution:
    def smallestEvenMultiple(self, n: int) -> int:
        return n if n % 2 == 0 else n * 2

B 最长的字母序连续子字符串的长度

设 \(i\) 是当前的迭代变量，\(cur\) 为当前连续字符串的长度。 - 如果 \(i = 0\) 或者 \(s[i] != s[i - 1] + 1\) 时，设为一段的起点 \(cur = 1\) - 否则，\(cur = cur + 1\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int longestContinuousSubstring(string s) {
        int res = 0, cur = 0;
        for (int i = 0; i < s.size(); i++) {
            if (i == 0 || s[i] != s[i - 1] + 1) {
                cur = 1;
            } else {
                cur++;
            }
            res = max(res, cur);
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def longestContinuousSubstring(self, s: str) -> int:
        res, cur = 0, 0
        for i, ch in enumerate(s):
            if i == 0 or ord(s[i]) != ord(s[i - 1]) + 1:
                cur = 1
            else:
                cur += 1
            res = max(res, cur)
        return res

C 反转二叉树的奇数层

按照先序遍历将每一个奇数层的节点存放到一个队列中，然后单独遍历每一层的队列，逆转其顺序即可。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        unordered_map<int, vector<TreeNode*>> mp;
        function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int dep) {
            if (root == nullptr) return;
            if (dep & 1) {
                mp[dep].push_back(root);
            }
            dfs(root->left, dep + 1);
            dfs(root->right, dep + 1);
        };
        dfs(root, 0);
        for (auto &[k, v] : mp) {
            int i = 0, j = v.size() - 1;
            while (i < j) {
                swap(v[i]->val, v[j]->val);
                i++;
                j--;
            }
        }
        return root;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        mp = defaultdict(list)
        def dfs(root:Optional[TreeNode], dep:int):
            if not root:
                return
            if dep % 2 == 1:
                mp[dep].append(root)
            dfs(root.left, dep + 1)
            dfs(root.right, dep + 1)

        dfs(root, 0)
        for k, v in mp.items():
            i = 0
            j = len(v) - 1
            while i < j:
                v[i].val, v[j].val = v[j].val, v[i].val
                i += 1
                j -= 1
        return root

D 字符串的前缀分数和

字典树统计每个前缀出现的次数即可。

时间复杂度 \(O(\sum words.length)\)

空间复杂度 \(O(\sum words.length)\)

struct Trie {
    static constexpr int N = 1000010, M = 26;
    int tot;
    int tr[N][M];
    int ends[N], prefix[N];
    void clear() {
        for(int i = 0; i <= tot; i++) memset(tr[i], 0, sizeof(tr[i]));
        for(int i = 0; i <= tot; i++) ends[i] = prefix[i] = 0;
        tot = 0; ends[0] = 0;
    }
    Trie() { tot = 0; }
    void insert(string &s) {
        int p = 0;
        for(auto &ch : s) {
            int c = ch - 'a';
            if(tr[p][c] == 0) tr[p][c] = ++tot;
            p = tr[p][c];
            prefix[p] ++;
        }
        ends[p] ++;
    }
    int get(string &s) {
        int p = 0, res = 0;
        for(auto &ch : s) {
            int c = ch - 'a';
            if (tr[p][c] == 0) break;
            p = tr[p][c];
            res += prefix[p];
        }
        return res;
    }
}tr;
class Solution {
public:
    vector<int> sumPrefixScores(vector<string>& words) {
        tr.clear();
        for (auto &s : words) {
            tr.insert(s);
        }
        vector<int> res;
        for (auto &s : words) {
            res.push_back(tr.get(s));
        }
        return res;
    }
};
本文访问 次