LeetCode 专题 ：分治算法
2019-05-26 本文已影响0人
李威威
LeetCode 第 23 题：归并多个有序链表
传送门：23. 合并K个排序链表。
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
思路1：使用优先队列。
首先要复习一下 Python 中优先队列的使用。
Python 代码：
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
import heapq
l = []
size = len(lists)
for index in range(size):
if lists[index]:
heapq.heappush(l, (lists[index].val, index))
dummy_node = ListNode(-1)
cur = dummy_node
while l:
_, index = heapq.heappop(l)
head = lists[index]
cur.next = head
cur = cur.next
if head.next:
heapq.heappush(l, (head.next.val, index))
lists[index] = head.next
head.next = None
return dummy_node.next
思路2：使用分治
参考资料：https://liweiwei1419.github.io/leetcode-solution/leetcode-0023-merge-k-sorted-lists/
Python 代码：
# 23. 合并K个排序链表
# 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
# 思路：分治法与优先队列
class Solution:
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
size = len(lists)
if size == 0:
return None
return self.__merge_k_lists(lists, 0, size - 1)
def __merge_k_lists(self, lists, left, right):
if left >= right:
return lists[left]
mid = left + (right - left) // 2
listnode1 = self.__merge_k_lists(lists, left, mid)
listnode2 = self.__merge_k_lists(lists, mid + 1, right)
return self.__merge_two_sorted_list_node(listnode1, listnode2)
def __merge_two_sorted_list_node(self, list1, list2):
if list1 is None:
return list2
if list2 is None:
return list1
if list1.val < list2.val:
list1.next = self.__merge_two_sorted_list_node(list1.next, list2)
return list1
else:
list2.next = self.__merge_two_sorted_list_node(list1, list2.next)
return list2
LeetCode 第 53 题：连续子数组的最大和
参考资料：LeetCode 第 53 题：连续子数组的最大和。
要做第 95 题，得先完成第 96 题。
LeetCode 第 96 题：不同的二叉搜索树（使用递归）
传送门：96. 不同的二叉搜索树。
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
Python 代码：
# 96. 不同的二叉搜索树
# 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
#
# 示例:
#
# 输入: 3
# 输出: 5
# 解释:
# 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
#
# 1 3 3 2 1
# \ / / / \ \
# 3 2 1 1 3 2
# / / \ \
# 2 1 2 3
class Solution:
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0 or n == 1:
return 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
for j in range(i):
dp[i] += dp[j] * dp[i - j - 1]
return dp[n]
if __name__ == '__main__':
solution = Solution()
n = 3
result = solution.numTrees(n)
print(result)
LeetCode 第 95 题：不同的二叉搜索树 II
传送门：95. 不同的二叉搜索树 II。
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例:
输入: 3 输出: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] 解释: 以上的输出对应以下 5 种不同结构的二叉搜索树： 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
思路1：动态规划。
Python 代码：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n <= 0:
return []
res = [None] * (n + 1)
res[0] = [None]
for i in range(1, n + 1):
# 初始化一个列表对象
res[i] = []
for j in range(i):
for left in res[j]:
for right in res[i - j - 1]:
# 注意：这里是 j + 1 ，表示根结点，画个图就很清楚了
root = TreeNode(j + 1)
root.left = left
# 每个结点都有固定偏移的拷贝
root.right = self.__shift_clone(right, j + 1)
res[i].append(root)
return res[n]
def __shift_clone(self, root, k):
if root is None:
return root
cur_node = TreeNode(root.val + k)
cur_node.left = self.__shift_clone(root.left, k)
cur_node.right = self.__shift_clone(root.right, k)
return cur_node
思路2：分治算法。
Python 代码：
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
res = []
if n <= 0:
return res
return self.helper(1, n)
def helper(self, left, right):
res = []
if left > right:
# 说明不构成区间，应该返回空结点
res.append(None)
return res
elif left == right:
res.append(TreeNode(left))
return res
else:
for i in range(left, right + 1):
left_sub_tree = self.helper(left, i - 1)
right_sub_tree = self.helper(i + 1, right)
for l in left_sub_tree:
for r in right_sub_tree:
root = TreeNode(i)
root.left = l
root.right = r
res.append(root)
return res
（本节完）
