leetcode contest 387

大放水的周赛，从本次周赛以后，题解代码准备用 python 和 rust 来写题解代码，希望把 rust 的语法能够快速掌握，用 python 的 sortedlist ，t4 就是一个简单题目了。

3069. 将元素分配到两个数组中 I

给你一个下标从 1 开始、包含 不同 整数的数组 nums ，数组长度为 n 。

你需要通过 n 次操作，将 nums 中的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：

• 如果 arr1 的最后一个元素 大于 arr2 的最后一个元素，就将 nums[i] 追加到 arr1 。否则，将 nums[i] 追加到 arr2 。

通过连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。

返回数组 result 。

示例 1：

输入：nums = [2,1,3]
输出：[2,3,1]
解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。
在第 3 次操作中，由于 arr1 的最后一个元素大于 arr2 的最后一个元素（2 > 1），将 nums[3] 追加到 arr1 。
3 次操作后，arr1 = [2,3] ，arr2 = [1] 。
因此，连接形成的数组 result 是 [2,3,1] 。

示例 2：

输入：nums = [5,4,3,8]
输出：[5,3,4,8]
解释：在前两次操作后，arr1 = [5] ，arr2 = [4] 。
在第 3 次操作中，由于 arr1 的最后一个元素大于 arr2 的最后一个元素（5 > 4），将 nums[3] 追加到 arr1 ，因此 arr1 变为 [5,3] 。
在第 4 次操作中，由于 arr2 的最后一个元素大于 arr1 的最后一个元素（4 > 3），将 nums[4] 追加到 arr2 ，因此 arr2 变为 [4,8] 。
4 次操作后，arr1 = [5,3] ，arr2 = [4,8] 。
因此，连接形成的数组 result 是 [5,3,4,8] 。

提示：

• 3 <= n <= 50
• 1 <= nums[i] <= 100
• nums中的所有元素都互不相同。

地址

https://leetcode.cn/contest/weekly-contest-387/problems/distribute-elements-into-two-arrays-i/

题意

直接模拟

思路

1. 根据题意直接模拟出两个数组，并将两个数组进行拼接即可。
2. 复杂度分析：

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

代码

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        arr1, arr2 = [nums[0]], [nums[1]]
        for i in range(2, len(nums)):
            if arr1[-1] > arr2[-1]:
                arr1.append(nums[i])
            else:
                arr2.append(nums[i])
        return arr1 + arr2

impl Solution {
    pub fn result_array(nums: Vec<i32>) -> Vec<i32> {
        let mut arr1 = vec![nums[0]];
        let mut arr2 = vec![nums[1]];
        
        for i in 2..nums.len() {
            if *arr1.last().unwrap() > *arr2.last().unwrap() {
                arr1.push(nums[i]);
            } else {
                arr2.push(nums[i]);
            }
        }
        arr1.append(&mut arr2);
        arr1
    }
}

3070. 元素和小于等于 k 的子矩阵的数目

给你一个下标从 0 开始的整数矩阵 grid 和一个整数 k。

返回包含 grid 左上角元素、元素和小于或等于 k 的 子矩阵 的数目。

示例 1：

输入：grid = [[7,6,3],[6,6,1]], k = 18
输出：4
解释：如上图所示，只有 4 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 18 。

示例 2：

输入：grid = [[7,2,9],[1,5,0],[2,6,6]], k = 20
输出：6
解释：如上图所示，只有 6 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 20 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= n, m <= 1000
• 0 <= grid[i][j] <= 1000
• 1 <= k <= 109

地址

https://leetcode.cn/contest/weekly-contest-386/problems/find-the-largest-area-of-square-inside-two-rectangles/

题意

动态规划，枚举

思路

1. 我们枚举每个以 $(0,0)$ 的左上顶点的矩阵，并计算矩阵中元素的和，统计元素和小于等于 $k$ 的矩形数目即可，此时我们可以利用动态规划快速计算出每个矩形的元素和。
2. 复杂度分析：

• 时间复杂度：$O(mn)$，其中 $mn$ 分别为矩形的行数与列数。
• 空间复杂度：$O(mn)$, 其中 $mn$ 分别为矩形的行数与列数。

代码

class Solution:
    def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        psum = [[0] * (n + 1) for _ in range(m + 1)]
        res = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + grid[i - 1][j - 1]
                if psum[i][j] <= k:
                    res += 1
        return res
    
    

impl Solution {
    pub fn count_submatrices(grid: Vec<Vec<i32>>, k: i32) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut psum = vec![vec![0; n + 1]; m + 1];
        let mut res = 0;
        for i in 1..= m {
            for j in 1..= n {
                psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + grid[i - 1][j - 1];
                if psum[i][j] <= k {
                    res += 1;
                }
            }
        }
        res
    }
}

3071. 在矩阵上写出字母 Y 所需的最少操作次数

给你一个下标从 0 开始、大小为 n x n 的矩阵 grid ，其中 n 为奇数，且 grid[r][c] 的值为 0 、1 或 2 。

如果一个单元格属于以下三条线中的任一一条，我们就认为它是字母 Y 的一部分：

• 从左上角单元格开始到矩阵中心单元格结束的对角线。
• 从右上角单元格开始到矩阵中心单元格结束的对角线。
• 从中心单元格开始到矩阵底部边界结束的垂直线。

当且仅当满足以下全部条件时，可以判定矩阵上写有字母 Y ：

• 属于 Y 的所有单元格的值相等。
• 不属于 Y 的所有单元格的值相等。
• 属于 Y 的单元格的值与不属于Y的单元格的值不同。

每次操作你可以将任意单元格的值改变为 0 、1 或 2 。返回在矩阵上写出字母 Y 所需的 最少 操作次数。

示例 1：

输入：grid = [[1,2,2],[1,1,0],[0,1,0]]
输出：3
解释：将在矩阵上写出字母 Y 需要执行的操作用蓝色高亮显示。操作后，所有属于 Y 的单元格（加粗显示）的值都为 1 ，而不属于 Y 的单元格的值都为 0 。
可以证明，写出 Y 至少需要进行 3 次操作。

示例 2：

输入：grid = [[0,1,0,1,0],[2,1,0,1,2],[2,2,2,0,1],[2,2,2,2,2],[2,1,2,2,2]]
输出：12
解释：将在矩阵上写出字母 Y 需要执行的操作用蓝色高亮显示。操作后，所有属于 Y 的单元格（加粗显示）的值都为 0 ，而不属于 Y 的单元格的值都为 2 。
可以证明，写出 Y 至少需要进行 12 次操作。

提示：

• 3 <= n <= 49
• n == grid.length == grid[i].length
• 0 <= grid[i][j] <= 2
• n 为奇数。

地址

https://leetcode.cn/contest/weekly-contest-387/problems/count-submatrices-with-top-left-element-and-sum-less-than-k/

题意

模拟

思路

1. 题目出的非常无聊，且没有任何技巧可言，算是质量较差的第三题了，首先我们需要统计出现在 $y$ 中的元素以及不出现在 $Y$ 中的元素，此时我们可以进行，如果一个元素 $grid[x][y]$ 出现在 $y$ 中则需要满足:

   • 出现在 $Y$ 的上半部分，此时 $(x,y)$ 满足：$(x = y) \or (x = n - 1 - y), x \le \dfrac{n}{2}$;
   • 出现在 $Y$ 的下半部分，此时 $(x,y)$ 满足：$y = \dfrac{n}{2}, x > \dfrac{n}{2}$；

   满足上述要求即可，分别统计 $Y$ 中出现 $(0,1,2)$ 的次数，同时统计不在 $Y$ 中时 ， $(0,1,2)$ 出现的次数，此时我们进行变换的最少此时即可；

2. 复杂度分析：

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

代码

class Solution:
    def minimumOperationsToWriteY(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = n // 2
        cnt1, cnt2 = [0] * 3, [0] * 3
        
        for i in range(n):
            for j in range(n):
                v = grid[i][j]
                if i < m:
                    if i == j or i == (n - 1 - j):
                        cnt1[v] += 1
                    else:
                        cnt2[v] += 1
                else:
                    if j == m:
                        cnt1[v] += 1
                    else:
                        cnt2[v] += 1
        
        res = n**2
        for i in range(3):
            for j in range(3):
                if i == j:
                    continue
                res = min(res, n**2 - cnt1[i] - cnt2[j])
                
        return res

use std::cmp;

impl Solution {
    pub fn minimum_operations_to_write_y(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let m = n / 2;
        let mut cnt1 = vec![0; 3];
        let mut cnt2 = vec![0; 3];
        
        for i in 0..= n - 1 {
            for j in 0..= n - 1 {
                let v = grid[i][j] as usize;
                if i < m {
                    if i == j || i == n - 1 - j {
                        cnt1[v] += 1;
                    } else {
                        cnt2[v] += 1;
                    }
                } else {
                    if j == m {
                        cnt1[v] += 1;
                    } else {
                        cnt2[v] += 1;
                    }
                }
            }
        }
        
        let mut res = n * n;
        for i in 0..= 2 {
            for j in 0..= 2 {
                if i == j {
                    continue;
                }
                res = cmp::min(res, n * n - cnt1[i] - cnt2[j]);
            }
        }
        res as i32
    }
}

3072. 将元素分配到两个数组中 II

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

现定义函数 greaterCount ，使得 greaterCount(arr, val) 返回数组 arr 中 严格大于 val 的元素数量。

你需要使用 n 次操作，将 nums 的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：

• 如果 greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr1 。
• 如果 greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr2 。
• 如果 greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ，将 nums[i] 追加到元素数量较少的数组中。
• 如果仍然相等，那么将 nums[i] 追加到 arr1 。

连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。

返回整数数组 result 。

示例 1：

输入：nums = [2,1,3,3]
输出：[2,3,1,3]
解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是零，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，两个数组中大于 3 的元素数量都是零，但 arr2 的长度较小，因此，将 nums[4] 追加到 arr2 。
在 4 次操作后，arr1 = [2,3] ，arr2 = [1,3] 。
因此，连接形成的数组 result 是 [2,3,1,3] 。

示例 2：

输入：nums = [5,14,3,1,2]
输出：[5,3,1,2,14]
解释：在前两次操作后，arr1 = [5] ，arr2 = [14] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是一，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，arr1 中大于 1 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[4] 追加到 arr1 。
在第 5 次操作中，arr1 中大于 2 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[5] 追加到 arr1 。
在 5 次操作后，arr1 = [5,3,1,2] ，arr2 = [14] 。
因此，连接形成的数组 result 是 [5,3,1,2,14] 。

示例 3：

输入：nums = [3,3,3,3]
输出：[3,3,3,3]
解释：在 4 次操作后，arr1 = [3,3] ，arr2 = [3,3] 。
因此，连接形成的数组 result 是 [3,3,3,3] 。

提示：

• 3 <= n <= 105
• 1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-387/problems/distribute-elements-into-two-arrays-ii/

题意

离散化 + 线段树

思路

1. 当然最直接的模版肯定是线段树即可，可以将数组中的元素进行离散化处理，然后用数组处理即可。最简单直接的办法是我们可以用 python 的 sortedlist 非常简单实现即可。每次处理如下：

• 我们分别在 $arr1$ 与 $arr2$ 中查找当前大于 $nums[i]$ 的元素数目，此时可以用 $bisect_right$ 直接查找即可；
• 按照要求进行添加到 $arr1$ 与 $arr2$ 中即可，由于有 $sortedlist$ 会导致数组顺序错乱，我们可以单独用一个 $list$ 保存中间结果，最后将两个 list 进行拼接即可；

2. 复杂度分析：

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

代码

from sortedcontainers import SortedList

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        arr1 = SortedList([nums[0]])
        arr2 = SortedList([nums[1]])
        res1, res2 = [nums[0]], [nums[1]]
        for i in range(2, len(nums)):
            x = len(arr1) - arr1.bisect_right(nums[i])
            y = len(arr2) - arr2.bisect_right(nums[i])
            if x > y:
                arr1.add(nums[i])
                res1.append(nums[i])
            elif x < y:
                arr2.add(nums[i])
                res2.append(nums[i])
            else:
                if len(arr1) > len(arr2):
                    arr2.add(nums[i])
                    res2.append(nums[i])
                else:
                    arr1.add(nums[i])
                    res1.append(nums[i])
        return res1 + res2

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

• 关注我的博客: https://mike-box.github.io/

• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu