LeetCode周賽311，中規中矩的裸題大賽……_樑唐

大家好，我是樑唐。

照慣例我們來聊聊昨天的LeetCode周賽。

上週的周賽由安賢量化贊助，今年網際網路行情整體不好，但很多量化公司還在招人。感興趣的朋友們可以關注一下。

評論區對這次比賽總體來說評價還可以，普遍反應賽題難度不大偏簡單。很多人在這場收穫了第一次ak。

好了，讓我們一起來看題吧。

最小偶倍數

給你一個正整數 n ，返回 2 和 n 的最小公倍數（正整數）。

題解

送分題，一個整數如果是偶數它和2的最小公倍數就是它本身，否則是它乘上2.

cpp class Solution { public: int smallestEvenMultiple(int n) { return n % 2 ? n << 1: n; } };

最長的字母序連續子字串的長度

字母序連續字串 是由字母表中連續字母組成的字串。換句話說，字串 "abcdefghijklmnopqrstuvwxyz" 的任意子字串都是 字母序連續字串 。

例如，"abc" 是一個字母序連續字串，而 "acb" 和 "za" 不是。

給你一個僅由小寫英文字母組成的字串 s ，返回其最長的字母序連續子字串的長度。

題解

two pointer裸題。

我們可以用兩個指標維護都是連續字串的頭尾，將右側指標往右移動。如果遇到新的字元無法和之前的連續字串連上，那麼將左側指標移動過來。因為s[right+1]和s[right]都不能連上就說明整個字串中斷了。

```cpp class Solution { public: int longestContinuousSubstring(string s) { int l = 0;

    int ret = 1;
    for (int r = 1; r < s.length(); r++) {
        if (s[r] != s[r-1]+1) {
            l = r;
        }
        ret = max(r - l + 1, ret);
    }
    return ret;
}

}; ```

反轉二叉樹的奇數層

給你一棵完美二叉樹的根節點 root ，請你反轉這棵樹中每個奇數層的節點值。

例如，假設第 3 層的節點值是 [2,1,3,4,7,11,29,18] ，那麼反轉後它應該變成 [18,29,11,7,4,3,1,2] 。

反轉後，返回樹的根節點。

完美二叉樹需滿足：二叉樹的所有父節點都有兩個子節點，且所有葉子節點都在同一層。

節點的層數等於該節點到根節點之間的邊數。

題解

這題的坑點在於翻轉的是整個一層節點，比如某一層如果是[3, 4, 5, 6]翻轉完變成[6, 5, 4, 3]。這會涉及到多個節點，所以直接dfs會稍微麻煩一點。

比較容易想到可以實用bfs，每次把一層的節點儲存下來，遇到要翻轉的層就單獨操作一下翻轉一下元素。

```cpp / * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode left, TreeNode right) : val(x), left(left), right(right) {} * }; / class Solution { public: TreeNode reverseOddLevels(TreeNode* root) { // cur儲存當前層的節點，next儲存下一層 vector cur, next; // 記錄下一層是否要翻轉 bool flag = true;

    cur.push_back(root);
    while (!cur.empty()) {
        for (auto &u: cur) {
            if (u->left != nullptr) {
                next.push_back(u->left);
                next.push_back(u->right);
            }
        }

        if (flag) {
            int l = 0, r = next.size() - 1;
            while (l < r) {
                swap(next[l]->val, next[r]->val);
                l++;
                r--;
            }
        }
        flag = !flag;
        cur = next;
        next = vector<TreeNode*> ();
    }
    return root;
}

}; ```

字串的字首分數和

給你一個長度為 n 的陣列 words ，該陣列由非空字串組成。

定義字串 word 的分數等於以 word 作為字首的 words[i] 的數目。

例如，如果 words = ["a", "ab", "abc", "cab"] ，那麼 "ab" 的分數是 2 ，因為 "ab" 是 "ab" 和 "abc" 的一個字首。

返回一個長度為 n 的陣列 answer ，其中 answer[i] 是 words[i] 的每個非空字首的分數總和。

注意：字串視作它自身的一個字首。

題解

要統計字串的每個前綴出現的次數，很容易想到可以使用字首樹。

想到字首樹之後基本上就是裸題了，我們對每個字首統計出現的次數。最後再把所有字串的所有字首對應的次數相加即可。

關於字首樹的相關原理這裡不做過多贅述，感興趣的同學可以搜尋一下，網上相關的博文非常豐富，加上原理本身也不難，相信肯定能學會的。

```cpp class Solution { public:

struct Node {
    int v;
    Node* chs[27] = {nullptr};
    Node(): v(1) {};
};

struct Trie {
    Node *node;
    Trie() {
        node = new Node();
    }
    void insert(string &str) {
        Node *cur = node;
        for (auto c: str) {
            int idx = c - 'a';
            if (cur->chs[idx] == nullptr) {
                cur->chs[idx] = new Node();
            }else {
                cur->chs[idx]->v++;
            }
            cur = cur->chs[idx];
        }
    }
    int query(string &str) {
        int ret = 0;
        Node *cur = node;
        for (auto c: str) {
            int idx = c - 'a';
            if (cur->chs[idx] == nullptr) break;
            ret += cur->chs[idx]->v;
            cur = cur->chs[idx];
        }
        return ret;
    }
};

vector<int> sumPrefixScores(vector<string>& words) {
    vector<int> ret;
    Trie* t = new Trie();
    for (auto &st : words) {
        t->insert(st);
    }

    for (auto &st: words) {
        int cur = t->query(st);
        ret.push_back(cur);
    }
    return ret;
}

}; ```