力扣周赛：第415场周赛

👨‍🎓作者简介：爱好技术和算法的研究生
🌌上期文章：力扣周赛：第414场周赛
📚订阅专栏：力扣周赛
希望文章对你们有所帮助

本场比赛是9.15日的10:30-12:00，而在9.14日的22:30-24:00有力扣双周赛（第139场），比赛有点多，而且题目有点难，补了挺长时间的，另外我觉得这场比赛的判题有点问题，尤其是第三题，我觉得判题的时候对于常数可能卡的有点严格了，同样的思想和解决方案，Python和C++能卡过去但是Java不行，必须得用dp优化才能过去。

数字小镇中的捣蛋鬼

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

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

返回一个长度为 2 的数组，包含这两个数字（顺序任意）。
示例1
输入： nums = [0,1,1,0]

输出： [0,1]

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

示例2
输入： nums = [0,3,2,1,3,2]

输出： [2,3]

解释:
数字 2 和 3 分别在数组中出现了两次。

签到题

class Solution {public int[] getSneakyNumbers(int[] nums) {int[] count = new int[150];int[] res = new int[2];int pos = 0;for(int i = 0; i < nums.length; ++i){count[nums[i]]++;}for(int i = 0; i < nums.length - 2; ++i){if(count[i] == 2)res[pos++] = i;}return res;}
}

最高乘法得分

题目描述
给你一个大小为 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] 的值。

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

示例1
输入： 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。

示例2
输入： a = [-1,4,5,-2], b = [-5,-1,-3,-2,-4]

输出： -1

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

• a.length == 4
• 4 <= b.length <= 105
• -10⁵ <= a[i], b[i] <= 10⁵

一开始我思考的是双指针思想，只要l0和l3大致确定了，就可以依靠l1和l2的双指针移动，但是l0与l3的确定是很难的一件事，因为a[3]所对应的b[l3]并不一定要满足是最大的情况，比如对于任意的x，都满足a[3] * b[l3]>a[3] * b[x]且x>3，并不代表l3就一定被确定，而是可以为了最终结果而牺牲，所以双指针思想被排除。

可以很容易想到动态规划，证明这种方法可行的关键是重复子问题：
我们可以假设b数组长度为n，即b[0]~b[n - 1]，显然最终结果可能使用到b[n - 1]也可能用不到，此时可以分类讨论：

• 若没有使用到b[n - 1]，那么问题转化为从b[0]~b[n - 2]中选出4个数来跟a[0]~a[3]做运算，求取最大值
• 若使用到b[n - 1]，那么问题转化为从b[0]~b[n - 2]中选出3个数来跟a[0]~a[2]做运算，求取最大值

显然，问题变为了重复子问题，看起来天然适合自顶向下用递归来解决，同理也非常适合自底向上的递推来解决，即动态规划，因此需要思考边界情况和转移方程：

• 首先必须要使用两个变量分别表示数组a和b的下标，因此可以定义f[i][j]，i表示此时a数组下标，j表示此时b数组下标。结合题意，f[i][j]表示为从b[0]~b[j - 1]中选取i个数，来与a[0]~a[i - 1]做运算，求取最大值，因此状态转移方程为f[i][j] = Math.max(f[i][j - 1], f[i - 1][j - 1] + a[i - 1] * b[j - 1]);，其中f[i][j - 1]表示不使用b[j - 1]的情况，而f[i-1][j-1]则表示使用b[j - 1]，即已经做了a[i - 1]*b[j - 1]运算的情况
• 边界情况很重要，也就是下标为0的情况，f[0][j]表示此时一个a元素都没有，显然为0，而f[i][0]则表示还没有选取b元素的情况，为了不影响状态转移过程的max，这里应该设置为无穷小-INF最合理

此外这道题需要注意返回结果是long类型，所以a[i - 1] * b[j - 1]这里需要强转，否则会爆数据范围。

代码如下：

class Solution {public long maxScore(int[] a, int[] b) {int n = b.length;long[][] f = new long[5][n + 1];for(int i = 1; i <= 4; ++i)f[i][0] = Long.MIN_VALUE / 2;for(int i = 1; i <= 4; ++i){for(int j = 1; j <= n; ++j){f[i][j] = Math.max(f[i][j - 1], f[i - 1][j - 1] + (long)a[i - 1] * b[j - 1]);}}return f[4][n];}
}

形成目标字符串需要的最少字符串数 I

题目描述
给你一个字符串数组 words 和一个字符串 target。

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

现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。
示例1
输入： words = [“abc”,“aaaaa”,“bcdef”], target = “aabcdabc”

输出： 3

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

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

示例2
输入： words = [“abababab”,“ab”], target = “ababaababa”

输出： 2

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

• words[0] 的长度为 5 的前缀，即 “ababa”。
• words[0] 的长度为 5 的前缀，即 “ababa”。

数据量

• 1 <= words.length <= 100
• 1 <= words[i].length <= 5 * 10³
• 输入确保 sum(words[i].length) <= 10⁵。
• words[i] 只包含小写英文字母。
• 1 <= target.length <= 5 * 10³
• target 只包含小写英文字母。

看到这种前缀的很容易就会想到字典树，讲words中的所有单词用来构建字典树，接着针对target来做查找，并且选取出最小的组合，分析复杂度感觉直接dfs暴搜是可以过去的，但是给我超时了（768 / 929 个通过的测试用例），即便我使用了记忆化，即vis[i]表示target从i开始到end结束这一个子串所需要的words的最小数量，但依旧超时。非常无奈，用Java来做的话必须对这道题进行优化！在这里我优化的方式是dp

暴搜

Java超时代码如下：

class Solution {class Trie {private Trie[] children;private boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for(int i = 0; i < word.length(); ++i){char c = word.charAt(i);int index = c - 'a';if(node.children[index] == null){node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;}private Trie searchPrefix(String prefix) {Trie node = this;for(int i = 0; i < prefix.length(); ++i){char c = prefix.charAt(i);int index = c - 'a';if(node.children[index] == null) {return null;}node = node.children[index];}return node;}}int[] vis = new int[5005];public int minValidStrings(String[] words, String target) {Trie trie = new Trie();for(String word : words){//System.out.println(word.substring(1));trie.insert(word);}return dfs(0, target.length() - 1, target, trie);}public int dfs(int start, int end, String s, Trie trie) {if(trie.startsWith(s.substring(start, end + 1))){vis[start] = 1;return 1;}int res = Integer.MAX_VALUE;Trie node = trie;for(int i = start; i <= end; ++i){char c = s.charAt(i);//System.out.print(i + "\t");if(node.children[c - 'a'] == null){//System.out.println(i + "\t" + c + "\t" + res);return res == Integer.MAX_VALUE ? -1 : res;}int k = -1;if(vis[i + 1] != 0){k = vis[i + 1];}else{k = dfs(i + 1, end, s, trie);}if(k != -1){res = Math.min(res, k + 1);if(vis[i + 1] > res)vis[i + 1] = res;}node = node.children[c - 'a'];}return res == Integer.MAX_VALUE ? -1 : res;}
}

比较扯淡的是，同样的思想，Python和C++却不会被卡，我觉得力扣需要把判题给做的完善一点了。。。这里贴一个其他人AC的Python代码：

class Trie:"""前缀树模板"""def __init__(self):self.children = dict()self.isEnd = Falsedef insert(self, word: str) -> None:node = selffor s in word:if s not in node.children:node.children[s] = Trie()node = node.children[s]node.isEnd = Truedef searchPrefix(self, prefix: str) -> 'Trie':node = selffor s in prefix:if s not in node.children:return Nonenode = node.children[s]return nodedef search(self, word: str) -> bool:node = self.searchPrefix(word)return node is not None and node.isEnddef startsWith(self, prefix: str) -> bool:return self.searchPrefix(prefix) is not Noneclass Solution:def minValidStrings(self, words: List[str], target: str) -> int:trie = Trie()for word in words:trie.insert(word)@cachedef dfs(start: int, end: int) -> int:if trie.searchPrefix(target[start: end + 1]):return 1res = infnode = triefor k in range(start, end + 1):# 从左往右遍历，这样可以直接移动node的位置# 不需要每次都重新遍历字典树判断前缀if target[k] not in node.children:# 当前位置匹配不上，最长可能前缀遍历完成，直接返回resreturn res if res < inf else -1n1 = dfs(k + 1, end)if n1 != -1:# 找到合法方案，更新最小值res = min(res, n1 + 1)node = node.children[target[k]]  # 直接向后移动node指针return dfs(0, len(target) - 1)

dp优化

dp思想其实是借鉴了暴力的一些思路，也就是说没必要每次都从头开始匹配前缀，而是直接从字典树往下判定，那么显然，target从start下标开始，所可以匹配的前缀长度是非单一的，例如样例1中的’a’和’aa’都是可以直接在字典树中匹配到的。
同理，对于target的任意end下标，我们可以从任意的start下标匹配过来，只要满足target[start: end]在字典树中可以直接匹配到，这时候我们就可以考虑到底要从哪个start下标转移过来，从而满足min，因此问题又转化成了dp。

代码如下：

class Solution {class Trie {private Trie[] children;private boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for(int i = 0; i < word.length(); ++i){char c = word.charAt(i);int index = c - 'a';if(node.children[index] == null){node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;}private Trie searchPrefix(String prefix) {Trie node = this;for(int i = 0; i < prefix.length(); ++i){char c = prefix.charAt(i);int index = c - 'a';if(node.children[index] == null) {return null;}node = node.children[index];}return node;}}Trie trie = new Trie();String s = "";public int minValidStrings(String[] words, String target) {//Trie trie = new Trie();Set<String> set = new HashSet<>(Arrays.asList(words));for(String word : set){//System.out.println(word.substring(1));trie.insert(word);}int[] f = new int[target.length() + 1];Arrays.fill(f, Integer.MAX_VALUE);int n = target.length();f[0] = 0;for(int i = 0; i < n; i++){if(f[i] == Integer.MAX_VALUE){continue;}//寻找从i下标开始满足的前缀的所有长度（在字典树中可以直接匹配）List<Integer> prefixLengths = getPrefixLengths(target, i);for(int len : prefixLengths){//状态转移，判断是否从i这个下标直接拼接到i+lenf[i + len] = Math.min(f[i + len], f[i] + 1);}}return f[n] == Integer.MAX_VALUE ? -1 : f[n];}public List<Integer> getPrefixLengths(String target, int start){List<Integer> lengths = new ArrayList<>();Trie cur = trie;for(int i = start; i < target.length(); i++){char ch = target.charAt(i);if(cur.children[ch - 'a'] == null){break;}cur = cur.children[ch - 'a'];lengths.add(i - start + 1);}return lengths;}}

形成目标字符串需要的最少字符串数 II

题目描述
给你一个字符串数组 words 和一个字符串 target。

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

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

示例1
如上题
示例2
如上题
数据量

• 1 <= words.length <= 100
• 1 <= words[i].length <= 5 * 10⁴
• 输入确保 sum(words[i].length) <= 10⁵.
• words[i] 只包含小写英文字母。
• 1 <= target.length <= 5 * 10⁴
• target 只包含小写英文字母。

与上一题相比，只是数据量更大了，按理说我上面的dp优化能卡的过去的。。。但是没有过得去，上面的dp优化在我这里是（801 / 807 个通过的测试用例），仅超时了6个样例。。。。

所以这里直接贴别人的题解吧，AC自动机我不会所以题解我也看不懂，我个人能理解的题解是哈希+dp+线段树+二分，dp和哈希本质上和我之前的思路是差不多的，只是这个人是反过来进行状态转换的，用二分降低复杂度的同时，状态转换时候的值也直接用线段树来维护。

AC代码如下：

class Solution {static int INF = 100000000;static int B = 127;// 哈希的基数static long[] A = new long[50001];// A[i] = B^istatic {A[0] = 1;for (int i = 1; i <= 50000; i++) {A[i] = A[i - 1] * B;}}long[] hash;public int minValidStrings(String[] words, String target) {HashSet<Long> set = new HashSet<>();// 用来存储 words 中字符串的前缀哈希值for (String s : words) {long v = 0;for (char c : s.toCharArray()) {// 搜集字符串 s 所有前缀的哈希值set.add(v = v * B + c);}}char[] str = target.toCharArray();int n = str.length;hash = new long[n + 1];for (int i = 1; i <= n; i++) {hash[i] = hash[i - 1] * B + str[i - 1];}int[] dp = new int[n + 1];Arrays.fill(dp, INF);dp[n] = 0;SegTree tree = new SegTree(n);tree.set(n, 0);for (int i = n - 1; i >= 0; i--) {int l = i, r = n - 1, m;while (l <= r) {m = (l + r) >> 1;if (set.contains(query(i, m))) {l = m + 1;} else {r = m - 1;}}if (l > i) {// 此时 target[i..j] ∈ S , j ∈ [i, l)dp[i] = Math.min(dp[i], tree.query(i + 1, l) + 1);}if (i > 0) {// 更新线段树中 i 位置的值tree.set(i, dp[i]);}}return dp[0] == INF ? -1 : dp[0];}long query(int l, int r) {return hash[r + 1] - hash[l] * A[r - l + 1];}static class SegTree {private int[] min;private int N;public SegTree(int len) {N = len;min = new int[N << 2];Arrays.fill(min, INF);}public void set(int o, int v) {set(o, v, 1, N, 1);}private void set(int o, int v, int l, int r, int i) {if (l == r) {min[i] = v;return;}int m = (l + r) >> 1;if (o <= m) {set(o, v, l, m, i << 1);} else {set(o, v, m + 1, r, i << 1 | 1);}min[i] = Math.min(min[i << 1], min[i << 1 | 1]);}public int query(int l, int r) {return query(l, r, 1, N, 1);}private int query(int L, int R, int l, int r, int i) {if (L <= l && r <= R) {return min[i];}int m  = (l + r) >> 1;int ans = INF;if (L <= m) {ans = Math.min(ans, query(L, R, l, m, i << 1));}if (R > m) {ans = Math.min(ans, query(L, R, m + 1, r, i << 1 | 1));}return ans;}}
}