5499. 重复至少 K 次且长度为 M 的模式
给你一个正整数数组 arr，请你找出一个长度为 m且在数组中至少重复k次的模式。
模式 是由一个或多个值组成的子数组（连续的子序列），连续 重复多次但 不重叠。 模式由其长度和重复次数定义。
如果数组中存在至少重复k次且长度为m的模式，则返回true，否则返回 false 。
分析
题意是在一个数组中是否存在连续的k个长度为m的相同子序列，我们只需要枚举起点，然后通过判断从这个起点开始的k个长为m的子序列即可。
代码
class Solution {
public:
bool containsPattern(vector<int>& arr, int m, int k) {
int n = arr.size();
if(m == 1 && k == 1) return true;
for(int j = 0; j<n; j++){
int cnt = 1;
int v = 0;
while(cnt<k){
int t = j+cnt*m;
bool f = true;
for(v = 0; v<m; v++){
if(t+v >=n || j+v >=n){
f = 0;
break;
}
if(arr[t+v] != arr[j+v]){
f = 0;
break;
}
}
cnt ++;
if(!f) break;
}
cout<<j<<" "<<cnt<<" "<<v<<endl;
if(cnt >= k && v == m) return true;
}
return false;
}
};
5500. 乘积为正数的最长子数组长度
给你一个整数数组 nums，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
分析
动态规划，设置两个数组， dp，fdp
- 1.dp[i]表示到第i个数为止乘积为正数的最长子数组长度。
- 2.fdp[i]表示到第i个数为止乘积为负数的最长子数组长度。
状态转移： 第i个数nums[i] 是：
- 1.正数：
- dp[i] = dp[i-1] + 1;
- 2.fdp[i] = (fdp[i-1] == 0? 0:fdp[i-1] + 1); //当fdp[i-1]等于0的时候， fdp[i] 不可能为1，因为当前数字是正数，不满足fdp数组的定义
- 2.负数
- 1.dp[i] = (fdp[i-1] == 0? 0:fdp[i-1]+1); //当fdp[i-1]等于0的时候，dp[i]不能为1，因为当前数字是负数，不满足定义
- 2.fdp[i] = dp[i-1] + 1;
代码
class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n+2,0);
vector<int> fdp(n+2,0);
if(nums[0]<0) fdp[0] = 1;
if(nums[0]>0) dp[0] = 1;
for(int i = 1; i<n; i++){
if(nums[i] > 0){
dp[i] = dp[i-1] + 1;
fdp[i] = (fdp[i-1]==0? 0:fdp[i-1]+1);
}
if(nums[i] < 0){
dp[i] = (fdp[i-1]==0? 0:fdp[i-1]+1);
fdp[i] = dp[i-1] + 1;
}
cout<<dp[i]<<endl;
}
int res = 0;
for(int i = 0; i<n; i++){
res = max(res,dp[i]);
}
// cout<<endl;
return res;
}
};
5501. 使陆地分离的最少天数
给你一个由若干 0和 1组成的二维网格grid，其中 0 表示水，而 1 表示陆地。岛屿由水平方向或竖直方向上相邻的 1（陆地）连接形成。
如果 恰好只有一座岛屿 ，则认为陆地是 连通的 ；否则，陆地就是 分离的 。
一天内，可以将任何单个陆地单元（1）更改为水单元（0）。
返回使陆地分离的最少天数。
分析
注意到，每个点只与上下左右四个点连通，且我们一定能找到第一小块陆地(1) (从左到右，从上到下进行遍历，一定可以找到第一个1)，对于这一块陆地，它的上方和左方都是水或者是空地，那么，只要确定了这块陆地的右方和下方的情况，就可以知道答案，且答案只有三种可能，0，1，2，对应三种情况：这块陆地孤立； 这块陆地的右边或者下边是另一块陆地； 这块陆地的右边和下边全是陆地。
如何判断当前已经成功分离陆地，我们只要对网格dfs一遍，找出其中连通块的个数是否大于1即可。
代码：
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
class Solution {
public:
vector<vector<bool>> st;
vector<vector<int>> g;
int n,m;
int minDays(vector<vector<int>>& grid) {
n = grid.size(), m = grid[0].size();
g = grid;
if(check()) return 0;
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
if(g[i][j] == 1){
g[i][j] = 0;
if(check()) return 1;
g[i][j] = 1;
}
}
}
return 2;
}
bool check(){
st = vector<vector<bool>> (n+2,vector<bool>(m+2,0));
int cnt = 0;
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
if(g[i][j] && !st[i][j]){
dfs(g,i,j);
cnt ++;
}
}
}
return cnt > 1;
}
void dfs(vector<vector<int>>& g,int x,int y){
st[x][y] = true;
for(int i = 0; i<4; i++){
int tx = x + dx[i];
int ty = y + dy[i];
if(tx <0 || tx >=n || ty<0 || ty>=m || st[tx][ty] || !g[tx][ty]) continue;
dfs(g,tx,ty);
}
}
};
5502. 将子数组重新排序得到同一个二叉查找树的方案数
给你一个数组 nums 表示1 到n的一个排列。我们按照元素在 nums中的顺序依次插入一个初始为空的二叉查找树（BST）。请你统计将 nums重新排序后，统计满足如下条件的方案数：重排后得到的二叉查找树与 nums原本数字顺序得到的二叉查找树相同。
比方说，给你 nums = [2,1,3]，我们得到一棵2 为根，1 为左孩子，3 为右孩子的树。数组[2,3,1]也能得到相同的 BST，但 [3,2,1]会得到一棵不同的 BST 。
请你返回重排 nums后，与原数组 nums得到相同二叉查找树的方案数。
由于答案可能会很大，请将结果对 10^9 + 7取余数。
分析
由于第一个数一定是根，根据BST的定义，可以左子树中的节点全是比根小的，右子树中的节点全是比根大的，而这两类数在排列中互不影响，那么我们现在假设一个数组序列长度为n，根节点是k，比k大的数right中(共n-k个)，比k小的数放在left中(共k-1个)，因为这两类数在序列中互不影响，所以先不考虑left和right中每个数字的顺序问题，保持相对顺序不变的话，共有方案C(n-1,k-1)种，对于left和right的话，他们自身也是二叉搜索树，所以可以用递归解决，即f(root) = C(n-1,k-1) * f(left) * f(right);
代码:
typedef long long LL;
const int mod = 1e9+7;
class Solution {
public:
vector<vector<int>> C;
int numOfWays(vector<int>& nums) {
int n = nums.size();
C = vector<vector<int>> (n+10,vector<int>(n+2,0));
for(int i = 0; i<=n; i++){
for(int j = 0; j<=i; j++){
if(!j) C[i][j] = 1;
else C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
}
}
return (f(nums)-1+mod)%mod;
}
int f(vector<int>& t){
if(t.size()<=0) return 1;
int n = t.size();
int k = t[0];
vector<int> left,right;
for(auto x:t){
if(x<k) left.emplace_back(x);
if(x>k) right.emplace_back(x-k);
}
return (LL)C[n-1][k-1]*f(left)%mod*f(right)%mod;
}
};
