5499. 重复至少 K 次且长度为 M 的模式
给你一个正整数数组 arr，请你找出一个长度为 m 且在数组中至少重复 k 次的模式。
模式 是由一个或多个值组成的子数组（连续的子序列），连续 重复多次但 不重叠 。 模式由其长度和重复次数定义。
如果数组中存在至少重复 k 次且长度为 m 的模式，则返回 true ，否则返回 false 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/detect-pattern-of-length-m-repeated-k-or-more-times
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
直接暴力就完事了，没啥好说的
class Solution {
public boolean containsPattern(int[] arr, int m, int k) {
if(m*k>arr.length){
return false;
}
int[] temp=new int[m];
//如果后面的长度已经小于m*k了，就没有继续的必要
for(int i=0;i<arr.length-m*k+1;i++){
for(int j=0;j<m;j++){
temp[j]=arr[i+j];
}
for(int j=m;j<m*k;j++){
if(temp[j%m]!=arr[i+j]){
//找到“捣乱分子”可以直接下次遍历
break;
}else if(j==m*k-1){
//找到一个满足的即可返回true
return true;
}
}
}
return false;
}
}
5500. 乘积为正数的最长子数组长度
给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-length-of-subarray-with-positive-product
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题和152. 乘积最大子数组类似，比它简单，只需要从左至右从右至左各遍历一次数组，记录当前所得符号，遇见0重置计数即可
class Solution {
public int getMaxLen(int[] nums) {
int flag=1;
int max=0;
int temp=0;
for(int i=0;i<nums.length;i++){
if(nums[i]==0){
flag=1;
temp=0;
}else{
flag=flag*nums[i]/Math.abs(nums[i]);
temp++;
if(flag==1){
max=Math.max(max,temp);
}
}
}
flag=1;
temp=0;
for(int i=nums.length-1;i>=0;i--){
if(nums[i]==0){
flag=1;
temp=0;
}else{
flag=flag*nums[i]/Math.abs(nums[i]);
temp++;
if(flag==1){
max=Math.max(max,temp);
}
}
}
return max;
}
}
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 取余数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-ways-to-reorder-array-to-get-same-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
找规律之后其实这就是一个简单的递归问题：
对于根节点R和左子树Ls以及右子树Rs（元素个数分别为n和m）
Ls和Rs分别有x和y种排列
那么R所对应的树，对应的排列应该为：
首先R应该在排列最前面，而左右子树元素的相对顺序应该是左右子树排列的一种。也就是说：除了R之外元素的排列中，左右子树的相对顺序应该是合法的。【而左右子树元素互相穿插不会影响树的结构】
从而，这个问题转化为n个红球m个黑球占据n+m个位置的问题（答案显然为C[n+m,m]）站好位置之后再把左右子树的各种顺序填进去即可
因此R对应的方法数应该是C[n+m,m]*x*y
class Solution {
class Tree{
public Tree right;
public Tree left;
public int val;
public int count=0;
public Tree(int val){
this.val=val;
}
public void in(Tree t){
this.count++;
if(t.val>this.val){
if(this.right==null){
this.right=t;
}else{
this.right.in(t);
}
}else{
if(this.left==null){
this.left=t;
}else{
this.left.in(t);
}
}
}
}
public long c(long x,long y){
long re=1;
for(long i=x;i>x-y;i--){
re*=i;
}
for(long i=1;i<=y;i++){
re/=i;
}
return re;
}
public long h(Tree root){
if(root.right==null&&root.left==null){
return 1;
}else if(root.right==null){
return h(root.left);
}else if(root.left==null){
return h(root.right);
}else{
long x=h(root.right);
long y=h(root.left);
return c(root.right.count+1+root.left.count+1,Math.min(root.right.count+1,root.left.count+1))*x*y;
}
}
public int numOfWays(int[] nums) {
if(nums.length==0){
return 0;
}
Tree root=new Tree(nums[0]);
for(int i=1;i<nums.length;i++){
root.in(new Tree(nums[i]));
}
return ((int)(h(root)%1000000007))-1;
}
}
然而会溢出，做题的时候还真没想出来咋处理这问题
5501. 使陆地分离的最少天数
给你一个由若干 0 和 1 组成的二维网格 grid ，其中 0 表示水，而 1 表示陆地。岛屿由水平方向或竖直方向上相邻的 1 （陆地）连接形成。
如果 恰好只有一座岛屿 ，则认为陆地是 连通的 ；否则，陆地就是 分离的 。
一天内，可以将任何单个陆地单元（1）更改为水单元（0）。
返回使陆地分离的最少天数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-number-of-days-to-disconnect-island
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。