侯瑞哲的博客

Ruizhe's Blog

0%

LeetCode 210 周赛

发表于 Valine：

5535. 括号的最大嵌套深度

比较简单，不贴代码了

5536. 最大网络秩

计算每个点的边，如果两点相连，减去一条重复的边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        neigh = defaultdict(set)
        for x, y in roads:
            neigh[x].add(y)
            neigh[y].add(x)
        res = 0

        def maxRank(x, y):
            if y in neigh[x]:
                return len(neigh[x]) + len(neigh[y]) - 1
            return len(neigh[x]) + len(neigh[y])

        for x in range(n):
            for y in range(x + 1, n):
                res = max(res, maxRank(x, y))
        return res

5537. 分割两个字符串得到回文串

找到a b从中心开始的最长回文串，从al, ar, bl, br，然后比较a[:al] == b[ar+1:] or a[:bl] == b[br + 1] or b[:al] == a[ar+1:] or b[:bl] == a[br+1:]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def isPalindrome(s):
            return s == s[::-1]

        if isPalindrome(a) and isPalindrome(b):
            return True
        n = len(a)

        if n & 1:
            l = r = n >> 1
        else:
            l, r = (n >> 1) - 1, n >> 1
        # print(len(a))
        # print(l, r)
        al, ar = l, r
        while al >= 0 and ar < n and a[al] == a[ar]:
            al -= 1
            ar += 1
        bl, br = l, r
        while bl >= 0 and br < n and b[bl] == b[br]:
            bl -= 1
            br += 1
        # print(a[:al + 1], b[ar:][::-1])
        # print(b[:bl + 1], a[br:][::-1])
        return a[:al + 1] == b[ar:][::-1] or b[:bl + 1] == a[br:][::-1] \
               or b[:al + 1] == a[ar:][::-1] or a[:bl + 1] == b[br:][::-1]

5538. 统计子树中城市之间最大距离

状压枚举所有集合，以集合的每一个点为根顶点，bfs计算这个点为根顶点时的树的高度，最大值即为这个集合构成子树的最大距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution(object):

    def countSubgraphsForEachDiameter(self, n, edges):
        G = [[] for _ in range(n)]
        for i, j in edges:
            G[i - 1].append(j - 1)
            G[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 G[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
            d = maxd(mask)
            if d:
                res[d - 1] += 1

        return res

AcWing《LeetCode究极班》拼团优惠！https://www.acwing.com/activity/content/introduction/31/group_buy/1154/