官方网站建立,wordpress 添加模板,wordpress自定义钩子,电商网站开发实训心得Leetcode 第 387 场周赛题解 Leetcode 第 387 场周赛题解题目1#xff1a;3069. 将元素分配到两个数组中 I思路代码复杂度分析 题目2#xff1a;3070. 元素和小于等于 k 的子矩阵的数目思路代码复杂度分析 题目3#xff1a;3071. 在矩阵上写出字母 Y 所需的最少操作次数思路… Leetcode 第 387 场周赛题解 Leetcode 第 387 场周赛题解题目13069. 将元素分配到两个数组中 I思路代码复杂度分析 题目23070. 元素和小于等于 k 的子矩阵的数目思路代码复杂度分析 题目33071. 在矩阵上写出字母 Y 所需的最少操作次数思路代码复杂度分析 题目43072. 将元素分配到两个数组中 II思路代码复杂度分析 Leetcode 第 387 场周赛题解
题目13069. 将元素分配到两个数组中 I
思路
简单地按题意模拟。
代码
/** lc appleetcode.cn id3069 langcpp** [3069] 将元素分配到两个数组中 I*/// lc codestart
class Solution
{
public:vectorint resultArray(vectorint nums){vectorint arr1, arr2;arr1.push_back(nums[0]);arr2.push_back(nums[1]);for (int i 2; i nums.size(); i){if (arr1.back() arr2.back())arr1.push_back(nums[i]);elsearr2.push_back(nums[i]);}vectorint result(arr1.begin(), arr1.end());for (int x : arr2)result.push_back(x);return result;}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 是数组 nums 的元素个数。
空间复杂度O(n)其中 n 是数组 nums 的元素个数。
题目23070. 元素和小于等于 k 的子矩阵的数目
思路
二维前缀和的模板题。
代码
/** lc appleetcode.cn id3070 langcpp** [3070] 元素和小于等于 k 的子矩阵的数目*/// lc codestart// 二维前缀和class Solution
{
public:int countSubmatrices(vectorvectorint grid, int k){if (grid.empty())return 0;if (grid[0][0] k)return 0;int m grid.size(), n m ? grid[0].size() : 0;// sum[i 1][j 1] 表示以 grid[0][0] 为左上角// 以 grid[i][j] 为右下角的子矩阵的元素和 vectorvectorint sum(m 1, vectorint(n 1, 0));int count 0;for (int i 0; i m; i)for (int j 0; j n; j){sum[i 1][j 1] sum[i 1][j] sum[i][j 1] - sum[i][j] grid[i][j];if (sum[i 1][j 1] k)count;}return count;}
};
// lc codeend复杂度分析
时间复杂度O(mn)其中 m 和 n 分别为二维数组 grid 的行数和列数。
空间复杂度O(mn)其中 m 和 n 分别为二维数组 grid 的行数和列数。
题目33071. 在矩阵上写出字母 Y 所需的最少操作次数
思路
统计 Y 中的元素出现次数记到一个长为 3 的数组 cnt1 中。统计不在 Y 中的元素出现次数记到一个长为 3 的数组 cnt2 中。
计算最多可以保留多少个元素不变设这个值为 maxNotChange。
在 0,1,2 中枚举 i 和 j其中 i≠j。让 Y 中的元素都变成 i不在 Y 中的元素都变成 j那么 maxNotChange 就是 cnt1[i]cnt2[j] 的最大值。
最后返回 n2−maxNotChange即最少要修改的元素个数。
代码
/** lc appleetcode.cn id3071 langcpp** [3071] 在矩阵上写出字母 Y 所需的最少操作次数*/// lc codestart
class Solution
{
public:int minimumOperationsToWriteY(vectorvectorint grid){int n grid.size(); // n 为奇数vectorint cnt1(3, 0); // 字母 Y 单元格各数字的出现次数vectorint cnt2(3, 0); // 非字母 Y 单元格各数字的出现次数auto isY [](int i, int j) - bool{if (i 0 || i n || j 0 || j n)return false;if (i j i n / 2)return true;if (i j n - 1 i n / 2)return true;if (i n / 2 j n / 2)return true;return false;};for (int i 0; i n; i)for (int j 0; j n; j){int x grid[i][j];if (isY(i, j))cnt1[x];elsecnt2[x];}int max_not_change 0;for (int i 0; i 3; i)for (int j 0; j 3; j)if (i ! j)max_not_change max(max_not_change, cnt1[i] cnt2[j]);return n * n - max_not_change;}
};
// lc codeend复杂度分析
时间复杂度O(n2k2)其中 n 为 grid 的长度k3。
空间复杂度O(k)其中 k3。
题目43072. 将元素分配到两个数组中 II
思路
题解离散化 树状数组附练习题Python/Java/C/Go 代码
/** lc appleetcode.cn id3072 langcpp** [3072] 将元素分配到两个数组中 II*/// lc codestart
class Fenwick
{vectorint tree;public:Fenwick(int n) : tree(n) {}// 把下标为 i 的元素增加 1void add(int i){while (i tree.size()){tree[i];i i -i;}}// 返回下标在 [1,i] 的元素之和int pre(int i){int res 0;while (i 0){res tree[i];i i - 1;}return res;}
};class Solution
{
public:vectorint resultArray(vectorint nums){auto sorted nums;ranges::sort(sorted);sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());int m sorted.size();vectorint a{nums[0]}, b{nums[1]};Fenwick t1(m 1), t2(m 1);t1.add(ranges::lower_bound(sorted, nums[0]) - sorted.begin() 1);t2.add(ranges::lower_bound(sorted, nums[1]) - sorted.begin() 1);for (int i 2; i nums.size(); i){int x nums[i];int v ranges::lower_bound(sorted, x) - sorted.begin() 1;int gc1 a.size() - t1.pre(v); // greaterCount(a, v)int gc2 b.size() - t2.pre(v); // greaterCount(b, v)if (gc1 gc2 || gc1 gc2 a.size() b.size()){a.push_back(x);t1.add(v);}else{b.push_back(x);t2.add(v);}}a.insert(a.end(), b.begin(), b.end());return a;}
};
// lc codeend复杂度分析
时间复杂度O(nlogn)其中 n 为数组 nums 的长度。
空间复杂度O(n)其中 n 为数组 nums 的长度。
