leetcode weekly contest 396

T4 确实是比较难的题目，非常不错的题目。

3136. 有效单词

有效单词 需要满足以下几个条件：

至少包含 3 个字符。
由数字 0-9 和英文大小写字母组成。（不必包含所有这类字符。）
至少包含一个 元音字母 。
至少包含一个 辅音字母 。

给你一个字符串 word 。如果 word 是一个有效单词，则返回 true ，否则返回 false 。

注意：

'a'、'e'、'i'、'o'、'u' 及其大写形式都属于 元音字母 。
英文中的 辅音字母 是指那些除元音字母之外的字母。

示例 1：

输入：word = “234Adas”

输出：true

解释：

这个单词满足所有条件。

示例 2：

输入：word = “b3”

输出：false

解释：

这个单词的长度少于 3 且没有包含元音字母。

示例 3：

输入：word = “a3$e”

输出：false

解释：

这个单词包含了 '$' 字符且没有包含辅音字母。

提示：

1 <= word.length <= 20
word 由英文大写和小写字母、数字、'@'、'#' 和 '$' 组成。

地址

https://leetcode.cn/contest/weekly-contest-396/problems/valid-word/

题意

直接模拟

思路

直接模拟即可，题目出的非常不好，细节处理问题较多，直接模拟即可。
复杂度分析：

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    bool isValid(string word) {
        if (word.length() < 3) {
            return false;
        }
        bool f[2]{};
        for (char c : word) {
            if (isalpha(c)) {
                c = tolower(c);
                f[c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'] = true;
            } else if (!isdigit(c)) {
                return false;
            }
        }
        return f[0] && f[1];
    }
};

3137. K 周期字符串需要的最少操作次数

给你一个长度为 n 的字符串 word 和一个整数 k ，其中 k 是 n 的因数。

在一次操作中，你可以选择任意两个下标 i 和 j，其中 0 <= i, j < n ，且这两个下标都可以被 k 整除，然后用从 j 开始的长度为 k 的子串替换从 i 开始的长度为 k 的子串。也就是说，将子串 word[i..i + k - 1] 替换为子串 word[j..j + k - 1] 。

返回使 word 成为 K 周期字符串 所需的最少操作次数。

如果存在某个长度为 k 的字符串 s，使得 word 可以表示为任意次数连接 s ，则称字符串 word 是 K 周期字符串 。例如，如果 word == "ababab"，那么 word 就是 s = "ab" 时的 2 周期字符串。

示例 1：

输入：word = “leetcodeleet”, k = 4

输出：1

解释：可以选择 i = 4 和 j = 0 获得一个 4 周期字符串。这次操作后，word 变为 “leetleetleet” 。

示例 2：

输入：word = “leetcoleet”, k = 2

输出：3

解释：可以执行以下操作获得一个 2 周期字符串。

i	j	word
0	2	etetcoleet
4	0	etetetleet
6	0	etetetetet

提示：

1 <= n == word.length <= 105
1 <= k <= word.length
k 能整除 word.length 。
word 仅由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-396/problems/minimum-number-of-operations-to-make-word-k-periodic/

题意

哈希统计

思路

依次统计字符串中连续长度为 $k$ 的字符串，统计出现次数最多的字符串即可。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示给定的字符串的长度。
空间复杂度：$O(n)$，其中 $n$ 表示给定的字符串的长度。

代码

class Solution:
    def minimumOperationsToMakeKPeriodic(self, word: str, k: int) -> int:
        cnt = {}
        for i in range(0, len(word), k):
            sub_word = word[i:i+k]
            cnt[sub_word] = cnt.get(sub_word, 0) + 1
        max_val = max(cnt.values(), default=1)
        return len(word) // k - max_val

use std::collections::HashMap;

impl Solution {
    pub fn minimum_operations_to_make_k_periodic(word: String, k: i32) -> i32 {
        let mut cnt = HashMap::new();
        for i in (0..word.len()).step_by(k as usize) {
            let sub_word = &word[i..i + k as usize];
            *cnt.entry(sub_word.to_string()).or_insert(0) += 1;
        }
        let max_val = *cnt.values().max().unwrap_or(&1);
       ( word.len() / k as usize - max_val) as i32
    }
}

3138. 同位字符串连接的最小长度

给你一个字符串 s ，它由某个字符串 t 和若干 t 的 同位字符串 连接而成。

请你返回字符串 t 的最小可能长度。

同位字符串 指的是重新排列一个单词得到的另外一个字符串，原来字符串中的每个字符在新字符串中都恰好只使用一次。

示例 1：

输入：s = “abba”

输出：2

解释：

一个可能的字符串 t 为 "ba" 。

示例 2：

输入：s = “cdef”

输出：4

解释：

一个可能的字符串 t 为 "cdef" ，注意 t 可能等于 s 。

提示：

1 <= s.length <= 105
s 只包含小写英文字母。

地址

https://leetcode.cn/contest/weekly-contest-396/problems/minimum-length-of-anagram-concatenation/

题意

数学

思路

对于两个字符串 $s,t$ ，判断其是否为同位字符串，方法比较简单，我们只需要要比较 $s,t$ 中所有的字符数目是否相等即可，按照题目要求需要找到同位字符串的最小连接长度，我们依次从小到大枚举长度 $l$ 即可，此时需要满足 $n \mod l = 0$ 即可，即 $l$ 一定是 $n$ 的因子，此时我们直接枚举 $l$ 即可，对于给定的整数 $n$ ，它最多有 $\log n$ 个因子，我们直接枚举即可，并检测在长度 $l$ 下，字符串 $s$ 分割程长度为 $l$ 的子字符串是否满足均为同位字符串即可。
复杂度：

时间复杂度：$O(n \log n |\Sigma|)$，其中 $n$ 表示给定的字符串的长度，$|\Sigma|$ 表示字符集的数目；
空间复杂度：$O(|\Sigma|)$；

代码

class Solution:
    def minAnagramLength(self, s: str) -> int:
        n = len(s)
        arr = []
        for i in range(1, n + 1):
            if n % i == 0:
                arr.append(i)

        for x in arr:
            cnt = [0] * 26  # ASCII 'a' to 'z' is 0 to 25
            for j in range(x):
                cnt[ord(s[j]) - ord('a')] += 1

            valid = True
            for j in range(x, n, x):
                now = [0] * 26
                for k in range(j, min(j + x, n)):
                    now[ord(s[k]) - ord('a')] += 1
                if now != cnt:
                    valid = False
                    break

            if valid:
                return x

        return n

impl Solution {
    pub fn min_anagram_length(s: String) -> i32 {
        let n = s.len();
        let bytes = s.as_bytes();
        let mut arr = Vec::new();
        for i in 1..=n {
            if n % i == 0 {
                arr.push(i);
            }
        }

        for &x in &arr {
            let mut cnt = vec![0; 26]; 
            for &j in bytes.iter().take(x) {
                cnt[(j - b'a') as usize] += 1;
            }

            let mut valid = true;
            for j in (x..n).step_by(x) {
                let mut now = vec![0; 26];
                for k in 0..x {
                    now[(bytes[j + k] - b'a') as usize] += 1;
                }
                if now != cnt {
                    valid = false;
                    break;
                }
            }

            if valid {
                return x as i32;
            }
        }
        n as i32
    }
}

3139. 使数组中所有元素相等的最小开销

给你一个整数数组 nums 和两个整数 cost1 和 cost2 。你可以执行以下任一操作任意次：

从 nums 中选择下标 i 并且将 nums[i] 增加 1 ，开销为 cost1。
选择 nums 中两个不同下标 i 和 j ，并且将 nums[i] 和 nums[j] 都增加 1 ，开销为 cost2 。

你的目标是使数组中所有元素都相等，请你返回需要的 最小开销 之和。

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

示例 1：

输入：nums = [4,1], cost1 = 5, cost2 = 2

输出：15

解释：

执行以下操作可以使数组中所有元素相等：

将 nums[1] 增加 1 ，开销为 5 ，nums 变为 [4,2] 。
将 nums[1] 增加 1 ，开销为 5 ，nums 变为 [4,3] 。
将 nums[1] 增加 1 ，开销为 5 ，nums 变为 [4,4] 。

总开销为 15 。

示例 2：

输入：nums = [2,3,3,3,5], cost1 = 2, cost2 = 1

输出：6

解释：

执行以下操作可以使数组中所有元素相等：

将 nums[0] 和 nums[1] 同时增加 1 ，开销为 1 ，nums 变为 [3,4,3,3,5] 。
将 nums[0] 和 nums[2] 同时增加 1 ，开销为 1 ，nums 变为 [4,4,4,3,5] 。
将 nums[0] 和 nums[3] 同时增加 1 ，开销为 1 ，nums 变为 [5,4,4,4,5] 。
将 nums[1] 和 nums[2] 同时增加 1 ，开销为 1 ，nums 变为 [5,5,5,4,5] 。
将 nums[3] 增加 1 ，开销为 2 ，nums 变为 [5,5,5,5,5] 。

总开销为 6 。

示例 3：

输入：nums = [3,5,3], cost1 = 1, cost2 = 3

输出：4

解释：

执行以下操作可以使数组中所有元素相等：

将 nums[0] 增加 1 ，开销为 1 ，nums 变为 [4,5,3] 。
将 nums[0] 增加 1 ，开销为 1 ，nums 变为 [5,5,3] 。
将 nums[2] 增加 1 ，开销为 1 ，nums 变为 [5,5,4] 。
将 nums[2] 增加 1 ，开销为 1 ，nums 变为 [5,5,5] 。

总开销为 4 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 106
1 <= cost1 <= 106
1 <= cost2 <= 106

地址

https://leetcode.cn/contest/weekly-contest-396/problems/minimum-cost-to-equalize-array/

题意

数学，贪心

思路

本题确实是个非常非常不错的思维题目，最喜欢的是这类思考性质的题目。我们首先要思考一个简单的问题，假设给定的数组，每次可以从数组中取两个不同的元素，将其减少 $1$，最多可以操作多少次？此时可以参考「1953. 你可以工作的最大周数」，设数组的总元素的和为 $sum$，数组中最大的元素为 $x$，此时可以直到有两种情况:

如果 $x <= sum - x$，我们一定可以将所有的元素都变为 $0$，操作次数即为 $\dfrac{sum}{2}$;
如果 $x > sum - x$，我们无法将所有不同的元素进行配对，操作次数即为 $\min(x, sum - x)$ 次;

回到题目本身，我们需要分类讨论：

当数组元素小于等于 $2$ 个时，如果两个元素不相等，此时哦我们只能利用操作 $1$，无法利用操作 $2$；
当 $2 * cost_1 \le cost_2$ 时，我们肯定是利用第一种操作的代价更小，此时最终的目标元素即为数组中的最大值；
当 $2 * cost_1 > cost_2$ 时，此时我们应该尽可能的使用操作 $2$ 才能使得代价最少。我们知道上述问题的解答方法后，再回到题目本身，对给定的数组 $nums$，我们要使得数组中所有元素相等，至少我们需要使得数组中的所有元素都与数组中的最大值相等。
- 假设已知数组中的最大值为 $x$，此时求出每个元素与 $x$ 的差值，每次从差值中取出 $2$ 个元素，因此此时我们至少需要将数组中所有的元素都增加到 $x$，此时根据前述分析此时需要的代价为 $(n \times x - sum) \times cost_1$;
- 每次取两个数增加比两次增加一个数的代价要小，此时我们应该尽可能的使用两个数的操作次数，假设我们将所有元素都增加到 $x$，此时需要的代价分两种即为：
  - 如果 $x \le sum - x$，此时最多可以进行 $\frac{(nx - sum)}{2}$ 次操作 $2$，需要 $(nx - sum) & 1$ 次操作 $1$,需要的代价即为 $\lfloor \dfrac{(nx - sum)}{2} \rfloor + (nx - sum) & 1$;
  - 如果 $x > sum - x$，此时最多可以进行 $sum - x$ 次操作 $2$，需要 $2x - sum$ 次操作 $1$,需要的代价即为 $(sum -x) \times cost_2 + (2x - sum) \times cost_1$;
- 但是我们需要继续明白一个问题， $x$ 的上限应该是多少？我们知道每次应该尽可能的使用操作 $2$，当 $x$ 增加到一定程度后，此时所有的操作已经都是操作 $2$ 时，此时继续增加 $x$ 就没有任何意义，此时我们需要计算这个上限制，即我们找到最小的 $x$ 使得所有的操作都可以使用操作 $2$ 完成即为上限制，此时需要满足两个条件：
  - 设数组中最大的元素为 $maxval$，此时数组中原有元素的之和为 $sum$，此时由于数组中所有的元素都需要增加到 $x$，此时

复杂度分析:

时间复杂度：$O(n + U)$，其中 $n$ 表示数组的长度， $U$ 表示数组中的最大元素；
空间复杂度：$O(1)$；

代码

class Solution:
    def minCostToEqualizeArray(self, nums: List[int], cost1: int, cost2: int) -> int:
        mod = 10**9 + 7
        maxVal = max(nums)
        n = len(nums)
        for i in range(n):
            nums[i] = maxVal - nums[i]
        maxVal = max(nums)
        tot = sum(nums)
        if n <= 2 or 2 * cost1 <= cost2:
            return tot * cost1 % mod
        
        res = tot * cost1
        cnt1, cnt2 = 0, 0
        # 求出增加的上限 
        x = max(0, (2 * maxVal - tot) // (n - 2)) + 2
        for i in range(0, x + 1):
            if maxVal + i > tot - maxVal + (n - 1) * i:
                cnt2 = tot - maxVal + (n - 1) * i
                cnt1 = tot + n * i - 2 * cnt2
            else:
                cnt2 = (tot + n * i) // 2
                cnt1 = (tot + n * i) & 1
            res = min(res, cost1 * cnt1 + cost2 * cnt2)
        return res % mod

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

关注我的博客: https://mike-box.github.io/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 哪些奋斗者

Tags: 题解力扣周赛赛

← leetcode biweekly contest 130 leetcode weekly contest 399 →

扫描二维码，分享此文章