做网站哪家好,附近电子商城,网站建设没付尾款,discuz门户论坛模板1. 树的先序遍历可以求高度#xff0c;后序遍历可以求深度。剑指 Offer 55 - II. 平衡二叉树leetcode-cn.com2. 二叉搜索树的中序遍历可以递增地返回所有元素。逆序的中序遍历#xff08;即先右子节点#xff0c;再根节点#xff0c;再左子节点#xff09;可以递减的返回…1. 树的先序遍历可以求高度后序遍历可以求深度。剑指 Offer 55 - II. 平衡二叉树leetcode-cn.com2. 二叉搜索树的中序遍历可以递增地返回所有元素。逆序的中序遍历即先右子节点再根节点再左子节点可以递减的返回所有元素。3. python 的字典就是非常好的哈希工具。get 方法可以写参数当默认值常用计数 dic.get(ch, 0) 14. 求质数比较快的方法 筛法isPrime [True] * (n 1) # 1, 2, ..., nisPrime[1] Falseidx 2while idx n:if isPrime[idx]:i idxwhile idx * i n:isPrime[idx * i] Falsei 1idx 15. python 快速排序实现可以更简洁思路更清楚class Solution:def quickSort(self, A, left, right):if left right:pos self.partition(A, left, right)self.quickSort(A, left, pos-1)self.quickSort(A, pos1, right)def partition(self, A, left, right):i, j left, rightwhile i j:while i j and A[j] A[left]: j - 1while i j and A[i] A[left]: i 1A[i], A[j] A[j], A[i]A[i], A[left] A[left], A[i]return i6. python 归并排序
def mergeSort(A, left, right):pass
def merge(A, left, mid, right): [left, mid] [mid1, right]pass观察最外层递归
[3, 2, 4, 5, 7, 1, 9]0 1 2 3 4 5 6 left 0 right 6, mid 3, mergeSort(A, 0, 3), mergeSort(A, 4, 6) merge(A, left 0, mid 3, right 6)[2, 3, 4, 5, 1, 7, 9]0 1 2 3 4 5 6 A[left], ..., A[mid] 序列 和 A[mid1], ..., A[right]观察最内层递归
mergeSort(A, left 2, right 3):if left right: Truemid 2mergeSort(A, left 2, mid 2)mergeSort(A, left mid 1 3, right 3)merge(A, left 2, mid 2, right 3)
def mergeSort(A, left, right):if left right:mid (left right) // 2mergeSort(A, left, mid)mergeSort(A, mid1, right)merge(A, left, mid, right)def merge(A, left, mid, right):i, j left, mid 1 # 合并 A[left], ..., A[mid] 序列 和 A[mid1], ..., A[right] 序列temp []while i mid and j right:if A[i] A[j]:temp.append(A[i])i 1else:temp.append(A[j])j 1while i mid:temp.append(A[i])i 1while j right:temp.append(A[j])j 1for i in range(len(temp)):A[lefti] temp[i]L [4,2,1,5,3,2,1]
mergeSort(L, 0, len(L)-1)7. python oj 处理标准输入 What does Pythons eval() do?示例1输入: [flower,flow,flight]
输出: flL list(map(lambda x: x.strip(), input().strip([]).split(,)))
? [flower,flow,flight]L[flower, flow, flight]示例2输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
def merge(self, intervals: List[List[int]]) - List[List[int]]: L eval(input())
? [[1,3],[2,6],[8,10],[15,18]]L[[1, 3], [2, 6], [8, 10], [15, 18]]8. 二叉树遍历的迭代算法# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right None前序遍历class Solution:def preorderTraversal(self, root: TreeNode) - List[int]:res []stack []cur rootwhile stack or cur:while cur:res.append(cur.val)stack.append(cur)cur cur.lefttop stack.pop()cur top.rightreturn res后序遍历class Solution:def postorderTraversal(self, root: TreeNode) - List[int]:res []stack []cur rootwhile stack or cur:while cur:res.append(cur.val)stack.append(cur)cur cur.righttop stack.pop()cur top.leftreturn res[::-1]中序遍历class Solution:def inorderTraversal(self, root: TreeNode) - List[int]:res []stack []cur rootwhile stack or cur:while cur:stack.append(cur)cur cur.lefttop stack.pop() #此时左子树遍历完成res.append(top.val) #将父节点加入列表cur top.right #遍历右子树return res9. BFSimport collections
graph {A: [B, C],B: [A, C, D],C: [A, B, D, E],D: [B, C, E, F],E: [C, D],F: [D]
}# 最初版本 BFS
def BFS(graph, s):queue collections.deque()queue.append(s)seen set()seen.add(s)while queue:vertex queue.popleft()nodes graph[vertex]for w in nodes:if w not in seen:queue.append(w)seen.add(w)print(vertex)BFS(graph, A) # ABCDEF
print(---------------)# DFS 迭代实现
def DFS(graph, s):stack []stack.append(s)seen set()seen.add(s)while stack:vertex stack.pop()nodes graph[vertex]for w in nodes:if w not in seen:stack.append(w)seen.add(w)print(vertex)
DFS(graph, A) # ACEDFB# BFS 打印路径
def BFS(graph, s):queue collections.deque()queue.append(s)seen set()seen.add(s)parent {s: None}while queue:vertex queue.popleft()nodes graph[vertex]for w in nodes:if w not in seen:queue.append(w)seen.add(w)parent[w] vertex# print(vertex)return parentparent BFS(graph, A)
v F
while v ! None:print(v)v parent[v]
# F D B A10. 并查集 # 对于一维输入
# https://leetcode-cn.com/problems/paths-with-sum-lcci/
class UF:def __init__(self, n):self.rank [0 for _ in range(n)] # 代表树的高度用来将树平衡self.up [i for i in range(n)]def find(self, x):if self.up[x] x:return xelse:self.up[x] self.find(self.up[x])return self.up[x]def union(self, x1, x2):r1 self.find(x1)r2 self.find(x2)if r1 r2:returnif self.rank[r1] self.rank[r2]:self.rank[r1] 1self.up[r2] r1elif self.rank[r1] self.rank[r2]:self.up[r2] r1else:self.up[r1] r2# 对于二维输入
# https://leetcode-cn.com/problems/number-of-islands/
class UnionFind:def __init__(self, grid: List[List[str]]):m, n len(grid), len(grid[0])self.count 0self.parent [-1] * (m * n)self.rank [0] * (m * n)for i in range(m):for j in range(n):if grid[i][j] 1:self.parent[i * n j] i * n jdef find(self, i):if self.parent[i] ! i:self.parent[i] self.find(self.parent[i])return self.parent[i]def union(self, x, y):rootx self.find(x)rooty self.find(y)if rootx ! rooty:if self.rank[rootx] self.rank[rooty]:rootx, rooty rooty, rootxself.parent[rooty] rootxif self.rank[rootx] self.rank[rooty]:self.rank[rootx] 111. DFS中序遍历树结构并时刻比较先后访问的节点。注意在什么位置更新上一个访问的节点 preNode。就是什么时候按照中序遍历中间访问到了新的值什么时候更新。# https://leetcode-cn.com/problems/recover-binary-search-tree/solution/zhong-xu-bian-li-by-powcai/
# 恢复二叉树
class TreeNode:def __init__(self, x):self.val xself.left Noneself.right Noneclass Solution:def __init__():self.preNode Nonedef InOrderTravalsal(root):if not root:returnInOrderTravalsal(root.left)# 把 root.val 和 self.pre.val 进行一些比较# ...# 就在这更新刚刚 preNode. 因为访问下一个节点也一定是在递归函数的这个位置self.preNode rootInOrderTravalsal(root.right)
