当前位置：首页 > article >正文

力扣周赛：第415场周赛

article 2024/9/21 6:40:03

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

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

力扣周赛：第415场周赛

数字小镇中的捣蛋鬼
最高乘法得分
形成目标字符串需要的最少字符串数 I
- 暴搜
- dp优化
形成目标字符串需要的最少字符串数 II

数字小镇中的捣蛋鬼

题目描述
数字小镇 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 = False


    def insert(self, word: str) -> None:
        node = self
        for s in word:
            if s not in node.children:
                node.children[s] = Trie()
            node = node.children[s]
        node.isEnd = True
    
    def searchPrefix(self, prefix: str) -> 'Trie':
        node = self
        for s in prefix:
            if s not in node.children:
                return None
            node = node.children[s]
        return node


    def search(self, word: str) -> bool:
        node = self.searchPrefix(word)
        return node is not None and node.isEnd


    def startsWith(self, prefix: str) -> bool:
        return self.searchPrefix(prefix) is not None


class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        trie = Trie()
        for word in words:
            trie.insert(word)
        
        @cache
        def dfs(start: int, end: int) -> int:
            if trie.searchPrefix(target[start: end + 1]):
                return 1
            res = inf
            node = trie
            for k in range(start, end + 1):
                # 从左往右遍历，这样可以直接移动node的位置
                # 不需要每次都重新遍历字典树判断前缀
                if target[k] not in node.children:
                    # 当前位置匹配不上，最长可能前缀遍历完成，直接返回res
                    return res if res < inf else -1
                n1 = 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+len
                f[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^i
    static {
        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;
        }

    }
}