LeetCode Contest 420

欢迎大家加QQ群：623375442，可以方便群里面交流。这周题目难度骤降。

100421. Find the Sequence of Strings Appeared on the Screen

给你一个字符串 target。

Alice 将会使用一种特殊的键盘在她的电脑上输入 target，这个键盘 只有两个 按键：

• 按键 1：在屏幕上的字符串后追加字符 'a'。
• 按键 2：将屏幕上字符串的 最后一个 字符更改为英文字母表中的 下一个 字符。例如，'c' 变为 'd'，'z' 变为 'a'。

注意，最初屏幕上是一个空字符串 ""，所以她 只能 按按键 1。

请你考虑按键次数 最少 的情况，按字符串出现顺序，返回 Alice 输入 target 时屏幕上出现的所有字符串列表。

测试样例：

输入： target = "abc"

输出： ["a","aa","ab","aba","abb","abc"]

解释：Alice 按键的顺序如下：

• 按下按键 1，屏幕上的字符串变为 "a"。
• 按下按键 1，屏幕上的字符串变为 "aa"。
• 按下按键 2，屏幕上的字符串变为 "ab"。
• 按下按键 1，屏幕上的字符串变为 "aba"。
• 按下按键 2，屏幕上的字符串变为 "abb"。
• 按下按键 2，屏幕上的字符串变为 "abc"。

解答：这题就是按照题意暴力枚举一下Alice的按键顺序。

class Solution {
    public List<String> stringSequence(String target) {
        List<String> res = new ArrayList<>();
        int last = 0;
        for (int i = 0; i < target.length(); ++i) {
            char cur = target.charAt(i);
            for (char c = 'a'; c <= cur; ++c) {
                if (i == 0) {
                    res.add(String.valueOf(c));
                } else {
                    res.add(res.get(last) + c);
                }
            }
            last = res.size() - 1;
        }
        return res;
    }
}

100369. Count Substrings With K-Frequency Characters I

给你一个字符串 s 和一个整数 k，在 s 的所有子字符串中，请你统计并返回 至少有一个 字符 至少出现 k 次的子字符串总数。

子字符串 是字符串中的一个连续、 非空 的字符序列。

测试样例：

输入：s = "abacb", k = 2

输出：4

解释：符合条件的子字符串如下：

• "aba"（字符 'a' 出现 2 次）。
• "abac"（字符 'a' 出现 2 次）。
• "abacb"（字符 'a' 出现 2 次）。
• "bacb"（字符 'b' 出现 2 次）。

解答：双指针题。右指针不断前进，左指针联动。左指针指向第一个不满足要求的位置。

class Solution {
    public int numberOfSubstrings(String s, int k) {
        int[][] count = new int[s.length() + 1][26];
        for (int i = 0; i < s.length(); ++i) {
            for (int j = 0; j < 26; ++j) {
                count[i + 1][j] = count[i][j];
            }
            count[i + 1][s.charAt(i) - 'a'] += 1;
        }
        int st = 0, ed = 0;
        int res = 0;
        while (ed < s.length()) {
            while (st <= ed && isValid(st, ed, k, count)) {
                ++st;
            }
            if (st - 1 >= 0 && isValid(st - 1, ed, k, count)) {
                res += st;
            }
            ++ed;
        }
        return res;
    }

    private boolean isValid(int st, int ed, int k, int[][] count) {
        boolean res = false;
        for (int i = 0; i < 26; ++i) {
            if (count[ed + 1][i] - count[st][i] >= k) {
                res = true;
                break;
            }
        }
        return res;
    }
}

100453. Minimum Division Operations to Make Array Non Decreasing

给你一个整数数组 nums 。

一个正整数 x 的任何一个 严格小于 x 的 正 因子都被称为 x 的 真因数 。比方说 2 是 4 的 真因数，但 6 不是 6 的 真因数。

你可以对 nums 的任何数字做任意次 操作 ，一次 操作 中，你可以选择 nums 中的任意一个元素，将它除以它的 最大真因数 。

你的目标是将数组变为 非递减 的，请你返回达成这一目标需要的 最少操作 次数。

如果 无法 将数组变成非递减的，请你返回 -1 。

测试样例：

输入：nums = [25,7]

输出：1

解释：通过一次操作，25 除以 5 ，nums 变为 [5, 7] 。

解答：动态规划，每个位置有俩状态。不被选中（保持原始数字），选中（除以最大真因数）。我们从一个dp数组，保留上一个位置选中和不被选中，最小的操作数（不满足要求就放Integer.MAX_VALUE）。迭代计算。

class Solution {
    public int minOperations(int[] nums) {
        int[] res = {0,1};
        for (int i = 1; i < nums.length; ++i) {
            int[] nextRes = {Integer.MAX_VALUE, Integer.MAX_VALUE};
            // 上一个位置，不被选中满足要求
            if (res[0] != Integer.MAX_VALUE) {
                // 按照要求更新当前位置状态
                if (nums[i] >= nums[i - 1]) {
                    nextRes[0] = Math.min(nextRes[0], res[0]);
                }
                if (MaxDiv.getResult(nums[i]) >= nums[i - 1]) {
                    nextRes[1] = Math.min(nextRes[1], res[0] + 1);
                }
            }
            // 上一个位置，被选中满足要求
            if (res[1] != Integer.MAX_VALUE) {
                if (nums[i] >= MaxDiv.getResult(nums[i - 1])) {
                    nextRes[0] = Math.min(nextRes[0], res[1]);
                }
                if (MaxDiv.getResult(nums[i]) >= MaxDiv.getResult(nums[i - 1])) {
                    nextRes[1] = Math.min(nextRes[1], res[1] + 1);
                }
            }
            res = nextRes;
        }
        return Math.min(res[0], res[1]) != Integer.MAX_VALUE ? Math.min(res[0], res[1]) : -1;
    }
}

class MaxDiv {
    private static int[] shared = new int[1_000_001];
    static {
        Arrays.fill(shared, -1);
    }

    public static int getResult(int n) {
        if (shared[n] == -1) {
            shared[n] = n;
            for (int i = 2; i * i <= n; ++i) {
                if (n % i == 0) {
                    shared[n] = i;
                    break;
                }
            }
        }
        return shared[n];
    }
}

100449. Check if DFS Strings Are Palindromes

给你一棵 n 个节点的树，树的根节点为 0 ，n 个节点的编号为 0 到 n - 1 。这棵树用一个长度为 n 的数组 parent 表示，其中 parent[i] 是节点 i 的父节点。由于节点 0 是根节点，所以 parent[0] == -1 。

给你一个长度为 n 的字符串 s ，其中 s[i] 是节点 i 对应的字符。

一开始你有一个空字符串 dfsStr ，定义一个递归函数 dfs(int x) ，它的输入是节点 x ，并依次执行以下操作：

• 按照 节点编号升序 遍历 x 的所有孩子节点 y ，并调用 dfs(y) 。
• 将 字符 s[x] 添加到字符串 dfsStr 的末尾。

注意，所有递归函数 dfs 都共享全局变量 dfsStr 。

你需要求出一个长度为 n 的布尔数组 answer ，对于 0 到 n - 1 的每一个下标 i ，你需要执行以下操作：

• 清空字符串 dfsStr 并调用 dfs(i) 。
• 如果结果字符串 dfsStr 是一个 回文串 ，answer[i] 为 true ，否则 answer[i] 为 false 。

请你返回字符串 answer 。

回文串 指的是一个字符串从前往后与从后往前是一模一样的。

测试样例：

输入：parent = [-1,0,0,1,1,2], s = "aababa"

输出：[true,true,false,true,true,true]

解释：

• 调用 dfs(0) ，得到字符串 dfsStr = "abaaba" ，是一个回文串。
• 调用 dfs(1) ，得到字符串dfsStr = "aba" ，是一个回文串。
• 调用 dfs(2) ，得到字符串dfsStr = "ab" ，不 是回文串。
• 调用 dfs(3) ，得到字符串dfsStr = "a" ，是一个回文串。
• 调用 dfs(4) ，得到字符串 dfsStr = "b" ，是一个回文串。
• 调用 dfs(5) ，得到字符串 dfsStr = "a" ，是一个回文串。

解答：这题不太会做，只想到用Rolling Hash暴力计算了。

class Solution {
    public boolean[] findAnswer(int[] parent, String s) {
        List<Integer>[] edges = new List[parent.length];
        for (int i = 0; i < parent.length; ++i) {
            edges[i] = new ArrayList<>();
        }
        for (int i = 1; i < parent.length; ++i) {
            edges[parent[i]].add(i);
        }
        // 计算每个几点子节点数量
        int[] childCount = new int[parent.length];
        dfsCount(edges, 0, childCount);
        // 按照子节点信息，向最后的String填充
        char[] list = new char[s.length()];
        dfsCharList(edges, 0, s, 0, s.length() - 1, childCount, list);
        boolean[] res = new boolean[parent.length];
        // 利用Rolling Hash快速计算是否对称
        RangeHash hash1 = new RangeHash(list, false), hash2 = new RangeHash(list, true);
        dfsResult(edges, 0, hash1, hash2, 0, s.length() - 1, childCount, res);
        return res;
    }

    private void dfsCount(List<Integer>[] edges, int cur, int[] childCount) {
        if (edges[cur].isEmpty()) {
            childCount[cur] = 1;
        } else {
            childCount[cur] = 1;
            for (int n : edges[cur]) {
                dfsCount(edges, n, childCount);
                childCount[cur] += childCount[n];
            }
        }
    }

    private void dfsCharList(List<Integer>[] edges, int cur, String s, int st, int ed, int[] childCount, char[] list) {
        list[ed] = s.charAt(cur);
        int pos = st;
        for (int n : edges[cur]) {
            dfsCharList(edges, n, s, pos, pos + childCount[n] - 1, childCount, list);
            pos += childCount[n];
        }
    }

    private void dfsResult(List<Integer>[] edges, int cur, RangeHash hash1, RangeHash hash2, int st, int ed, int[] childCount, boolean[] res) {
        int len = hash1.getLen();
        long h1 = hash1.getRangeHash(st, ed), h2 = hash2.getRangeHash(len - 1 - ed, len - 1 - st);
        res[cur] = h1 == h2;
        int pos = st;
        for (int n : edges[cur]) {
            dfsResult(edges, n, hash1, hash2, pos, pos + childCount[n] - 1, childCount, res);
            pos += childCount[n];
        }
    }
}

// Rolling Hash模版
class RangeHash {
    private static final int mod = 1_000_000_007;
    private static final int inv = 129032259;
    public long[] prefix, div;

    public RangeHash(char[] word, boolean dir) {
        prefix = new long[word.length + 1];
        div = new long[word.length + 1];
        long mul = 1;
        div[0] = 1;
        int i = !dir ? 0 : word.length - 1;
        int pos = !dir ? 1 : -1;
        for (int j = 0; i < word.length && i >= 0; i += pos, ++j) {
            int t = word[i] - 'a';
            prefix[j + 1] = (prefix[j] + t * mul) % mod;
            mul = (mul * 31) % mod;
            div[j + 1] = div[j] * inv % mod;
        }
    }

    public long getRangeHash(int st, int ed) {
        long diff = (prefix[ed + 1] - prefix[st] + mod) % mod;
        return diff * div[st] % mod;
    }

    public int getLen() {
        return prefix.length - 1;
    }
}