Algorithm
本周选择的算法题是：Copy List with Random Pointer。
规则
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representingNode.valrandom_index: the index of the node (range from0ton-1) that therandompointer points to, ornullif it does not point to any node.
Your code will only be given the head of the original linked list.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
Example 4:
Input: head = []
Output: []
Explanation: The given linked list is empty (null pointer), so return null.
Constraints:
0 <= n <= 1000-10000 <= Node.val <= 10000Node.randomisnullor is pointing to some node in the linked list.
Solution
class Solution:
def copyRandomList(self, head):
cache = {}
def dfs(old):
if not old: return None
node = cache.get(old, Node(old.val))
if old not in cache:
cache[old] = node
node.next = dfs(old.next)
node.random = dfs(old.random)
return node
return dfs(head)
Review
| [Pattern matching tutorial for Pythonic code | Pydon’t](https://mathspp.com/blog/pydonts/pattern-matching-tutorial-for-pythonic-code) |
这篇文章详细介绍了 Python 3.10 的 match，我虽然是 Python 的重度用户，但还是被惊艳到了，接下来我们一起看看这些 Pythonic 的代码。
比较初级的，可以用 match 代替硬编码的 if：
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
factorial(5) # 120
替换为 match 后：
def factorial(n):
match n:
case 0 | 1:
return 1
case _:
return n * factorial(n - 1)
factorial(5) # 120
序列也不在话下：
def normalise_colour_info(colour):
"""Normalise colour info to (name, (r, g, b, alpha))."""
match colour:
case (r, g, b):
name = ""
a = 0
case (r, g, b, a):
name = ""
case (name, (r, g, b)):
a = 0
case (name, (r, g, b, a)):
pass
case _:
raise ValueError("Unknown colour info.")
return (name, (r, g, b, a))
print(normalise_colour_info((240, 248, 255))) # ('', (240, 248, 255, 0))
print(normalise_colour_info((240, 248, 255, 0))) # ('', (240, 248, 255, 0))
print(normalise_colour_info(("AliceBlue", (240, 248, 255)))) # ('AliceBlue', (240, 248, 255, 0))
print(normalise_colour_info(("AliceBlue", (240, 248, 255, 0.3)))) # ('AliceBlue', (240, 248, 255, 0.3))
还可以加上类型检查：
def normalise_colour_info(colour):
"""Normalise colour info to (name, (r, g, b, alpha))."""
match colour:
case (int(r), int(g), int(b)):
name = ""
a = 0
case (int(r), int(g), int(b), int(a)):
name = ""
case (str(name), (int(r), int(g), int(b))):
a = 0
case (str(name), (int(r), int(g), int(b), int(a))):
pass
case _:
raise ValueError("Unknown colour info.")
return (name, (r, g, b, a)))
print(normalise_colour_info(("AliceBlue", (240, 248, 255)))) # ('AliceBlue', (240, 248, 255, 0))
print(normalise_colour_info2(("Red", (255, 0, "0")))) # ValueError: Unknown colour info.
如果是自定义对象，可以通过 __match_args__ 支持 match：
class Point2D:
"""A class to represent points in a 2D space."""
__match_args__ = ["x", "y"]
def __init__(self, x, y):
self.x = x
self.y = y
def describe_point(point):
"""Write a human-readable description of the point position."""
match point:
case Point2D(0, 0):
desc = "at the origin"
case Point2D(0, y):
desc = f"in the vertical axis, at y = {y}"
case Point2D(x, 0):
desc = f"in the horizontal axis, at x = {x}"
case Point2D(x, y):
desc = f"at {point}"
return "The point is " + desc
print(describe_point(Point2D(0, 0))) # The point is at the origin
print(describe_point(Point2D(3, 0))) # The point is in the horizontal axis, at x = 3
print(describe_point(Point2D(1, 2))) # The point is at (1, 2)
字典的绝对匹配：
d = {0: "oi", 1: "uno"}
match d:
case {0: "oi"}:
print("yeah.")
# prints yeah.
模糊匹配：
d = {0: "oi", 1: "uno"}
match d:
case {0: "oi", **remainder}:
print(remainder)
# prints {1: 'uno'}
再看一个包含通配符号、条件 case 的复杂例子：
def rule_substitution(seq):
new_seq = []
while seq:
match seq:
case [x, y, z, *tail] if x == y == z:
new_seq.extend(["3", x])
case [x, y, *tail] if x == y:
new_seq.extend(["2", x])
case [x, *tail]:
new_seq.extend(["1", x])
seq = tail
return new_seq
seq = ["1"]
print(seq[0])
for _ in range(10):
seq = rule_substitution(seq)
print("".join(seq))
"""
Prints:
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
"""
总体来说，match 语法并不复杂，作为一个新功能，可以减化代码、提高阅读性。
Tip
找到了一种跳过 SSH 验证的远程执行方式，可以用于远程部署，需要 sshpass 结合 ssh 的 options 使用：
sshpass -p $PASSWORD ssh -o StrictHostKeyChecking=no -o UserKnownHostsFile=/dev/nul $HOST 'ls'
由于 sshpass 不安全，所以该方式只适合在内网小范围使用。
顺便给博客增加了一个自定义的 404 页面：测试链接。