5
LeetCode 第 204 场周赛
source link: https://xienaoban.github.io/posts/173.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode 第 204 场周赛
5499. 重复至少 K 次且长度为 M 的模式
垃圾题解 略
class Solution:
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
print('ohhh')
n = len(arr)
if m * k > n: return False
for i in range(n - m + 1):
a = arr[i : i + m]
c = 1
j = i + m
while j <= n - m:
kk = 0
while kk < m and a[kk] == arr[j + kk]: kk += 1
if kk == m: c += 1
else: break
j += kk
# print(str(i) + " " + str(c) + "-----")
if c >= k: return True
return False
5500. 乘积为正数的最长子数组长度
垃圾题解 略
class Solution:
def getMaxLen(self, nums: List[int]) -> int:
l0, l1, l_1 = -1, 0, -1
flag = False
res = 0
for i in range(len(nums)):
n = nums[i]
if n == 0:
l0 = i
l1 = i + 1
l_1 = -1
flag = False
else:
if n < 0:
flag = not flag
if l_1 == -1: l_1 = i
if flag and l_1 != -1: res = max(res, i - l_1)
elif not flag: res = max(res, i - l1 + 1)
# print(res, end=' ')
# print('----')
return res
5501. 使陆地分离的最少天数
求把一个连通分量拆成俩的最小切割次数. 这题撑死最多切两次 (即当图有三个及以上的点时, 图的边缘必存在只有两条边的点).
先遍历一遍全图, 如果本来就有不止一个分量, 直接返回 0.
然后判断一个特例: 连通分量就一个, 但该分量就两个点. 这样的话删除一个后依然是一个连通分量. 所以要删两次, 返回 2.
然后遍历所有点, 如果找到一个点只有一条边, 返回 1; 如果找到有点有两条边, 则临时删除该点, DFS 遍历全图判断是不是变成了两个分量, 是则返回 1 (不要问我什么割点、什么 Tarjan, 爷忘光啦. 反正我赌 LeetCode 会让我过).
剩下的情况直接返回 2.
class Solution:
def minDays(self, grid: List[List[int]]) -> int:
n, m = len(grid), len(grid[0])
cnt1 = 0
vis = [[False] * m for _ in range(n)]
def dfs(g, v, x, y):
if v[x][y]: return True
v[x][y] = True
if x > 0 and g[x - 1][y] == 1 and not v[x - 1][y]: dfs(g, v, x - 1, y)
if y > 0 and g[x][y - 1] == 1 and not v[x][y - 1]: dfs(g, v, x, y - 1)
if x < len(g) - 1 and g[x + 1][y] == 1 and not v[x + 1][y]: dfs(g, v, x + 1, y)
if y < len(g[0]) - 1 and g[x][y + 1] == 1 and not v[x][y + 1]: dfs(g, v, x, y + 1)
flag = False
for i in range(n):
for j in range(m):
if grid[i][j] == 1: cnt1 += 1
if grid[i][j] == 1 and not vis[i][j]:
if flag: return 0
flag = True
dfs(grid, vis, i, j)
if cnt1 == 2: return 2
for i in range(n):
for j in range(m):
if grid[i][j] == 0: continue
c = []
if i > 0 and grid[i - 1][j] == 1: c.append((i - 1, j))
if j > 0 and grid[i][j - 1] == 1: c.append((i, j - 1))
if i < n - 1 and grid[i + 1][j] == 1: c.append((i + 1, j))
if j < m - 1 and grid[i][j + 1] == 1: c.append((i, j + 1))
if len(c) == 1: return 1
if len(c) != 2: continue
grid[i][j] = 0
for ii in range(n):
for jj in range(m):
vis[ii][jj] = False
dfs(grid, vis, c[0][0], c[0][1])
if not vis[c[1][0]][c[1][1]]: return 1
grid[i][j] = 1
return 2
5502. 将子数组重新排序得到同一个二叉查找树的方案数
给一棵二叉查找树, 问有多少种方法产生此树 (即求可行的输入顺序的个数 - 1).
根节点必为输入的第一个. 剩下的, 左右子树互不影响, 可以随意穿插 (只要左子树的顺序之间、右子树的顺序之间的顺序不变即可).
所以 输入顺序个数 = 左子树输入顺序个数 * 右子树输入顺序个数 * 左右子树所有穿插的可能数, 其中 左右子树所有穿插的可能数 = C(总结点数 - 1, 左或右子树节点个数).
import math
class Solution:
def numOfWays(self, nums: List[int]) -> int:
def comb(n, m):
return math.factorial(n)//(math.factorial(n-m)*math.factorial(m))
MOD = int(10 ** 9 + 7)
def dfs(arr):
n = len(arr)
if n <= 2: return 1
left, right = [], []
for i in range(1, n):
if arr[i] < arr[0]: left.append(arr[i])
else: right.append(arr[i])
l, r = len(left), len(right)
return dfs(left) * dfs(right) * comb(n - 1, l) % MOD
return dfs(nums) - 1
- 本文作者： XieNaoban
- 本文链接： https://xienaoban.github.io/posts/173.html
- 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-ND 许可协议。转载请注明出处！
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK