力扣第 311 场周赛

比赛时间 2022-09-18。本场周赛国服共 2289 人 AK。

T1. 最小偶倍数（3 分）

解题思路

数学。当 n 为奇数时，答案为 2n；当 n 为偶数时，答案为 n。

时间复杂度：O(1)。

参考代码

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

T2. 最长的字母序连续子字符串的长度（4 分）

解题思路

双指针。

时间复杂度：O(n)。

参考代码

class Solution {
    public int longestContinuousSubstring(String s) {
        int len = s.length();

        int max = 0;
        // 双指针。对于每个 i，找到最右的 j，长度为 j-i+1
        int i = 0;
        for (int j = i; j < len; j++) {
            if (s.charAt(j) - s.charAt(i) == j - i) {
                max = Math.max(max, j - i + 1);
            } else {
                i = j;
            }
        }
        return max;
    }
}

T3. 反转二叉树的奇数层（5 分）

解题思路

二叉树层序遍历。对奇数层节点重新赋值即可。

时间复杂度：O(n)。

参考代码

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        int level = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> curLevelVal = new ArrayList<>();
            List<TreeNode> curLevelNode = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.remove();
                curLevelVal.add(cur.val);
                curLevelNode.add(cur);

                if (cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }

            // 奇数层节点重新赋值
            if (level % 2 == 1) {
                Collections.reverse(curLevelVal);
                for (int i = 0; i < curLevelVal.size(); i++) {
                    curLevelNode.get(i).val = curLevelVal.get(i);
                }
            }
            level++;
        }
        return root;
    }
}

T4. 字符串的前缀分数和（6 分）

解题思路

暴力时间复杂度：O(n^2*|s|)。会 TLE（听说 Python 暴力能 AC？）

Trie 字典树。

时间复杂度：O(n*|s|)。

参考代码

class Solution {
    public int[] sumPrefixScores(String[] words) {
        int len = words.length;
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            res[i] = trie.startsWith(words[i]);
        }
        return res;
    }

    private static class Trie {
        private final Trie[] children;
        // 有多少个前缀
        private int val;

        public Trie() {
            children = new Trie[26];
        }

        public void insert(String word) {
            Trie node = this;
            for (char ch : word.toCharArray()) {
                int idx = ch - 'a';
                if (node.children[idx] == null) {
                    node.children[idx] = new Trie();
                }
                node = node.children[idx];
                node.val++;
            }
        }

        public int startsWith(String prefix) {
            int res = 0;
            Trie node = this;
            for (char ch : prefix.toCharArray()) {
                int idx = ch - 'a';
                if (node.children[idx] == null) {
                    return res;
                }
                node = node.children[idx];
                res += node.val;
            }
            return res;
        }
    }
}

（全文完）