且听疯吟

leetcode weekly contest 389

2024-03-22

leetcode weekly contest 389

周赛质量还不错， t4 是个不错的题目，前 3 题太差了。

3083. 字符串及其反转中是否存在同一子字符串

给你一个字符串 s ，请你判断字符串 s 是否存在一个长度为 2 的子字符串，在其反转后的字符串中也出现。

如果存在这样的子字符串，返回 true；如果不存在，返回 false 。

示例 1：

输入：s = “leetcode”

输出：true

解释：子字符串 "ee" 的长度为 2，它也出现在 reverse(s) == "edocteel" 中。

示例 2：

输入：s = “abcba”

输出：true

解释：所有长度为 2 的子字符串 "ab"、"bc"、"cb"、"ba" 也都出现在 reverse(s) == "abcba" 中。

示例 3：

输入：s = “abcd”

输出：false

解释：字符串 s 中不存在满足「在其反转后的字符串中也出现」且长度为 2 的子字符串。

提示：

  • 1 <= s.length <= 100
  • 字符串 s 仅由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-389/problems/existence-of-a-substring-in-a-string-and-its-reverse/

题意

模拟

思路

  1. 按照题目要求进行模拟即可，并返回结果即可
  2. 复杂度分析：
  • 时间复杂度：$O(n^3)$，其中 $n$ 表示给定字符串的长度。
  • 空间复杂度：$O(1)$。

代码

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        t = s[::-1]
        for i in range(len(s) - 1):
            for j in range(i + 2, len(s) + 1):
                ss = s[i:j]
                if ss in t:
                    return True
        return False
impl Solution {
    pub fn is_substring_present(s: String) -> bool {
        let t: String = s.chars().rev().collect();
        for i in 0..s.len() - 1 {
            for j in i + 2..=s.len() {
                let ss = &s[i..j];
                if t.contains(ss) {
                    return true;
                }
            }
        }
        false
    }
}

3084. 统计以给定字符开头和结尾的子字符串总数

给你一个字符串 s 和一个字符 c 。返回在字符串 s 中并且以 c 字符开头和结尾的非空子字符串的总数。

示例 1：

输入：s = “abada”, c = “a”

输出：6

解释：以 "a" 开头和结尾的子字符串有： "**a**bada"、"**aba**da"、"**abada**"、"ab**a**da"、"ab**ada**"、"abad**a**"。

示例 2：

输入：s = “zzz”, c = “z”

输出：6

解释：字符串 s 中总共有 6 个子字符串，并且它们都以 "z" 开头和结尾。

提示：

  • 1 <= s.length <= 105
  • s 和 c 均由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-389/problems/count-substrings-starting-and-ending-with-given-character/

题意

数学问题

思路

  1. 排列组合问题，假设有 $n$个相同的字符，此时我们从 $n$ 个字符中任意选择两个字符作为开头和结尾，还需要考虑单个字符的情况，此时一共有 $\dfrac{n \times (n + 1)}{2}$ 个。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示给定字符串的长度。
  • 空间复杂度：$O(n)$, 其中 $n$ 表示给定字符串的长度。

代码

class Solution:
    def countSubstrings(self, s: str, c: str) -> int:
        n = s.count(c)
        return n * (n + 1) // 2
impl Solution {
    pub fn count_substrings(s: String, c: char) -> i64 {
        let n = s.chars().filter(|&ch| ch == c).count() as i64;
        n * (n + 1) / 2
    }
}

3085. 成为 K 特殊字符串需要删除的最少字符数

给你一个字符串 word 和一个整数 k。

如果 |freq(word[i]) - freq(word[j])| <= k 对于字符串中所有下标 i 和 j 都成立，则认为 word 是 k 特殊字符串。

此处，freq(x) 表示字符 x 在 word 中的出现频率，而 |y| 表示 y 的绝对值。

返回使 word 成为 k 特殊字符串 需要删除的字符的最小数量。

示例 1：

输入：word = “aabcaba”, k = 0

输出：3

解释：可以删除 2 个 "a" 和 1 个 "c" 使 word 成为 0 特殊字符串。word 变为 "baba"，此时 freq('a') == freq('b') == 2。

示例 2：

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

输出：2

解释：可以删除 1 个 "a" 和 1 个 "d" 使 word 成为 2 特殊字符串。word 变为 "bdcbdcdcd"，此时 freq('b') == 2，freq('c') == 3，freq('d') == 4。

示例 3：

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

输出：1

解释：可以删除 1 个 "b" 使 word 成为 2特殊字符串。因此，word 变为 "aaaaaa"，此时每个字母的频率都是 6。

提示：

  • 1 <= word.length <= 105
  • 0 <= k <= 105
  • word 仅由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-389/problems/minimum-deletions-to-make-string-k-special/

题意

模拟 + 枚举

思路

  1. 题目所谓的频率，题目可以转换为给定数组，使得数组中任意元素的差的绝对值均小于等于 $k$，根据贪心原则可以知道所有的数的区间一定处在 $[nums[i], nums[i] +x]$ 或者 $[nums[i] - x, nums[i]]$ 这两个区间内，此时我们直接枚举，枚举区间的左侧和右侧 $nums[i]$，分别求出最小的删除数量即可。

  2. 复杂度分析：

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

代码

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        cnt = Counter(word)
        arr = list(cnt.values())
        res = inf
        for i in range(len(arr)):
            left = sum(x for x in arr if x < arr[i] - k)
            right = sum(x - arr[i] for x in arr if x > arr[i])
            res = min(res, left + right)
            left = sum(x for x in arr if x < arr[i])
            right = sum(x - arr[i] - k for x in arr if x > arr[i] + k)
            res = min(res, left + right)
        return res
use std::collections::HashMap;

impl Solution {
    pub fn minimum_deletions(word: String, k: i32) -> i32 {
        let mut cnt: HashMap<char, i32> = HashMap::new();
        for c in word.chars() {
            *cnt.entry(c).or_insert(0) += 1;
        }
        let arr: Vec<i32> = cnt.values().copied().collect();
        let mut res = i32::MAX;
        for i in 0..arr.len() {
            let left = arr.iter().filter(|&&x| x < arr[i] - k).sum::<i32>();
            let right = arr.iter().filter(|&&x| x > arr[i]).map(|&x| x - arr[i]).sum::<i32>();
            res = res.min(left + right);
            let left = arr.iter().filter(|&&x| x < arr[i]).sum::<i32>();
            let right = arr.iter().filter(|&&x| x > arr[i] + k).map(|&x| x - arr[i] - k).sum::<i32>();
            res = res.min(left + right);
        }
        res
    }
}

3086. 拾起 K 个 1 需要的最少行动次数

给你一个下标从 0 开始的二进制数组 nums，其长度为 n ；另给你一个 正整数 k 以及一个 非负整数 maxChanges 。

Alice 在玩一个游戏，游戏的目标是让 Alice 使用 最少 数量的 行动 次数从 nums 中拾起 k 个 1 。游戏开始时，Alice 可以选择数组 [0, n - 1] 范围内的任何索引index 站立。如果 nums[index] == 1 ，Alice 会拾起一个 1 ，并且 nums[index] 变成0（这 不算 作一次行动）。之后，Alice 可以执行 任意数量 的 行动（包括****零次），在每次行动中 Alice 必须 恰好 执行以下动作之一：

  • 选择任意一个下标 j != index 且满足 nums[j] == 0 ，然后将 nums[j] 设置为 1 。这个动作最多可以执行 maxChanges 次。
  • 选择任意两个相邻的下标 x 和 y（|x - y| == 1）且满足 nums[x] == 1, nums[y] == 0 ，然后交换它们的值（将 nums[y] = 1 和 nums[x] = 0）。如果 y == index，在这次行动后 Alice 拾起一个 1 ，并且 nums[y] 变成 0 。

返回 Alice 拾起 恰好 k 个 1 所需的 最少 行动次数。

示例 1：

输入：nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1

输出：3

解释：如果游戏开始时 Alice 在 index == 1 的位置上，按照以下步骤执行每个动作，他可以利用 3 次行动拾取 3 个 1 ：

  • 游戏开始时 Alice 拾取了一个 1 ，nums[1] 变成了 0。此时 nums 变为 [1,**0**,0,0,0,1,1,0,0,1] 。
  • 选择 j == 2 并执行第一种类型的动作。nums 变为 [1,**0**,1,0,0,1,1,0,0,1]
  • 选择 x == 2 和 y == 1 ，并执行第二种类型的动作。nums 变为 [1,**1**,0,0,0,1,1,0,0,1] 。由于 y == index，Alice 拾取了一个 1 ，nums 变为 [1,**0**,0,0,0,1,1,0,0,1] 。
  • 选择 x == 0 和 y == 1 ，并执行第二种类型的动作。nums 变为 [0,**1**,0,0,0,1,1,0,0,1] 。由于 y == index，Alice 拾取了一个 1 ，nums 变为 [0,**0**,0,0,0,1,1,0,0,1] 。

请注意，Alice 也可能执行其他的 3 次行动序列达成拾取 3 个 1 。

示例 2：

输入：nums = [0,0,0,0], k = 2, maxChanges = 3

输出：4

解释：如果游戏开始时 Alice 在 index == 0 的位置上，按照以下步骤执行每个动作，他可以利用 4 次行动拾取 2 个 1 ：

  • 选择 j == 1 并执行第一种类型的动作。nums 变为 [**0**,1,0,0] 。
  • 选择 x == 1 和 y == 0 ，并执行第二种类型的动作。nums 变为 [**1**,0,0,0] 。由于 y == index，Alice 拾起了一个 1 ，nums 变为 [**0**,0,0,0] 。
  • 再次选择 j == 1 并执行第一种类型的动作。nums 变为 [**0**,1,0,0] 。
  • 再次选择 x == 1 和 y == 0 ，并执行第二种类型的动作。nums 变为 [**1**,0,0,0] 。由于y == index，Alice 拾起了一个 1 ，nums 变为 [**0**,0,0,0] 。

提示：

  • 2 <= n <= 105
  • 0 <= nums[i] <= 1
  • 1 <= k <= 105
  • 0 <= maxChanges <= 105
  • maxChanges + sum(nums) >= k

地址

https://leetcode.cn/contest/weekly-contest-389/problems/minimum-moves-to-pick-k-ones/

题意

贪心 + 二分查找

思路

  1. 题目本身倒不是特别难，但是细节处理起来非常容易出错，所以比赛的时候如果要把题目全部作对其实挺不容易，我们可以分析一下以下贪心原则：
    • 首先假如选的 $index$ 有 $1$ ，此时直接拾起这个 $1$ ，需要的花费为 $0$;
    • 其次我们优先选择 $index$ 两侧的 $1$，拾起两侧的 $1$ 需要的花费为 $1$​，最多只有 $2$ 个这样的 $1$ 可以选择；
    • 再次我们可以优先选择使用第一种行动，在 $index$ 的两侧选择一个位置填入 $1$ ，然后再选择使用第二种变换拾起 $1$, 每拾起 $1$ 个 $1$ 需要的行动次数为 $2$ ；
    • 最后我们再选择其它的 $1$ 将起拾起，次数第 $i$ 个索引上的 $1$ 需要耗费的变换次数为 $|i - index|$，假设此时我们还需要拾起 $x$ ，我们直接利用二分查找找到距离 $i$ 的最小距离 $j$，使得区间 $[i-j,i-2]\cup[i+2, i + j]$ 中 $1$ 的数目大于等于 $x$ ，此时还需要处理奇偶数的关系，我们减掉一个距离 $index$，最远的 $1$​ 即可。
    • 题目不是很难，但是细节处理特别麻烦，二分查找的关键是我们要处理好各种细节问题，利用前缀和求出区间中 $1$ 的数目，以及求出需要变换的最少次数。
  2. 复杂度分析：
  • 时间复杂度：$O(n\log n)$，其中 $n$ 表示给定数组的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。

代码

class Solution:
    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:
        n = len(nums)
        res = inf
        ssum = [0] * (n + 1)
        psum = [0] * (n + 1)
        for i, x in enumerate(nums):
            ssum[i + 1] = ssum[i] + x
            psum[i + 1] = psum[i] + (i if nums[i] == 1 else 0)
        
        def check(i, j, tot):
            left = ssum[max(0, i - 1)] - ssum[max(0, i - j)]
            right = ssum[min(n, i + j + 1)] - ssum[min(i + 2, n)]
            return left + right >= tot
        
        for i in range(n):
            need, cost = k, 0
            if nums[i] == 1:
                need -= 1
                if need == 0:
                    res = min(res, cost)
                    continue
            if i > 0 and nums[i - 1] == 1:
                need -= 1
                cost += 1
                if need == 0:
                    res = min(res, cost)
                    continue
                    
            if i + 1 < n and nums[i + 1] == 1:
                need -= 1
                cost += 1
                if need == 0:
                    res = min(res, cost)
                    continue

            
            if maxChanges >= need:
                cost += need * 2
                res = min(res, cost)
                continue
            
            lo, hi = 2, n
            diff = 0
            cost += 2 * maxChanges
            need -= maxChanges
            while lo <= hi:
                mid = (lo + hi) // 2
                if check(i, mid, need):
                    hi = mid - 1
                    diff = mid
                else:
                    lo = mid + 1
            
            left = ssum[max(0, i - 1)] - ssum[max(0, i - diff)]
            right = ssum[min(n, i + diff + 1)] - ssum[min(i + 2, n)]
            left_sum = psum[max(0, i - 1)] - psum[max(0, i - diff)]
            right_sum = psum[min(n, i + diff + 1)] - psum[min(i + 2, n)]
            cost += left * i - left_sum + right_sum - right * i
            if left + right > need:
                 l = i - max(0, i - diff)
                 r = min(n - 1, i + diff) - i
                 if l >= r:
                     cost -= l
                 else:
                     cost -= r
            res = min(res, cost)     
        return res
use std::cmp::min;
use std::cmp::max;

fn check(nums: &[i32], i: usize, j: usize, tot: i32) -> bool {
    let n = nums.len();
    let left = nums[max(0, (i as i32) - 1) as usize] - nums[max(0, (i as i32) - (j as i32)) as usize];
    let right = nums[min(n - 1, i + j + 1)] - nums[min(i + 2, n - 1)];
    left + right >= tot
}

impl Solution {
    pub fn minimum_moves(nums: Vec<i32>, k: i32, max_changes: i32) -> i64 {
        let n = nums.len();
        let mut res = i64::MAX;
        let mut ssum: Vec<i32> = vec![0; n + 1];
        let mut psum: Vec<i64> = vec![0; n + 1];
        
        for i in 0..n {
            ssum[i + 1] = ssum[i] + nums[i];
            psum[i + 1] = psum[i] + if nums[i] == 1 { i as i64 } else { 0 };
        }

        for i in 0..n {
            let mut need = k as i32;
            let mut cost = 0 as i64;

            if nums[i] == 1 {
                need -= 1;
                if need == 0 {
                    res = min(res, cost);
                    continue;
                }
            }
            if i > 0 && nums[i - 1] == 1 {
                need -= 1;
                cost += 1;
                if need == 0 {
                    res = min(res, cost);
                    continue;
                }
            }

            if i + 1 < n && nums[i + 1] == 1 {
                need -= 1;
                cost += 1;
                if need == 0 {
                    res = min(res, cost);
                    continue;
                }
            }

            if max_changes >= need {
                cost += (need * 2) as i64;
                res = min(res, cost);
                continue;
            }

            let mut lo = 2;
            let mut hi = n;
            let mut diff = 0;
            cost += (2 * max_changes) as i64;
            need -= max_changes;
            while lo <= hi {
                let mid = (lo + hi) / 2;
                if check(&ssum, i, mid, need) {
                    hi = mid - 1;
                    diff = mid;
                } else {
                    lo = mid + 1;
                }
            }

            let left = ssum[max(0, (i as i32) - 1) as usize] - ssum[max(0, (i as i32) - (diff as i32)) as usize];
            let right = ssum[min(n, i + diff + 1)] - ssum[min(i + 2, n)];
            let left_sum = psum[max(0, (i as i32) - 1) as usize] - psum[max(0, (i as i32) - (diff as i32)) as usize];
            let right_sum = psum[min(n, i + diff + 1)] - psum[min(i + 2, n)];
            cost += (left as i64) * (i as i64) - left_sum + right_sum - (right as i64) * (i as i64);
            if left + right > need {
                let l = i - if i > diff { i - diff } else { 0 };
                let r = if i + diff >= n - 1 { 0 } else { i + diff } - i;
                if l >= r {
                    cost -= l as i64;
                } else {
                    cost -= r as i64;
                }
            }
            res = min(res, cost);
        }
        res
    }
}

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

Tags: 题解 力扣周赛赛
← leetcode biweekly contest 126 leetcode weekly contest 390 →

扫描二维码，分享此文章