Drafts of Leetcode May 2022

发表于 更新于 分类于 ， 阅读次数：

2022年5月力扣, 学习了Counter, :=, pairwise, bisect_left, @cache, yield等Python高级用法.

❤ 691. 贴纸拼词

输入： stickers = ["with","example","science"], target = "thehat" 输出：3 解释： 我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。 把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。 此外，这是形成目标字符串所需的最小贴纸数量。

20220514美团第三题"替换"即691. 贴纸拼词.

❗ Time Limit Exceeded - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        if len(target) == 0:  # 递归时删光了, 目标没有字母, 自然返回0
            return 0
        counts = []
        stickers = [_ for _ in stickers if set(_) & set(target)]  # 减少时间, 挑选贴纸
        for sticker in stickers:
            temp = target
            for s in sticker:
                if s in temp:
                    temp = temp.replace(s, '', 1)  # 做一个target-sticker的集合操作
            if temp != target:  # 仅当有删减时才纳入考虑
                counts.append(self.minStickers(stickers, temp))
        counts = [_ for _ in counts if _ >= 0]  # 避免出现-1进入递归
        # print(target, counts)
        return -1 if not counts else min(counts) + 1

🌟 [Python/Java/JavaScript/Go] BFS - Benhao

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
class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        """
        @param stickers: e.g. ["with","example","science"]
        @param target: e.g. "thehat"
        @return: e.g. 3
        """
        def trans(s):  # 统计s中每个字母在target中被需要的次数
            cnts = Counter()
            for c in s:
                if c in target:
                    cnts[c] += 1
            return cnts
        availables = [c for st in stickers if (c:=trans(st))]
        # [Counter({'t': 1, 'h': 1}), Counter({'e': 2, 'a': 1}), Counter({'e': 2})]
        queue = deque([(target, 0)])  # 维护一个step递增的队列 (先进先出), 也可从BFS的角度理解; 翻译为: 已经使用0个贴纸了, 剩下要拼的字符串为target
        explored = {target}
        while queue:
            cur, step = queue.popleft()  # 保证step小的先被处理
            if not cur:
                return step
            for avl in availables:
                if cur[0] in avl:  # !! 最左侧的元素迟早是要被删掉的, 仅仅检查一个字母, 节约时间
                    nxt = cur
                    for k, v in avl.items():
                        nxt = nxt.replace(k, '', v)  # 删去v个字符k
                    if nxt not in explored:  # 相同的nxt, 其step必然相同, 这是避免了重复
                        explored.add(nxt)
                        queue.append((nxt, step + 1))  # 翻译为: 已经使用了step+1个贴纸了, 剩下的要拼的字符串为nxt
        return -1

🛠 collections.Counter

A Counter is a dict subclass for counting hashable objects. It is a collection where elements are stored as dictionary keys and their counts are stored as dictionary values. Counts are allowed to be any integer value including zero or negative counts. The Counter class is similar to bags or multisets in other languages.

1
2
3
4
5
c = Counter()  # Counter()            
c = Counter('gallahad')  #  Counter({'g': 1, 'a': 3, 'l': 2, 'h': 1, 'd': 1})
c = Counter({'red': 4, 'blue': 2})  # Counter({'red': 4, 'blue': 2})
c = Counter(cats=4, dogs=8)  # Counter({'cats': 4, 'dogs': 8}), count of a missing element is zero
del c['cats']  # del removes the entry

🛠 Assignment expressions

There is new syntax := that assigns values to variables as part of a larger expression. It is affectionately known as “the walrus operator” due to its resemblance to the eyes and tusks of a walrus.

💛 62. 不同路径

image-20220514173113889

DP - Carlos

1
2
3
4
5
6
7
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        array = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                array[i][j] = array[i - 1][j] + array[i][j - 1]
        return array[-1][-1]

💛 64. 最小路径和

与20220514美团第二题"飞行"思路一致.

DP - Carlos

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        array = [[grid[0][0]] * n for _ in range(m)]
        for _ in range(1, m): array[_][0] = array[_ - 1][0] + grid[_][0]
        for _ in range(1, n): array[0][_] = array[0][_ - 1] + grid[0][_]
        for i in range(1, m):
            for j in range(1, n):
                array[i][j] = min(array[i - 1][j], array[i][j - 1]) + grid[i][j]
        return array[-1][-1]

💛 剑指 Offer 47. 礼物的最大价值

DP - Carlos

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        array = [[grid[0][0]] * n for _ in range(m)]
        for i in range(1, m): array[i][0] = array[i - 1][0] + grid[i][0]
        for j in range(1, n): array[0][j] = array[0][j - 1] + grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                array[i][j] = max(array[i - 1][j], array[i][j - 1]) + grid[i][j]
        return array[-1][-1]

💚 812. 最大三角形面积

Loop - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        n = len(points)
        results = []
        for i in range(n - 2):
            x1, y1 = points[i]
            for j in range(i + 1, n - 1):
                x2, y2 = points[j]
                for k in range(j + 1, n):
                    x3, y3 = points[k]
                    results.append(abs(
                        x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3
                    ) / 2)
        return max(results)

最大三角形面积 - 力扣官方题解

方法一：枚举 (时O3空O1)

1
2
3
4
5
class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        def triangleArea(x1: int, y1: int, x2: int, y2: int, x3: int, y3: int) -> float:
            return abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2) / 2
        return max(triangleArea(x1, y1, x2, y2, x3, y3) for (x1, y1), (x2, y2), (x3, y3) in combinations(points, 3))

🛠 itertools.combinations

方法二：凸包 (时O2空On)

💛 面试题 04.06. 后继者

找出给定节点的中序后继节点. 复习一下三种遍历: Tree Traversals (Inorder, Preorder and Postorder).

In-order Traverse and Index - Carlos

1
2
3
4
5
6
7
8
class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        def inorder(root, nodes=[]):  # 递归的中序遍历函数, 将遍历结果存进nodes返回
            if not root: return []
            if not root.left and not root.right: return [root]
            return nodes + inorder(root.left, nodes) + [root] + inorder(root.right, nodes)
        idx = (nodes:=inorder(root)).index(p)  # 找到中序遍历列表里p的index
        return nodes[idx + 1] if idx < len(nodes) - 1 else None

🌟 [Python/Java/JavaScript/Go] 二叉搜索树的后继 - Benhao

观察到所求后继节点集为值比该节点大的节点中最小的一个.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        parent, node = None, root  # 维护一个父节点
        while node:
            if node.val > p.val:  # 当前值大了, 那么所求可能为root, 或在root.left中
                parent, node = node, node.left
            elif node.val < p.val:  # 当前值小了, 所求不可能为root, 只会在root.right中
                node = node.right
            elif node.right:  # 当前节点为p, 要找值比它大的最小的那个, 则在右子树里穷尽左子树
                node = node.right
                while node.left:
                    node = node.left
                return node
            else:  # node.val为None, 这在前两个if中更新后的node为None时发生, 此时分别返回root或None
                return parent
        return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        return (res if (res := self.inorderSuccessor(root.left, p)) else root if root.val > p.val else self.inorderSuccessor(root.right, p)) if root else root
# if root:
#     res = self.inorderSuccessor(root.left, p)  #现在左子树里找, 符合中序遍历的顺序
#     if res:
#         return res
#     else:  # 从root的左子树里找不到, 说明目标要么是root, 要么在root的右子树, 要么是None
#         if root.val > p.val:  # 运用了了BST的性质, 因为val: root.right > root > p, 此是比p的值大的节点中最小的就是root
#             return root
#         else:  # 否则就在root的右子树里找
#             return self.inorderSuccessor(root.right, p)
# else:
#     return root

📚 Binary Search Tree

Binary Search Tree is a node-based binary tree data structure which has the following properties:

  • The left subtree of a node contains only nodes with keys lesser than the node’s key. (一个节点的左子树只包含键值小于该节点的键值的节点。)
  • The right subtree of a node contains only nodes with keys greater than the node’s key. (一个节点的右子树只包含键值大于该节点的键值的节点。)
  • The left and right subtree each must also be a binary search tree. (左和右子树也必须是一棵二进制搜索树。)

💚 953. 验证外星语词典

Pairwise Check - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        mydict = {order[_]: _ for _ in range(len(order))}  # 每个字符映射为整数, 用于比较大小
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            l1, l2 = len(w1), len(w2)
            count = 0
            for _ in range(min(l1, l2)):
                if mydict[w1[_]] > mydict[w2[_]]:  # 某个字符顺序不对
                    return False
                elif mydict[w1[_]] < mydict[w2[_]]:  # 可以检查下一对词了
                    break
                else:  # 记录相同的字符数
                    count += 1
            if l2 < l1 and count == min(l1, l2):  # 特殊情况如["apple", "app"]就是要返回False, 因为短的要放前面
                return False
        return True

验证外星语词典- 力扣官方题解

1
2
3
4
class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        index = {c: i for i, c in enumerate(order)}
        return all(s <= t for s, t in pairwise([index[c] for c in word] for word in words))

🛠 itertools.pairwise

Return successive overlapping pairs taken from the input iterable.

1
2
3
4
5
def pairwise(iterable):
    # pairwise('ABCDEFG') --> AB BC CD DE EF FG
    a, b = tee(iterable)  # tee默认参数为2, 这里返回了两个相同的iterators
    next(b, None)
    return zip(a, b)

🛠 itertools.tee

Return n independent iterators from a single iterable. See examples on Python – Itertools.tee().

[Python/Java/JavaScript/Go] 模拟 - Benhao

按order的规则逐位比较，从左往右只要有一组相邻单词不满足序，直接返回false即可。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        mp = {c: i for i, c in enumerate(order)}
        for i, w in enumerate(words[:-1]):
            j = 0  # 检查到的相同的字符总数
            while j < len(w):  # 检查w中的每个字符
                if j == len(words[i + 1]) or (a := mp[w[j]] - mp[words[i + 1][j]]) > 0:  # 发现下一个词对应位置没有字符, 或不满足字典顺序
                    return False
                elif a < 0:  # 检查的这一对满足要求了, 检查下一对
                    break
                j += 1
        return True
1
2
3
class Solution:  # 直接对words进行排序, key用的是tuple, 因为tuple的排序方式和题目要求的字典顺序吻合
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        return sorted(words, key=lambda x:tuple(mp[c] for c in x)) == words if (mp := {c:i for i, c in enumerate(order)}) else False

Pairwise - jerryluan

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        mp = {c: i for i, c in enumerate(order)}
        for w1, w2 in pairwise(words):
            j = 0  # 检查到的相同的字符总数
            while j < len(w1):  # 检查w1中的每个字符
                if j == len(w2) or (a := mp[w1[j]] - mp[w2[j]]) > 0:  # 发现下一个词对应位置没有字符, 或不满足字典顺序
                    return False
                elif a < 0:  # 检查的这一对满足要求了, 检查下一对
                    break
                j += 1
        return True

💛 46. 全排列

20220517快手一面第一题.

DC - Carlos

1
2
3
4
5
6
7
8
9
10
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 1:
            return [nums]
        result = []
        for i, n in enumerate(nums):
            temp = self.permute(nums[:i] + nums[i+1:])
            for _ in temp:
                result.append([n] + _)
        return result

Permutations

1
2
def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))

🛠 itertools.permutations

Return successive r length permutations of elements in the iterable.

❤ 668. 乘法表中第k小的数

二分思想, 另见378, 719, 786, 2040题.

❗ Time Limit Exceeded - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        num, count = 0, 0  # 按顺序记录每个整数出现的次数
        m, n = (m, n) if m > n else (n, m)  # 规范乘法表的形状, 这决定了count的更新方式
        while True:
            num += 1
            for i in range(ceil(sqrt(num)), m + 1):  # 起点取法是为了节约计算时间, 注意一定要加ceil
                quotient, remainder = divmod(num, i)  # [divmod](https://docs.python.org/3/library/functions.html#divmod)
                if remainder == 0 and quotient <= n:  # 整除且商在要求范围内
                    count += 1 + (0 if quotient == i else i <= n)  # 两个因数分别为i和quotient, 其中quotient<=n<m, 若相等, 只要加一次; 若i<=n<m则加两次
                if quotient == 0:  # 除数大于被除数了, 计算下一个num
                    break
            if count >= k:
                return num

乘法表中第k小的数 - 力扣官方题解

1
2
3
class Solution:  # 问题转化为: 有几个数<=x? 每行有min(n, x//i)个! 随后观察i对min内两个数的影响, 把求和号拆掉
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        return bisect_left(range(m * n), k, key=lambda x: x // n * n + sum(x // i for i in range(x // n + 1, m + 1)))

🛠 bisect.bisect_left(a, x, lo=0, hi=len(a), **, key=None*)

Locate the insertion point for x in a to maintain sorted order.

The returned insertion point i partitions the array a into two halves so that all(val < x for val in a[lo : i]) for the left side and all(val >= x for val in a[i : hi]) for the right side.

  • 理解: 求a中某值使key(a)=x; 给了值域a, 逆映射key, 求接近x的自变量值

  • bisect_left和bisect_right有什么不同呢? 先给出When are bisect_left and bisect_right not equal?的一个修改后的例子如下:

When the target to locate is in the list, bisect_left, bisect_right return different result. For example:

1
2
3
4
bisect.bisect_left([4, 5, 6], 5)  # 1, a[:1]=[4]<5,  a[1:]=[5,6]>=5
bisect.bisect_right([4, 5, 6], 5)  # 2, a[:2]=[4,5]<=5, a[2:]=[6]>5
bisect.bisect_left([4, 5, 5 , 6], 5) # 1 
bisect.bisect_right([4, 5, 5, 6], 5)  # 3

​ 可以理解为输出了一种分割线, bisect_left选到了4.5, bisect_left选到了5.5, 差别在于分割线划在5的哪一边.

[Python/Java/JavaScript/Go] 二分 - Benhao

1
2
3
class Solution:  # 问题转化为: 有几个数<=x? 每行有min(n, x//i)个!
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        return bisect_left(range(m * n + 1), k, key=lambda x:sum(min(n, x // i) for i in range(1, m + 1))) if n >= m else self.findKthNumber(n, m, k)  # 交换行数，对小的行数统计二分值

二分查找时会遇到x为质数的情况, 其解释得很好:

有朋友可能问了，这个值域中还包括并不在乘法表中的质数呢？ 根据二段性，比这个质数小一点的乘法表中的数和这个质数，在这个乘法表中小于它的个数是一样的，我们会取左边界也就是乘法表里的数(这也是为啥Py里用bisect_left而不是bisect_right)。

  • 首先k一定在经过key映射后得列表里, 从上面bisect_left和bisect_right的分析来看, bisect_left可以输出恰好满足条件的位置, 即输出位置及大于其的所有乘法表中的数, 都满足<=其的数有>=k个

  • 举个例子: 对于乘法表[[1,2], [2,4]], 和k=3, 搜索范围为[1,2,3,4], 经过key映射后的范围为[1,3,3,4], 则bisect_left返回1, bisect_right返回3, 显然后者返回的是错的

  • 总结一下, 每个>2质数经过key映射后的值是和比其小1的偶数映射后的值相等的, 那么映射后的列表一定会出现连续重复的数, 因此必须要用bisect_left, 其能返回第一个重复数的位置, 而bisect_right返回的是最后重复数的位置+1.

💛 剑指 Offer 07. 重建二叉树

DC - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
# 观察下面的树, 其preorder为[1234567], inorder为[4251637], 考虑把根节点拿掉做递归.
#    1
#  2   3
# 4 5 6 7
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder: return None
        root = TreeNode(n := preorder[0])
        idx = inorder.index(n)
        root.left = self.buildTree(preorder[1:idx+1], inorder[:idx])
        root.right = self.buildTree(preorder[idx+1:], inorder[idx+1:])
        return root

💚 剑指 Offer 57. 和为s的两个数字

❗ Time Limit Exceeded - Carlos

1
2
3
4
5
6
7
class Solution:  # 遍历每个数, 然后二分找第二个数
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            temp = nums[:i] + nums[i+1:]
            second = bisect_left(temp, target - nums[i])
            if second < len(temp) and temp[second] == target - nums[i]:  # 第一个条件是为了防止二分超出索引限制
                return [nums[i], temp[second]]

面试题57. 和为 s 的两个数字（双指针 + 证明，清晰图解） - Krahets

1
2
3
4
5
6
7
8
9
class Solution:  # 对撞双指针
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        i, j = 0, len(nums) - 1
        while i < j:
            s = nums[i] + nums[j]
            if s > target: j -= 1
            elif s < target: i += 1
            else: return nums[i], nums[j]
        return []

💛 102. 二叉树的层序遍历

队列 - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:  # 写得难看的队列
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        visited = [root]  # 储存每层要扫的节点
        while visited and not all([_ is None for _ in visited]):
            temp = []
            result.append([_.val for _ in visited if _])
            for r in visited:
                if r:  # 这一步不能保证加入的不是None, 污染了visited!!
                    temp.append(r.left)
                    temp.append(r.right)
            visited = temp
        return result

ACM 选手图解 LeetCode 二叉树的层次遍历（递归 + 非递归）| 编程文青李狗蛋 - 编程文青李狗蛋

队列 (时On空On)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if　root == None: return []
        res = []
        queue = [root]
        while queue:
            res.append([node.val for node in queue])  # 存储当前层的孩子节点列表
            childNodes = []
            for node in queue:
                if node.left: childNodes.append(node.left)  # 若节点存在左孩子，入队
                if node.right: childNodes.append(node.right)  # 若节点存在右孩子，入队
            queue = childNodes  # 更新队列为下一层的节点，继续遍历
        return res

递归 (时On空On)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        def level(root: TreeNode, depth, res):
            if root == None: return  # 什么都不操作
            if len(res) < depth: res.append([])  # 若当前行对应的列表不存在，加一个空列表
            res[depth - 1].append(root.val)  # 将当前节点的值加入当前行的 res 中
            if root.left: level(root.left, depth + 1, res)  # 将左节点的值加入res中对应depth的子列表中
            if root.right: level(root.right, depth + 1, res)  # 将右节点的值加入res中对应depth的子列表中
        res = []
        level(root, 1, res)
        return res

💚 101. 对称二叉树

❗ Wrong Answer - Carlos

1
2
3
4
5
6
class Solution:  # 面试时写的错误方法, 对于非对称二叉树[1,2,2,2,null,2]会返回True
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def traverse(root, mode):
            if not root: return []
            return traverse(root.left, mode) + [root.val] + traverse(root.right, mode) if mode else traverse(root.right, mode) + [root.val] + traverse(root.left, mode)
        return True if traverse(root, 0) == traverse(root, 1) else False

Stack - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root: return True
        lefts, rights = [root.left], [root.right]
        while lefts and rights:
            left, right = lefts.pop(), rights.pop()  # pop出末尾元素, 这是把list当堆栈了
            if left is None and right is None: continue  # 扫到了两个叶子
            if left is None or right is None: return False  # 发现形状不对称
            if left.val != right.val: return False  # 发现值不对称
            lefts.append(left.left)
            rights.append(right.right)
            lefts.append(left.right)
            rights.append(right.left)
        return True

动画演示+多种实现 101. 对称二叉树 - 王尼玛

1
2
3
4
5
6
7
8
9
class Solution:  # 递归
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root: return True
        def f(left, right):
            if left is None and right is None: return True
            if left is None or right is None: return False
            if left.val != right.val: return False
            return f(left.left, right.right) and f(left.right, right.left)
        return f(root.left, root.right)

💛 462. 最少移动次数使数组元素相等 II

Median - Carlos

1
2
3
4
5
class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums = sorted(nums)  # 输入是无序的, 排序后方便取中位数
        mid = nums[len(nums) // 2]
        return sum(abs(_ - mid) for _ in nums)

[Python/Java/JavaScript/Go] 中位数

1
2
3
class Solution:  # 强行一行
    def minMoves2(self, nums: List[int]) -> int:
        return sum(abs(mid - num) for num in nums) if (mid := sorted(nums)[len(nums) // 2]) != inf else inf

💛 436. 寻找右区间

sorted + bisect - Carlos

1
2
3
4
5
6
7
8
class Solution:  # 思路与Benhao一致
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        temp = sorted([(_[0], i) for i, _ in enumerate(intervals)], key=lambda x: x[0])  # 储存区间的左端点
        result = []
        for interval in intervals:
            idx = bisect_left(temp, interval[1], key=lambda x: x[0])  # 在temp里二分找目标区间右端点的位置
            result.append(temp[idx][1] if idx < len(temp) else -1)  # 若找不到, 即没有区间的左端点比目标区间的右端点大, 即输出-1
        return result
1
2
3
class Solution:  # 一行版
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        return [temp[idx][1] if (idx := bisect_left(temp, interval[1], key=lambda x: x[0])) < len(temp) else -1 for interval in intervals] if (temp := sorted([(_[0], i) for i, _ in enumerate(intervals)], key=lambda x: x[0])) else None  # 注意使用:=的语句一定要用括号括起来

💚 961. 在长度 2N 的数组中找出重复 N 次的元素

Counter - Carlos

1
2
3
class Solution:  # 暴力使用Counter
    def repeatedNTimes(self, nums: List[int]) -> int:
        return list(counter.keys())[list(counter.values()).index(len(nums) // 2)] if (counter:= Counter(nums)) else -1

在长度 2N 的数组中找出重复 N 次的元素 - 力扣官方题解

方法一: 哈希表 (时On空On)

1
2
3
4
5
6
7
8
class Solution:  # 时间复杂度O(n), 空间复杂度O(n)
    def repeatedNTimes(self, nums: List[int]) -> int:
        found = set()  # 利用2n的列表里有n个相同的数, n+1个不同的数的性质, 维护一个已查看的集合
        for num in nums:
            if num in found:
                return num
            found.add(num)
		return -1

🌟 方法二: 数学 (时On空O1)

设所求为x, 假设相同的x间间隔至少为2, 则数组长度至少为3n-2, 当n>2时不存在这样的数组, 因此当n>2时必有两个x其间隔至多为1, 因此先检查n=2时头尾为x的特殊情况, 其余只需遍历每个元素并判断该元素和之后的两个元素是否相等, 若相等则输出. (代码见[Python/Java/JavaScript/Go] 抽屉原理 - Benhao)

1
2
3
4
5
6
7
8
class Solution:  # 时间复杂度O(n), 空间复杂度O(1)
    def repeatedNTimes(self, nums: List[int]) -> int:
        if nums[0] == nums[3]:  # 处理n=2的特殊情况
            return nums[0]
        for i, num in enumerate(nums):
            if nums[i + 1] == num or nums[i + 2] == num:  # 检查其后间隔为0和1的元素
                return num
        return -1

🌟 方法三: 随机选择 (时O1空O1)

随机选择到两个相同元素的概率为\(n(n-1)/(2n)^2=(n-1)/(4n)\rightarrow 0.25\), 因此期望选4次结束.

1
2
3
4
5
6
7
class Solution:  # 时间复杂度O(1), 空间复杂度O(1)
    def repeatedNTimes(self, nums: List[int]) -> int:
        n = len(nums)
        while True:
            x, y = random.randrange(n), random.randrange(n)
            if x != y and nums[x] == nums[y]:
                return nums[x]

💛 464. 我能赢吗

此题让人联想到一个图论问题: 交替选择无向图顶点, 第一个人有得胜策略当且仅当该图中无完美匹配, 见北京大学图论习题课 - 习题13.5

❗ Time Limit Exceeded - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:  # 遍历我的选择, 再遍历对手选择, 之后递归我的选择, 只有遍历对手选择我全能获胜才返回True 
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        def f(nums, total):
            if len(nums) == 0: return False  # 无数字可选
            if total <= 0: return True  # 在上一步已经被对手选光了
            if len(nums) == 1:
                if nums[0] >= total: return True
                else: return False
            for n in nums:  # 我选择了数字n
                nums2 = [_ for _ in nums if _ != n]
                total2 = total - n
                if total2 <= 0: return True  # 我选择后胜出
                count = 0
                for m in nums2:  # 对手选择了数字m
                    nums3 = [_ for _ in nums2 if _ != m]
                    total3 = total2 - m
                    if total3 <= 0: break  # 对手选择后胜出
                    if f(nums3, total3): count += 1
                else:
                    if count == len(nums2): return True
            return False
        return f(list(range(1, maxChoosableInteger + 1)), desiredTotal)

🌟 我能赢吗 - 力扣官方题解

1
2
3
4
5
6
7
8
9
10
class Solution:  # 记忆化搜索 + 状态压缩
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        @cache
        def dfs(usedNumbers: int, currentTotal: int) -> bool:  # usedNumbers的二进制第n位代表n+1是否被选择
            for i in range(maxChoosableInteger):
                if (usedNumbers >> i) & 1 == 0:  # 右侧抹掉i个数, 检查第i+1个数是否可以被选择, 若尚未选择, 进入下个if
                    if currentTotal + i + 1 >= desiredTotal or not dfs(usedNumbers | (1 << i), currentTotal + i + 1):  # 刚才检查的位置右侧有i个数, 现在把1的右侧加i个数, 作为dfs的第一项输入
                        return True
            return False
        return (1 + maxChoosableInteger) * maxChoosableInteger // 2 >= desiredTotal and dfs(0, 0)

🛠 functools.cache

Simple lightweight unbounded function cache. Sometimes called “memoize”.

  • 可减少递归函数的调用次数, 官方示例很清晰

🛠 Bitwise Operators in Python

img img img img
img img img img
img img

🎯 第 294 场周赛 - 普渡机器人

12 / 18, 2024 / 6640.

💚 2278. 字母在字符串中的百分比

1
2
3
class Solution(object):
    def percentageLetter(self, s, letter):
        return int(Counter(s)[letter] / len(s) * 100)

💛 2279. 装满石头的背包的最大数量

1
2
3
4
5
6
7
8
9
class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        temp = sorted([capacity[_] - rocks[_] for _ in range(len(capacity))])
        count, rock_sum = 0, 0
        while count < len(capacity):
            rock_sum += temp[count]
            if rock_sum <= additionalRocks: count += 1
            else: break
        return count

💛 2280. 表示一个折线图的最少线段数

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:  # 避免使用除法, 否则因为误差会出错
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        length = len(stockPrices)
        if length == 1: return 0
        stockPrices = sorted(stockPrices, key=lambda x: x[0])
        p0, p1 = stockPrices[0], stockPrices[1]
        count = 1
        for i in range(2, length):
            p2 = stockPrices[i]
            if (p1[1] - p0[1]) * p2[0] + p0[1] * p1[0] != (p1[0] - p0[0]) * p2[1] + p0[0] * p1[1]:
                count += 1
            p0, p1 = p1, p2
        return count

❤ ==2281. 巫师的总力量和== - TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def totalStrength(self, strength: List[int]) -> int:
        summation_dict = {(_, _ + 1): strength[_] for _ in range(len(strength))}
        minimum_dict = {(_, _ + 1): strength[_] for _ in range(len(strength))}
        result = 0
        for l in range(1, len(strength) + 1):
            for i in range(len(strength) - l + 1):
                temp = strength[i: i+l]
                if (i, i + l) in summation_dict:
                    temp_sum = summation_dict[(i, i + l)]
                    temp_min = minimum_dict[(i, i + l)]
                else:
                    if (i + 1, i + l) in summation_dict:
                        temp_sum = summation_dict[(i + 1, i + l)] + strength[i]
                        temp_min = min(minimum_dict[(i + 1, i + l)], strength[i])
                    elif (i, i + l - 1) in summation_dict:
                        temp_sum = summation_dict[(i, i + l - 1)] + strength[i + l - 1]
                        temp_min = min(minimum_dict[(i, i + l - 1)], strength[i + l - 1])
                    else:
                        assert False, (i, i + l, summation_dict)
                    summation_dict[(i, i + l)] = temp_sum
                    minimum_dict[(i, i + l)] = temp_min
                result += temp_min * temp_sum
        return result % (1000000007)

❤ 675. 为高尔夫比赛砍树 ==学习BFS的写法, 延用贪吃蛇的思路复杂度高==

❗ Time Limit Error - Carlos

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
38
39
40
41
42
import numpy as np
class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        forest = np.array(forest)
        m, n = forest.shape
        def f(p1, p2):  # 返回p1到p2的最短路程, 采用的是两头探索的方法, 实际上最好应该用A*算法
            if p1 == p2: return 0  # 处理自(0, 0)出发, 而第一颗树也在(0, 0)的特殊情况, 否则会返回2
            p2d1, p2d2 = {p1: 0}, {p2: 0}  # position to distance, 储存所有已经探索过的点到始点的最短距离
            last1, last2 = [p1], [p2]  # 维护上一步探索的节点
            while last1 and last2:
                temp1 = []
                for x_, y_ in last1:
                    for x, y in [(x_ + 1, y_), (x_ - 1, y_), (x_, y_ + 1), (x_, y_ - 1)]:
                        if 0 <= x < m and 0 <= y < n and forest[x, y] and (x, y) not in p2d1 and (x, y) not in temp1:  # 遍历每个待探索点的4邻域, 要满足其索引合法, 没有障碍物, 且未探索过, 且temp不能重复
                            p2d1[(x, y)] = p2d1[last1[0]] + 1
                            temp1.append((x, y))
                last1 = temp1
                for p in last1:  # 第一次检查, 思考p1和p2距离为1的情况, last1更新好后刚好盖到p2
                    if p in last2:
                        return p2d1[p] + p2d2[p]
                temp2 = []
                for x_, y_ in last2:
                    for x, y in [(x_ + 1, y_), (x_ - 1, y_), (x_, y_ + 1), (x_, y_ - 1)]:
                        if 0 <= x < m and 0 <= y < n and forest[x, y] and (x, y) not in p2d2 and (x, y) not in temp2:
                            p2d2[(x, y)] = p2d2[last2[0]] + 1
                            temp2.append((x, y))
                last2 = temp2
                for p in last1:  # 第二次检查, 思考p1和p2距离为2的情况, last2更新好后刚好盖到更新后的last1
                    if p in last2: return p2d1[p] + p2d2[p]
            return -1
        
        tree_idxes = np.where(forest > 0)
        sorted_idxes = sorted(np.array(tree_idxes).T, key=lambda x: forest[x[0], x[1]])  # e.g. [array([0, 0]), array([0, 1]), ..., array([2, 2])]
        sorted_idxes = [(0, 0)] + [(_[0], _[1]) for _ in sorted_idxes]
        result = 0
        for i in range(len(sorted_idxes) - 1):
            x1, y1 = sorted_idxes[i]
            x2, y2 = sorted_idxes[i + 1]
            temp = f((x1, y1), (x2, y2))
            if temp == -1: return -1
            result += temp
        return result

[Python/Java/JavaScript/Go] BFS or A*

💚 965. 单值二叉树

Traverse - Carlos

1
2
3
4
5
6
7
8
class Solution:
    def isUnivalTree(self, root: TreeNode) -> bool:
        if not root or root.left == root.right == None: return True
        if self.isUnivalTree(root.left) and self.isUnivalTree(root.right):
            if root.left and root.right: return root.val == root.left.val == root.right.val
            if root.left: return root.val == root.left.val
            return root.val == root.right.val
        return False

[Python/Java/TypeScript/Go] 模拟 - Benhao

1
2
3
4
5
6
class Solution:  # dfs
    def isUnivalTree(self, root: TreeNode) -> bool:
        v = root.val  # !! 这一步省去了判断两个孩子节点时, 要判断两个孩子节点的值是否相同
        def dfs(node):  # 首先判断当前点的值是否是v, 随后分别判断两个孩子节点, 分别判断是也会各判断孩子节点的值是否是v
            return node is None or (node.val == v and dfs(node.left) and dfs(node.right))
        return dfs(root)
1
2
3
4
5
6
7
8
9
class Solution:  # 迭代器写法, 前中后序的遍历输出可以参照这种方式写出
    def isUnivalTree(self, root: TreeNode) -> bool:
        v = root.val
        def dfs(node):
            if node:
                yield node.val
                yield from dfs(node.left)
                yield from dfs(node.right)
        return all(v == other for other in dfs(root))

🛠Yield expressions

What does the "yield" keyword do?: 从易到难, 逻辑清晰的迭代器解释

In practice, what are the main uses for the "yield from" syntax in Python 3.3?: What yield from does is it establishes a transparent bidirectional connection between the caller and the sub-generator. (yield from的作用是它在调用者和子生成器之间建立一个透明的双向连接.)

💛 467. 环绕字符串中唯一的子字符串

❗ Wrong Answer - Carlos

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:  # 对于长度超过26个的字符, 会无法去重, 返回(len(p)+1)*len(p)//2
    def findSubstringInWraproundString(self, p: str) -> int:
        s1, s2 = 'abcdefghijklmnopqrstuvwxyz', 'bcdefghijklmnopqrstuvwxyza'
        d = {s1[_]: s2[_] for _ in range(26)}
        d[' '] = None
        count, ctn_count = 0, 0
        last = ' '
        mem, seen = [], set()
        for curr in p + ' ':
            if curr != d[last]:
                if curr in seen:  # 维护seen是为了防止重复计数, 如"zaba", 因为看过"a", 就会跳过
                    continue
                if (last, ctn_count) not in mem:  # 维护mem是为了防止重复计数, 如"abab", 因为算过"ab", 就会跳过
                    count += (ctn_count + 1) * ctn_count // 2
                    mem.append((last, ctn_count))
                    print((last, ctn_count), d[last], curr, mem, seen)
                ctn_count = 1
            else: 
                ctn_count += 1
            seen.add(curr)
            last = curr
        return count
# input: "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd"
# output: 1596 (expected: 1131)
# stdout:
# (' ', 0) None a [(' ', 0)] set()
# ('d', 56) e   [(' ', 0), ('d', 56)] {'a', 'g', 'b', 'w', 't', 'q', 'l', 'n', 'u', 'f', 'p', 'o', 'x', 'y', 'z', 'j', 'e', 'v', 'h', 'c', 'd', 'k', 'r', 'i', 'm', 's'}

[Python/Java/JavaScript/Go] 动态规划 - Benhao

1
2
3
4
5
6
7
8
9
class Solution:  # 维护以每个字符结尾的最长子串长度
    def findSubstringInWraproundString(self, p: str) -> int:
        dp, cur = [0] * 26, 1
        dp[ord(p[0]) - ord('a')] = 1  # 初始化, 第一个字符结尾的子串长度为1
        for c1, c2 in pairwise(p):
            if not (ord(c2) - ord(c1) - 1) % 26: cur += 1  # 注意循环字符串的处理方式
            else: cur = 1
            dp[idx] = max(dp[idx := ord(c2) - ord('a')], cur)
        return sum(dp)

❤ 699. 掉落的方块

❗ Time Limit Error - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:  # 对与过大的方块, 阶梯函数的求最大和更新太慢
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        max_len = max(_[0] + _[1] for _ in positions)
        f = [0] * max_len  # step function (阶梯函数)
        result, max_height = [], 0
        for x, l  in positions:
            idxes = range(x, x + l)  # 加入方块后, 会影响的区间
            max_f = max(f[_] for _ in idxes)  # 找该区间内阶梯函数的最大值
            for idx in idxes: f[idx] = max_f + l  # 更新阶梯函数
            max_height = max(max_f + l, max_height)  # 找阶梯函数的全局最大值
            result.append(max_height)
        return result

掉落的方块 - 力扣官方题解

方法一: 暴力枚举 (时O2空O1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        n = len(positions)
        heights = [0] * n
        for i, (left1, side1) in enumerate(positions):
            right1 = left1 + side1  # left和right分别是正方形边缘在数轴上对应的坐标
            heights[i] = side1  # 初始化高度为自己的高度
            for j in range(i):  # 遍历之前放下的每个方块
                left2, right2 = positions[j][0], positions[j][0] + positions[j][1]
                if right1 > left2 and right2 > left1:  # 若相交, 注意取等号时是正好放下的情况
                    heights[i] = max(heights[i], heights[j] + side1)  # 若重叠有多个方块, 要逐个检查
        for i in range(1, n):  # 之前算的是放下所在区间的局部高度, 要对前面所有方块的高度取最大
            heights[i] = max(heights[i], heights[i - 1])  # !! 注意只需对前一个取最大
        return heights

方法二: 有序集合 (时Onlogn空On)

💛 面试题 17.11. 单词距离

Dict - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:  # 创建一个字典储存每个单词出现的位置, 然后做一个二重循环查找最小距离
    def findClosest(self, words: List[str], word1: str, word2: str) -> int:
        temp = dict()
        for i, _ in enumerate(words):
            if _ in temp:
                temp[_].append(i)
            else:
                temp[_] = [i]
        result = len(words)
        for i in temp[word1]:
            for j in temp[word2]:
                if abs(i - j) < result:
                    result = abs(i - j)
        return result

[Python/Java/TypeScript/Go] 模拟

1
2
3
4
5
6
7
8
9
10
class Solution:  # 对每个字符串依次存储他们的全部坐标即可反复比较不同的单词的距离
    def findClosest(self, words: List[str], word1: str, word2: str) -> int:
        ans, idx1, idx2 = inf, inf, -inf
        for i, word in enumerate(words):
            if word1 == word:
                idx1 = i
            elif word2 == word:
                idx2 = i
            ans = min(ans, abs(idx1 - idx2))
        return ans

💚 1021. 删除最外层的括号

Loop - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        result = ''
        start, temp = 0, 0  # start表明是否将正在检查的字符加入result, temp用来检查待打印的括号是否匹配
        for i, _ in enumerate(s):
            if start == 0 and _ == '(':  # 表明开始打印后续的字符
                start = 1
            else:
                if temp == 0 and _ == ')':  # 表明结束打印, 初始化start
                    start = 0
                    continue
                if _ == '(':
                    result += _
                    temp += 1
                elif _ == ')':
                    result += _
                    temp -= 1
        return result

删除最外层的括号

方法一: 栈 (时On空On)

1
2
3
4
5
6
7
8
class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        res, stack = "", []  # stack至多只有一个字符'('
        for c in s:
            if c == ')': stack.pop()  # 让stack空, 停止输出
            if stack: res += c
            if c == '(': stack.append(c)  # 让stack非空知道有匹配的)
        return res

方法二: 计数 (时On空On)

1
2
3
4
5
6
7
8
class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        res, level = "", 0
        for c in s:
            if c == ')': level -= 1
            if level: res += c
            if c == '(': level += 1
        return res

🎯 第 79 场双周赛 - 极氪智能科技

12 / 18, 824 / 4250.

💚 2283. 判断一个数的数字计数是否等于数位的值

1
2
3
4
5
6
7
class Solution:
    def digitCount(self, num: str) -> bool:
        temp = Counter(num)
        for i, n in enumerate(num):
            if not int(n) == temp[str(i)]:
                return False
        return True

## 💛 2284. 最多单词数的发件人

1
2
3
4
5
6
7
class Solution:
    def largestWordCount(self, messages: List[str], senders: List[str]) -> str:
        d = {s:0 for s in senders[::-1]}
        for i, s in enumerate(senders):
            d[s] += len(messages[i].split())
        targets = [k for k, v in d.items() if v == max(d.values())]
        return max(targets)

💛 2285. 道路的最大总重要性

1
2
3
4
5
6
7
8
class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        degrees = [0] * n
        for x, y in roads:
            degrees[x] += 1
            degrees[y] += 1
        degrees = sorted(degrees)
        return sum((_ + 1) * degrees[_]  for _ in range(n))

❤ ==2286. 以组为单位订音乐会的门票== - TLE

🎯 第 295 场周赛 - 博乐科技

7 / 18, 815 / 6447.

💚 2287. 重排字符形成目标字符串

1
2
3
4
5
class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        temp1 = Counter(s)
        temp2 = Counter(target)
        return min(temp1[_] // temp2[_] for _ in target)

💛 2288. 价格减免

1
2
3
4
5
6
7
8
9
class Solution:
    def discountPrices(self, sentence: str, discount: int) -> str:
        temp = sentence.split()
        result = deque()
        for s in temp:
            if s[0] == '$' and s[1:].isdigit():
                result.append('${:.2f}'.format(int(s[1:]) * (100 - discount) / 100))
            else: result.append(s)
        return ' '.join(result)

💛 ==2289. 使数组按非递减顺序排列== - WA

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:  # 大数后升序子序列长度的最大值
    def totalSteps(self, nums: List[int]) -> int:
        idx = 0
        d = {idx: 0}
        for i, n in enumerate(nums):
            if n < nums[idx] and (i == idx + 1 or i - 1 >= 0 and nums[i - 1] <= n):
                d[idx] = d[idx] + 1  # 大条件第一个是保证后面的子序列都严格比其小; 子条件里第一个条件是保证处理到大数后升序的首个数字, 第二个是保证子序列是升序的
                if not (i + 1 < len(nums) and nums[i + 1] < n):
                    continue
            idx = i
            d[idx] = 0
        return max(d.values())

题意为删去降序数字对中的后者.对于实例[7,14,4,14,13,2,6,13], 第一轮变为[7,14,14,6,13], 第二轮变为[7, 14, 14, 13], 第三轮变为[7, 14, 14], 由元素14产生的删去是13, 6 和13, 这是我算法的核心观察没有考虑到的情况.

❤❗ ==2290. 到达角落需要移除障碍物的最小数目==

💛 468. 验证IP地址

Simulation - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:  # 蠢蠢地判断就行了
    def validIPAddress(self, queryIP: str) -> str:
        ipv4 = queryIP.split('.')
        if len(ipv4) == 4:
            for s in ipv4:  # 单0或无前导0要求, 范围要求
                if not (s == '0' or s.isdigit() and s[0] != '0' and 0 <= int(s) <= 255):
                    break
            else:
                return 'IPv4'
        ipv6 = queryIP.split(':')
        o1 = (ord('0') + ord('9')) / 2
        o2 = (ord('a') + ord('f')) / 2
        o3 = (ord('A') + ord('F')) / 2
        if len(ipv6) == 8:
            for s in ipv6:  # 长度要求, 范围要求
                if not (1 <= len(s) <= 4 and all(abs(ord(t) - o1) < 5 or abs(ord(t) - o2) < 3 or abs(ord(t) - o3) < 3 for t in s)):
                    break
            else:
                return 'IPv6'
        return 'Neither'

💚 1022. 从根到叶的二进制数之和

❗ Wrong Answer - Carlos

1
2
3
4
5
6
7
8
9
class Solution:  # 递归
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        def f(r):  # 返回子树二进制数之和, 已经所有叶子的深度
            if not r: return 0, []  # 空树, 和为0, 没有叶子
            sum_left, depths_left = f(r.left) if root.left else (0, [])
            sum_right, depths_right = f(r.right) if root.right else (0, [])
            depths = [_ + 1 for _ in depths_left + depths_right]  # 所有叶子深度加1, 为了计算r对应其的权重
            return (sum_left + sum_right + r.val * sum(2 ** _ for _ in depths), depths) if depths else (r.val, depths + [0])  # 若非叶子, 三部分求和; 若是叶子, 只有自身的值, 是深度为0的叶子
        return f(root)[0]

实例61/63[1,null,0,0,1,1,null,1,null,null,1,null,0,null,1], 我的算法给出答案为5, 答案为61, 疑惑这个实例看上去不是一个二叉树, 不知道答案是怎么得到的.

从根到叶的二进制数之和

方法一: 递归 (时On空On)

方法二: 迭代 (时On空On)

❤❗ 剑指 Offer II 114. 外星文字典

外星文字典

方法一: 拓扑排序 + 深度优先搜索

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
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # input: ["wrt","wrf","er","ett","rftt"], output: "wertf"
        g = {}
        for c in words[0]:
            g[c] = []  # 初始化第一个word
        for s, t in pairwise(words):
            for c in t:
                g.setdefault(c, [])  # 初始化后len(words)-1个word
                # In Python Dictionary, setdefault() method returns the value of a key (if the key is in dictionary). If not, it inserts key with a value to the dictionary.
            for u, v in zip(s, t):
                # 注意zip对长度不一word的效果, s=wrf, t=er, list(zip(s, t))=[('w', 'e'), ('r', 'r')]
                if u != v:  # 字典排序依据1是第一个不同的字幕
                    g[u].append(v)  # 有向边u→v
                    break
            else:
                if len(s) > len(t):  # 字典排序依据2是长度, 短的要排在前面
                    return ""
        # g为{'w': ['e'], 'r': ['t'], 't': ['f'], 'f': [], 'e': ['r']}, g至多有len(words)-1条边
        VISITING, VISITED = 1, 2
        states = {}
        order = []
        def dfs(u: str) -> bool:
            states[u] = VISITING
            for v in g[u]:
                if v not in states:  # 深度优先
                    if not dfs(v):
                        return False
                elif states[v] == VISITING:  # 有圈
                    return False
                # else, v状态为VISITED, 不做任何操作
            order.append(u)  
            states[u] = VISITED  # u的所有邻居都是VISITED, 此时把u置为VISITED
            return True
        return ''.join(reversed(order)) if all(dfs(u) for u in g if u not in states) else ""

方法二: 拓扑排序 + 广度优先搜索

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
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # input: ["ac","ab","zc","zb"], output: "aczb"
        g = defaultdict(list)  # 有向图的邻接表
        inDeg = {c: 0 for c in words[0]}  # 每个顶点的入度, 顺序是重要的!
        for s, t in pairwise(words):
            for c in t:
                inDeg.setdefault(c, 0)  # ~~inDeg为0的节点不唯一时, 如何保证入队列顶点顺序的正确性? 观察inDeg计算方式, 考察边u→v时, 只有v的入度可能变大, 因此前面的点更可能为度0点, 因此inDeg初始化方式为从左到右扫视所有words, 能保证结果的正确性~~
                # ~~再观察一个我构造的实例["abc", "dcb", "dbc"], 有意先按顺序扫视abc, 但实际上c是排在b后面的, 期望输出为"acbd", 而g为{'a': 0, 'b': 1, 'c': 0, 'd': 1}, q为['a', 'c'], 可以看到, b根本不出现在q中~~
                # inDeg的顺序和结果无关!!
            for u, v in zip(s, t):
                if u != v:
                    g[u].append(v)
                    inDeg[v] += 1
                    break
            else:
                if len(s) > len(t):
                    return ""
        q = [u for u, d in inDeg.items() if d == 0] # len(q)不一定为1, 如input为["z","x","z"]时q为[]
        # g为{'c': ['b', 'b'], 'a': ['z']}), 有多重边!, q为['a', 'c']
        print(g)
        print(q)
        print(inDeg)
        for u in q:
            for v in g[u]:
                inDeg[v] -= 1  # 删除边u→v, 更新入度
                if inDeg[v] == 0:
                    q.append(v)
                    print(v)
        return ''.join(q) if len(q) == len(inDeg) else ""
        # 对于实例["ozvcdpgfq","mridvkklqj","dpwecbwor","xxtistijm","xxuon","tudbazpggu","hnuumktbjy","bogbcoi"], 预期结果为"acefgijklnomdpqrsvwxthbuyz", 输出为"ozvcpgfqrikljwesnaymdxtuhb" (也是正确的, 其只是在q的基础上加了mdxtuhb)
        # g为{'o': ['m'], 'm': ['d'], 'd': ['x'], 't': ['u', 'h'], 'x': ['t'], 'h': ['b']}, 
        # inDeg为{'o': 0, 'z': 0, 'v': 0, 'c': 0, 'd': 1, 'p': 0, 'g': 0, 'f': 0, 'q': 0, 'm': 1, 'r': 0, 'i': 0, 'k': 0, 'l': 0, 'j': 0, 'w': 0, 'e': 0, 'b': 1, 'x': 1, 't': 1, 's': 0, 'u': 1, 'n': 0, 'a': 0, 'h': 1, 'y': 0}
        # q为['o', 'z', 'v', 'c', 'p', 'g', 'f', 'q', 'r', 'i', 'k', 'l', 'j', 'w', 'e', 's', 'n', 'a', 'y'], q的顺序是可以调换的!!
        # bfs时, 当u为t时, 依次删去边t→u和边t→h, 使得u和h的入度依次变为0, 这里u和h的顺序是可以调换的!