【LeetCode周赛】第 387 场周赛

本文主要是介绍【LeetCode周赛】第 387 场周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

100243. 将元素分配到两个数组中 I 简单

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

分析：
根据题意模拟即可！

代码：

class Solution {
public:vector<int> resultArray(vector<int>& nums) {vector<int> r1, r2, ans;r1.push_back(nums[0]),r2.push_back(nums[1]);int n=nums.size();for(int i=2;i<n;i++){int rr1 = r1[r1.size()-1], rr2 = r2[r2.size()-1];if(rr1>rr2) r1.push_back(nums[i]);else r2.push_back(nums[i]);}for(int i=0;i<r1.size();i++) ans.push_back(r1[i]);for(int i=0;i<r2.size();i++) ans.push_back(r2[i]);return ans;}
};

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

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

分析：
二维前缀和，子矩阵必须包含原矩阵的最左上角的数，因此直接枚举所有矩阵的前缀和即可！

代码：

class Solution {
public:int countSubmatrices(vector<vector<int>>& grid, int k) {if(grid[0][0]>k) return 0;int n=grid.size(),m=grid[0].size(),ans=0;vector<vector<int>> ma(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(j==0) ma[i][j]=grid[i][j];else  ma[i][j]=grid[i][j]+ma[i][j-1];}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(i!=0) ma[i][j]+=ma[i-1][j];}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(ma[i][j]<=k) ans++;}}return ans;}
};

更为精简的写法：

class Solution {
public:int countSubmatrices(vector<vector<int>>& grid, int k) {if(grid[0][0]>k) return 0;int n=grid.size(),m=grid[0].size(),ans=0;vector<vector<int>> ma(n+1,vector<int>(m+1,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){ma[i+1][j+1] = ma[i+1][j] + ma[i][j+1] -ma[i][j] + grid[i][j];ans+= ma[i+1][j+1]<=k;}}return ans;}
};

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

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

分析：
记录 属于Y，不属于Y 的0、1、2的个数，再枚举各种可能，计算最小的操作数。

代码：

class Solution {
public:int minimumOperationsToWriteY(vector<vector<int>>& grid) {int n=grid.size(),m=n/2;vector<int> y(3,0),o(3,0);for(int i=0;i<n;i++){for(int j=0;j<n;j++){if((i==j&&i<=m)||(i+j==n-1&&i<=m)||(j==m&&i>m)){y[grid[i][j]]++;}else{o[grid[i][j]]++;}}}int yy=y[0]+y[1]+y[2],oo=o[0]+o[1]+o[2],ans=n*n;for(int i=0;i<3;i++){for(int j=0;j<3;j++){if(i==j) continue;ans=min(ans,yy-y[i]+oo-o[j]);}}return ans;}
};

100246. 将元素分配到两个数组中 II 困难

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

分析：
我的方法（错误）：

对于 arr1，再创建一个数组t1用于维持arr1中的数组有序，arr2同理。
nums[i]需要插入时，使用二分查找分别计算 arr1 和arr2中大于它的值的数量，同时计算插入t1或者t2的对应位置。

但是 vector.insert()的时间复杂度是 O(n)，因此总体时间复杂度变为了O(n^2)，会超时，但是提交之后也能过，但不是最优解。

离散化+树状数组：
题解

代码：
我的代码（错误）：

class Solution {
public:vector<int> resultArray(vector<int>& nums) {vector<int> r1,rr1,r2,rr2,ans;r1.push_back(nums[0]);r2.push_back(nums[1]);rr1.push_back(nums[0]);rr2.push_back(nums[1]);int n=nums.size();for(int i=2;i<n;i++){int l1=r1.size(), l2=r2.size();int i1=upper_bound(r1.begin(),r1.end(),nums[i]) - r1.begin(), i2=upper_bound(r2.begin(),r2.end(),nums[i]) - r2.begin();if(l1-i1>l2-i2){r1.insert(r1.begin()+i1,nums[i]);rr1.push_back(nums[i]);}else if(l1-i1<l2-i2){r2.insert(r2.begin()+i2,nums[i]);rr2.push_back(nums[i]);}else{if(l1<=l2){r1.insert(r1.begin()+i1,nums[i]);rr1.push_back(nums[i]);}else if(l1>l2){r2.insert(r2.begin()+i2,nums[i]);rr2.push_back(nums[i]);}}}rr1.insert(rr1.end(),rr2.begin(),rr2.end());return rr1;}
};

离散化+树状数组：

class TreeVector{
private:vector<int> tree;
public:TreeVector(int n): tree(n){}void add(int v){int i = v;while(i<tree.size()){tree[i]+=1;i += (i & -i);}}int pre(int v){int res = 0;while(v>0){res+=tree[v];v &= v-1;}return res;}
};class Solution {
public:vector<int> resultArray(vector<int>& nums) {auto sorted = nums;ranges::sort(sorted);sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());int m=sorted.size(),n=nums.size();TreeVector t1(m+1), t2(m+1);vector<int> r1{nums[0]},r2{nums[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<n;i++){int x=nums[i];int v = ranges::lower_bound(sorted, x) - sorted.begin() + 1;int c1 = r1.size() - t1.pre(v), c2 = r2.size() - t2.pre(v);if(c1 > c2 || c1 == c2 && r1.size()<=r2.size()){r1.push_back(nums[i]);t1.add(v);}else{r2.push_back(nums[i]);t2.add(v);}}r1.insert(r1.end(), r2.begin(), r2.end());return r1;}
};