第一题：https://leetcode-cn.com/problems/maximum-nesting-depth-of-the-parentheses/
第二题：https://leetcode-cn.com/problems/maximal-network-rank/
第三题：https://leetcode-cn.com/problems/split-two-strings-to-make-palindrome/
第四题：https://leetcode-cn.com/problems/count-subtrees-with-max-distance-between-cities/
一、括号的最大嵌套深度
class Solution:
def maxDepth(self, s: str) -> int:
ans=0
cnt=0
for i in s:
if i=="(": ans+=1
elif i==")": ans-=1
cnt=max(cnt,ans)
return cnt
二、最大网络秩
n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。每个 roads[i] = [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。
两座不同城市构成的 城市对 的 网络秩 定义为：与这两座城市 直接 相连的道路总数。如果存在一条道路直接连接这两座城市，则这条道路只计算 一次 。
整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。
给你整数 n 和数组 roads，返回整个基础设施网络的 最大网络秩 。
class Solution:
def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
ans=0
d=defaultdict(list)
for i,j in roads:
d[i].append(j)
d[j].append(i)
for i in range(n):
for j in range(i+1,n):
tmp=len(d[i])+len(d[j])
if i in d[j]: tmp-=1
ans=max(ans,tmp)
return ans
# 穷举
三、分割两个字符串得到回文串
给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串： aprefix 和 asuffix ，满足 a = aprefix + asuffix ，同理，由 b 可以得到两个字符串 bprefix 和 bsuffix ，满足 b = bprefix + bsuffix 。请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。
当你将一个字符串 s 分割成 sprefix 和 ssuffix 时， ssuffix 或者 sprefix 可以为空。比方说， s = "abc" 那么 "" + "abc" ， "a" + "bc" ， "ab" + "c" 和 "abc" + "" 都是合法分割。
如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。
class Solution:
def checkPalindromeFormation(self, a: str, b: str) -> bool:
def check(str1,str2,left):
right=len(str1)-1-left
while(left>=0 and right<len(str1)):
if str1[left]!=str2[right]: break
left-=1
right+=1
return left
left=len(a)//2-1 #第一次检测的下标
left=min(check(a,a,left),check(b,b,left))
left=min(check(a,b,left),check(b,a,left))
return left==-1 #检测是否扩展到底
# 核心思路：中心扩展
# 第一步：前a后a,前b后b,找到中间的回文串
# 第二步：开始拼接
四、统计子树间最大距离
任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵 树 。
输入：n = 4, edges = [[1,2],[2,3],[2,4]]
输出：[3,4,0]
解释：
子树 {1,2}, {2,3} 和 {2,4} 最大距离都是 1 。
子树 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距离都为 2 。
不存在城市间最大距离为 3 的子树。
class Solution:
def countSubgraphsForEachDiameter(self, n, edges):
d=defaultdict(list)
for i, j in edges:
d[i - 1].append(j - 1)
d[j - 1].append(i - 1)
def maxd(mask0):
res = 0
for i in range(n):
if (1 << i) & mask0:
mask = mask0
bfs, bfs2 = [i], []
cur = 0
while bfs:
for i in bfs:
mask ^= 1 << i
for j in d[i]:
if mask & (1 << j):
bfs2.append(j)
cur += 1
bfs, bfs2 = bfs2, []
if mask: return 0
res = max(res, cur - 1)
return res
res = [0] * (n - 1)
for mask in range(1 << n):
if mask & (mask - 1) == 0: continue
k = maxd(mask)
if k:
res[k - 1] += 1
return res
# copy
# 不懂
