本系列为Leetcode刷题笔记，刷题平台为Leetcode中文站， 刷题按Tag分类。本系列题解汇总如下 (持续更新…)：
本文主要是分治算法相关题目题解总结。
[TOC]
分治算法
基本概念
分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或者更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。如快速排序，归并排序。
基本思想及策略
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治法的策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
分治法使用场景
分治法所能解决的问题一般具有以下几个特征：
- 该问题的规模缩小到一定的程度就可以容易地解决；
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
- 利用该问题分解出的子问题的解可以合并为该问题的解；
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题；
- 第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
- 第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；
- 第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑使用贪心法或者动态规划法；
- 第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可以使用分治法，但一般动态规划较好。
分治法的基本步骤
分治法在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
- 解决：若子问题规模较小容易被解决则直接解，否则递归地解各个子问题；
- 合并：将各个子问题的解合并为原问题的解。
分治法的应用
二分搜索
大整数乘法
Strassen矩阵乘法
棋盘覆盖
合并排序
快速排序
线性时间选择
最接近点对问题
循环赛日程表
汉诺塔
二分搜索
- 二分搜索的要求：线性表为有序表，并且要用向量作为表的存储结构；
- 二分搜索得基本思想：先确定待查找记录所在的范围，然后逐步缩小范围直至找到或找不到该记录位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution(object):
def searchRange(self, nums, key):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
return self.bSearch(nums, 0, len(nums)-1,key)
def bSearch(self, nums, left, right, key):
mid = (left+right) // 2
if nums[mid] == key:
return mid
elif nums[mid] > key:
return self.bSearch(nums,left,mid-1,key)
else:
return self.bSearch(nums, mid+1,right,key)
汉诺塔
从左到右 A B C 柱 大盘子在下, 小盘子在上, 借助B柱将所有盘子从A柱移动到C柱, 期间只有一个原则: 大盘子只能在小盘子的下面。
求解思路：
- 当盘子只有一个的时候,只有一个动作 从 A 移动到 C 即结束；
- 当有N个盘子的时候, 中间的动作是从 A 移动到 C, 表示最下面的第N个盘子移动完毕；
- 中间动作之上都可以认为是: 从 A 移动到 B；
- 中间动作之下都可以认为是: 从 B 移动到 C。
1
2
3
4
5
6
7
8
9
10class Solution(object):
def move(self, n, a, b, c):
if n == 1:
print(a+'->'+c)
else:
self.move(n-1, a, c, b)
print(a+'->'+ c)
self.move(n-1, b, a, c)
if __name__ == '__main__':
Solution().move(3,'a','b','c')
参考
https://www.cnblogs.com/xsyfl/p/6921687.html
https://blog.csdn.net/not_guy/article/details/72823951
241. 为运算表达式设计优先级
题目描述
给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
- 示例 1:
输入: “2-1-1”
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2 - 示例 2:
输入: “23-45”
输出: [-34, -14, -10, -10, 10]
解释:
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10
解题思路
如果字符串为数字直接返回；
使用分治法，遍历字符串，当遇到运算符时，将字符串分为运算符前及运算符后两部分，根据运算符做相应运算。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
29class Solution(object):
def diffWaysToCompute(self, input):
"""
:type input: str
:rtype: List[int]
"""
if input.isdigit():
return [int(input)]
res = []
for i in range(len(input)):
if input[i] in '+-*':
left = self.diffWaysToCompute(input[:i])
right = self.diffWaysToCompute(input[i+1:])
for j in left:
for k in right:
res.append(self.helper(j, k, input[i]))
return res
def helper(self, j, k, op):
if op == '+':
return j + k
elif op == '-':
return j - k
elif op == '*':
return j * k
if __name__ == '__main__':
result = Solution().diffWaysToCompute("2*3-4*5")
print(result)
169. 求众数
题目描述
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
- 示例 1:
输入: [3,2,3]
输出: 3 - 示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
解题思路
维护一个候选数candidate和计数器counter。遍历数组中所有的元素， 设当前的元素为x，若 counter = 0,则 candidate = x, counter = 1; 否则， 根据candidate 与x是否相等来更新counter（相等+1，不等-1）
在遍历一次，判断候选数是否为合法的主元素。
为什么这样做是对的呢？因为若在有解的情况下，一个元素y出现>n/2次，那么要抵消掉它，必然也要有相同的元素才行，而总的元素才n个，也就是说元素y在这样的计数中不会被抵消。保证有解的情况最后的候选数就是主要元素。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
candidate = 0
count = 0
for x in nums:
if count == 0:
count = 1
candidate = x
elif x == candidate:
count += 1
else:
count -= 1
return candidate
if __name__ == '__main__':
result = Solution().majorityElement([6,5,5])
print(result)
215. 数组中的第K个最大元素
题目描述
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
- 示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5 - 示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4 - 说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
解题思路
堆排序。
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
41class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
if len(nums) < k or k <= 0:
return 0
res = nums[:k]
change = True
for i in range(k, len(nums)+1):
if change:
for j in range(k//2, -1, -1):
self.adjust(res, j, k)
for j in range(k-1, 0, -1):
res[j], res[0] = res[0], res[j]
self.adjust(res, 0, j)
change = False
if i != len(nums) and nums[i] > res[-1]:
res[-1] = nums[i]
change = True
return res[-1]
def adjust(self, res, parent, length):
temp = res[parent]
child = 2*parent+1
while child < length:
if child+1 < length and res[child+1] < res[child]:
child += 1
if temp < res[child]:
break
res[parent] = res[child]
parent = child
child = 2*parent+1
res[parent] = temp分治算法，这里使用快速排序算法。
- 通过一趟排序将要排序的数据分割成两个独立的两部分：左部分都是比它小的数，右部分都是比它大的数；
- 然后在按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，最终使整个数据变成有序序列。
1 | class Solution(object): |
