周赛总结

本场周赛总结,重回三题水平,名次500+,(终于不用掉分了),本次周赛除了第四题不在能力范围之内,剩下题都挺有意思,主要记录一下第二题和第三题。

第二题

1726.同积元组

这个题,让我最先想到的是,四数之和这个题,然后比赛的时候,先暴力,然后改用C++枚举两个再双指针,一直TLE,最后转换思路,其实只要将所有的二元乘积对枚举出来,并统计个数,然后就转换成一个排列组合问题,公示如下
$$
P^2_nP_2^2P^2_2
$$
其中n表示,乘积相同的数有n个,也就是有n对,从n对中选两对进行排列$P^2_n$,再各自内部排列$P_2^2P^2_2$,就是答案

class Solution {
public:
int tupleSameProduct(vector<int>& nums) {
unordered_map<int,int> mp;
for(int i =0;i < nums.size();i++){
for(int j = i+1;j < nums.size();j++){
mp[nums[i] * nums[j]] ++;
}
}
int ans = 0;
for(auto m : mp){
int cur = m.second;
ans += (cur * (cur-1))*4;
}
return ans;
}
};

第三题

1727. 重新排列后的最大子矩阵

这个题蛮有意思,考试的时候偷了个懒,直接把以前的代码复用,原理也很简单,就是在每一层上,把柱状图的高度算出来,考虑一些为0的情况,(重新计算高度),然后将高度排序,因为可以交换列,套用以前的代码84. 柱状图中最大的矩形就可以,其实也可以,直接求min然后乘宽度,因为我偷懒了。

class Solution:
def largestSubmatrix(self, matrix: List[List[int]]) -> int:
def largestRectangleArea(heights: List[int]) -> int:
stack = []
stack.append(-1)
res = 0
for i in range(len(heights)):
while(stack[-1]!=-1 and heights[stack[-1]] >= heights[i]):#维护一个单调递增的栈
m = stack[-1]
stack.pop()
res = max(res,heights[m]*(i-1-stack[-1])) #先算一遍本身
stack.append(i)
while stack[-1]!=-1: #算一遍剩下的
n = stack[-1]
stack.pop()
p = len(heights)-stack[-1]-1
res = max(res,heights[n]*p)
return res
m , n = len(matrix) , len(matrix[0])
ans = 0
cur = [[0] * n] * m
for j in range(n):
cur[0][j] = (matrix[0][j])
temp = cur[0][::]
temp.sort()
ans = max(ans,largestRectangleArea(temp))
for i in range(1,m):
for j in range(n):
if matrix[i][j] == 0:
cur[i][j] = 0
elif matrix[i-1][j] == 1 and matrix[i][j] == 1:
cur[i][j] = cur[i-1][j] + 1
elif matrix[i-1][j] == 0 and matrix[i][j] == 1:
cur[i][j] = 1
temp = cur[i][::]
temp.sort()
ans = max(ans,largestRectangleArea(temp))
return ans

第四题

1728. 猫和老鼠 II

这题属实看不懂,面试应该也不会考察吧,爬。

int f[8][8][8][8][200];

class Solution {
public:
int n, m, cj, mj;
vector<string> grid;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp(int cx, int cy, int mx, int my, int k) {
if (k >= 200) return 0;
auto& v = f[cx][cy][mx][my][k];
if (v != -1) return v;

if (k & 1) { // 移动猫
for (int i = 0; i < 4; i ++ ) {
for (int j = 0; j <= cj; j ++ ) {
int x = cx + dx[i] * j, y = cy + dy[i] * j;
if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '#') break;
if (x == mx && y == my || grid[x][y] == 'F') return v = 0;
if (dp(x, y, mx, my, k + 1) == 0) return v = 0;
}
}
return v = 1;
} else { // 移动老鼠
for (int i = 0; i < 4; i ++ ) {
for (int j = 0; j <= mj; j ++ ) {
int x = mx + dx[i] * j, y = my + dy[i] * j;
if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '#') break;
if (x == cx && y == cy) continue;
if (grid[x][y] == 'F') return v = 1;
if (dp(cx, cy, x, y, k + 1) == 1) return v = 1;
}
}
return v = 0;
}
}

bool canMouseWin(vector<string>& _grid, int catJump, int mouseJump) {
grid = _grid;
n = grid.size(), m = grid[0].size(), cj = catJump, mj = mouseJump;
memset(f, -1, sizeof f);

int cx, cy, mx, my;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (grid[i][j] == 'C') cx = i, cy = j;
else if (grid[i][j] == 'M') mx = i, my = j;
return dp(cx, cy, mx, my, 0);
}
};