LeetCode Contest 415

欢迎大家加QQ群：623375442，可以方便群里面交流。

3289. The Two Sneaky Numbers of Digitville

数字小镇 Digitville 中，存在一个数字列表 nums，其中包含从 0 到 n - 1 的整数。每个数字本应 只出现一次，然而，有 两个 顽皮的数字额外多出现了一次，使得列表变得比正常情况下更长。

为了恢复 Digitville 的和平，作为小镇中的名侦探，请你找出这两个顽皮的数字。

返回一个长度为 2 的数组，包含这两个数字（顺序任意）。

测试样例：

输入：nums = [0,1,1,0]

输出：[0,1]

解释：数字 0 和 1 分别在数组中出现了两次。

解答：直接利用HashSet来搜索出现多次的数字。

class Solution {
    public int[] getSneakyNumbers(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int[] res = {-1,-1};
        int pos = 0;
        for (int n : nums) {
            if (set.contains(n)) {
                res[pos++] = n;
            } else {
                set.add(n);
            }
        }
        return res;
    }
}

3290. Maximum Multiplication Score

给你一个大小为 4 的整数数组 a 和一个大小 至少为 4 的整数数组 b。

你需要从数组 b 中选择四个下标 i0, i1, i2, 和 i3，并满足 i0 < i1 < i2 < i3。你的得分将是 a[0] b[i0] + a[1] b[i1] + a[2] b[i2] + a[3] b[i3] 的值。

返回你能够获得的 最大 得分。

测试样例：

输入： a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]

输出：26

解释：选择下标 0, 1, 2 和 5。得分为 3 2 + 2 (-6) + 5 4 + 6 2 = 26。

解答：经典动态规划题目。

class Solution {
    public long maxScore(int[] a, int[] b) {
        long[] dp = new long[4];
        Arrays.fill(dp, Long.MIN_VALUE);
        long res = Long.MIN_VALUE;
        for (int i = 0; i < b.length; ++i) {
            long[] nextDP = new long[4];
            Arrays.fill(nextDP, Long.MIN_VALUE);
            for (int j = Math.min(3, i); j >= 0; --j) {
                long mul = (long) a[j];
                if (j == 0) {
                    nextDP[j] = Math.max(dp[j], mul * b[i]);
                } else if (dp[j - 1] != Long.MIN_VALUE) {
                    nextDP[j] = Math.max(dp[j], dp[j - 1] + mul * b[i]);
                }
            }
            res = Math.max(res, nextDP[3]);
            dp = nextDP;
        }
        return res;
    }
}

3292. Minimum Number of Valid Strings to Form Target II

给你一个字符串数组 words 和一个字符串 target。

如果字符串 x 是 words 中 任意 字符串的 前缀，则认为 x 是一个 有效 字符串。

现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。

测试样例：

输入：words = ["abc","aaaaa","bcdef"], target = "aabcdabc"

输出：3

解释：target 字符串可以通过连接以下有效字符串形成：

• words[1] 的长度为 2 的前缀，即 "aa"。
• words[2] 的长度为 3 的前缀，即 "bcd"。
• words[0] 的长度为 3 的前缀，即 "abc"。

解答：利用AC自动机。前缀越短，需要的匹配数量一定越小。

class Solution {
    public static final int INF = Integer.MAX_VALUE / 2;

    public int minValidStrings(String[] words, String target) {
        int[] dp = new ACAutomaton(words).minCost(target);
        int n = target.length();
        return dp[n] == INF ? -1 : dp[n];
    }

    private class ACAutomaton {
        Node root = new Node();

        ACAutomaton(String[] words) {
            for (String word : words) {
                add(word);
            }
            buildLinks();
        }

        public int[] minCost(String target) {
            int n = target.length();
            int[] dp = new int[n + 1];
            Arrays.fill(dp, INF);
            dp[0] = 0;
            updateDp(target, dp);
            return dp;
        }

        private void add(String word) {
            Node node = root;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (node.next[index] == null) {
                    node.next[index] = new Node();
                }
                node = node.next[index];
                node.length = i + 1;
            }
        }

        private void buildLinks() {
            Queue<Node> queue = new ArrayDeque<>();
            for (Node node : root.next) {
                if (node != null) {
                    node.suffix = root;
                    queue.offer(node);
                }
            }
            while (!queue.isEmpty()) {
                Node node = queue.poll();
                for (int i = 0; i < 26; i++) {
                    Node next = node.next[i];
                    if (next != null) {
                        Node suffix = node.suffix;
                        while (next.suffix == null) {
                            if (suffix.next[i] != null) {
                                next.suffix = suffix.next[i];
                            } else if (suffix == root) {
                                next.suffix = root;
                            } else {
                                suffix = suffix.suffix;
                            }
                        }
                        queue.offer(next);
                    }
                }
            }
        }

        private void updateDp(String target, int[] dp) {
            Node node = root;
            for (int i = 1; i <= target.length(); i++) {
                int index = target.charAt(i - 1) - 'a';
                while (node != root && node.next[index] == null) {
                    node = node.suffix;
                }
                if (node.next[index] != null) {
                    node = node.next[index];
                }
                if (node.length != -1) {
                    dp[i] = Math.min(dp[i], dp[i - node.length] + 1);
                }
            }
        }

        private class Node {
            Node[] next = new Node[26];
            Node suffix;
            int length = -1;
        }
    }
}