1.算法（Algorithm）：一个计算过程，解决问题的方法。
2. “程序=数据结构+算法”
1.时间复杂度是用来估计算法运行时间的一个式子。
2. 一般来说，时间复杂度高的算法比复杂度低的算法慢。
3. 常见的时间复杂度（按效率排序）
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n2logn) < O(n3)
4. 复杂问题的时间复杂度
O(n!) O(2
n
^n
n) O(n
n
^n
n) ···
5. 如何简单快速地判断算法复杂度
快速判断算法复杂度（适用于绝大多数简单情况）：
确定问题规模n循环减半过程—>lognk层关于n的循环—>nk
复杂情况：根据算法执行过程判断
1.3 空间复杂度1.空间复杂度：用来评估算法内存占用大小的式子
2.空间复杂度的表示方式与时间复杂度完全一样
算法使用了几个变量：O(1)算法使用了长度为n的一维列表：O(n)算法使用了m行n列的二维列表：O(mn)
4.“空间换时间”—时间比空间重要
1.4 递归递归的两个条件：
- 调用自身结束条件
func3先打印后递归；func4先递归后打印
输入x=3，func3打印3 2 1；func4打印1 2 3
n = 2时：
- 把小圆盘从A移动到B把大圆盘从A移动到C把小圆盘从B移动到C
n个盘子时：
- 把n-1个圆盘从A经过C移动到B把第n个圆盘从A移动到C把n-1个小圆盘从B经过A移动到C
def hanoi(n,a,b,c):
if n>0:
hanoi(n-1,a,c,b)
print("moving from %s to %s" % (a,c))
hanoi(n-1,b,a,c)
hanoi(3,'A','B','C')
2 列表查找
2.1 什么是列表查找
1.查找：在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程。
2.列表查找（线性表查找）：从列表中查找指定元素
输入：列表、待查找元素输出：元素下标（未找到元素时一般返回None或-1）
3.内置列表查找函数：index()
2.2 顺序查找顺序查找，也叫线性查找，从列表第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表最后一个元素为止。
def linear_search(li,val): for ind,v in enumerate(li): if v == val: return ind else: return None
时间复杂度：O(n)
2.3二分查找二分查找，又叫折半查找，从有序列表的初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
def binary_search(li,val): left = 0 right = len(li) - 1 while left <= right: #候选区有值 mid = (left + right) // 2 if li[mid] == val: return mid elif li[mid] > val: #待查找的值在mid的左侧 right = mid - 1 else: #li[mid] < val: 待查找的值在mid的右侧 left = mid + 1 else: return None
时间复杂度：O(logn)
注：二分查找时间复杂度低，运行快，但是使用二分查找的是有序列表。
无序列表用顺序查找，或者排序后用二分查找。排序时间复杂度有时会更高。
有序列表用二分查找
1.排序：将一组“无序”的记录序列调整为“有序”的记录序列。
2.列表排序：将无序列表变为有序列表
输入：列表输出：有序列表
3.升序与降序
4.内痔排序函数：sort()
列表每两个相邻的数，如果前面比后面大，则交换这两个数。 一趟排序完成后，则无序区减少一个数，有序区增加一个数。
代码关键点：趟、无序区范围。
def bubble_sort(li):
for i in range(len(li)-1): #第i趟
for j in range(len(li)-i-1):
#if li[j] > li[j+1]: #升序
if li[j] < li[j + 1]: #降序
li[j],li[j+1] = li[j+1],li[j]
#优化版：没有再进行交换说明剩下的已经排好序了，不用再进行排序
def bubble_sort(li):
for i in range(len(li)-1): #第i趟
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]: #升序
li[j],li[j+1] = li[j+1],li[j]
exchange = True
print(li)
if not exchange:
return
时间复杂度：O(n2)
3.2.2 选择排序一趟排序记录最小的数，放到第一个位置；
再一趟排序记录列表无序区最小的数，放到第二个位置；
······
算法关键点：有序区和无序区、无序区最小数的位置
def select_sort_simple(li):
li_new = []
for i in range(len(li)):
min_val = min(li)
li_new.append(min_val)
li.remove(min_val)
return li_new
#优化版：降低时间复杂度
def select_sort(li):
for i in range(len(li)-1): #第i趟
min_loc = i
for j in range(i+1,len(li)): #range前包后不包，[i+1,len(li))
if li[j] < li[min_loc]:
min_loc = j
li[i],li[min_loc] = li[min_loc],li[i]
print(li) #打印每趟排序的结果
时间复杂度：O(n2)
3.2.3 插入排序初始时手里（有序区）只有一张牌， 每次（从无序区）摸一张牌，插入到手里已有牌的正确位置。
def insert_sort(li):
for i in range(1,len(li)): #i 表示摸到的牌的下标
tmp = li[i] #摸到的牌
j = i - 1 #j 表示手里的牌的下标
while j >= 0 and li[j] > tmp:
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
时间复杂度：O(n2)
3.2.4 快速排序
快速排序：快
快速排序思路：
1.取一个元素p（第一个元素），使元素p归位；
2.列表被p分成两部分，左边都比p小，右边都比p大；
3.递归完成排序。
def partition(li,left,right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp: #从右边找比tmp小的数
right -= 1 #往左走一步
li[left] = li[right] #把右边的值写到左边空位上
while left < right and li[left] <= tmp: #从左边找比tmp大的数
left += 1 #往右走一步
li[right] = li[left] #把左边的值写到右边空位上
li[left] = tmp #tmp归位
return left
def quick_sort(li,left,right):
if left < right:
mid = partition(li,left,right)
quick_sort(li,left,mid-1)
quick_sort(li,mid+1,right)
时间复杂度：O(nlogn)
3.2.5 堆排序1.树的基础知识
树是一种数据结构，比如：目录结构。
树是一种可以递归定义的数据结构。
树是由n个节点组成的集合：
如果n=0,那这是一棵空树；
如果n>0,那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。
一些概念：
根节点（最根上的节点）、叶子结点（没有分叉的节点）
树的深度（高度）（有多少层）
树的度（=最大的节点的度）
孩子节点/父节点（相对关系）
子树
2.二叉树的基础知识
二叉树：度不超过2的树。
每个节点最多有两个孩子节点，两个孩子节点被区分为左孩子节点和右孩子节点。
满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。
完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
二叉树的存储方式（表示方式）：
链式存储方式
顺序存储方式（用列表来存储）
二叉树的顺序存储方式：
父节点和左孩子节点的编号下标的关系：i—>2i+1
父节点和右孩子节点的编号下标的关系：i—>2i+2
孩子节点和父节点的编号下标的关系：i—>(i-1)//2
3.什么是堆
堆：一种特殊的完全二叉树结构。
大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大。
小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小。
堆的向下调整性质
假设根节点的左右子树都是堆，但根节点不满足堆的性质，可以通过一次向下的调整来将其变成一个堆。
4.堆排序过程
（1）建立堆。
（2）得到堆顶元素，为最大元素。
（3）去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序。
（4）堆顶元素为第二大元素。
（5）重复步骤3，直到堆变空。
# 大根堆
def sift(li,low,high):
"""
:param li: 列表
:param low:堆的根节点位置
:param high:堆的最后一个元素的位置
:return:
"""
i = low #i最开始指向根结点（堆顶元素）
j = 2 * i + 1 #j开始是左孩子
tmp = li[low] #把堆顶元素存起来
while j <= high: #只要j位置有数
if j+1 <= high and li[j+1] > li[j]: # 如果右孩子有并且比较大
j = j + 1 #j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j #往下看一层
j = 2 * i + 1
else: #tmp更大
li[i] = tmp #把tmp放到i的位置上
break
else:
li[i] = tmp #把tmp放到叶子结点上
'''
#简化版
def sift(li,low,high):
"""
:param li: 列表
:param low:堆的根节点位置
:param high:堆的最后一个元素的位置
:return:
"""
i = low #i最开始指向根结点（堆顶元素）
j = 2 * i + 1 #j开始是左孩子
tmp = li[low] #把堆顶元素存起来
while j <= high: #只要j位置有数
if j+1 <= high and li[j+1] > li[j]: # 如果右孩子有并且比较大
j = j + 1 #j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j #往下看一层
j = 2 * i + 1
else: #tmp更大
break
li[i] = tmp #把tmp放到i的位置上（两种情况：1.tmp比li[j]大；2.j>high）
'''
def heap_sort(li):
n = len(li)
for i in range((n-2)//2,-1,-1): #知道孩子结点位置求父结点位置，孩子结点位置i = n-1，则父结点位置为(i-1)//2
# i 表示建堆的时候调整部分的根的下标
sift(li,i,n-1)
#建堆完成
for i in range(n-1,-1,-1):
# i 指向当前堆的最后一个元素
li[0],li[i] = li[i],li[0]
sift(li,0,i - 1) #i-1 是新的high
li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)
heap_sort(li)
print(li)
时间复杂度：O(nlogn)
5.堆的内置模块
Python内置模块——heapq
常用函数：heapify(x)、heappush(heap,item)、heappop(heap)
import heapq #q->queue 优先队列
import random
li = list(range(100))
random.shuffle(li)
print(li)
heapq.heapify(li) #建堆
n = len(li)
for i in range(n):
print(heapq.heappop(li),end=',')
6.topk问题
现在有n个数，设计算法得到前k大的数。（k
排序后切片——O(nlogn)
冒泡、选择、插入——O(kn)
堆排序思路——O(nlogk)
（1）取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数。
（2）依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整；
（3）遍历列表所有元素后，倒序弹出堆顶。
# 小根堆
def sift(li,low,high):
"""
:param li: 列表
:param low:堆的根节点位置
:param high:堆的最后一个元素的位置
:return:
"""
i = low #i最开始指向根结点（堆顶元素）
j = 2 * i + 1 #j开始是左孩子
tmp = li[low] #把堆顶元素存起来
while j <= high: #只要j位置有数
if j+1 <= high and li[j+1] < li[j]: # 如果右孩子有并且比较小
j = j + 1 #j指向右孩子
if li[j] < tmp:
li[i] = li[j]
i = j #往下看一层
j = 2 * i + 1
else: #tmp更大
break
li[i] = tmp #把tmp放到i的位置上（两种情况：1.tmp比li[j]大；2.j>high）
def topk(li,k):
heap = li[0:k]
#1.建堆
for i in range((k-2)//2,-1,-1):
sift(heap,i,k-1)
#2.遍历
for i in range(k,len(li)):
if li[i] > heap[0]:
heap[0] = li[i]
sift(heap,0,k-1)
#3.出数
for i in range(k-1,-1,-1):
heap[0],heap[i] = heap[i],heap[0]
sift(heap,0,i-1)
return heap
import random
li = list(range(100))
random.shuffle(li)
print(topk(li,10))
3.2.6 归并排序
假设现在的列表分两段有序，如何将其合成为一个有序列表，这种操作称为一次归并。
def merge(li,low,mid,high):
"""
:param li: 列表
:param low: 第一段有序列表的第一个数
:param mid:第一段有序列表的最后一个数
:param high:第二段有序列表的最后一个数
:return:
"""
i = low
j = mid + 1
ltmp = []
while i <= mid and j <= high: #只要左右两边都有数
if li[i] < li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
# while 执行完，肯定有一部分没数了
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp
li = [2,4,5,7,1,3,6,8]
merge(li,0,3,7)
print(li)
使用归并：
（1）分解：将列表越分越小，直至分成一个元素。
（2）终止条件：一个元素是有序的。
（3）合并：将两个有序列表归并，列表越来越大。
def merge_sort(li,low,high):
if low < high: #至少有两个元素，递归
mid = (low+high) // 2
merge_sort(li,low,mid)
merge_sort(li,mid+1,high)
merge(li,low,mid,high)
li = list(range(100))
import random
random.shuffle(li)
merge_sort(li,0,len(li)-1)
print(li)
时间复杂度：O(nlogn)
空间复杂度：O(n)
1.三种排序算法的时间复杂度都是O(nlogn).
2.一般情况下，就运行时间而言：
快速排序 < 归并排序 < 堆排序
3.三种排序算法的缺点：
（1）快速排序：极端情况下排序效率低；
（2）归并排序：需要额外的内存开销；
（3）堆排序：在快的排序算法中相对较慢。
| 排序方法 | 时间复杂度（最坏情况） | 时间复杂度（平均情况） | 时间复杂度（最好情况） | 空间复杂度 | 稳定性 | 代码复杂度 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 | 简单 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 | 简单 |
| 插入排序 | O(n2) | O(n2) | O(n2) | O(1) | 稳定 | 简单 |
| 快速排序 | O(n2) | O(nlogn) | O(nlogn) | 平均情况：O(nlogn)；最坏情况O(n) | 不稳定 | 较复杂 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | 复杂 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | 较复杂 |
3.2.7 希尔排序
希尔排序(Shell Sort)是一种分组插入排序算法。
（1）首先取一个整数d1=n/2，将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序。
（2）取第二个整数d2=d1/2 ，重复上述分组排序过程，直到di=1，即所有元素在同一组内进行直接插入排序。
希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。
def insert_sort_gap(li,gap):
for i in range(gap,len(li)): #i 表示摸到的牌的下标
tmp = li[i] #摸到的牌
j = i - gap #j 表示手里的牌的下标
while j >= 0 and li[j] > tmp:
li[j+gap] = li[j]
j -= gap
li[j+gap] = tmp
def shell_sort(li):
d = len(li) // 2
while d >= 1:
insert_sort_gap(li,d)
d //= 2
li = list(range(1000))
import random
random.shuffle(li)
shell_sort(li)
print(li)
希尔排序的时间复杂度讨论比较复杂，并且和选取的gap序列有关。
3.2.8 计数排序对列表进行排序，已知列表中的数范围都在0到100之间。设计时间复杂度为O(n)的算法。
def count_sort(li,max_count=100):
count = [0 for _ in range(max_count+1)]
for val in li:
count[val] += 1
li.clear()
for ind,val in enumerate(count):
for i in range(val):
li.append(ind)
import random
li = [random.randint(0,100) for _ in range(1000)]
print(li)
count_sort(li)
print(li)
桶排序
在计数排序中，如果元素的范围比较大（比如在1到1亿之间），如何改造算法？
桶排序(Bucket Sort)：首先将元素分在不同的桶中，再对每个桶中的元素排序。
def bucket_sort(li,n = 100,max_num = 10000):
buckets = [[] for _ in range(n)] #创建桶
for var in li:
i = min(var // (max_num // n), n-1) #i 表示var放到几号桶里
buckets[i].append(var) #把var加到桶里边
#保持桶内的顺序
for j in range(len(buckets[i])-1,0,-1):
if buckets[i][j] < buckets[i][j-1]:
buckets[i][j],buckets[i][j-1] = buckets[i][j-1],buckets[i][j]
else:
break
sorted_li = []
for buc in buckets:
sorted_li.extend(buc) # 把每个buc列表加到sorted_li里边
return sorted_li
import random
li = [random.randint(0,10000) for i in range(10000)]
li = bucket_sort(li)
print(li)
桶排序的表现取决于数据的分布。也就是需要对不同数据排序时采取不同的分桶策略。
平均情况时间复杂度：O(n+k)
最坏情况时间复杂度：O(n2k)
空间复杂度：O(nk)
多关键字排序：加入现在有一个员工表，要求按照薪资排序，薪资相同的员工按照年龄排序。
先按照年龄进行排序，再按照薪资进行稳定的排序。
对32，13，94，52,17，54，93排序，也可以看做多关键字排序。先按照个位进行排序，再按照十位进行稳定的排序。
def radix_sort(li):
max_num = max(li) # 最大值 9->1,99->2,888->3,1000->5
it = 0
while 10 ** it <= max_num:
buckets = [[] for _ in range(10)]
for var in li:
# 987 it=1 987//10->98 98%10->8; it=2 987//100->9 9%10->9
digit = (var // 10 ** it) % 10
buckets[digit].append(var)
# 分桶完成
# 把数重新写回li
li.clear()
for buc in buckets:
li.extend(buc)
it += 1
import random
li = list(range(100000))
random.shuffle(li)
radix_sort(li)
print(li)
时间复杂度：O(kn)
空间复杂度：O(k+n)
k表示数字位数。
1.给两个字符串s和t，判断t是否为s的重新排列后组成的单词
s = “anagram”,t = “nagaram”,return true.
s = “rat”,t = “car”,return false.
#法一
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
return sorted(s) == sorted(t)
#法二
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
dict1 = {}
dict2 = {}
for ch in s:
dict1[ch] = dict1.get(ch,0) + 1
for ch in t:
dict2[ch] = dict2.get(ch,0) + 1
return dict1 == dict2
2.给定一个m*n的二维列表，查找一个数是否存在。列表有下列特性：
每一行的列表从左到右已经排序好。
每一行第一个数比上一行最后一个数大。
[
[1, 3, 5, 7],
[10,11,16,20],
[23,30,34,50]
]
#法一
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
for line in matrix:
if target in line:
return True
return False
#法二
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
h = len(matrix)
if h == 0:
return False
w = len(matrix[0])
# if w == 0：
# return False
left = 0
right = h * w - 1
while left <= right:
mid = (left + right) // 2
i = mid // w #第i行
j = mid % w #第j行
if matrix[i][j] == target:
return True
elif matrix[i][j] < target:
left = mid + 1
else:
right = mid - 1
return False
3.给定一个列表和一个整数，设计算法找到两个数的下标，使得两个数之和为给定的整数。保证肯定仅有一个结果。
例如，列表[1,2,5,4]与目标整数3,1+2=3，结果为(0,1).
class Solution(object):
def binary_search(self,li,left,right,val):
while left <= right:
mid = (left + right) // 2
if li[mid][0] == val:
return mid
elif li[mid][0] < val:
left = mid + 1
else:
right = mid - 1
else:
return None
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
new_numbers = [[num,i] for i,num in enumerate(numbers)]
new_numbers.sort(key=lambda x:x[0])
for i in range(len(new_numbers)):
a = new_numbers[i][0]
b = target - a
if b >= a:
j = self.binary_search(new_numbers,i + 1,len(new_numbers)-1,b)
else:
j = self.binary_search(new_numbers,0,i - 1,b)
if j:
break
return sorted([new_numbers[i][1],new_numbers[j][1]])
