提交20160725例题与课后作业

yingl · yingl · commit 4267a88e4c61 · 2016-07-26T11:32:24.000+08:00
diff --git a/binary_tree_inorder_traversal.py b/binary_tree_inorder_traversal.py
@@ -0,0 +1,17 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    def __init__(self):
+        self.ret = []
+
+    """
+    @param root: The root of binary tree.
+    @return: Preorder in ArrayList which contains node values.
+    """
+    def inorderTraversal(self, root):
+        # write your code here
+        if root is not None:
+            self.inorderTraversal(root.left)    # 遍历左子树
+            self.ret.append(root.val)
+            self.inorderTraversal(root.right)   # 遍历右子树
+        return self.ret
diff --git a/binary_tree_postorder_traversal.py b/binary_tree_postorder_traversal.py
@@ -0,0 +1,17 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    def __init__(self):
+        self.ret = []
+
+    """
+    @param root: The root of binary tree.
+    @return: Postorder in ArrayList which contains node values.
+    """
+    def postorderTraversal(self, root):
+        # write your code here
+        if root is not None:
+            self.postorderTraversal(root.left)    # 遍历左子树
+            self.postorderTraversal(root.right)   # 遍历右子树
+            self.values.ret(root.val)
+        return self.values
diff --git a/binary_tree_preorder_traversal.py b/binary_tree_preorder_traversal.py
@@ -0,0 +1,17 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    def __init__(self):
+        self.ret = []
+
+    """
+    @param root: The root of binary tree.
+    @return: Preorder in ArrayList which contains node values.
+    """
+    def preorderTraversal(self, root):
+        # write your code here
+        if root is not None:
+            self.ret.append(root.val)
+            self.preorderTraversal(root.left)
+            self.preorderTraversal(root.right)
+        return self.ret
diff --git a/binary_tree_serialization.py b/binary_tree_serialization.py
@@ -0,0 +1,63 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+
+    '''
+    @param root: An object of TreeNode, denote the root of the binary tree.
+    This method will be invoked first, you should design your own algorithm 
+    to serialize a binary tree which denote by a root node to a string which
+    can be easily deserialized by your own "deserialize" method later.
+    '''
+    def serialize(self, root):
+        # write your code here
+        # 分层遍历，子节点为空用#代替，最后清理尾部的所有#。
+        ret = []
+        if not root:
+            return ret
+        level = [root]
+        while level:
+            new_level = []
+            for node in level:
+                ret.append(str(node.val) if node else '#')
+                if node:
+                    new_level.append(node.left)
+                    new_level.append(node.right)
+            level = new_level
+        i = len(ret) - 1
+        while i >= 0:
+            if ret[i] == '#':
+                ret.pop()
+                i -= 1
+            else:
+                break
+        return ret
+
+    '''
+    @param data: A string serialized by your serialize method.
+    This method will be invoked second, the argument data is what exactly
+    you serialized at method "serialize", that means the data is not given by
+    system, it's given by your own serialize method. So the format of data is
+    designed by yourself, and deserialize it here as you serialize it in 
+    "serialize" method.
+    '''
+    def deserialize(self, data):
+        # write your code here
+        if not data:
+            return None
+        root = TreeNode(data[0])
+        level = [root]
+        i = 1
+        while i < len(data):
+            new_level = []
+            for node in level:
+                node.left = TreeNode(data[i]) if data[i] != '#' else None
+                if node.left:
+                    new_level.append(node.left)
+                i += 1
+                if i < len(data):
+                    node.right = TreeNode(data[i]) if data[i] != '#' else None
+                    if node.right:
+                        new_level.append(node.right)
+                    i += 1
+            level = new_level
+        return root
diff --git a/binary_tree_zigzag_level_order_traversal.py b/binary_tree_zigzag_level_order_traversal.py
@@ -0,0 +1,35 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    """
+    @param root: The root of binary tree.
+    @return: A list of list of integer include 
+             the zig zag level order traversal of its nodes' values
+    """
+    def zigzagLevelOrder(self, root):
+        # write your code here
+        ret = []
+        if not root:
+            return ret
+        level = [root]  # 当前遍历层
+        order = 1   # 顺序遍历
+        while level:
+            data = []
+            new_level = []  # 下一次循环遍历层
+            for node in level:
+                data.append(node.val)
+                if order == 1:  # 顺序的时候先访问左节点 
+                    if node.left:
+                        new_level.append(node.left)
+                    if node.right:
+                        new_level.append(node.right)
+                else:   # 逆序的时候先访问右节点
+                    if node.right:
+                        new_level.append(node.right)
+                    if node.left:
+                        new_level.append(node.left)
+            order *= -1 # 反转访问顺序
+            level = new_level
+            level.reverse() # 殷雯访问顺序反转，该层的数据也要反转。
+            ret.append(data)
+        return ret
diff --git a/flatten_binary_tree_to_linked_list.py b/flatten_binary_tree_to_linked_list.py
@@ -0,0 +1,30 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param root: a TreeNode, the root of the binary tree
+    # @return: nothing
+    def flatten(self, root):
+        # write your code here
+        if not root:
+            return None
+        head, tail = self.dfs(root)
+        return head
+
+    def dfs(self, root):
+        if not (root.left or root.right):
+            return root, root
+        head, tail = root, root
+        left_head, left_tail = None, None
+        right_head, right_tail = None, None
+        if root.left:
+            left_head, left_tail = self.dfs(root.left)  # 将左子树拆成链表
+        if root.right:
+            right_head, right_tail = self.dfs(root.right) # 将右子树拆成链表
+        if left_head: # 插入左子树拆成的链表
+            root.right = left_head
+            left_tail.right = right_head
+            tail = right_tail if right_tail else left_tail
+        else: # 没有左子树
+            tail = right_tail
+        head.left = None
+        return head, tail
diff --git a/heapify.py b/heapify.py
@@ -0,0 +1,25 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param A: Given an integer array
+    # @return: void
+    def heapify(self, A):
+        # write your code here
+        '''
+        为什么从1/2的位置从后往前遍历？
+        因为对于堆中下标为i的元素，子节点下标为i * 2 + 1和i * 2 + 2，
+        对于下标大于1/2位置的元素一定是叶子节点，无须做向下调整。
+        '''
+        for i in xrange((len(A) - 1) / 2, -1, -1):
+            while i < len(A):
+                left, right = i * 2 + 1, i * 2 + 2
+                min_pos = i
+                if (left < len(A)) and (A[left] < A[min_pos]):
+                    min_pos = left
+                if (right < len(A)) and (A[right] < A[min_pos]):
+                    min_pos = right
+                if min_pos != i:    # 调整A[i]元素位置，继续向下调整。
+                    A[i], A[min_pos] = A[min_pos], A[i]
+                    i = min_pos
+                else:   # min_pos没变，A[i]无须调整，结束循环。
+                    break
diff --git a/implement_trie.py b/implement_trie.py
@@ -0,0 +1,53 @@
+# -*- coding: utf-8 -*-
+
+class TrieNode:
+  def __init__(self):
+    # Initialize your data structure here.
+    self.map = {} # 记录后序某个字母是否出现
+    self.isLeaf = False
+
+class Trie:
+  def __init__(self):
+    self.root = TrieNode()  # 根节点
+
+  # @param {string} word
+  # @return {void}
+  # Inserts a word into the trie.
+  def insert(self, word):
+    root = self.root
+    for ch in word:
+      if ch not in root.map:
+          root.map[ch] = TrieNode() # ch出现并记录
+      root = root.map[ch]
+    root.isLeaf = True  # 该节点可以为叶子节点
+
+
+  # @param {string} word
+  # @return {boolean}
+  # Returns if the word is in the trie.
+  def search(self, word):
+    root = self.root
+    i = 0
+    for ch in word:
+      if ch not in root.map:  # 找不到匹配字符，直接返回False。
+        return False
+      else:
+        i += 1
+        if (i == len(word)) and root.map[ch].isLeaf:  # 判断是否最后一个字母且为叶子节点
+          return True
+        root = root.map[ch]
+    return False
+        
+
+  # @param {string} prefix
+  # @return {boolean}
+  # Returns if there is any word in the trie
+  # that starts with the given prefix.
+  def startsWith(self, prefix):
+    root = self.root
+    for ch in prefix:
+      if ch not in root.map:
+        return False
+      else:
+        root = root.map[ch]
+    return True
diff --git a/kth_smallest_number_in_sorted_matrix.py b/kth_smallest_number_in_sorted_matrix.py
@@ -0,0 +1,55 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param matrix: a matrix of integers
+    # @param k: an integer
+    # @return: the kth smallest number in the matrix
+    def kthSmallest(self, matrix, k):
+        # write your code here
+        heap = []
+        i = 0
+        while i < len(matrix):
+            j = 0
+            while j < len(matrix[0]):
+                if len(heap) < k: # 先把堆填满
+                    heap.append(matrix[i][j])
+                    self.adjustUp(heap) # 因为新元素添加在尾部，只要做向上调整。
+                    j += 1  # 下一列
+                else:
+                    if matrix[i][j] < heap[0]:
+                        heap[0] = matrix[i][j]  # 因为matrix[i][j]更小，替换原来的根节点。
+                        self.adjustDown(heap) # 因为根节点更新了，所以做向下调整。
+                        j += 1  # 下一列
+                    else:
+                        '''
+                        这段很重要，因为matrix[i][j] > heap[0]，
+                        所以对于后面的所有列，不肯能会出现matrix[i][j'] < heap[0]，
+                        直接从下一行开始，不然数据量大会超时。
+                        '''
+                        break
+            i += 1  # 下一行
+        return heap[0]
+
+    def adjustUp(self, heap):
+        i = len(heap) - 1
+        while i >= 0:
+            parent = (i - 1) / 2
+            if (parent >= 0) and (heap[parent] < heap[i]):
+                heap[i], heap[parent] = heap[parent], heap[i]
+                i = parent
+            else:
+                break
+
+    def adjustDown(self, heap):
+        i = 0
+        while i < len(heap):
+            left, right, max_pos = i * 2 + 1, i * 2 + 2, i
+            if (left < len(heap)) and (heap[left] > heap[max_pos]):
+                max_pos = left
+            if (right < len(heap)) and (heap[right] > heap[max_pos]):
+                max_pos = right
+            if max_pos != i:
+                heap[i], heap[max_pos] = heap[max_pos], heap[i]
+                i = max_pos
+            else:
+                break
diff --git a/lowest_common_ancestor.py b/lowest_common_ancestor.py
@@ -0,0 +1,22 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    """
+    @param root: The root of the binary search tree.
+    @param A and B: two nodes in a Binary.
+    @return: Return the least common ancestor(LCA) of the two nodes.
+    """ 
+    def lowestCommonAncestor(self, root, A, B):
+        # write your code here
+        if (not root) or (root == A) or (root == B):
+            return root
+        left = self.lowestCommonAncestor(root.left, A, B)   # 在左子树找AB的最近公共祖先
+        right = self.lowestCommonAncestor(root.right, A, B) # 在右子树找AB的最近公共祖先
+        '''
+        如果left和right都不会空，说明A、B分别在root的左、右子树，root是最近公共祖先。
+        如果A、B都在root的左子树，那么right肯定为空，最近公共祖先肯定在左子树中。所以left就是返回最近公共祖先。
+        '''
+        if left and right:
+            return root
+        else:
+            return left if left else right
diff --git a/merge_k_sorted_lists.py b/merge_k_sorted_lists.py
