LeetCode周賽311,中規中矩的裸題大賽……

語言: CN / TW / HK

大家好,我是梁唐。

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

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

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

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

最小偶倍數

給你一個正整數 n ,返回 2n 的最小公倍數(正整數)。

題解

送分題,一個整數如果是偶數它和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;
}

}; ```