第一题：https://leetcode-cn.com/problems/detect-pattern-of-length-m-repeated-k-or-more-times/
第二题：https://leetcode-cn.com/problems/maximum-length-of-subarray-with-positive-product/
第三题：https://leetcode-cn.com/problems/minimum-number-of-days-to-disconnect-island/
第四题：https://leetcode-cn.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/
一、重复至少 K 次且长度为 M 的模式
给你一个正整数数组 arr，请你找出一个长度为 m 且在数组中至少重复 k 次的模式。
模式 是由一个或多个值组成的子数组（连续的子序列），连续 重复多次但 不重叠 。 模式由其长度和重复次数定义。
如果数组中存在一个至少重复 k 次且长度为 m 的模式，则返回 true ，否则返回 false 。
class Solution:
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
len_arr=len(arr)
for i in range(len_arr):
temp=arr[i:i+m]
if temp*k==arr[i:i+m*k]: return True
return False
#暴力法
二、乘积为正数的最长子数组长度
给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
class Solution:
def getMaxLen(self, nums: List[int]) -> int:
nums.append(0)
start = 0
temp = []
ans = 0
for i, t in enumerate(nums) :
if t == 0 :
if len(temp) % 2 == 0 : #偶数个负数
ans = max(ans, i-start) #用i-start更新ans
else :
ans = max([ans, i-temp[0]-1, temp[-1]-start])
#还是用偶数个负数的情况来更新ans
start = i+1
temp = []
elif t < 0 :
temp.append(i) #暂存小于0的数
return ans
#主要思路：硬模拟，负数为主线索
三、使陆地分离的最少天数
给你一个由若干 0 和 1 组成的二维网格 grid ，其中 0 表示水，而 1 表示陆地。岛屿由水平方向或竖直方向上相邻的 1 （陆地）连接形成。
如果 恰好只有一座岛屿 ，则认为陆地是 连通 的 ；否则，陆地就是 分离 的 。
一天内，可以将任何单个陆地单元（1）更改为水单元（0）。
返回使陆地分离的最少天数。
#不会啊，吐了
四、将子数组重新排序得到同一个二叉查找树的方案数
给你一个数组 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 取余数。
from math import comb
class Solution:
def numOfWays(self, nums: List[int]) -> int:
def f(nums):
if len(nums) < 3: return 1
left = [num for num in nums if num < nums[0]]
right = [num for num in nums if num > nums[0]]
l, r = f(left), f(right)
res = comb(len(nums) - 1, len(left)) * l * r
return res
return (f(nums) - 1)%(10**9 + 7)
# 分治
