LeetCode周赛311，中规中矩的裸题大赛……

大家好，我是梁唐。

照惯例我们来聊聊昨天的LeetCode周赛。

上周的周赛由安贤量化赞助，今年互联网行情整体不好，但很多量化公司还在招人。感兴趣的朋友们可以关注一下。

评论区对这次比赛总体来说评价还可以，普遍反应赛题难度不大偏简单。很多人在这场收获了第一次ak。

好了， 让我们一起来看题吧。

最小偶倍数

给你一个正整数 n ，返回 2 和 n 的最小公倍数（正整数）。

题解

送分题，一个整数如果是偶数它和2的最小公倍数就是它本身，否则是它乘上2.

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]都不能连上就说明整个字符串中断了。

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，每次把一层的节点存储下来，遇到要翻转的层就单独操作一下翻转一下元素。

/**
 * 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<TreeNode*> 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] 的每个非空前缀的分数 总和 。

**注意：**字符串视作它自身的一个前缀。

题解

要统计字符串的每个前缀出现的次数，很容易想到可以使用前缀树。

想到前缀树之后基本上就是裸题了，我们对每个前缀统计出现的次数。最后再把所有字符串的所有前缀对应的次数相加即可。

关于前缀树的相关原理这里不做过多赘述，感兴趣的同学可以搜索一下，网上相关的博文非常丰富，加上原理本身也不难，相信肯定能学会的。

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;
    }
};