Leetcode第 204 场周赛

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

1566. 重复至少 K 次且长度为 M 的模式

思路： 直接模拟

class Solution {
public:bool containsPattern(vector<int>& arr, int m, int k) {int n = arr.size();for(int i = 0;i + m - 1 < n;i++) { //起点int cnt = 1;for(int j = i + m;j + m - 1 < n;j += m) {int flag = 1;for(int q = 0;q < m;q++) {if(arr[i + q] != arr[j + q]) {flag = 0;break;}}if(flag) cnt++;else break;}if(cnt >= k) return true;}return false;}
};

1567. 乘积为正数的最长子数组长度

思路：
我的思路类似维护前缀和。
先不考虑0，连续乘积为正数，就是从起点开始一直乘到现在；结果如果是正数，那么直接算上。
如果是负数，则找到最开始出现负数的位置，位置相减就是正数乘积的长度。

再说0，因为0乘以任何数都是0，所以直接可以不考虑，每次遇到一个0，都当做是开始了一个新数列就好了。

class Solution {
public:int getMaxLen(vector<int>& nums) {int n = nums.size();int pos = -1;//第一次出现负数的位置int zero = -1;//上一次出现0的位置int sum = 1;int ans = 0;for(int i = 0;i < n;i++) {if(nums[i] < 0) {sum *= -1;} else if(nums[i] > 0) {sum *= 1;} else if(nums[i] == 0) {sum = 1;zero = i;pos = -1;}if(sum == 1) {ans = max(ans,i - zero);} else if(sum == -1) {if(pos != -1) {ans = max(ans,i - pos);} else {pos = i;}}}return ans;}
};

1568. 使陆地分离的最少天数

思路：
很容易想到，使得连通分量改变的最大删除数为2，因为一个连通块边界总能找到一个点，删除周围两个就可以使得这个点分出来。

而数据范围特别特别小，才30，所以可以想到去枚举删除哪些点，然后再用bfs去check看连通分量是否为1。

class Solution {
public:int dirx[10] = {0,0,1,-1};int diry[10] = {1,-1,0,0};void bfs(int x,int y,vector<vector<int>>& grid) {int n = grid.size();int m = grid[0].size();queue<pair<int,int>>q;q.push({x,y});while(!q.empty()) {pair<int,int>now = q.front();q.pop();for(int i = 0;i < 4;i++) {int dx = now.first + dirx[i],dy = now.second + diry[i];if(dx < 0 || dy < 0 || dx >= n || dy >= m) continue;if(grid[dx][dy] == 1) {grid[dx][dy] = 0;q.push({dx,dy});}}}}bool check(vector<vector<int>> grid) {int n = grid.size();int m = grid[0].size();int cnt = 0;for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {if(grid[i][j] == 1) {bfs(i,j,grid);cnt++;}}}if(cnt == 0 || cnt >= 2) return true;return false;}int minDays(vector<vector<int>>& grid) {int n = grid.size();int m = grid[0].size();if(check(grid)) return 0;for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {if(grid[i][j] == 1) {grid[i][j] = 0;if(check(grid)) return 1;grid[i][j] = 1;}}}for(int x1 = 0;x1 < n;x1++) {for(int y1 = 0;y1 < m;y1++) {if(grid[x1][y1] == 1) {for(int x2 = 0;x2 < n;x2++) {for(int y2 = 0;y2 < m;y2++) {if(grid[x2][y2] == 1) {grid[x1][y1] = 0;grid[x2][y2] = 0;if(check(grid)) return 2;grid[x1][y1] = 1;grid[x2][y2] = 1;}}}}}}return 3;}
};

1569. 将子数组重新排序得到同一个二叉查找树的方案数

思路： 感觉算是这几次周赛中最有意思的一道题。
首先可以把这棵二叉查找树给建出来，然后题意就转换为了：每次建立一个点，条件是其父节点已经建立了，问建立这棵二叉搜索树的方案数。

则可以定义$f[i]$代表建立以$i$为根节点的二叉搜索树的方案数。
则两个子节点的建树方案数为$f[l[i]],f[r[i]]$。
假设左子树大小为$siz[l[i]]$，右子树大小为$siz[r[i]]$。

则可以看作是一个大小为$siz[l[i]]+siz[r[i]]$的排列，然后其中$siz[l[i]]$，$siz[r[i]]$个数的相对顺序确定了，这相当于是多重集的排列问题（当然这也等价于是组合数），所以可以有$f[i]=f[l[i]]\ast f[r[i]]\ast fac[siz[l[i]]+siz[r[i]]/fac[siz[l[i]]/fac[siz[r[i]]$

这可以推广到任意树的建树方案数。通过一次又一次的转换，看似麻烦的数据结构问题最终归结成了简单的数学问题，这就是感觉有趣的地方吧。

typedef long long ll;
const int maxn = 1e3 + 7;
const int mod = 1e9 + 7;
class Solution {
public:int G[maxn][2];ll f[maxn],fac[maxn],siz[maxn];ll qpow(ll x,ll n) {ll res = 1;while(n) {if(n & 1) res = res * x % mod;x = x * x % mod;n >>= 1;}return res;}void insert(int root,int x) {while(1) {if(x > root) {if(G[root][1]) { //右边root = G[root][1];} else {G[root][1] = x;break;}} else {if(G[root][0]) { //左边root = G[root][0];} else {G[root][0] = x;break;}}}}void dfs(int root) {siz[root] = 1;if(G[root][0]) {dfs(G[root][0]);siz[root] += siz[G[root][0]];}if(G[root][1]) {dfs(G[root][1]);siz[root] += siz[G[root][1]];}f[root] = fac[siz[G[root][0]] + siz[G[root][1]]];if(G[root][0]) {f[root] = f[root] * f[G[root][0]] % mod * qpow(fac[siz[G[root][0]]],mod - 2) % mod;}if(G[root][1]) {f[root] = f[root] * f[G[root][1]] % mod * qpow(fac[siz[G[root][1]]],mod - 2) % mod;}}int numOfWays(vector<int>& nums) {int n = nums.size();int root = nums[0];fac[0] = 1;for(int i = 1;i <= n;i++) fac[i] = fac[i - 1] * i % mod;for(int i = 1;i < n;i++) {insert(root,nums[i]);}dfs(root);return (f[root] - 1 + mod) % mod;}
};

这篇关于Leetcode第 204 场周赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---