面试准备:数据结构

发表于

数学基础

  1. 斯特林公式
    • n! = sqrt(2PIn) * (n/e)^n
  2. 卡特兰数
    • 递归式1：h(n) = h(0)h(n-1) + h(1)h(n-2) + … + h(n-1)h(0), h(0) = h(1) = 1
    • 递归式2：h(n) = (4(n-2)/(n+1)) * h(n-1)
    • 解为：
      • Cn = C(2n, n) / (n+1) = (2n)! / (n!*(n+1)!)
      • Cn = C(2n, n) - C(2n , n+1)
      • C0 = 1 and Cn+1 = sum(Ci*Cn-i), i from 0 to n
    • 性质：
      • 所有的奇数卡特兰数Cn都满足n = 2^k - 1
    • 前几项：
      • 1,1,2,5,14,42,132,429,…
    • 应用场景：
      • 1.括号化问题
        • 矩阵连乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)
      • 2.出栈次序问题。
        • 一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
        • 类似：
          • (1)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
          • (2)在圆上选择2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数。
      • 3.将多边行划分为三角形问题。
        • 将一个凸多边形区域分成三角形区域的方法数?
        • 类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
        • 类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
      • 4.给顶节点组成二叉树的问题。
        • 给定N个节点，能构成多少种形状不同的二叉树？(一定是二叉树!
        • 先去一个点作为顶点,然后左边依次可以取0至N-1个相对应的,右边是N-1到0个,两两配对相乘,就是h(0)h(n-1) + h(2)h(n-2) + … + h(n-1)h(0)=h(n))
        • 答：能构成h（N）个

  3. 数组array

链表Linked List

  • 定义：

    • 1
      2
      3
      class ListNode(val):
      	self.val = val
      	self.next = None

  • 分类：

  • 典型问题：

    1. 求单链表长度:

      • 比较简单，但需要一开始就养成链表为空判断的习惯。
        1
        2
        3
        4
        5
        6
        7
        8
        9
        def getLinkListLength(head):
        	if None == head:
        		return 0
        	p = head
        	length = 0
        	while p:
        		length += 1
        		p = p.next
        	return length

    2. 翻转链表：

      • 两种都行
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        def reverseLinkList(head):
        	if None == head or None == head.next:
        		return head
        	p = head
        	pre = None
        	while p:
        		# 法一：保存p
        		#cur = p
        		#p = p.next
        		#cur.next = pre
        		#pre = cur
        		# 法二：保存p.next
        		next = p.next
        		p.next = pre
        		pre = p
        		p = next
        	return pre

    3. 返回单链表倒数第k个节点

    • 思路：快慢指针，fast先走k次，然后slow和fast一起走，fast到达终点则slow为倒数第k个节点。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      def findLastKthNode(head, k):
      	if None == head or 0 == k:
      		return None
      	fast, slow = head, head
      	for i in range(k):
      		fast = fast.next
      	if None == fast:
      		return None
      	while fast:
      		slow = slow.next
      		fast = fast.next
      	return slow
    1. 查找中间节点
    • 思路：快慢指针，和上面类似
      1
      2
      3
      4
      5
      6
      7
      8
      def getMiddleNode(head):
      	if None == head or None.next == None:
      		return head
      	slow, fast = head, head
      	while fast.next:
      		slow = slow.next
      		fast = fast.next.next
      	return slow

    1. 判断两个链表是否相交

      • 思路：两个链表分别遍历，判断尾节点是否相等
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        def isIntersect(head1, head2):
        	# 应该先判断是否有环，
        	# 一个有环一个无环，return False
        	# 两个都有环：判断交叉点
        	# 两个都无环：判断尾节点
        	p1, p2 = head1, head2
        	while p1.next:
        		p1 = p1.next
        	while p2.next:
        		p2 = p2.next
        	return p1 == p2

    2. 求两个单链表相交的第一个节点

      • 思路：先求出两个链表的长度，然后让长链表的head先走长度之差，再一起往前走，直到相等
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        def getIntersectPoint(head1, head2):
        	p1, p2 = head1, head2
        	length1 = length2 = 0
        	while p1:
        		length1 += 1
        		p1 = p1.next
        	while p2:
        		length2 += 1
        		p2 = p2.next
        	p1, p2 = head1, head2
        	if length1 > length2:
        		for i in range(length1 - length2):
        			p1 = p1.next
        	else:
        		for i in range(length2 - length1):
        			p2 = p2.next
        	while p1 != p2:
        		p1 = p1.next
        		p2 = p2.next
        	return p1

    3. 判断是否有环：

    • 思路：快慢指针，fast前进2步，slow每次前进1步，这样如果有环最终fast和slow会相遇一次，没环则fast到达终点。
    • 证明为什么有环必相遇：
      • 方法一：
        • 哲学法：运动是相对的，从slow看，也就是slow静止，fast相当于是每次前进一步，则两者必然相遇
      • 方法二：
        • 等价法：设环长度为L步，head到环入口点距离a，当slow从入口点处开始继续走x步的时候，假设两者相遇，则有：
        • slow:a+x -> a + x%L
        • fast:2(a+x) -> a + (a+2x)%L
        • 两者相遇等价于a + x%L == a + (a+2x)%L
        • 根据求余%的可加性，等价于(a+x)%L==0有解
        • 等价于a+x = nL
        • 存在整数x，满足x = nL - a
        • 所以两者可以相遇
      • 方法三：
        • 数学归纳法：
        • ①slow与fast差1步：那么slow继续走1，fast继续走2，则两者相遇
        • ②slow与fast差2步：那么slow继续走1，fast继续走2，则转化为问题①，两者相遇
        • ③假设slow与fast差n-1步时，两者相遇
        • ④当slow与fast差n步时，slow走1，fast走2，进一步转化为问题③，两者相遇
        • 综上，两者相遇
    • 证明为什么有环必相遇于slow的第一圈内：
      • 方法一：
        • 哲学法：运动是相对的，从slow角度看，当slow处于环的入口点时，fast处于环上的某一点，slow不动，相当于fast在追赶slow直到入口点相遇，所以fast需要跑的步数m在0-L之间，也即在slow再走m步，不到L步之内就相遇了。
      • 方法二：
        • 数学归纳法：
        • 由上一个问题的数归法，可得，slow与fast差n步时，再走n步即相遇，而两者在圈内的距离是小于L的，so证毕
          1
          2
          3
          4
          5
          6
          7
          8
          def hasCycle(head):
          	slow = fast = head
          	while fast and fast.next:
          		slow = slow.next
          		fast = fast.next.next
          		if fast == slow:
          			return True
          	return False

    1. 取出环的入口点：

      • 思路：快慢指针，slow每次1，fast每次2，当两者相遇后，slow继续每次1，同时fast置位head，从头开始每次1步，当两者再次相遇时，就是入口点
      • 证明：
        • head -> 入口点 -> 第一次相遇点
        • 设head到入口点距离为a，环长为L，入口点到第一次相遇点距离b，fast已经走了n圈
        • 2(a+b) = a+b + nL
        • a = nL - b = (n-1)L + L - b
        • 所以，当fast从head出发到入口点时，走了a，slow继续从第一次相遇点也走了a=L-b+(n-1)L（多走了n-1圈）
        • 所以他们在入口点处相遇。
          1
          2
          3
          4
          5
          6
          7
          8
          9
          10
          11
          12
          13
          14
          15
          16
          17
          18
          def getCycleStart(head):
          	slow = fast = head
          	if None == head or None == head.next:
          		return None

          	while fast and fast.next:
          		slow = slow.next
          		fast = fast.next.next
          		if None == slow or None == fast:
          			return None
          		if slow == fast:
          			break
          	fast = head
          	while fast and slow:
          		if fast == slow:
          			return slow
          		fast = fast.next
          		slow = slow.next

    2. 合并两个有序链表：

      • 思路：直接迭代或者递归都可以
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        def merge2Lists(self, head1, head2):  # leetcode类方法
        	# 法一：迭代
        	p1, p2 = head1, head2
        	dummy = ListNode(0)
        	p = dummy
        	while p1 and p2:
        		if p1.val < p2.val:
        			p.next = p1
        			p1 = p1.next
        		else:
        			p.next = p2
        			p2 = p2.next
        		p = p.next
        	p.next = p1 if p1 else p2  # 简写为p.next = p1 or p2
        	return dummy.next
        	# 法二：递归
        	if not p1 or not p2:
        		return p1 or p2  
        	if p1.val < p2.val:
        		p1.next = self.merge2Lists(p1.next, p2)
        		return p1
        	else:
        		p2.next = self.merge2Lists(p1, p2.next)
        		return p2

    3. 合并k个有序链表：

      • 思路：二分法
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        def mergeKLists(self, lists):  # leetcode类方法
        	if len(lists) < 1:
        		return None
        	return self.helper(lists, 0, len(lists) - 1)

        	def helper(self, lists, left, right):
        		if left < right:
        			mid = left + (right - left) // 2
        			return self.merge2Lists(self.helper(lists, left, mid), 
        				self.helper(lists, mid + 1, right))
        		return lists[left]

    4. 删除链表中的重复元素：输入：12234，输出134

      • 思路：递归；指针
        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
        def deleteDuplication(self, head):
        	# 法0：如果是输入12234，输出1234
        	if not head or not head.next: return head
        	p = head
        	while p.next:
        		if p.val == p.next.val:
        		    p.next = p.next.next
        		else:
        			p = p.next
        	return head

        	# 法一：递归法
        	if head == None or head.next == None: return head
        	# 1.处理重复节点
        	if head.val == head.next.val:
        		cur = head.next.next
        		while cur != None and head.val == cur.val:
        			cur = cur.next
        		return self.deleteDuplication(cur)
        	# 2.处理非重复节点
        	cur = head.next
        	head.next = self.deleteDuplication(cur)
        	return head

        	# 法二：指针
        	dummy = ListNode(0)
            dummy.next = pHead
            pre, cur = dummy, pHead
            while cur:
            	while cur.next != None and cur.val == cur.next.val:
            		cur = cur.next
            	if pre.next == cur:
            		pre = cur
            		cur = cur.next
            	else:
            		cur = cur.next
            		pre.next = cur
            return dummy.next

            # 法三：hash表统计次数

树Tree

  1. Tree

    • 定义：一种抽象数据类型ADT，用来模拟具有树状结构的数据集和。
    • 概念：（以下基数为1,基数为1时树的深度=树的高度=最大层数）
      • 节点的深度：对于任意节点n，n的深度为从根到n的唯一路径长，根的深度为1
      • 节点的高度：对于任意节点n，n的高度为从n到一片树叶的最长路径长，所有树叶的高度为1
      • 节点的层次：从根开始为第一层，以此类推
      • 节点的度：一个节点含有的子树的个数称为该节点的度
      • 树的度：一棵树中，最大的节点的度称为树的度
      • 叶节点或终端节点：度为零的节点
      • 非终端节点或分支节点：度不为零的节点
      • 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
      • 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点
      • 兄弟节点：具有相同父节点的节点互称为兄弟节点
      • 堂兄弟节点：父节点在同一层的节点互为堂兄弟
      • 节点的祖先：从根到该节点所经分支上的所有节点
      • 子孙：以某节点为根的子树中任意节点都称为该节点的子孙
      • 森林：由m棵互不相交的树的集合
    • 特性：
    • 分类：
      • 无序树：树中任意节点的子节点之间没有顺序关系，也称为自由树
      • 有序树：树中任意节点的子节点之间又顺序关系
        • 二叉树：每个节点最多含有两个子树的树
        • 完全二叉树：对于一颗二叉树，假设深度为d(d>1)，除了第d层外，其它各层的节点数目均已达到最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树称为完全二叉树
        • 满二叉树：所有叶子节点都在最底层的完全二叉树
        • 平衡二叉树AVL：当且仅当任何节点的两棵子树的高度差不大于1的二叉树
        • 二叉查找树：树中的每个节点，它的左子树中所有项小于x中的项，他的右子树中的所有项都大于x中的项
        • 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树
        • B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。
    • 实现：
      • 定义：
        1
        2
        3
        4
        5
        class TreeNode(object):
        	def __init__(self, val=None, left=None, right=None):
        		self.val = val
        		self.left = left
        		self.right = right

  2. 二叉树

    • 定义：二叉树的每个节点最多只有二棵子树，二叉树的子树有左右之分，次序不能颠倒
    • 性质：
      • 第i层至多有2^(i-1)个节点
      • 深度为k的二叉树至多有2^k-1个节点，k>=1，最少有k个节点
      • 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
      • 具有n个节点的完全二叉树的深度为log2(n+1)
      • 给定n个节点，能构成h(n)种不同的二叉树，其中h(n)为卡特兰数的第n项，h(n) = C(2n, n) / (n+1)
      • 设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2^i。
    • 遍历分类：
      • 深度优先DFS：
        • 先序、中序、后序
        • 递归方法+用栈实现的迭代方法
      • 广度优先BFS：
        • 层次遍历
        • 递归方法+队列实现的迭代方法
    • 实现：
      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
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      113
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      126
      127
      128
      129
      130
      131
      132
      133
      134
      135
      136
      137
      138
      139
      140
      141
      142
      143
      144
      145
      146
      147
      148
      149
      150
      151
      152
      153
      154
      155
      156
      157
      158
      159
      160
      161
      162
      163
      164
      165
      166
      167
      168
      169
      170
      171
      172
      173
      174
      175
      176
      177
      178
      179
      180
      181
      182
      183
      184
      185
      186
      187
      188
      189
      190
      191
      192
      193
      194
      195
      196
      197
      198
      199
      200
      201
      202
      203
      204
      205
      206
      207
      208
      209
      210
      211
      212
      213
      214
      215
      216
      217
      218
      219
      220
      221
      222
      223
      224
      225
      226
      227
      228
      229
      230
      231
      232
      233
      234
      235
      236
      237
      238
      239
      240
      241
      242
      243
      244
      245
      246
      247
      248
      249
      250
      251
      252
      253
      254
      255
      256
      257
      258
      259
      260
      261
      262
      263
      264
      265
      266
      267
      268
      269
      270
      271
      272
      273
      274
      275
      276
      277
      278
      279
      280
      281
      282
      283
      class binary_tree(object):
      	def __init__(self):
      		self.root = TreeNode()

      	def isEmpty(self):
      		if self.root.val == None:
      			return True
      		else:
      			return False
      	# 1. 插入
      	def add(self, data):
      		node = TreeNode(data)
      		if self.isEmpty():
      			self.root = node
      		else:
      			treeNode = self.root
      			queue = []
      			queue.append(self.root)
      			while queue:
      				treeNode = queue.pop(0)
      				if treeNode.left == None:
      					treeNode.left = node
      					return
      				elif treeNode.right == None:
      					treeNode.right = node
      					return 
      				else:
      					queue.append(treeNode.left)
      					queue.append(treeNode.right)
      	# 2. 先序遍历
      	def pre_order(self, start):
      		if start == None:
      			return start
      		print(start.val)			# 根
      		self.pre_order(start.left)	# 左
      		self.pre_order(start.right) # 右
          # 3. 中序遍历
          # 3.1 递归
          def in_order(self, start):
              if start == None:
                  return None
              self.in_order(start.left)      # 左
              print(start.val)                # 根
              self.in_order(start.right)     # 右
          # 3.2 迭代
          def in_order_2_stack(self, root):
              # 思路：栈来模拟递归的过程，用栈的方法，顺序保存，过程中维护一个node表示当前走到的结点（不是中序遍历的那个结点）
              # 算法时间复杂度也是O(n)，空间复杂度是栈的大小O(logn)
              list_ = []
              stack_ = []
              while root or len(stack_) >= 1:
                  if root:
                      stack_.append(root)
                      root = root.left
                  else:
                      root = stack_.pop(-1)
                      list_.append(root.val)
                      root = root.right
              return list_
          # 3.3 高大上法 Morris Traversal
         	def in_order_morris(self, root):
              # 思路：充分利用叶子节点的空指针，增加叶子的指针，添加前驱节点的right指针保存root，用O(1)的空间复杂度来代替递归/迭代
              cur = root
              while cur:
                  if cur.left == None: 
                      list_.append(cur.val)  # 左
                      cur = cur.right
                  else:
                      predecessor = cur.left
                      while predecessor.right and predecessor.right != cur:  # 注意两个条件，直到cur.left的最右叶子节点位置，!=cur是防止死循环
                          predecessor = predecessor.right
                      if predecessor.right == None:  # a
                          predecessor.right = cur    # 利用叶子节点的空节点来保存root
                          cur = cur.left 			   # 保存了root后，开始进一步遍历左子树
                      if predecessor.right == cur:   # b.恢复原树结构
                          predecessor.right = None
                          list_.append(cur.val)      # 根节点val
                          cur = cur.right       	   # 到此处时，左子树已经遍历完毕，开始遍历右子树
              return list_

          # 4. 后序遍历
          def post_order(self, start):
              if start == None:
                  return
              self.post_order(start.left)     # 左
              self.post_order(start.right)    # 右
              print(start.val)                # 根
          # 5. 层次遍历1
          def level_order(self, start):
          	if start == None:
          		return
          	else:
          		queue = []
          		queue.append(start)
          		while len(queue) >= 1:
          			front = queue.pop(0)
          			if front.left != None:
          				queue.append(front.left)
          			if front.right != None:
          				queue.append(front.right)
          			print(front.val)
          # 6. 层次 - 遍历保存每层val
          def save_level_order(self, start):
          	# 法一：迭代
              res_ = []
              cur = 0  # 这次用的双指针 进行层次遍历
              end = 1
              if start == None: return None
              queue = [start]
              while cur < len(queue):  # 外循环，无法添加更多node，最终截止，
                  temp = []
                  while cur < end:
                  	front = queue[cur]
                      if front.left != None:
                          queue.append(front.left)
                      if front.right != None:
                          queue.append(front.right)
                      temp.append(front.val)
                      cur += 1
                  end = len(queue)
                  res_.append(temp)  # temp保存每层的值，res_为最终结果
              return res_
              # 法二：递归
              res = []
              def helper(root, level):
              	if not root: return 
              	if level == len(res): res.append([])
              	res[level].append(root.val)
              	helper(root.left, level+1)
              	helper(root.right, level+1)
              helper(root, 0)
              return res



          # 7. 树 的合并
          def mergeTrees(self, t1, t2):
          	# 法一：递归
          	if t1 == None: return t2
          	if t2 == None: return t1
          	t1.val += t2.val
          	t1.left = self.mergeTrees(t1.left, t2.left)
          	t1.right = self.mergeTrees(t1.right, t2.right)
          	return t1

          	# 法二：迭代
          	if t1 == None: return t2
          	if t2 == None: return t1
          	stack = []
          	stack.append((t1, t2))
          	while len(stack):
                  s1,s2 = stack.pop()
                  if not s1 or not s2 :
                      continue 
                  s1.val += s2.val
                  if not s1.left:
                      s1.left = s2.left
                  else:
                      stack.append((s1.left, s2.left))
                  
                  if not s1.right:
                       s1.right = s2.right
                  else:
                       stack.append((s1.right, s2.right))
                       
              return t1

          # 8. 树 的深度
          def maxDepth(root):
          	# 法一：递归
          	def helper(root):
          		if not root: return 0
          		return max(helper(root.left), helper(root.right)) + 1

          # 9. 树 的翻转invert
          def invertTree(root):
          	def helper(root):
          		if not root: return root
          		left = helper(root.left)
          		root.left = helper(root.right)
          		root.right = left
          		return root
          	return helper(root)

          # 10. 530. Minimum Absolute Difference in BST求最小的差
          def getMinimumDifference(self, root):
              # 树的遍历方式：
              # 1. 深度：前中后
              # 2. 广度：层次
              # 方法：中序遍历，因为是BST所以是有序的，也就是左-根-右的顺序保存，
              # 左-根-右。。。
              # 根-右。。。
              # 取正好差一个的顺序的差，也就是每两个node之间的差
              # 取最小值，所以是 abs(根-左子树的右) < abs(根 - 左子树的root)
              min_ = -1
              def dfs(node, l=[]):  
                  if node.left: dfs(node.left, l) 
                  l.append(node.val) # 中序遍历
                  if node.right: dfs(node.right, l)
                  return l
              l = dfs(root)
              return min([abs(a-b) for a,b in zip(l, l[1:])])
          # 11. 114. Flatten Binary Tree to Linked List将二叉树转成链表
          def flatten(self, root):
          	# 实现一：树的先序遍历
          	self.pre = None
          	def dfs(root):
          	    if root==None: return
          	    root_right = root.right
          	    if self.pre != None:
          	    	self.pre.left = None
          	    	self.pre.right = root
          	    self.pre = root
          	    dfs(root.left)
          	    dfs(root_right)
         		dfs(root)
         		# 实现二：
         		def helper(self, root):
         			if not root: return 
         			helper(root.right)
         			helper(root.left)
         			root.right = self.pre
         			root.left = None
         			self.pre = root

         	# 12. 538. Convert BST to Greater Tree变成大的树
         	def convertBST(self, root):
         		self.sum = 0
         		def convert(root):
         		    if root:
         		        if root.right: convert(root.right) # 右
         		        root.val += self.sum # 中
         		        self.sum = root.val
         		        if root.left: convert(root.left) # 左
         		    return root

          # 13. 543. Diameter of Binary Tree
          def diameterOfBinaryTree(self, root):
              self.res = 0
              def dfs(root):
                  if root == None: return 0
                  left, right = dfs(root.left), dfs(root.right)
                  self.res = max(self.res, left+right)
                  return max(left, right) + 1
              dfs(root) 
              return self.res

          # 14. 572. Subtree of Another Tree
          def isSubtree(self, s, t):
              def isSame(s, t):
                  if s == None and t == None: return True
                  if s == None or t == None: return False
                  if s.val != t.val: return False
                  return isSame(s.left, t.left) and isSame(s.right, t.right)
              if s == None: return False
              if isSame(s, t):
                  return True
              return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

          # 235. Lowest Common Ancestor of a Binary Search Tree
          def lowestCommonAncestor(self, root, p, q):
          	# 思路：最低公共祖先
          	# 法一：递归
          	if (root.val - p.val) * (root.val - q.val) <= 0: return root
          	if root.val > p.val: # 一定也大于q.val
          		return self.lowestCommonAncestor(root.left, p, q)
          	if root.val < p.val:
          		return self.lowestCommonAncestor(root.right, p, q)
          	# 法二：迭代
          	while (root.val - p.val) * (root.val - q.val) > 0:
          		if root.val > p.val:
          			root = root.left
          		elif root.val < p.val:
          			root = root.right
          	return root

          # 236. Lowest Common Ancestor of a Binary Tree
          def lowestCommonAncestor(self, root, p, q):
          	# 思路：如果左右子树同时存在，则返回root；否则返回左或右子树
          	if root in (p, q, None): return root
          	left = self.lowestCommonAncestor(root.left, p, q)
          	right = self.lowestCommonAncestor(root.right, p, q)
          	return root if left and right else left or right

  3. 满二叉树和完全二叉树：

    • 定义：除最后一层无任何子节点外，每层上的所有节点都有两个子节点。
    • 性质：
      • 一棵树深度为h，最大层数为k，深度与最大层数相同，k=h
      • 叶子数为2^h
      • 第k层的节点数是：2^(k-1)
      • 总结点数是：2^(k-1)，且总结点数一定是奇数。
    • 完全二叉树定义：设二叉树深度为h，除第h层外，其他各层（1-(h-1)层）的节点数都达到最大个数，第h层所有节点都连续集中在最左边，就是完全二叉树
    • 性质：
      • 完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。
  4. 二叉搜索树BST
    • 定义：二叉排序树Binary Sort Tree
      • 若左子树不为空，则左子树上所有节点的值均小于它的根节点的值
      • 若右子树不为空，则右子树上所有节点的志军大于或等于他的根节点的值
      • 左右子树也分别是二叉排序树
      • 没有键值相等的节点
    • 性质：
      • 对二叉搜索树进行中序遍历，即可得到有序的数列
      • 二叉搜索树的时间复杂度：
        • 和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度
        • 原因：在插入和删除元素的时候，树没有保持平衡
        • 说明：但是我们追求的是在最坏的情况下，仍然有较好的时间复杂度，这也就是平衡查找树设计的初衷
      • 二叉查找树的高度决定了二叉查找树的查找效率
    • 实现：
      • 插入：
        • 若当前的二叉查找树为空，则插入的元素为根节点
        • 若插入的元素值小于根节点值，则将元素插入到左子树中
        • 若插入的元素值不小于根节点值，则将元素插入到右子树中
      • 删除：
        • p为叶子节点，直接删除该节点，再修改其父节点的指针
        • p为单支节点(即只有左子树或右子树),让p的子树与p的父节点相连，删除p即可
        • p的左子树和右子树均不空：找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点称为y的右子树的父亲节点，并用y的值代替p的值；或者方法二是找到p的前驱x，x一定没有右子树，所以可以删除x，并让x的父节点成为y的左子树的父节点
  5. 平衡搜索树AVL：
    • 定义：
      • 背景：
        • 一般的二叉搜索树BST，其期望高度是log2n，其各项操作的时间复杂度O(log2n)同时也由此而决定，但是在某些极端情况下，比如插入的序列是有序的，此时二叉搜索树就退化为链，此时的时间复杂度将退化为线性O(n)。
        • 可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。于是就有了平衡二叉树。
      • 又被称为AVL树（有别于AVL算法）
    • 性质：
      • 一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
      • 最小二叉平衡树的节点的公式：
        • F(n)=F(n-1)+F(n-2)+1
      • 时间复杂度：
        • 查找、插入和删除在平均和最坏情况下都是O(logn)。
        • 增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。
        • 但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
    • 实现：
      • 插入
      • 删除
      • 旋转：
        • AVL树的自平衡操作
        • 单旋转：
          • 左左 和 右右
        • 双旋转：
          • 左右 和 右左
  6. 平衡二叉树红黑树RBT
    • 定义：红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组，最早称为：对称二叉B树
    • 性质：
      • 1节点是红色或黑色
      • 2根是黑色
      • 3所有叶子节点都是黑色（NIL）
      • 4每个红色节点必须有两个黑色的子节点
      • (从每个叶子节点到根的所有路径上不能有两个连续的红色节点)
      • 5从任意节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
      • 推出结论：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长
    • 时间复杂度：
      • 它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。
    • 实现：
      • 插入
      • 删除
      • 颜色变更：O(log(n))
  7. B-树
    • 定义：
      • B树也是一种用于查找的平衡树，但不是二叉树，能够用来存储排序后的数据
      • B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。
      • 与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。
      • 1) 定义任意非叶子结点最多只有M个儿子；且M>2；
      • 2) 根结点的儿子数为[2, M]；
      • 3) 除根结点以外的非叶子结点的儿子数为[M/2, M]；
      • 4) 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
      • 5) 非叶子结点的关键字个数=指向儿子的指针个数-1；
      • 6) 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
      • 7) 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
      • 8) 所有叶子结点位于同一层；
    • 性质：

H

  1. B+树
    • 定义：
      • B+树是B树的变体，也是一种多路搜索树：
      • 1) 其定义基本与B-树相同，除了：
      • 2) 非叶子结点的子树指针与关键字个数相同；
      • 3) 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
      • 4) 为所有叶子结点增加一个链指针；
      • 5) 所有关键字都在叶子结点出现；
    • 性质：
      • 1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
      • 2.不可能在非叶子结点命中；
      • 3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
      • 4.更适合文件索引系统。
    • 实现：
  2. B*树
    • 定义：
      • B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针，将结点的最低利用率从1/2提高到2/3。
    • 性质：
      • 特点：B*树分配新结点的概率比B+树要低，空间使用率更高。
    • 实现：
  3. 字典树Trie：字符串查找
    • 定义：
      • Tire树称为字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。
      • 来自retrieve， 读作：/traɪ/ “try”或者/tri:/ “tree”
      • 典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
    • 性质：
      • 1) 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
      • 2) 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
      • 3) 每个节点的所有子节点包含的字符都不相同。
    • 特点：
      • 如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。
      • 插入查找的复杂度为O(n)，n为字符串长度。
    • 优缺点：
      • 最大限度地减少无谓的字符串比较，查询效率比哈希表高。
      • 缺点就是空间开销大。
    • 应用：
      • 串的快速检索：
        • 给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
        • 在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。
      • 串的排序：给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出。用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。
      • 最长公共前缀：对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为求公共祖先的问题。
    • 实现：
    • LeetCode：
      • LeetCode：
        1. Implement Trie (Prefix Tree)这道题是实现一个前缀树，作为基础题啦
        2. Add and Search Word - Data structure design这道题是把前缀树做一个简单的变形
        3. Concatenated Words
        4. Word Search II
        5. Maximum XOR of Two Numbers in an Array
  4. 后缀树
  5. 广义后缀树

堆Heap

栈Stack

  1. 单调栈
    • 单调栈顾名思义就是让栈中的元素是单调的，要么递增，要么递减。同样它也满足栈的性质，先进后出。
    • 单调递增栈，则从栈顶到栈底的元素是严格递增的
    • 单调递减栈，则从栈顶到栈底的元素是严格递减的
    • google题目1：
      • 问题：给一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素（如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1）
      • 例子：
        • input: 5,3,1,2,4
        • return: -1 3 1 1 -1
      • 解决：
        • 建立一个单调递减栈stack
        • stack保存每个递减元素的下标
        • 5来了后，stack.push(0)
        • 3来了后，stack.push(1)
        • 1来了后，stack.push(2)
        • 2来了后，2 > input[stack.top()]，所以result[stack.top()] = 3-stack.top()=1,同时stack.pop(),stack.push(3)
        • 4来了后，4>input[stack.top()]，所以result[stack.top()] = 4-stack.top()=1,同时stack.pop()
          • 4>input[stack.top()],所以result[stack.top()] = 4-stack.top()=3,stack.pop()
        • 结束，result = [-1, 3, 1, 1, -1]

图论 Graph Theory

  • 定义：
    • 图结构：节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关
    • 树结构：数据元素之间存在明显的层次关系，每个元素只与上一层中的一个元素及下一层的多个元素有关
    • 线性结构：数据元素之间满足唯一的线性关系，每个元素只有一个直接前驱和一个直接后继
    • 图G由两个集合V(顶点Vertex)和E(边Edge)组成，定义为G=(V,E)
  • 概念：
    • 顶点的度：
      • 无向图：顶点的度表示该顶点作为一个端点的边的数目
      • 有向图：顶点的度分为入度和出度，入度表示以该顶点为终点的入边数目，出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和
      • 满足：边数e=sum(D(Vi)) / 2
  • 图的存储结构/表示图：
    • 邻接矩阵：
      • n个顶点，需要n*n的矩阵
      • 位置值表示是否相连/权重，位置值为0表示不相连
    • 邻接表：
      • 每个点存储一个链表，用来指向所有与该点直接相连的点
    • 特点：
      • 邻接矩阵浪费空间，但时间复杂度低；
      • 邻接表比较耗时，牺牲很大的时间来查找，因此比较耗时；
  • 图的遍历：
    • 深度优先遍历：Depth First Search，DFS
      • 空间复杂度O(V)
      • 时间复杂度：
        • 邻接表：O(V+E)
        • 邻接矩阵：O(V^2)
    • 广度优先遍历：Breadth First Search，BFS
      *
  • 最短路径：
  • 拓扑排序：Topological Sorting，是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。
    • 线性序列条件：
      • 每个顶点出现且只出现一次
      • 若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B的前面
    • 一个有向无环图可以有一个或多个拓扑排序序列
    • 方法：
      • 从DAG图中选择一个没有前驱(即入度为0)的顶点并输出
      • 从图中删除该顶点和所有以它为起点的有向边
      • 重复1和2，直到当前DAG图为空或当前图中不存在无前驱的顶点为止；后一种情况说明有向图中必然存在环
  • LeetCode
    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
    def canFinish(self, numCourses, prerequisites):
    	# 法一：递归DFS
    	graph = [[] for _ in xrange(numCourses)]
    	visit = [0 for _ in xrange(numCourses)]
    	for x, y in prerequisites:
    		graph[x].append(y)
    	def dfs(i):
    		if visit[i] == -1: return False # -1表示正在访问
    		if visit[i] == 1: return True # 1表示访问完了
    		visit[i] = -1
    		for j in graph[i]:
    			if not dfs(j): return False
    		visit[i] = 1
    		return True
    	for i in xrange(numCourses):
    		if not dfs(i):
    			return False
    	return True

    	# 法二：迭代DFS
    	graph = [[] for _in range(numCourses)]
    	visit = [0] * numCourses
    	for i, j in prerequisites:
    		graph[i].append(j)
    		visit[j] += 1  # 每个点的入度
    	queue = collections.deque()
    	for i in range(numCourses):
    		if visit[i] == 0:
    			queue.append(i)  # 将所有入度为0的顶点入队
    	k = 0	# 计数，记录当前已经输出的顶点数 
    	while queue:
    		node = queue.popleft()
    		k += 1
    		for i in graph[node]:
    			visit[i] -= 1
    			if visit[i] == 0:
    				queue.append(i)
    	return k == numCourses
thank you for donating~