leetcode biweekly contest 126

总体来说，双周赛的题目难度确实还是挺高的，题目质量也是很好，不过有一些偏竞赛的题目。

3079. 求出加密整数的和

给你一个整数数组 nums ，数组中的元素都是正整数。定义一个加密函数 encrypt ，encrypt(x) 将一个整数 x 中 每一个 数位都用 x 中的最大数位替换。比方说 encrypt(523) = 555 且 encrypt(213) = 333 。

请你返回数组中所有元素加密后的和。

示例 1：

输入：nums = [1,2,3]

输出：6

解释：加密后的元素位 [1,2,3] 。加密元素的和为 1 + 2 + 3 == 6 。

示例 2：

输入：nums = [10,21,31]

输出：66

解释：加密后的元素为 [11,22,33] 。加密元素的和为 11 + 22 + 33 == 66 。

提示：

1 <= nums.length <= 50
1 <= nums[i] <= 1000

地址

https://leetcode.cn/contest/biweekly-contest-126/problems/find-the-sum-of-encrypted-integers/

题意

模拟

思路

按照题目要求进行模拟即可，并返回所有结果的和即可。
复杂度分析：

时间复杂度：$O(n \log U)$，其中 $n$ 表示给定数组的长度。
空间复杂度：$O(1)$。

代码

class Solution:
    def sumOfEncryptedInt(self, nums: List[int]) -> int:
        ans = 0
        for x in nums:
            b, cur = 0, 0
            while x > 0:
                b = max(b, x % 10)
                cur = cur * 10 + 1
                x //= 10
            ans += cur * b
        return ans

impl Solution {
    pub fn sum_of_encrypted_int(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        for &x in nums.iter() {
            let mut x = x;
            let mut b = 0;
            let mut cur = 0;
            while x > 0 {
                b = b.max(x % 10);
                cur = cur * 10 + 1;
                x /= 10;
            }
            ans += cur * b;
        }
        ans
    }
}

3080. 执行操作标记数组中的元素

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

同时给你一个长度为 m 的二维操作数组 queries ，其中 queries[i] = [indexi, ki] 。

一开始，数组中的所有元素都 未标记 。

你需要依次对数组执行 m 次操作，第 i 次操作中，你需要执行：

如果下标 indexi 对应的元素还没标记，那么标记这个元素。
然后标记 ki 个数组中还没有标记的最小元素。如果有元素的值相等，那么优先标记它们中下标较小的。如果少于 ki 个未标记元素存在，那么将它们全部标记。

请你返回一个长度为 m 的数组 answer ，其中 answer[i]是第 i 次操作后数组中还没标记元素的和。

示例 1：

输入：nums = [1,2,2,1,2,3,1], queries = [[1,2],[3,3],[4,2]]

输出：[8,3,0]

解释：

我们依次对数组做以下操作：

标记下标为 1 的元素，同时标记 2 个未标记的最小元素。标记完后数组为 nums = [***1***,***2***,2,***1***,2,3,1] 。未标记元素的和为 2 + 2 + 3 + 1 = 8 。
标记下标为 3 的元素，由于它已经被标记过了，所以我们忽略这次标记，同时标记最靠前的 3 个未标记的最小元素。标记完后数组为 nums = [***1***,***2***,***2***,***1***,***2***,3,***1***] 。未标记元素的和为 3 。
标记下标为 4 的元素，由于它已经被标记过了，所以我们忽略这次标记，同时标记最靠前的 2 个未标记的最小元素。标记完后数组为 nums = [***1***,***2***,***2***,***1***,***2***,***3***,***1***] 。未标记元素的和为 0 。

示例 2：

输入：nums = [1,4,2,3], queries = [[0,1]]

输出：[7]

解释：我们执行一次操作，将下标为 0 处的元素标记，并且标记最靠前的 1 个未标记的最小元素。标记完后数组为 nums = [***1***,4,***2***,3] 。未标记元素的和为 4 + 3 = 7 。

提示：

n == nums.length
m == queries.length
1 <= m <= n <= 105
1 <= nums[i] <= 105
queries[i].length == 2
0 <= indexi, ki <= n - 1

地址

https://leetcode.cn/contest/biweekly-contest-126/problems/mark-elements-on-array-by-performing-queries/

题意

排序

思路

根据题目要求，对数组中每个元素进行标记，每次从数组中取出元素时，依次按照从小到大顺序取出数据，取出 $k$ 个位被标记的元素，并同时进行标记即可，还算是中规中距的题目，不算太难。
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 表示给定数组的长度。
空间复杂度：$O(n)$, 其中 $n$ 表示给定数组的长度。

代码

class Solution:
    def unmarkedSumArray(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        tot = sum(nums)
        visit = [False] * len(nums)
        arr = [(x, i) for i, x in enumerate(nums)]
        arr.sort()
        
        ans = []
        i = 0
        for idx, k in queries:
            if not visit[idx]:
                visit[idx] = True
                tot -= nums[idx]
            while i < len(nums) and k > 0:
                x = arr[i][1]
                if not visit[x]:
                    tot -= nums[x]
                    visit[x] = True
                    k -= 1
                i += 1
            ans.append(tot)
        return ans

impl Solution {
    pub fn unmarked_sum_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i64> {
        let mut tot: i64 =  nums.iter().map(|&x| x as i64).sum();
        let mut visit = vec![false; nums.len()];
        let mut arr: Vec<(i32, usize)> = nums.iter().enumerate().map(|(i, &x)| (x, i)).collect();
        arr.sort();

        let mut ans: Vec<i64> = Vec::new();
        let mut i: usize = 0;
        for q in queries.iter() {
            let (idx, mut k) = (q[0] as usize, q[1]);
            if !visit[idx] {
                visit[idx] = true;
                tot -= nums[idx] as i64;
            }
            while i < nums.len() && k > 0 {
                let x = arr[i].1;
                if !visit[x] {
                    tot -= nums[x] as i64;
                    visit[x] = true;
                    k -= 1;
                }
                i += 1;
            }
            ans.push(tot);
        }
        ans
    }
}

3081. 替换字符串中的问号使分数最小

给你一个字符串 s 。s[i] 要么是小写英文字母，要么是问号 '?' 。

对于长度为 m 且只含有小写英文字母的字符串 t ，我们定义函数 cost(i) 为下标 i 之前（也就是范围 [0, i - 1] 中）出现过与 t[i] 相同字符出现的次数。

字符串 t 的分数为所有下标 i 的 cost(i) 之和。

比方说，字符串 t = "aab" ：

cost(0) = 0
cost(1) = 1
cost(2) = 0
所以，字符串 "aab" 的分数为 0 + 1 + 0 = 1 。

你的任务是用小写英文字母替换 s 中所有问号，使 s 的 分数****最小 。

请你返回替换所有问号 '?' 之后且分数最小的字符串。如果有多个字符串的 分数最小 ，那么返回字典序最小的一个。

示例 1：

输入：s = “???”

输出： “abc”

解释：这个例子中，我们将 s 中的问号 '?' 替换得到 "abc" 。

对于字符串 "abc" ，cost(0) = 0 ，cost(1) = 0 和 cost(2) = 0 。

"abc" 的分数为 0 。

其他修改 s 得到分数 0 的字符串为 "cba" ，"abz" 和 "hey" 。

这些字符串中，我们返回字典序最小的。

示例 2：

输入： s = “a?a?”

输出： “abac”

解释：这个例子中，我们将 s 中的问号 '?' 替换得到 "abac" 。

对于字符串 "abac" ，cost(0) = 0 ，cost(1) = 0 ，cost(2) = 1 和 cost(3) = 0 。

"abac" 的分数为 1 。

提示：

1 <= s.length <= 105
s[i] 要么是小写英文字母，要么是 '?' 。

地址

https://leetcode.cn/contest/biweekly-contest-126/problems/replace-question-marks-in-string-to-minimize-its-value/

题意

贪心

思路

题目要求总的分数最小，首先我们需要明确一点是，假设给定的字符 $c$ 出现的次数为 $cnt$ ，则此时该字符 $c$ 的得分即为 $\dfrac{cnt\times(cnt -1)}{2}$，根据这个原则可以知道，如果每个字符串出现的次数越少，则总的分数也就越少，我们的目标即使得字符串中每个字符出现的总此时尽可能的少即可，此时我们统计所有的 $?$ 的次数，并将这些位置贪心的分配给频次最少的字符即可。
复杂度分析：

时间复杂度：$O(n \times \Sigma)$, $n$ 表示给定字符串数组的长度， $\Sigma$ 表示字符的种类；
空间复杂度：$O(n)$,, $n$ 表示定字符串数组的长度

代码

class Solution:
    def minimizeStringValue(self, s: str) -> str:
        n = len(s);
        cnt = [0] * 26
        tot = s.count('?')
        for i, c in enumerate(s):
            if c != '?':
                cnt[ord(c) - ord('a')] += 1
        arr = []
        for i in range(tot):
            idx, freq = 0, n
            for j in range(26):
                if cnt[j] < freq:
                    freq, idx = cnt[j], j
            arr.append(chr(ord('a') + idx))
            cnt[idx] += 1
        arr.sort()
        t = list(s)
        j = 0
        for i in range(n):
            if t[i] == '?':
                t[i] = arr[j]
                j += 1
        return ''.join(t)

impl Solution {
    pub fn minimize_string_value(s: String) -> String {
        let mut s = s;
        let n = s.len();
        let mut cnt: Vec<usize> = vec![0; 26];
        let mut arr: Vec<usize> = Vec::new();
        let mut t = String::new();

        for (i, c) in s.chars().enumerate() {
            if c == '?' {
                arr.push(i);
                let mut min_freq = usize::MAX;
                let mut target = 0;
                for j in 0..26 {
                    if cnt[j] < min_freq {
                        target = j;
                        min_freq = cnt[j];
                    }
                }
                t.push((b'a' + target as u8) as char);
                cnt[target] += 1;
            } else {
                let index = (c as u8 - b'a') as usize;
                cnt[index] += 1;
            }
        }

        let mut sorted_t: Vec<char> = t.chars().collect();
        sorted_t.sort();
        for (i, idx) in arr.iter().enumerate() {
            s.replace_range(*idx..=*idx, &sorted_t[i].to_string());
        }
        s
    }
}

3082. 求出所有子序列的能量和

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个整数数组的能量定义为和等于 k 的子序列的数目。

请你返回 nums 中所有子序列的 能量和 。

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

示例 1：

输入： nums = [1,2,3], k = 3

输出： 6

解释：

总共有 5 个能量不为 0 的子序列：

子序列 [***1***,***2***,***3***] 有 2 个和为 3 的子序列：[1,2,***3\***] 和 [***1\***,***2\***,3] 。
子序列 [***1***,2,***3***] 有 1 个和为 3 的子序列：[1,2,***3\***] 。
子序列 [1,***2***,***3***] 有 1 个和为 3 的子序列：[1,2,***3\***] 。
子序列 [***1***,***2***,3] 有 1 个和为 3 的子序列：[***1\***,***2\***,3] 。
子序列 [1,2,***3***] 有 1 个和为 3 的子序列：[1,2,***3\***] 。

所以答案为 2 + 1 + 1 + 1 + 1 = 6 。

示例 2：

输入： nums = [2,3,3], k = 5

输出： 4

解释：

总共有 3 个能量不为 0 的子序列：

子序列 [***2***,***3***,***3***] 有 2 个子序列和为 5 ：[***2\***,3,***3\***] 和 [***2\***,***3\***,3] 。
子序列 [***2***,3,***3***] 有 1 个子序列和为 5 ：[***2\***,3,***3\***] 。
子序列 [***2***,***3***,3] 有 1 个子序列和为 5 ：[***2\***,***3\***,3] 。

所以答案为 2 + 1 + 1 = 4 。

示例 3：

输入： nums = [1,2,3], k = 7

输出： 0

解释：不存在和为 7 的子序列，所以 nums 的能量和为 0 。

提示：

1 <= n <= 100
1 <= nums[i] <= 104
1 <= k <= 100

地址

https://leetcode.cn/contest/biweekly-contest-126/problems/find-the-sum-of-the-power-of-all-subsequences/

题意

动态规划

思路

对于每个和为 $k$ 的子序列 $list$，且它的长度为 $c$，此时其余的元素可以选择或者不选，此时可以构成一定含有 $list$ 的子序列 $2^{n-k}$ 个，此时我们只需要计算含有长度为 $c$ 的子序列的数目即可，此时可以知道总的数目即为：$$ T = \sum_{i=1}^{n}f[i][k]$$，其中 $f[i][k]$ 表示长度为 $i$ 且元素和为 $k$ 的子序列数目。此时直接按照递推公式即可
- 如果不选择当前的 $x$，则此时 $f[i][k] = f[i][k]$;
- 如果选择当前的 $x$，则此时可以推出 $f[i][k] = f[i][k] + f[i-1][k - x]$；
复杂度分析：

时间复杂度：$O(n^2k)$，其中 $n$ 表示给定数组的长度，$k$ 表示给定的整数。
空间复杂度：$O(nk)$，其中 $n$ 表示给定数组的长度，$k$ 表示给定的整数。

代码

class Solution:
    def sumOfPower(self, nums: List[int], k: int) -> int:
        n = len(nums)
        mod = 10**9 + 7
        f = [[0] * (k + 1) for _ in range(n + 1)]
        f[0][0] = 1
        for x in nums:
            if (x > k):
                continue
            for i in range(n, 0, -1):
                for j in range(k, x - 1, -1):
                    f[i][j] = (f[i][j] + f[i - 1][j - x]) % mod
        
        res, cur = 0, 1
        for i in range(n, 0, -1):
            res = (res + cur * f[i][k]) % mod
            cur = cur * 2 % mod
        return res

impl Solution {
    pub fn sum_of_power(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let MOD: i64 = 1_000_000_007;
        let mut f: Vec<Vec<i64>> = vec![vec![0; (k + 1) as usize]; (n + 1)];

        f[0][0] = 1;
        for x in nums {
            if x > k {
                continue;
            }
            for i in (1..= n).rev() {
                for j in (x..= k).rev() {
                    f[i][j as usize] = (f[i][j as usize] + f[i - 1][(j - x) as usize]) % MOD;
                }
            }
        }

        let mut res = 0;
        let mut cur = 1;
        for i in (1..=n).rev() {
            res = (res + cur * f[i][k as usize]) % MOD;
            cur = (cur * 2) % MOD;
        }
        res as i32
    }
}

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

关注我的博客: https://mike-box.github.io/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu

Tags: 题解力扣周赛赛

← leetcode contest 388 leetcode weekly contest 389 →

扫描二维码，分享此文章