leetcode weekly contest 399

t4 又是线段树类的题目

3162. 优质数对的总数 I

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回 优质数对 的总数。

示例 1：

输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1

输出：5

解释：

5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2：

输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3

输出：2

解释：

2个优质数对分别是 (3, 0) 和 (3, 1)。

提示：

1 <= n, m <= 50
1 <= nums1[i], nums2[j] <= 50
1 <= k <= 50

地址

https://leetcode.cn/contest/weekly-contest-399/problems/find-the-number-of-good-pairs-i/

题意

直接枚举

思路

直接枚举，检测数对是否满足题目要求。
复杂度分析：

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

代码

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        res = 0
        for x in nums1:
            for y in nums2:
                if x % (k * y) == 0:
                    res += 1
        return res

impl Solution {
    pub fn number_of_pairs(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i32 {
        let mut res = 0;
        for x in nums1.iter() {
            for y in nums2.iter() {
                if x % (k * y) == 0 {
                    res += 1;
                }
            }
        }
        return res;
    }
}

3163. 压缩字符串 III

给你一个字符串 word，请你使用以下算法进行压缩：

从空字符串
comp
开始。当
word
不为空

时，执行以下操作：
- 移除 word 的最长单字符前缀，该前缀由单一字符 c 重复多次组成，且该前缀长度最多为 9 。
- 将前缀的长度和字符 c 追加到 comp 。

返回字符串 comp 。

示例 1：

输入：word = “abcde”

输出：“1a1b1c1d1e”

解释：

初始时，comp = "" 。进行 5 次操作，每次操作分别选择 "a"、"b"、"c"、"d" 和 "e" 作为前缀。

对每个前缀，将 "1" 和对应的字符追加到 comp。

示例 2：

输入：word = “aaaaaaaaaaaaaabb”

输出：“9a5a2b”

解释：

初始时，comp = ""。进行 3 次操作，每次操作分别选择 "aaaaaaaaa"、"aaaaa" 和 "bb" 作为前缀。

对于前缀 "aaaaaaaaa"，将 "9" 和 "a" 追加到 comp。
对于前缀 "aaaaa"，将 "5" 和 "a" 追加到 comp。
对于前缀 "bb"，将 "2" 和 "b" 追加到 comp。

提示：

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

地址

https://leetcode.cn/contest/weekly-contest-399/problems/string-compression-iii/

题意

模拟

思路

每次找到字符中连续相等的字符且最长长度小于等于 $9$ ，然后压缩填入字符即可。
复杂度分析：

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

代码

class Solution:
    def compressedString(self, s: str) -> str:
        res = ""
        i , j = 0, 0
        while i < len(s):
            while j < len(s) and s[j] == s[i] and j - i + 1 <= 9:
                j += 1
            res += str(j - i)
            res += s[i]
            i = j
        return res

impl Solution {
    pub fn compressed_string(s: String) -> String {
        let mut res = String::new();
        let mut i = 0;
        let chars: Vec<char> = s.chars().collect();
        while i < chars.len() {
            let mut j = i;
            while j < chars.len() && chars[j] == chars[i] && j - i + 1 <= 9 {
                j += 1;
            }
            res.push_str(&(j - i).to_string());
            res.push(chars[i]);
            i = j;
        }
        res
    }
}

3164. 优质数对的总数 II

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回 优质数对 的总数。

示例 1：

输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1

输出：5

解释：

5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2：

输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3

输出：2

解释：

2个优质数对分别是 (3, 0) 和 (3, 1)。

提示：

1 <= n, m <= 105
1 <= nums1[i], nums2[j] <= 106
1 <= k <= 103

地址

https://leetcode.cn/contest/weekly-contest-399/problems/find-the-number-of-good-pairs-ii/

题意

哈希统计，因子分解

思路

我们统计 $nums1, nums2$ 中所有元素出现的次数，次数遍历 $nums1$ 中出现的元素 $x$，此时如下:
- 如果 $x$ 无法被 $k$ 整除，则跳过改元素；
- 如果 $x$ 可以被 $k$ 整除，枚举 $tot =\dfrac{x}{k}$ 的所有因子 $a, \dfrac{tot}{a}$ ，利用哈希表统计 $a, \dfrac{tot}{a}$ 在 $nums2$ 中出现的次数；
复杂度：

时间复杂度：$O(m + n \times \sqrt U)$，其中 $m,n$ 表示给定的数组的长度, $U$ 表示数组中的最大长度；
空间复杂度：$O(n + m)$；

代码

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        cnt1 = Counter(nums1)
        cnt2 = Counter(nums2)
        res = 0
        for key, val in cnt1.items():
            if (key % k) != 0:
                continue
            tot = key / k
            j = 1
            while j**2 <= tot:
                if tot % j == 0:
                    a, b = j, tot / j
                    if a == b:
                        res += val * cnt2[a]
                    else:
                        res += val * (cnt2[a] + cnt2[b])
                j += 1
        
        return res

use std::collections::HashMap;

impl Solution {
    pub fn number_of_pairs(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
        let mut cnt1 = HashMap::new();
        let mut cnt2 = HashMap::new();
        for &num in nums1.iter() {
            *cnt1.entry(num).or_insert(0) += 1;
        }
        for &num in nums2.iter() {
            *cnt2.entry(num).or_insert(0) += 1;
        }
        
        let mut res = 0;
        for (&key, &val) in cnt1.iter() {
            if key % k != 0 {
                continue;
            }
            let tot = key / k;
            let mut j = 1;
            while j * j <= tot {
                if tot % j == 0 {
                    let a = j;
                    let b = tot / j;
                    if a == b {
                        res += val * cnt2.get(&a).unwrap_or(&0);
                    } else {
                        res += val * (cnt2.get(&a).unwrap_or(&0) + cnt2.get(&b).unwrap_or(&0));
                    }
                }
                j += 1;
            }
        }
        
        res
    }
}

3165. 不包含相邻元素的子序列的最大和

给你一个整数数组 nums 和一个二维数组 queries，其中 queries[i] = [posi, xi]。

对于每个查询 i，首先将 nums[posi] 设置为 xi，然后计算查询 i 的答案，该答案为 nums 中 不包含相邻元素 的子序列的最大和。

返回所有查询的答案之和。

由于最终答案可能非常大，返回其对 109 + 7 取余的结果。

子序列 是指从另一个数组中删除一些或不删除元素而不改变剩余元素顺序得到的数组。

示例 1：

输入：nums = [3,5,9], queries = [[1,-2],[0,-3]]

输出：21

解释：
执行第 1 个查询后，nums = [3,-2,9]，不包含相邻元素的子序列的最大和为 3 + 9 = 12。
执行第 2 个查询后，nums = [-3,-2,9]，不包含相邻元素的子序列的最大和为 9 。

示例 2：

输入：nums = [0,-1], queries = [[0,-5]]

输出：0

解释：
执行第 1 个查询后，nums = [-5,-1]，不包含相邻元素的子序列的最大和为 0（选择空子序列）。

提示：

1 <= nums.length <= 5 * 104
-105 <= nums[i] <= 105
1 <= queries.length <= 5 * 104
queries[i] == [posi, xi]
0 <= posi <= nums.length - 1
-105 <= xi <= 105

地址

https://leetcode.cn/contest/weekly-contest-399/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/

题意

线段树，动态规划

思路

比赛的时候想到了线段树，但没有想清楚应该怎么去解决分段的问题，只想到了 lazy标记的解法，但是写起来太复杂了，还是看到关键的动态规划的写法。
- $f_{00}(A)$ 表示在 $A$ 第一个数一定不选，最后一个数也一定不选的情况下，打家劫舍的答案。
- $f_{01}(A)$ 表示在 $A$ 第一个数一定不选，最后一个数可选可不选的情况下，打家劫舍的答案。
- $f_{10}(A)$ 表示在 $A$ 第一个数可选可不选，最后一个数一定不选的情况下，打家劫舍的答案。
- $f_{11}(A)$ 表示在 $A$ 第一个数可选可不选，最后一个数也可选可不选的情况下，打家劫舍的答案。
可以得到递推公式如下：
$$
f_{00}(a) = \max(f_{01}(p) + f_{00}(q),f_{00}(p) + f_{10}(q)) \
f_{01}(a) = \max(f_{01}(p) + f_{01}(q),f_{00}(p) + f_{11}(q)) \
f_{10}(a) = \max(f_{11}(p) + f_{00}(q),f_{10}(p) + f_{10}(q)) \
f_{11}(a) = \max(f_{11}(p) + f_{01}(q),f_{10}(p) + f_{11}(q)) \
$$
得到上诉递推公式后，本身的运算就显得比较简单了。
复杂度分析：

时间复杂度：$O(n \times \log^2 U)$，其中 $n$ 表示给定查询的数组的长度， $U$ 表示给定查询中元素的最大数目；
空间复杂度：$O(1ogU)$， $U$ 表示给定查询中元素的最大数目；

代码

class Solution:
    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)
        tree = [[0] * 4 for _ in range(n * 4 + 7)]

        def pushUp(idx: int):
            a, b = tree[idx * 2], tree[idx * 2 + 1]
            tree[idx][0] = max(a[1] + b[0], a[0] + b[2])
            tree[idx][1] = max(a[0] + b[3], a[1] + b[1])
            tree[idx][2] = max(a[2] + b[2], a[3] + b[0])
            tree[idx][3] = max(a[2] + b[3], a[3] + b[1])

        def build(idx: int, l: int, r: int):
            if l == r:
                tree[idx][3] = max(nums[l], 0)
                return
            mid = (l + r) // 2
            build(idx * 2, l, mid)
            build(idx * 2 + 1, mid + 1, r)
            pushUp(idx)

        def update(idx, l, r, i, val):
            if l == r:
                tree[idx][3] = max(val, 0)
                return
            mid = (l + r) // 2
            if i <= mid:
                update(idx * 2, l, mid, i, val)
            else:
                update(idx * 2 + 1, mid + 1, r, i, val)
            pushUp(idx)

        build(1, 0, n - 1)
        ans = 0
        for i, x in queries:
            update(1, 0, n - 1, i, x) 
            ans += tree[1][3]
        return ans % 1_000_000_007

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

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

Tags: 题解力扣周赛赛

← leetcode weekly contest 396 leetcode biweekly contest 131 →

扫描二维码，分享此文章