🏆 第 311 场力扣周赛

VP

2413. 最小偶倍数

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

示例 1：
输入：n = 5 输出：10 解释：5 和 2 的最小公倍数是 10 。
示例 2：
输入：n = 6 输出：6 解释：6 和 2 的最小公倍数是 6 。注意数字会是它自身的倍数。

提示：

• 1 <= n <= 150

思路：数学

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

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

显示英文描述
字母序连续字符串 是由字母表中连续字母组成的字符串。换句话说，字符串 “abcdefghijklmnopqrstuvwxyz” 的任意子字符串都是 字母序连续字符串 。

• 例如，”abc” 是一个字母序连续字符串，而 “acb” 和 “za” 不是。

给你一个仅由小写英文字母组成的字符串 s ，返回其 最长 的 字母序连续子字符串 的长度。

示例 1：
输入：s = “abacaba” 输出：2 解释：共有 4 个不同的字母序连续子字符串 “a”、”b”、”c” 和 “ab” 。 “ab” 是最长的字母序连续子字符串。
示例 2：
输入：s = “abcde” 输出：5 解释：“abcde” 是最长的字母序连续子字符串。

提示：

• 1 <= s.length <= 105
• s 由小写英文字母组成

思路：模拟

class Solution {
    public int longestContinuousSubstring(String s) {
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            int j = i + 1;
            while (j < s.length() && s.charAt(j) - 1 == s.charAt(j - 1))
                j++;
            max = Math.max(max, j - i);
            i = j - 1;
        }
        return max;
    }
}

2415. 反转二叉树的奇数层

给你一棵 完美 二叉树的根节点 root ，请你反转这棵树中每个 奇数 层的节点值。

• 例如，假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。

反转后，返回树的根节点。
完美 二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。
节点的 层数 等于该节点到根节点之间的边数。

示例 1：
输入：root = [2,3,5,8,13,21,34] 输出：[2,5,3,8,13,21,34] 解释： 这棵树只有一个奇数层。 在第 1 层的节点分别是 3、5 ，反转后为 5、3 。
示例 2：
输入：root = [7,13,11] 输出：[7,11,13] 解释： 在第 1 层的节点分别是 13、11 ，反转后为 11、13 。
示例 3：
输入：root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2] 输出：[0,2,1,0,0,0,0,2,2,2,2,1,1,1,1] 解释：奇数层由非零值组成。 在第 1 层的节点分别是 1、2 ，反转后为 2、1 。 在第 3 层的节点分别是 1、1、1、1、2、2、2、2 ，反转后为 2、2、2、2、1、1、1、1 。

提示：

• 树中的节点数目在范围 [1, 214] 内
• 0 <= Node.val <= 105
• root 是一棵 完美 二叉树

思路：想法不难，重点是怎么让代码更简洁

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
// dfs
class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        dfs(root.left, root.right, 1);
        return root;
    }
    void dfs(TreeNode l, TreeNode r, int x) {
        if (l == null) return;
        if (x == 1) {
            int t = l.val;
            l.val = r.val;
            r.val = t;
        }
        dfs(l.left, r.right, x ^ 1);
        dfs(l.right, r.left, x ^ 1);
    }
}

类似的问题还有：101. 对称二叉树

2416. 字符串的前缀分数和

给你一个长度为 n 的数组 words ，该数组由 非空 字符串组成。
定义字符串 word 的 分数 等于以 word 作为 前缀 的 words[i] 的数目。

• 例如，如果 words = [“a”, “ab”, “abc”, “cab”] ，那么 “ab” 的分数是 2 ，因为 “ab” 是 “ab” 和 “abc” 的一个前缀。

返回一个长度为 _n 的数组 answer ，其中 answer[i] 是 words[i] 的每个非空前缀的分数 总和 。_
注意：字符串视作它自身的一个前缀。

示例 1：
输入：words = [“abc”,”ab”,”bc”,”b”] 输出：[5,4,3,2] 解释：对应每个字符串的答案如下： - “abc” 有 3 个前缀：”a”、”ab” 和 “abc” 。 - 2 个字符串的前缀为 “a” ，2 个字符串的前缀为 “ab” ，1 个字符串的前缀为 “abc” 。 总计 answer[0] = 2 + 2 + 1 = 5 。 - “ab” 有 2 个前缀：”a” 和 “ab” 。 - 2 个字符串的前缀为 “a” ，2 个字符串的前缀为 “ab” 。 总计 answer[1] = 2 + 2 = 4 。 - “bc” 有 2 个前缀：”b” 和 “bc” 。 - 2 个字符串的前缀为 “b” ，1 个字符串的前缀为 “bc” 。 总计 answer[2] = 2 + 1 = 3 。 - “b” 有 1 个前缀：”b”。 - 2 个字符串的前缀为 “b” 。 总计 answer[3] = 2 。
示例 2：
输入：words = [“abcd”] 输出：[4] 解释： “abcd” 有 4 个前缀 “a”、”ab”、”abc” 和 “abcd”。 每个前缀的分数都是 1 ，总计 answer[0] = 1 + 1 + 1 + 1 = 4 。

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] 由小写英文字母组成

思路：
方法1：字符串哈希
方法2：Trie

class Solution {
    public int[] sumPrefixScores(String[] words) {
        Map<Long, Integer> map = new HashMap<>();
        long p = 13331;
        for (int i = 0; i < words.length; i++) {
            long x = 0;
            for (int j = 0; j < words[i].length(); j++) {
                x = x * p + words[i].charAt(j);
                map.merge(x, 1, Integer::sum);
            }
        }
        int[] res = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            int s = 0;
            long x = 0;
            for (int j = 0; j < words[i].length(); j++) {
                x = x * p + words[i].charAt(j);
                s += map.get(x);
            }
            res[i] = s;
        }
        return res;
    }
}

class Solution {
    public int[] sumPrefixScores(String[] words) {
        Trie tr = new Trie();
        for (String s : words) tr.insert(s);
        int[] res = new int[words.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = tr.query(words[i]);
        }
        return res;
    }
}
class Trie {
    class Node {
        Node[] son = new Node[26];
        int cnt;
    }
    Node root = new Node();
    void insert(String s) {
        Node p = root;
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (p.son[idx] == null)
                p.son[idx] = new Node();
            p = p.son[idx];
            p.cnt++;
        }
    }
    int query(String s) {
        int res = 0;
        Node p = root;
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            p = p.son[idx];
            res += p.cnt;
        }
        return res;
    }
}