leetcode weekly contest 390

放水的一周，开心的一周周赛。

100245. 每个字符最多出现两次的最长子字符串

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。

示例 1：

输入： s = “bcbbbcba”

输出： 4

解释：

以下子字符串长度为 4，并且每个字符最多出现两次："bcbbbcba"。

示例 2：

输入： s = “aaaa”

输出： 2

解释：

以下子字符串长度为 2，并且每个字符最多出现两次："aaaa"。

提示：

2 <= s.length <= 100
s 仅由小写英文字母组成。

地址

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

题意

滑动窗口

思路

滑动窗口统计窗口内字符出现的次数，假设存在当前字符出现的次数大于 $2$ 时，则缩小窗口。
复杂度分析：

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

代码

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        n = len(s)
        ans, j = 0, 0
        cnt = Counter()
        for i, c in enumerate(s):
            cnt [c] += 1
            while cnt[c] > 2:
                cnt[s[j]] -= 1
                j += 1
            ans = max(ans, i - j + 1)
        return ans

use std::collections::HashMap;

impl Solution {
    pub fn maximum_length_substring(s: String) -> i32 {
        let n = s.len();
        let mut ans = 0;
        let mut j = 0;
        let mut cnt: HashMap<char, usize> = HashMap::new();

        for (i, c) in s.chars().enumerate() {
            *cnt.entry(c).or_insert(0) += 1;
            while *cnt.get(&c).unwrap_or(&0) > 2 {
                if let Some(val) = cnt.get_mut(&s.chars().nth(j).unwrap()) {
                    *val -= 1;
                }
                j += 1;
            }
            ans = ans.max((i - j + 1) as i32)
        }

        ans
    }
}

100228. 执行操作使数据元素之和大于等于 K

给你一个正整数 k 。最初，你有一个数组 nums = [1] 。

你可以对数组执行以下任意操作任意次数（可能为零）：

选择数组中的任何一个元素，然后将它的值增加 1 。
复制数组中的任何一个元素，然后将它附加到数组的末尾。

返回使得最终数组元素之和大于或等于 k 所需的最少操作次数。

示例 1：

输入：k = 11

输出：5

解释：

可以对数组 nums = [1] 执行以下操作：

将元素的值增加 1 三次。结果数组为 nums = [4] 。
复制元素两次。结果数组为 nums = [4,4,4] 。

最终数组的和为 4 + 4 + 4 = 12 ，大于等于 k = 11 。
执行的总操作次数为 3 + 2 = 5 。

示例 2：

输入：k = 1

输出：0

解释：

原始数组的和已经大于等于 1 ，因此不需要执行操作。

提示：

1 <= k <= 105

地址

https://leetcode.cn/contest/weekly-contest-390/problems/apply-operations-to-make-sum-of-array-greater-than-or-equal-to-k/

题意

贪心

思路

有两种选择要么 $+1$，要么复制一个元素，根据贪心原则，我们肯定是优先 $+1$，然后复制，因为复制之后可以增加的值为 $x$，值得数组的和大于等于 $k$，最简单的办法就是我们将每个 $x$ 都尝试一遍即可。最优选择时我们先将 $x$ $+1$ 增加至 $\lceil\sqrt{k}\rceil$, 然后复制 $x$ 直到元素的和大于等于 $k$ 即可。
复杂度分析：

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

代码

class Solution:
    def minOperations(self, k: int) -> int:
        x = int(math.sqrt(k))
        if x * x == k:
            return 2 * (x - 1)
        else:
            return x + (k - 1) // (x + 1)

impl Solution {
    pub fn min_operations(k: i32) -> i32 {
        let x = (k as f64).sqrt() as i32;
        if x * x == k {
            return 2 * (x - 1);
        } else {
            return x + (k - 1) / (x + 1);
        }
    }
}

100258. 最高频率的 ID

你需要在一个集合里动态记录 ID 的出现频率。给你两个长度都为 n 的整数数组 nums 和 freq ，nums 中每一个元素表示一个 ID ，对应的 freq 中的元素表示这个 ID 在集合中此次操作后需要增加或者减少的数目。

增加 ID 的数目：如果 freq[i] 是正数，那么 freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会添加到集合中。
减少 ID 的数目：如果 freq[i] 是负数，那么 -freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会从集合中删除。

请你返回一个长度为 n 的数组 ans ，其中 ans[i] 表示第 i 步操作后出现频率最高的 ID 数目，如果在某次操作后集合为空，那么 ans[i] 为 0 。

示例 1：

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

输出：[3,3,2,2]

解释：

第 0 步操作后，有 3 个 ID 为 2 的元素，所以 ans[0] = 3 。
第 1 步操作后，有 3 个 ID 为 2 的元素和 2 个 ID 为 3 的元素，所以 ans[1] = 3 。
第 2 步操作后，有 2 个 ID 为 3 的元素，所以 ans[2] = 2 。
第 3 步操作后，有 2 个 ID 为 3 的元素和 1 个 ID 为 1 的元素，所以 ans[3] = 2 。

示例 2：

输入：nums = [5,5,3], freq = [2,-2,1]

输出：[2,0,1]

解释：

第 0 步操作后，有 2 个 ID 为 5 的元素，所以 ans[0] = 2 。
第 1 步操作后，集合中没有任何元素，所以 ans[1] = 0 。
第 2 步操作后，有 1 个 ID 为 3 的元素，所以 ans[2] = 1 。

提示：

1 <= nums.length == freq.length <= 105
1 <= nums[i] <= 105
-105 <= freq[i] <= 105
freq[i] != 0
输入保证任何操作后，集合中的元素出现次数不会为负数。

提示：

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

地址

https://leetcode.cn/contest/weekly-contest-390/problems/most-frequent-ids/

题意

红黑树，动态更新

思路

本题目为力扣的经典的模版题目了，利用 treeset 记录当前频数，已经出现很多次了，假设当前的 id 出现的频率为 $\textit{freq}[idx]$，此时需要更新 $id$ 的频数为 $x$ 时，此时可以进行如下操作：
- 从 $treeset$ 中删除 $\textit{freq}[idx]$;
- 更新 $\textit{freq}[idx] = \textit{freq}[idx] + x$；
- 在 treeset 中插入新的元素 $\textit{freq}[idx] + x$;
复杂度分析：

时间复杂度：$O(n \times \log n)$, $n$ 表示给定数组的长度；
空间复杂度：$O(n)$,, $n$ 表示给定数组的长度；

代码

from sortedcontainers import SortedList

class Solution:
    def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:
        cnt = Counter()
        arr = SortedList([0])
        ans = [] 
        for idx, x in zip(nums, freq): 
            old = cnt[idx]
            cnt[idx] += x
            new = cnt[idx] 
            if old > 0:
                arr.remove(old)
            arr.add(new)
            ans.append(arr[-1]) 
            
        return ans

100268. 最长公共后缀查询

给你两个字符串数组 wordsContainer 和 wordsQuery 。

对于每个 wordsQuery[i] ，你需要从 wordsContainer 中找到一个与 wordsQuery[i] 有 最长公共后缀 的字符串。如果 wordsContainer 中有两个或者更多字符串有最长公共后缀，那么答案为长度最短的。如果有超过两个字符串有相同最短长度，那么答案为它们在 wordsContainer 中出现更早的一个。

请你返回一个整数数组 ans ，其中 ans[i]是 wordsContainer中与 wordsQuery[i] 有 最长公共后缀 字符串的下标。

示例 1：

输入：wordsContainer = [“abcd”,”bcd”,”xbcd”], wordsQuery = [“cd”,”bcd”,”xyz”]

输出：[1,1,1]

解释：

我们分别来看每一个 wordsQuery[i] ：

对于 wordsQuery[0] = "cd" ，wordsContainer 中有最长公共后缀 "cd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
对于 wordsQuery[1] = "bcd" ，wordsContainer 中有最长公共后缀 "bcd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
对于 wordsQuery[2] = "xyz" ，wordsContainer 中没有字符串跟它有公共后缀，所以最长公共后缀为 "" ，下标为 0 ，1 和 2 的字符串都得到这一公共后缀。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。

示例 2：

输入：wordsContainer = [“abcdefgh”,”poiuygh”,”ghghgh”], wordsQuery = [“gh”,”acbfgh”,”acbfegh”]

输出：[2,0,2]

解释：

我们分别来看每一个 wordsQuery[i] ：

对于 wordsQuery[0] = "gh" ，wordsContainer 中有最长公共后缀 "gh" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。
对于 wordsQuery[1] = "acbfgh" ，只有下标为 0 的字符串有最长公共后缀 "fgh" 。所以尽管下标为 2 的字符串是最短的字符串，但答案是 0 。
对于 wordsQuery[2] = "acbfegh" ，wordsContainer 中有最长公共后缀 "gh" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。

提示：

1 <= wordsContainer.length, wordsQuery.length <= 104
1 <= wordsContainer[i].length <= 5 * 103
1 <= wordsQuery[i].length <= 5 * 103
wordsContainer[i] 只包含小写英文字母。
wordsQuery[i] 只包含小写英文字母。
wordsContainer[i].length 的和至多为 5 * 105 。
wordsQuery[i].length 的和至多为 5 * 105 。

地址

https://leetcode.cn/contest/weekly-contest-390/problems/longest-common-suffix-queries/

题意

字典树

思路

当然题目本身为字典树模版题目，基本上拿到题目就有思路，不过题目要求的重点是找到最长后缀中字符串长度最短且出现位置最靠的字符串，此时我们可以在字典树中存储每个当前匹配的后缀出现的最短且最靠前的字符串的 $id$ 即可，此时我们每次查询时，直接从 trie 中的节点中找到最长后缀的 id 返回即可，题目本省比较模版，不再细谈。
复杂度分析：

时间复杂度：$O(n + m)$，其中 $n$ 表示给字符串中所有字符的总数，$m$ 表示给定查询的字符串中所有字符的总数。
空间复杂度：$O(n)$，其中 $n$ 表示给字符串中所有字符的总数。

代码

class TrieNode:
    def __init__(self):
        self.idx = -1
        self.next = [None] * 26

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word, index, words):
        node = self.root
        if node.idx == -1 or len(word) < len(words[node.idx]):
            node.idx = index
        for c in word:
            if node.next[ord(c) - ord('a')] is None:
                node.next[ord(c) - ord('a')] = TrieNode()
            node = node.next[ord(c) - ord('a')]
            if node.idx == -1 or len(word) < len(words[node.idx]):
                node.idx = index
    
    def query(self, word):
        node = self.root
        ans = node.idx
        for c in word:
            if node.next[ord(c) - ord('a')] is not None:
                node = node.next[ord(c) - ord('a')]
                ans = node.idx
            else:
                break
        return ans
        
class Solution:
    def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
        trie = Trie()
        ans = []
        for i, word in enumerate(wordsContainer):
            trie.insert(word[::-1], i, wordsContainer)
        for i, word in enumerate(wordsQuery):         
            ans.append(trie.query(word[::-1])) 
        return ans

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

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

Tags: 题解力扣周赛赛

← leetcode weekly contest 389 leetcode biweekly contest 127 →

扫描二维码，分享此文章