2022 年第 51 周总结

发布于 2022-12-18  1061 次阅读

本周学习情况

  • 每日算法练习按时完成（使用python）
  • 学习了并查集的概念、性质和应用，其简化版本和完整版本的定义（包括 find()、 union() 等方法的实现和优化）。
  • 学习了差分数组的定义和应用

每日练习

周赛情况

这次完全用python打周赛，成绩不佳。比较遗憾只做了两题，赛后回顾发现，这可能是离做出4题最近的一次，实在不应该。在第三题上死磕，没去看第四题，而实际上第四题要更简单。

Problem 1

当使用某种字符搭配的单词数固定时，对数也是固定的，所以统计每个字符搭配有几个单词即可。

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        dicts = defaultdict(int)
        for word in words:
            dic = [0 for i in range(26)]
            for ch in word: dic[ord(ch) - ord("a")] = 1
            dicts[dic] += 1
        ans = 0
        keys = dicts.keys()
        for key in keys:
            if (dicts[key] > 1): ans += dicts[key] * (dicts[key] - 1) // 2
        return ans

Problem 2

求质因数有法可循，只要从2开始依次检查能否被整除即可。

class Solution:
    def smallestValue(self, n: int) -> int:
        def getContent(x: int) -> List[int]:
            content = []
            i = 2
            while i * i <= x:
                if (x % i == 0):
                    while x % i == 0:
                        content.append(i)
                        x = x // i
                i += 1
            if x > 1: content.append(x)
            return content
        c = getContent(n)
        while len(c) != 1:
            n = sum(c)
            c = getContent(n)
            if n == sum(c): return n
        return c[0]

Problem 3

思路没有走错，但最后分情况讨论漏掉了一种，导致最后一个用例没能通过。

我的代码：

class Solution:
    def isPossible(self, n: int, edges: List[List[int]]) -> bool:
        graph = [[] for i in range(n)]
        for edge in edges:
            graph[edge[0] - 1].append(edge[1] - 1)
            graph[edge[1] - 1].append(edge[0] - 1)
        pale = defaultdict(list)
        for i in range(n):
            du = len(graph[i])
            if (du & 1) == 1:
                if du == n - 1: return False
                else:
                    for j in range(n):
                        if j != i and (j not in graph[i]):
                            pale[i].append(j)
        num = len(pale)
        if num == 0: return True
        if (num & 1) == 1: return False
        if num > 4: return False
        vs = list(pale.keys())
        if num == 2:
            for i in range(n):
                if i in pale[vs[0]] and i in pale[vs[1]]: return True
            if (vs[0] not in pale[vs[1]]): return False
            else: return True
        if num == 4:
            if ((vs[0] in pale[vs[1]]) and (vs[2] not in pale[vs[3]])) or ((vs[0] in pale[vs[2]]) and (vs[1] not in pale[vs[3]])) or ((vs[0] in pale[vs[3]]) and (vs[1] not in pale[vs[2]])): return False
            else: return True

先统计哪几个点的度是奇数，如果有顶点的度是奇数且为定点总数减一，那么肯定是返回False。

如果奇数度顶点的个数（记为 num ）不是0、2、4中的一种，那么也返回False。

如果 num == 0 ，已经满足要求，返回True。

如果 num == 2 ，说明只有两个顶点是奇数度，那么看这两个顶点间能否加上一条边（或者说两者间是否已经存在一条边），不能加的话就返回False，否则True。

如果 num == 4 ，说明有四个奇数度顶点，要考虑在四个顶点上加两条边。

在2和4的情况下，我漏掉了一种情况——就是两个或四个奇数度的顶点，即便他们之间已经存在边，也可以同时连接到一个相同顶点（记为 X ），这样 X 的度依旧为偶数，而几个奇数度顶点也变为偶数度。因为没考虑到这个情况，最后一个用例没能通过。

Problem 4

竞赛时完全没看这题，习惯告诉我第四题总是最难的一题，事实证明不一定。以后要吸取教训，上来应该先把四个题干都看一遍，再决定做题顺序。

因为是完全树，可以很方便地从下标去找每个结点的父亲和祖先。事实上，环的长度就和两个结点跟它们共同祖先的距离相关，所以计算出两点跟共同祖先的距离，问题就迎刃而解。

赛后写出的代码：

class Solution:
    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        m = len(queries)
        ans = [0 for i in range(m)]
        for i in range(m):
            h1 = h2 = 0
            q1, q2 = queries[i][0], queries[i][1]
            while q1 != q2:
                if q1 > q2:
                    q1 //= 2
                    h1 += 1
                else:
                    q2 //= 2
                    h2 += 1
            ans[i] = h1 + h2 + 1
        return ans