leetcode竞赛：20220918周赛

整体比较简单

题目一 6180. 最小偶倍数

class Solution {
public:
    int smallestEvenMultiple(int n) {
        if (n & 1) return n << 1;
        return n;
    }
};
1
2
3
4
5
6
7

题目二 6181. 最长的字母序连续子字符串的长度

暴力或者双指针都可以

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

双指针时，避免最后一部分没有被枚举到的办法是以前指针作为枚举指针。

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

题目三 6182. 反转二叉树的奇数层

典型层序遍历。思考复杂度：最多$2^{14}$个节点，那么每层最多$2^{13}$个节点，也就是每层最多$8\ast 10^3$个节点，不算多。第一次看$2^{14}$，以为很多。

class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        dequeque;
        que.push_back(root);
        int curL = 0;
        while(!que.empty()) {
            int n = que.size();
            
            for (int i = 0, j = n - 1; i < n; i++, j--) {
                TreeNode* cur = que[i];
                if (cur->left) {
                    que.push_back(cur->left);
                    que.push_back(cur->right);
                }
                
                if ((curL % 2) && i < j) {
                    // cout << curL << " " << que[i]->val << que[j]->val << endl;
                    swap(que[i]->val, que[j]->val);
                }
            }
            que.erase(que.begin(), que.begin() + n);
            curL++;
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

可以用深度优先遍历，做镜像遍历，这个思想很好。代码也很漂亮。
这个dfs的每一层的两个节点，都是左右两棵子树镜像分布的。

class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        dfs(root->left, root->right, 1);
        return root;
    }
    void dfs(TreeNode* left, TreeNode* right, int d) {
        if (!left) return ;
        dfs(left->left, right->right, d + 1);
        dfs(left->right, right->left, d + 1);
        if (d & 1) swap(left->val, right->val);
        return ;  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

6183. 字符串的前缀分数和

近几次做的最容易的4题。超时一次，因为忽略了哈希的时间复杂度。如果直接以哈希前缀字符串来做，时间复杂度是$O(n^3)$ ,数据量1000是过不了的。应该用Trie树优化。Trie树是一种听着难，写起来比想象中容易的多的数据结构。

class Solution {
public:
    struct Treenode {
        int ct = 0;
        Treenode *next[30] = {nullptr};
    };
    class Trie {
        public:
        Trie() {
            root = new Treenode();
        }
        Treenode *root;
        void update(const string& s) {
            Treenode *cur = root;
            for (int i = 0; i < s.size(); i++) {
                char c = s[i];
                int id = c - 'a';
                if (!cur->next[id]) cur->next[id] = new Treenode();
                cur->next[id]->ct++;
                cur = cur->next[id];
            }
            
        }
        int find(const string& s) {
            Treenode *cur = root;
            int res = 0;
            for (int i = 0; i < s.size(); i++) {
                char c = s[i];
                int id = c - 'a';
                if (!cur->next[id]) cur->next[id] = new Treenode();
                res += cur->next[id]->ct;
                cur = cur->next[id];
            }
            return res;
        }
    };
    vector sumPrefixScores(vector& words) {
        unordered_map ai;
        Trie root;
        for (auto s: words) {
            root.update(s);
        }
        vector res;
        for (auto s: words) {
            int r = root.find(s);
            res.push_back(r);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50