且听疯吟

leetcode weekly contes 368

2023-10-24

leetcode weekly contes 368

本周的题目难度还是非常高的，特别是 T3 是个好题目，容易出错，且不好写的题目。

2908. 元素和最小的山形三元组 I

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

  • i < j < k
  • nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

示例 1：

输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为： 
- 2 < 3 < 4
- nums[2] < nums[3] 且 nums[4] < nums[3]
这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。

示例 2：

输入：nums = [5,4,8,7,10,2]
输出：13
解释：三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组，因为： 
- 1 < 3 < 5 
- nums[1] < nums[3] 且 nums[5] < nums[3]
这个三元组的元素和等于 nums[1] + nums[3] + nums[5] = 13 。可以证明不存在元素和小于 13 的山形三元组。

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山形三元组。

提示：

  • 3 <= nums.length <= 50
  • 1 <= nums[i] <= 50

地址

https://leetcode.cn/contest/weekly-contest-368/problems/minimum-sum-of-mountain-triplets-i/

题意

枚举

思路

  1. 设 $nums[i]$ 为三元组中的中间元素，则此时和最小情形应该是 $[0,i-1]$ 的最小值加上 $[i+1,n-1]$ 的最小值，此时我们利用前后缀分别保存前 $i-1$ 个元素的最小值，以及从 $i+1$ 开始往后的最小值，依次遍历枚举即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。

代码

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        left = [nums[0]] * n
        right = [nums[n-1]] * n
        for i in range(1, n):
            left[i] = min(left[i - 1], nums[i])
        for i in range(n - 2, -1, -1):
            right[i] = min(right[i + 1], nums[i])
        res = inf
        for i in range(1, n - 1):
            if nums[i] > left[i - 1] and nums[i] > right[i + 1]:
                res = min(res, nums[i] + left[i - 1] + right[i + 1])
        if res == inf:
            return -1
        return res

2909. 元素和最小的山形三元组 II

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

  • i < j < k
  • nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

示例 1：

输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为： 
- 2 < 3 < 4
- nums[2] < nums[3] 且 nums[4] < nums[3]
这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。

示例 2：

输入：nums = [5,4,8,7,10,2]
输出：13
解释：三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组，因为： 
- 1 < 3 < 5 
- nums[1] < nums[3] 且 nums[5] < nums[3]
这个三元组的元素和等于 nums[1] + nums[3] + nums[5] = 13 。可以证明不存在元素和小于 13 的山形三元组。

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山形三元组。

提示：

  • 3 <= nums.length <= 105
  • 1 <= nums[i] <= 108

地址

https://leetcode.cn/contest/weekly-contest-368/problems/minimum-sum-of-mountain-triplets-ii/

题意

枚举

思路

  1. 与第一题的解法一模一样，设 $nums[i]$ 为三元组中的中间元素，则此时和最小情形应该是 $[0,i-1]$ 的最小值加上 $[i+1,n-1]$ 的最小值，此时我们利用前后缀分别保存前 $i-1$ 个元素的最小值，以及从 $i+1$ 开始往后的最小值，依次遍历枚举即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。

代码

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        left = [nums[0]] * n
        right = [nums[n-1]] * n
        for i in range(1, n):
            left[i] = min(left[i - 1], nums[i])
        for i in range(n - 2, -1, -1):
            right[i] = min(right[i + 1], nums[i])
        res = inf
        for i in range(1, n - 1):
            if nums[i] > left[i - 1] and nums[i] > right[i + 1]:
                res = min(res, nums[i] + left[i - 1] + right[i + 1])
        if res == inf:
            return -1
        return res

2910. 合法分组的最少组数

给你一个长度为 n 下标从 0 开始的整数数组 nums 。

我们想将下标进行分组，使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。

如果以下条件成立，我们说这个分组方案是合法的：

  • 对于每个组 g ，同一组内所有下标在 nums 中对应的数值都相等。
  • 对于任意两个组 g1 和 g2 ，两个组中 下标数量 的 差值不超过 1 。

请你返回一个整数，表示得到一个合法分组方案的 最少 组数。

示例 1：

输入：nums = [3,2,3,2,3]
输出：2
解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：
组 1 -> [0,2,4]
组 2 -> [1,3]
所有下标都只属于一个组。
组 1 中，nums[0] == nums[2] == nums[4] ，所有下标对应的数值都相等。
组 2 中，nums[1] == nums[3] ，所有下标对应的数值都相等。
组 1 中下标数目为 3 ，组 2 中下标数目为 2 。
两者之差不超过 1 。
无法得到一个小于 2 组的答案，因为如果只有 1 组，组内所有下标对应的数值都要相等。
所以答案为 2 。

示例 2：

输入：nums = [10,10,10,3,1,1]
输出：4
解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：
组 1 -> [0]
组 2 -> [1,2]
组 3 -> [3]
组 4 -> [4,5]
分组方案满足题目要求的两个条件。
无法得到一个小于 4 组的答案。
所以答案为 4 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-368/problems/minimum-number-of-groups-to-create-a-valid-assignment/

题意

枚举

思路

  1. 设当前分组的下标数量的最大值为 $x$，刚开始拿到题目准备用二分查找，后来仔细发现实际并不满足单调性，无法使用二分查找，比如 $[1,1,1,1,1]$ 利用二分查找时可能会失效，$x=3$ 的时候成立，$x=4$ 的时候不成立，$x=5$ 时成立，则不符合单调性，因此不能用二分查找问题。由于每个分组只能为相同的元素，首先我们对各个元素进行分组统计，假设我们已经知道当前所有分组中下标数量最多的数目为 $x$，则此时所有分组中下标的数量要么是 $x$，要么是 $x-1$，此时我们即可计算出分数的数量。本题本质上就是求最大的分组的下标数量 $x$。仔细分析一下：
    • $x$ 的取值范围，假设当前相同元素中，出现次数最少的数字为 $k$，出现次数为 $cnt[k]$, 则此时 $x$ 的取值一定不能大于 $cnt[k] + 1$，否则无法成立，因此我们可以知道 $x$ 的取值范围为 $[1,cnt[k] + 1]$；
    • 根据上面推论，我们找到 $x$ 的取值范围后，依次枚举 $x$，找到最大的 $x$ 可以满足分组要求则返回当前的分组个数即可；
    • 假设当前数字的数量为 $v$ 个，我们如何将其划分为大小为 $x,x-1$ 的分组，$v$ 到底需要满足什么条件才可以划分？
      • $v \mod x = 0$ 时，此时我们直接划分，因为此时可以将 $v$ 划分为 $\dfrac{v}{x}$ 个分组；
      • $v \bmod x \neq 0$ 时，此时我们无法直接划分，需要进行检测：
        • 我们可以知道此时有 $t = \lfloor \dfrac{v}{x}\rfloor$ 个 $x$，剩余的元素为 $v \mod x$ 个，此时我们需要将 $v \bmod x$ 尽量往 $x- 1$ 上凑，至少还需要 $x-1 - v \bmod x$ 个元素才能凑成 $x-1$，。此时由于存在 $t$ 个 $x$ ，每个 $x$ 最多可以取出一个 $1$，一共可以取出 $t$ 个 $1$，此时只需要满足 $t \ge (x - 1) - v \bmod x$, 即此时需要满足 $t + 1 \ge x - v \bmod x$ 即可满足上述要求。
    • 根据上述分析，我们直接枚举窗口大小并进行模拟即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中$n$ 表示数组的长度；
  • 空间复杂度：$O(n)$，其中$n$ 表示数组的长度；

代码

class Solution:
    def minGroupsForValidAssignment(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        minSize = min(cnt.values())
        for i in range(minSize + 1, 0, -1):
            valid = True
            tot = 0
            for k, v in cnt.items():
                if v % i == 0:
                    tot += v // i
                    continue
                    
                x = v // i
                y = i - (v % i)
                if x + 1 >= y:
                    tot += x + 1
                else:
                    valid = False
                    break
            if valid:
                return tot
        return -1

2911. 得到 K 个半回文串的最少修改次数

给你一个字符串 s 和一个整数 k ，请你将 s 分成 k 个 子字符串 ，使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。

请你返回一个整数，表示需要修改的 最少 字符数目。

注意：

  • 如果一个字符串从左往右和从右往左读是一样的，那么它是一个 回文串 。
  • 如果长度为 len 的字符串存在一个满足 1 <= d < len 的正整数 d ，len % d == 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 ，那么我们说这个字符串是 半回文串 。比方说 "aa" ，"aba" ，"adbgad" 和 "abab" 都是 半回文串 ，而 "a" ，"ab" 和 "abca" 不是。
  • 子字符串 指的是一个字符串中一段连续的字符序列。

示例 1：

输入：s = "abcac", k = 2
输出：1
解释：我们可以将 s 分成子字符串 "ab" 和 "cac" 。子字符串 "cac" 已经是半回文串。如果我们将 "ab" 变成 "aa" ，它也会变成一个 d = 1 的半回文串。
该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 1 。

示例 2:

输入：s = "abcdef", k = 2
输出：2
解释：我们可以将 s 分成子字符串 "abc" 和 "def" 。子字符串 "abc" 和 "def" 都需要修改一个字符得到半回文串，所以我们总共需要 2 次字符修改使所有子字符串变成半回文串。
该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 2 。

示例 3：

输入：s = "aabbaa", k = 3
输出：0
解释：我们可以将 s 分成子字符串 "aa" ，"bb" 和 "aa" 。
字符串 "aa" 和 "bb" 都已经是半回文串了。所以答案为 0 。

提示：

  • 2 <= s.length <= 200
  • 1 <= k <= s.length / 2
  • s 只包含小写英文字母。

地址

https://leetcode.cn/contest/weekly-contest-368/problems/minimum-changes-to-make-k-semi-palindromes/

题意

动态规划

思路

  1. 其实感觉 T4 过于套路的题目了，感觉没啥太大的难度，设 $dp[i][j]$ 表示将前 $i$ 个字符转换为 $j$ 个半回文串的最少修改次数，次数可以可以得到递推公式为：
    $$
    dp[i][j] = \min(dp[i][j], dp[i-m][j-1] + cost[i-m+1][i])
    $$
    其中 $cost[i-m+1][i]$ 表示将字符串 $s[i-m+1\cdots i]$ 转化为半回文串的最少替换次数，这个求法比较简单，我们直接计算即可，不需要太花费时间，我们依次尝试对于子串 $s[i-m+1\cdots i]$ 尝试所有可能的 $d$，此时 $d\in[1,m-1]$，依次求出所有可能的划分即可，可以提前预处理，求出所有的 $cost[i][j]$，本身难度不是很大，没有太多需要描述。

  2. 复杂度分析：

  • 时间复杂度：$O(n^3 \log n + k\times n^2)$，其中 $n$ 表示字符串的长度，$k$ 为给定的元素；
  • 空间复杂度：$O(n^2)$，其中 $n$ 表示字符串的长度；

代码

class Solution:
    def minimumChanges(self, s: str, k: int) -> int:
        n = len(s)
        dp = [[inf] * (k + 1) for _ in range(n + 1)]
        cost = [[inf] * (n + 1) for _ in range(n + 1)]
        fac = [[] for _ in range(n + 1)]
        
        for i in range(1, n + 1):
            for j in range(1, i):
                if i % j == 0:
                    fac[i].append(j)
        
        for i in range(1, n + 1):
            cost[i][i] = 0
            for j in range(i + 1, n + 1):
                x = j - i + 1
                for d in fac[x]:
                    cnt = 0
                    for m in range(0, d):
                        str1 = ""
                        for t in range(i + m, j + 1, d):
                            str1 += s[t - 1]
                        str2 = str1[::-1]
                        cnt += sum(1 for a, b in zip(str1, str2) if a != b) // 2
                    cost[i][j] = min(cost[i][j], cnt)
        
        dp[0][0] = 0
        for j in range(1, k + 1):
            for i in range(2, n + 1):
                for m in range(i - 1, 0, -1):
                    if dp[m - 1][j - 1] != inf:
                        dp[i][j] = min(dp[i][j], dp[m-1][j-1] + cost[m][i])
        return dp[n][k]

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

Tags: 题解 力扣周赛赛
← leetcode biweekly contes 115 leetcode biweekly contes 116 →

扫描二维码，分享此文章