defprint_circle(mx, rows, cols, start): cend = cols - 1 - start rend = rows - 1 - start for i in range(start, cend+1): print(mx[start][i]) for i in range(start+1, rend+1): print(mx[i][cend]) for i in reversed(range(start, cend)): print(mx[rend][i]) for i in reversed(range(start+1, rend)): print(mx[i][start])
从左到右和从上到下时应该没问题,可是最后两步的从右到左和从下到上就需要判断边界了。对于前者,要保证 start < rend,否则只有一行的矩阵就会有问题,因为 rend 和 start 都是 0,会重复打印;反之,后面这种情况则在只有一列的矩阵时有问题。修改后如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
defprint_circle(mx, rows, cols, start): cend = cols - 1 - start rend = rows - 1 - start for i in range(start, cend+1): print(mx[start][i]) for i in range(start+1, rend+1): print(mx[i][cend]) # 防止只有一行时打印 if rend > start: for i in reversed(range(start, cend)): print(mx[rend][i]) # 防止只有一列时打印 if cend > start: for i in reversed(range(start+1, rend)): print(mx[i][start])
defis_pop_order(push_order, pop_order): stack = [] for i in pop_order: if stack and stack[-1] == i: stack.pop() else: while push_order and push_order[0] != i: x = push_order.pop(0) stack.append(x) if push_order: push_order.pop(0) else: returnFalse returnTrue
defprint_tree(tree): queue = [tree] while queue: for i in range(len(queue)): node = queue.pop(0) print(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) print("\n")
defprint_tree(tree): queue = [tree] level = 0 while queue: level += 1 tmp = [] for i in range(len(queue)): node = queue.pop(0) if node.left: queue.append(node.left) if node.right: queue.append(node.right) if level % 2 == 0: tmp.reverse() # or tmp = reversed(tmp) if tmp: print(" ".join(tmp)) print("\n")
因此,我们可以将前 n 个比根节点小的当做左子树,后面的自然就是右子树。左右子树又可以用同样的方法确定。典型的递归操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
defis_postorder(lst): root = lst[-1] i = 0 for i in range(len(lst)): if lst[i] > root: break j = i for j in range(i, len(lst)): if lst[j] < root: returnFalse left, right = True, True if i > 0: left = is_postorder(lst[:i]) if j < len(lst) - 1: right = is_postorder(lst[j:-1]) return left and right
defclone_nodes(head): node = head while node: new = ComplexNode(node.val) new.next = node.next node.next = new node = new.next return head
defconnect_sibling_nodes(head): node = head while node: clone = node.next if node.sibling: clone.sibling = node.sibling.next node = clone.next return head
defconvert_bst_to_dll(tree): head = convert(tree, None) while head and head.next: head = head.left return head
defconvert(head, last): ifnot head: returnNone curr = head if curr.left: last = convert(curr.left, last) curr.left = last if last: last.right = curr last = curr if curr.right: last = convert(curr.right, last) return last
有几个点需要特别注意:
要记得从 right 的 last 回到 left,判断条件也要留心,既要 head 存在,也要 next 存在
defdeserialize(res): head = None val = res.pop(0) if val != "$": head = BSN(val) head.left = deserialize(res) head.right = deserialize(res) return head
# 出处:https://www.youtube.com/watch?v=KBHFyg2AcZ4 defpermutate(s, l, r, res) -> list: if l == r - 1: if s notin res: res.append(s) else: for i in range(l, r): lst = list(s) lst[i], lst[l] = lst[l], lst[i] permutate("".join(lst), l+1, r, res) lst[l], lst[i] = lst[i], lst[l] return res
defpermutate(s: str, moves: list, res: list): for i in range(len(s)): remain = s[0:i] + s[i+1:] moves.append(s[i]) if remain: permutate(remain, moves, res) else: res.append("".join(moves)) moves.pop() return res
此外还可以先生成所有的组合,然后剔除包含重复元素的:
1 2 3 4 5 6
defproduct(s, repeat): pools = [tuple(s)] * repeat result = [""] for pool in pools: result = [x+y for x in result for y in pool] return result
不过最简洁的方式当属下面这种,思想和上面的都差不多:
1 2 3 4 5 6 7 8
# 出处:https://www.youtube.com/watch?v=IPWmrjE1_MU defpermutate(prefix, suffix, res) -> list: ifnot suffix: res.append(prefix) else: for i in range(len(suffix)): permutate(prefix+suffix[i], suffix[:i]+suffix[i+1:], res) return res
最后再介绍一种相对容易理解的:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
# 出处:https://www.youtube.com/watch?v=hqijNdQTBH8 defpermutate6(s: str) -> list: lst = list(s) ifnot lst: return [] elif len(lst) == 1: return [lst] else: res = [] for i in range(len(lst)): head = lst[i] remain = lst[:i] + lst[i+1:] for p in permutate6(remain): res.append([head] + p) return res