[数据结构与算法]LeetCode笔记：Biweekly Contest 81

• LeetCode笔记：Biweekly Contest 81
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

• 比赛链接：https://leetcode.com/contest/biweekly-contest-81/

1. 题目一

给出题目一的试题链接如下：

• 2315. Count Asterisks

1. 解题思路

这一题思路上还是比较直接的，按照题意找出成对的|组成的pair，然后忽略掉其中的*，然后统计位置上的*即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def countAsterisks(self, s: str) -> int:
        res, cnt, bars = 0, 0, 0
        for ch in s:
            if ch == "|":
                if bars % 2 == 0:
                    res += cnt
                cnt = 0
                bars += 1
            elif ch == "*":
                cnt += 1
        return res + cnt

提交代码评测得到：耗时32ms，占用内存13.8MB。

2. 题目二

给出题目二的试题链接如下：

• 2316. Count Unreachable Pairs of Nodes in an Undirected Graph

1. 解题思路

这一题我的思路就是找到所有的相互之间存在连接的点的集合，然后对于每一个集合内的点，其与其他集合之间的任一点都可以构成一个不连通的点对。

由此，只要能够找出这些互通的点的集合，那么题目就迎刃而解了。

而至于如何去找到这些互通的点的集合，我这边的一个实现思路是通过DSU进行实现，关于DSU的部分，网上应该挺多了，有兴趣的读者也可以参考我之前写的博客【经典算法：并查集（DSU）结构简介】，这里就不过多赘述了。

2. 代码实现

给出python代码实现如下：

class DSU:
    def __init__(self, n):
        self.root = [i for i in range(n)]
        
    def find(self, k):
        if self.root[k] == k:
            return k
        self.root[k] = self.find(self.root[k])
        return self.root[k]
    
    def union(self, a, b):
        x = self.find(a)
        y = self.find(b)
        if x != y:
            self.root[y] = x
        return

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        dsu = DSU(n)
        for u, v in edges:
            dsu.union(u, v)
        
        cnt = defaultdict(int)
        for i in range(n):
            cnt[dsu.find(i)] += 1  
        
        res = 0
        for u in cnt:
            res += cnt[u] * (n - cnt[u])
        return res // 2

提交代码评测得到：耗时4812ms，占用内存73.9MB。

3. 题目三

给出题目三的试题链接如下：

• 2317. Maximum XOR After Operations

1. 解题思路

这一题还是蛮有意思的，考察变换$a\wedge (a\oplus x)$，它能够将位上的1修改为0或者1，但是位上的0始终还是0。

因此，只要存在某一个数的某一位上是1，那么我们总能够使得最终的结果在这一位上保持为1；反之，如果某一位上所有的数都为0，那么无论我们怎么取值，都无法令最后的结果中这一位上为1。

综上，我们就可以获得我们最终的答案。

2. 代码实现

给出python的代码实现如下：

class Solution:
    def maximumXOR(self, nums: List[int]) -> int:
        digits = [0 for _ in range(32)]
        for x in nums:
            idx = 0
            while x != 0:
                digits[31-idx] += x % 2
                x = x // 2
                idx += 1
        res = 0
        for d in digits:
            if d > 0:
                res = res * 2 + 1
            else:
                res = res * 2
        return res

提交代码评测得到：耗时2595ms，占用内存23.9MB。

4. 题目四

给出题目四的试题链接如下：

• 2318. Number of Distinct Roll Sequences

1. 解题思路

这一题思路上反而比较直接，就是一个动态规划就完事了，这里就不过多展开了，稍微注意一下边界条件就行。

2. 代码实现

给出python代码实现如下：

class Solution:
    def distinctSequences(self, n: int) -> int:
        MOD = 10**9 + 7
        
        @lru_cache(None)
        def gcd(a, b):
            if a < b:
                return gcd(b, a)
            elif b == 0:
                return a
            a, b = b, a%b
            return gcd(a, b)
        
        @lru_cache(None)
        def dp(idx, pre1, pre2):
            if idx >= n:
                return 1
            elif idx == 0:
                return sum(dp(1, i, 0) for i in range(1, 7)) % MOD
            elif idx == 1:
                res = 0
                for i in range(1, 7):
                    if i != pre1 and gcd(i, pre1) == 1:
                        res = (res + dp(idx+1, i, pre1)) % MOD
                return res % MOD
            res = 0
            for i in range(1, 7):
                if i != pre1 and gcd(i, pre1) == 1 and i != pre2:
                    res = (res + dp(idx+1, i, pre1)) % MOD
            return res % MOD
        
        return dp(0, -1, -1)

提交代码评测得到：耗时5259ms，占用内存528.3MB。