leetcode biweekly contes 115

双周赛的题目不太好，出的比较怪异的题目，特别是第一题。T4 竟然没有想到解法。

2899. 上一个遍历的整数

给你一个下标从 0 开始的字符串数组 words ，其中 words[i] 要么是一个字符串形式的正整数，要么是字符串 "prev" 。

我们从数组的开头开始遍历，对于 words 中的每个 "prev" 字符串，找到 words 中的 上一个遍历的整数 ，定义如下：

k 表示到当前位置为止的连续 "prev" 字符串数目（包含当前字符串），令下标从 0 开始的整数数组 nums 表示目前为止遍历过的所有整数，同时用 nums_reverse 表示 nums 反转得到的数组，那么当前 "prev" 对应的 上一个遍历的整数 是 nums_reverse 数组中下标为 (k - 1) 的整数。
如果 k 比目前为止遍历过的整数数目更多，那么上一个遍历的整数为 -1 。

请你返回一个整数数组，包含所有上一个遍历的整数。

示例 1：

输入：words = ["1","2","prev","prev","prev"]
输出：[2,1,-1]
解释：
对于下标为 2 处的 "prev" ，上一个遍历的整数是 2 ，因为连续 "prev" 数目为 1 ，同时在数组 reverse_nums 中，第一个元素是 2 。
对于下标为 3 处的 "prev" ，上一个遍历的整数是 1 ，因为连续 "prev" 数目为 2 ，同时在数组 reverse_nums 中，第二个元素是 1 。
对于下标为 4 处的 "prev" ，上一个遍历的整数是 -1 ，因为连续 "prev" 数目为 3 ，但总共只遍历过 2 个整数。

示例 2：

输入：words = ["1","prev","2","prev","prev"]
输出：[1,2,1]
解释：
对于下标为 1 处的 "prev" ，上一个遍历的整数是 1 。
对于下标为 3 处的 "prev" ，上一个遍历的整数是 2 。
对于下标为 4 处的 "prev" ，上一个遍历的整数是 1 ，因为连续 "prev" 数目为 2 ，同时在数组 reverse_nums 中，第二个元素是 1 。

提示：

1 <= words.length <= 100
words[i] == "prev" 或 1 <= int(words[i]) <= 100

地址

https://leetcode.cn/contest/biweekly-contest-115/problems/last-visited-integers/

题意

模拟

思路

按照题意模拟即可，但是改题目确实出的不好。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示给定的元素。
空间复杂度：$O(1)$。

代码

class Solution:
    def lastVisitedIntegers(self, words: List[str]) -> List[int]:
        n = len(words)
        ans = []
        nums = []
        k = 0
        for i, word in enumerate(words):
            if word == "prev":
                k += 1
                ans.append(-1 if k > len(nums) else nums[-k])
            else:
                nums.append(int(word))
                k = 0
        return ans

2900. 最长相邻不相等子序列 I

给你一个整数 n 和一个下标从 0 开始的字符串数组 words ，和一个下标从 0 开始的 二进制 数组 groups ，两个数组长度都是 n 。

你需要从下标 [0, 1, ..., n - 1] 中选出一个 最长子序列 ，将这个子序列记作长度为 k 的 [i0, i1, ..., ik - 1] ，对于所有满足 0 < j + 1 < k 的 j 都有 groups[ij] != groups[ij + 1] 。

请你返回一个字符串数组，它是下标子序列依次对应 words 数组中的字符串连接形成的字符串数组。如果有多个答案，返回任意一个。

子序列 指的是从原数组中删掉一些（也可能一个也不删掉）元素，剩余元素不改变相对位置得到的新的数组。

注意：words 中的字符串长度可能 不相等 。

示例 1：

输入：n = 3, words = ["e","a","b"], groups = [0,0,1]
输出：["e","b"]
解释：一个可行的子序列是 [0,2] ，因为 groups[0] != groups[2] 。
所以一个可行的答案是 [words[0],words[2]] = ["e","b"] 。
另一个可行的子序列是 [1,2] ，因为 groups[1] != groups[2] 。
得到答案为 [words[1],words[2]] = ["a","b"] 。
这也是一个可行的答案。
符合题意的最长子序列的长度为 2 。

示例 2：

输入：n = 4, words = ["a","b","c","d"], groups = [1,0,1,1]
输出：["a","b","c"]
解释：一个可行的子序列为 [0,1,2] 因为 groups[0] != groups[1] 且 groups[1] != groups[2] 。
所以一个可行的答案是 [words[0],words[1],words[2]] = ["a","b","c"] 。
另一个可行的子序列为 [0,1,3] 因为 groups[0] != groups[1] 且 groups[1] != groups[3] 。
得到答案为 [words[0],words[1],words[3]] = ["a","b","d"] 。
这也是一个可行的答案。
符合题意的最长子序列的长度为 3 。

提示：

1 <= n == words.length == groups.length <= 100
1 <= words[i].length <= 10
0 <= groups[i] < 2
words 中的字符串 互不相同 。
words[i] 只包含小写英文字母。

地址

https://leetcode.cn/contest/biweekly-contest-115/problems/longest-unequal-adjacent-groups-subsequence-i/

题意

贪心

思路

尽量选择不同的字符，每个连续相同的字符选择一个即可
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
空间复杂度：$O(\log n)$，其中 $n$ 为数组的长度。

代码

class Solution:
    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:
        dp = [1] * n
        prev = [-1] * n
        for i in range(1, n):
            for j in range(i - 1, -1, -1):
                if groups[i] != groups[j] and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    prev[i] = j

        maxLen = max(dp)
        res = []
        for i in range(n):
            if dp[i] == maxLen:
                while i >= 0:
                    res.append(words[i])
                    i = prev[i]
                break
        res.reverse()
        return res   
           
                        
class Solution:
    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:
        return [words[0]] + [words[i] for i in range(1, n) if groups[i] != groups[i - 1]]

2901. 最长相邻不相等子序列 II

给你一个整数 n 和一个下标从 0 开始的字符串数组 words ，和一个下标从 0 开始的数组 groups ，两个数组长度都是 n 。

两个长度相等字符串的 汉明距离 定义为对应位置字符不同的数目。

你需要从下标 [0, 1, ..., n - 1] 中选出一个 最长子序列 ，将这个子序列记作长度为 k 的 [i0, i1, ..., ik - 1] ，它需要满足以下条件：

相邻下标对应的 groups 值不同。即，对于所有满足 0 < j + 1 < k 的 j 都有 groups[ij] != groups[ij + 1] 。
对于所有 0 < j + 1 < k 的下标 j ，都满足 words[ij] 和 words[ij + 1] 的长度相等，且两个字符串之间的 汉明距离 为 1 。

请你返回一个字符串数组，它是下标子序列依次对应 words 数组中的字符串连接形成的字符串数组。如果有多个答案，返回任意一个。

子序列 指的是从原数组中删掉一些（也可能一个也不删掉）元素，剩余元素不改变相对位置得到的新的数组。

注意：words 中的字符串长度可能 不相等 。

示例 1：

输入：n = 3, words = ["bab","dab","cab"], groups = [1,2,2]
输出：["bab","cab"]
解释：一个可行的子序列是 [0,2] 。
- groups[0] != groups[2]
- words[0].length == words[2].length 且它们之间的汉明距离为 1 。
所以一个可行的答案是 [words[0],words[2]] = ["bab","cab"] 。
另一个可行的子序列是 [0,1] 。
- groups[0] != groups[1]
- words[0].length = words[1].length 且它们之间的汉明距离为 1 。
所以另一个可行的答案是 [words[0],words[1]] = ["bab","dab"] 。
符合题意的最长子序列的长度为 2 。

示例 2：

输入：n = 4, words = ["a","b","c","d"], groups = [1,2,3,4]
输出：["a","b","c","d"]
解释：我们选择子序列 [0,1,2,3] 。
它同时满足两个条件。
所以答案为 [words[0],words[1],words[2],words[3]] = ["a","b","c","d"] 。
它是所有下标子序列里最长且满足所有条件的。
所以它是唯一的答案。

提示：

1 <= n == words.length == groups.length <= 1000
1 <= words[i].length <= 10
1 <= groups[i] <= n
words 中的字符串 互不相同 。
words[i] 只包含小写英文字母。

地址

https://leetcode.cn/contest/biweekly-contest-115/problems/longest-unequal-adjacent-groups-subsequence-ii/

题意

动态规划

思路

典型的子序列动态规划，设 $dp[i]$ 表示以第 $i$ 个元素为结尾的构成的最长子序列的长度，则此时可以知道假设 $dp[i]$ 的前一个元素为 $dp[j]$，此时需要满足 $words[i] \neq words[j]$，且汉明码距离为 $1$, 此时可以得到递推公式为： $dp[i] = max(dp[j] + 1)$，同时我们需要记录前一个元素的索引，这样可以便于找到所有的子序列。
相关的动态规划题目已经非常多了，我们仔细去查找即可，解法基本都类似；
复杂度分析：

时间复杂度：$O(n^2)$，其中$n$ 表示字符串数组的长度；
空间复杂度：$O(n)$，其中$n$ 表示字符串数组的长度；

代码

class Solution:
    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:
        def check(s, t) -> bool:
            return len(s) == len(t) and sum(x != y for x, y in zip(s, t)) == 1
        
        dp = [1] * n
        prev = [-1] * n
        mx = 0
        for i in range(1, n):
            for j in range(i - 1, -1, -1):
                if groups[i] != groups[j] and check(words[i], words[j]) and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            if dp[i] > dp[mx]:
                mx = i
        ans = []
        while mx >= 0:
            ans.append(words[mx])
            mx = prev[mx]
        ans.reverse()
        return ans

2902. 和带限制的子多重集合的数目

给你一个下标从 0 开始的非负整数数组 nums 和两个整数 l 和 r 。

请你返回 nums 中子多重集合的和在闭区间 [l, r] 之间的 子多重集合的数目 。

由于答案可能很大，请你将答案对 109 + 7 取余后返回。

子多重集合 指的是从数组中选出一些元素构成的无序集合，每个元素 x 出现的次数可以是 0, 1, ..., occ[x] 次，其中 occ[x] 是元素 x 在数组中的出现次数。

注意：

如果两个子多重集合中的元素排序后一模一样，那么它们两个是相同的 子多重集合 。
空集合的和是 0 。

示例 1：

输入：nums = [1,2,2,3], l = 6, r = 6
输出：1
解释：唯一和为 6 的子集合是 {1, 2, 3} 。

示例 2：

输入：nums = [2,1,4,2,7], l = 1, r = 5
输出：7
解释：和在闭区间 [1, 5] 之间的子多重集合为 {1} ，{2} ，{4} ，{2, 2} ，{1, 2} ，{1, 4} 和 {1, 2, 2} 。

示例 3：

输入：nums = [1,2,1,3,5,2], l = 3, r = 5
输出：9
解释：和在闭区间 [3, 5] 之间的子多重集合为 {3} ，{5} ，{1, 2} ，{1, 3} ，{2, 2} ，{2, 3} ，{1, 1, 2} ，{1, 1, 3} 和 {1, 2, 2} 。

提示：

1 <= nums.length <= 2 * 104
0 <= nums[i] <= 2 * 104
nums 的和不超过 2 * 104 。
0 <= l <= r <= 2 * 104

地址

https://leetcode.cn/contest/biweekly-contest-115/problems/count-of-sub-multisets-with-bounded-sum/

题意

背包问题，动态规划

思路

题目是典型的背包问题，当然直接用动态规划的解法时间复杂度为 $O(n^2)$，明显超时需要进一步进行优化。设 $dp[i][j]$ 表示前 $i$ 种元素中选择一些数构成和为 $j$ 的方案数。假设第 $i$ 种元素为 $x$，它的数量为 $cnt[x]$，此时第 $i$ 种数可以取 $k$ 个，此时 $k \in [0,cnt[x]]$ 。

此时根据背包的解法，我们可以知道如下：

$$
dp[i][j] = dp[i-1][j] + dp[i-1][j-x] + dp[i-1][j-2x] + \cdots + dp[i-1][j-cnt[x] \times x] \
= \sum_{k=0}^{cnt[x]}dp[i-1][j-k\times x]
$$
当然我们直接计算的时间复杂度肯定为 $O(n^2)$，但是我们注意到如下：
$$
dp[i][j-x] = dp[i-1][j-x] + dp[i-1][j-2x] + dp[i-1][j-3x] + \cdots + dp[i-1][j-(cnt[x] + 1) \times x] \
= \sum_{k=0}^{cnt[x]}dp[i-1][j-k\times x]
$$

根据上述递推公式可以知道: $$dp[i][j] = dp[i-1][j] + dp[i][j-x] - dp[i-1][j-(cnt[x] + 1) \times x]$$, 进一步将上述公式变形可以得到如下：

$$dp[i][j] = dp[i][j-x] + dp[i-1][j] - dp[i-1][j - (cnt[x] + 1) \times x]$$

得到上述推理公式后，我们即可按照上述解法依次求解。由于本题所有元素之和为 $n$, 则我们知道此时 $n = 1 + 2 + 3 + \cdots$, $n$ 最后可以包含 $\sqrt{n}$ 种不同的数，依次按照上述分解进行求解即可。

复杂度分析：

时间复杂度：$O(\sqrt{n} \times n)$，其中 $n$ 表示数组的长度；
空间复杂度：$O(\sqrt{n} \times n)$，其中 $n$ 表示数组的长度；

代码

class Solution:
    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:
        mod = 10**9 + 7
        total = sum(nums)
        if (l > total):
            return 0
        
        r = min(r, total)
        cnt = Counter(nums)
        n = len(cnt)
        dp = [0] * (r + 1)
        dp[0] = cnt[0] + 1
        del cnt[0]

        for x, c in cnt.items():
            ndp = dp.copy()
            for j in range(r + 1):
                if j >= x:
                    ndp[j] += ndp[j - x]
                if j >= (c + 1) * x:
                    ndp[j] -= dp[j - (c + 1) * x]
                ndp[j] %= mod
            dp = ndp
        
        return sum(dp[l:]) % mod

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 题解力扣周赛赛

← leetcode weekly contes 366 leetcode weekly contes 368 →

扫描二维码，分享此文章