力扣第387场周赛

前言

竞赛地址，感兴趣的可以进行虚拟vp：https://leetcode.cn/contest/weekly-contest-387/ranking/
在这里查看其他其他人的代码进行code review或者学习：https://leetcode.cn/contest/weekly-contest-387/ranking/

感觉还挺难的，Go语言的都是摘抄的灵茶佬的，我自己写的都是C++的。

将元素分配到两个数组中 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中的所有元素都互不相同。

• cpp

• go

#include <vector>
#include <iostream>

class Solution {
public:
    std::vector<int> resultArray(std::vector<int>& nums) {
        // 创建两个数组 arr1 和 arr2
        std::vector<int> arr1, arr2;
        
        // 检查数组是否为空
        if (nums.empty()) return {};
        
        // 第一次操作
        arr1.push_back(nums[0]);
        
        // 如果只有一个元素，直接返回 arr1
        if (nums.size() == 1) return arr1;
        
        // 第二次操作
        arr2.push_back(nums[1]);
        
        // 从第三个元素开始
        for (size_t i = 2; i < nums.size(); ++i) {
            // 最后一个元素比较
            if (!arr1.empty() && !arr2.empty() && arr1.back() > arr2.back()) {
                arr1.push_back(nums[i]);
            } else {
                arr2.push_back(nums[i]);
            }
        }
        
        // 合并 arr1 和 arr2
        std::vector<int> result;
        result.insert(result.end(), arr1.begin(), arr1.end());
        result.insert(result.end(), arr2.begin(), arr2.end());
        return result;
    }
};

int main() {
    // 实例化Solution类
    Solution solution;
    // 创建并初始化nums数组
    std::vector<int> nums = {5, 4, 3, 8};
    // 调用函数并接收结果
    std::vector<int> result = solution.resultArray(nums);
    // 打印结果
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

func resultArray(a []int) (ans []int) {
  p := []int{a[0]}
  q := []int{a[1]}
  for i := 2; i < len(a); i++ {
    v := a[i]
    if p[len(p)-1] > q[len(q)-1] {
      p = append(p, v)
    } else {
      q = append(q, v)
    }
  }
  p = append(p, q...)
  return p
}

这段代码定义了一个名为 Solution 的类，并在该类中实现了一个名为 resultArray 的公有成员函数。该函数接受一个整数数组 nums 并返回最终的结果数组 result。程序的主要逻辑分为以下几步：

1. 创建两个空的数组 arr1 和 arr2 来分别保存两个结果数组。
2. 将 nums 的第一个元素添加到 arr1。
3. 如果 nums 只有一个元素，则直接返回 arr1。
4. 将 nums 的第二个元素添加到 arr2。
5. 从第三个元素开始迭代 nums，根据题目描述的条件将每个元素添加到 arr1 或 arr2。
6. 最后，将 arr1 和 arr2 合并到一个数组 result 中并返回。

在 main 函数中，我们创建了一个 Solution 类的实例，并调用 resultArray 函数来处理示例数组，最后打印出结果数组。

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

本文由 简悦 SimpRead 转码， 原文地址 leetcode.cn

3070. 元素和小于等于 k 的子矩阵的数目 - 给你一个下标从 0 开始的整数矩阵 grid 和一个整数 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

#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size(), count = 0;
        // Prefix Sum
        vector<vector<int>> prefix(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int sum = grid[i][j];
                if (i > 0) sum += prefix[i - 1][j];
                if (j > 0) sum += prefix[i][j - 1];
                if (i > 0 && j > 0) sum -= prefix[i - 1][j - 1];
                prefix[i][j] = sum;
                if (sum <= k) ++count;  // Count single cell
            }
        }

        // Check all possible submatrices
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int p = i; p < m; ++p) {
                    for (int q = j; q < n; ++q) {
                        int submatrix_sum = prefix[p][q];
                        if (i > 0) submatrix_sum -= prefix[i - 1][q];
                        if (j > 0) submatrix_sum -= prefix[p][j - 1];
                        if (i > 0 && j > 0) submatrix_sum += prefix[i - 1][j - 1];
                        if (submatrix_sum <= k) ++count;
                    }
                }
            }
        }

        // Deduct the single cells which are counted in the first time
        return count - m * n;
    }
};

int main() {
    Solution s;
    vector<vector<int>> grid = {{7,2,9},{1,5,0},{2,6,6}};
    int k = 20;
    cout << "The number of submatrices is: " << s.countSubmatrices(grid, k) << endl;
    return 0;
}

在这段代码中，首先计算了每个位置到左上角(0,0)位置的子矩阵元素和（前缀和），这样我们可以用O(1)的时间计算任意子矩阵的元素和。接着，对每个可能的子矩阵位置组合进行遍历计算，并累加出满足条件的子矩阵数量。注意，为了避免对单个元素的重复计数，在最终返回的结果中需要减去矩阵中单元格的数量。