PS:头一次写 $LeetCode$ 周赛的题解，感觉真的好水啊……

如果觉得不错就点个收藏吧！谢谢啦~~

A.最小偶倍数

思路

我们知道，$a$ 和 $b$ 的最小公倍数等于 $a \times b {\div} gcd(a, b)$，所以我们直接计算一下就行了。

//复杂度：O(log(max(a,b)))
class Solution {
public:
    int gcd(int x, int y) {
        if (y == 0) return x;
        return gcd(y, x % y);
    }
    int smallestEvenMultiple(int n) {
        return 2 * n / gcd(2, n);
    }
};

优化

我们可以发现，一个数和 $2$ 的最大公约数只有两种可能：

1. 如果是 $2$ 的倍数，那么结果为 $2$

2. 如果不是 $2$ 的倍数，那么结果为 $1$

对于第一种情况，我们只要返回 $n$ 即可，第二种情况，我们返回 $2 {\times} n$ 即可。

class Solution {
public:
    int smallestEvenMultiple(int n) {
        if (n % 2 == 0) return n;
        else return 2 * n;
    }
};

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

思路

这是一道很简单的双指针算法。

我们用 $j$ 指针作为区间开头，$i$ 指针作为区间结尾。

如果加入 $i + 1$ 后当前区间满足条件，则 $i$ 去到下一位，否则 $j = i + 1$，每次更新最大长度，最后返回即可。

代码

class Solution {
public:
    int longestContinuousSubstring(string s) {
        int res = 0;
        for (int i = 1, j = 0; i <= s.size(); i ++) {
            if (i == s.size() || s[i] != s[i - 1] + 1) {
                res = max(res, i - j);
                j = i;
            }
        }
        return res;
    }
};

C.反转二叉树的奇数层

思路

$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) {
        queue<TreeNode*> q;
        q.push(root);
        int res = 0;
        while (q.size()) {
            vector<TreeNode*> path;
            int l = q.size();
            for (int i = 0; i < l; i ++) {
                auto t = q.front();
                q.pop();
                path.push_back(t);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            cout << endl;
            if (res % 2 == 1)
                for (int i = 0; i < path.size()/ 2; i ++) 
                    swap(path[i]->val, path[path.size() - 1 - i]->val);
            res ++;
        }
        return root;
    }
};

D.字符串的前缀分数和

思路

一看到前缀，就应该反应出 $Trie$ 这个东西，而本题正是 $Trie$ 题。

首先我们要开一个 $cnt$ 数组，存的是以当前结点在 $Trie$ 中有多少的子树，然后来思考一下 $insert$ 操作该怎么写。

我们把板子修改一下即可得到：

void insert(string &s) {
    int p = 0;
    for (auto c : s) {
        auto u = c - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
        //比模板多出一句将p的子树加一
        cnt[p] ++;
    }
}

然后就是查询操作，一样改板子即可。

int query(string &s) {
    int res = 0;
    int p = 0;
    for (auto c : s) {
        auto u = c - 'a';
        p = son[p][u];
        res += cnt[p];
    } 
    return res;
}

完整代码

//要开全局，不能开在类里面，不然会爆内存，都是血的教训啊qwq
int son[1000010][26], idx;
int cnt[1000010];

class Solution {
public:
    void insert(string &s) {
        int p = 0;
        for (auto c : s) {
            auto u = c - 'a';
            if (!son[p][u]) son[p][u] = ++ idx;
            p = son[p][u];
            cnt[p] ++;
        }
    }

    int query(string &s) {
        int res = 0;
        int p = 0;
        for (auto c : s) {
            auto u = c - 'a';
            p = son[p][u];
            res += cnt[p];
        } 
        return res;
    }

    vector<int> sumPrefixScores(vector<string>& words) {
        //注意一定要提前初始化，否则会WA
        idx = 0;
        memset(son, 0, sizeof(son));
        memset(cnt, 0, sizeof(cnt));
        //将每个字符串都插入进去
        for (auto &s : words) insert(s);
        //每个answer就是查询的结果
        vector<int> ans;
        for (auto &s : words)
            ans.push_back(query(s));
        return ans;
    }
};