python算法思想-刷题专用
一、枚举法（循环+判断）
如质数求解、鸡兔同笼、水仙花数（3位数位幂为自身）、最大公约数求解、孪生素数（间隔2的素数对）、完全数（所有真因子和为自身）
for n in range(10,100): for i in range(2,n-1): if n%i==0:break else:print(n,'是质数')
# rabbit：1~34
# chicken：35-rabbit
for rabbit in range(1,35):
chicken = 35-rabbit
if 4*rabbit+2*chicken==94:
print('兔',rabbit,'鸡',chicken)
二、排序算法（快速排序、堆排序、归并排序）
2.1快速排序(Quick Sort)——分治法(递归)——时间复杂度O(nlogn)
使用分治法策略，将一个序列分为两个子序列，递归对两个子序列进行排序。
两个要素：1.选出基准(pivot)；2.分区操作(partition)
挑选基准值：从数列中挑出一个元素，称为"基准"（pivot），本例子选择最后面的元素作为基准
分区操作：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成；返回分割位置。
快排函数：确定分割位置，再对基准值分成两半的区域分别进行快排；递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
# small,large是顺序 def partition(array,small,large): s = (small-1) # 最小元素的索引 pivot = array[large] # 选取最大元素值作为基准pivot for j in range(small,large): if arr[j]<=pivot: s = s+1 arr[s],arr[j] = arr[j],arr[s] arr[s+1],arr[large] = arr[large],arr[s+1] return s+1
def quicksort(array,small,large): if small < large: pi = partition(array,small,large) # 基准值的位置，已经确定最终位置了 quicksort(array,small,pi-1) # 对基准值左边元素进行排序 quicksort(array,pi+1,large) # 对基准值右边元素进行排序
arr = [10, 7, 8, 9, 1, 5] n = len(arr) quickSort(arr, 0, n - 1)
2.2堆排序(Heap Sort)——递归——时间复杂度O(nlogn)
堆是一颗完全二叉树，适合用数组实现。使用最大堆，通过1.建堆和2.堆的维护操作进行排序
def heapify(arr,n,i):
'''
:param arr: 存储堆的数组
:param n: 数组长度
:param i: 待维护节点的下标
'''
largest = i
#假设父节点最大，找到左节点、右节点下标
left = i*2+1
right = i*2+2
if left<n and arr[largest]<arr[left]:
largest = left
if right<n and arr[largest]<arr[right]:
largest = right
if largest != i:
arr[i],arr[largest]=arr[largest],arr[i]
heapify(arr,n,largest)
堆的维护操作即确保父节点的值要大于它的左子节点和右子节点，将整个数组维护成满足堆的规则
def heapsort(arr):
#建堆-将arr数组中的元素挨个进行堆的维护
n = len(arr)
for i in range(n,-1,-1):
heapify(arr,n,i)
#排序
for i in range(n-1,0,-1):
# 将堆中的堆顶元素换到最后一位（即最大值）
arr[i],arr[0]=arr[0],arr[i]
heapify(arr,i,0)
# 重新维护剩余i个元素
return arr
2.3归并排序(Merge Sort)——分治法(递归)——时间复杂度O(nlogn)
def merge_sort(lists):
'''
递归进行归并排序。
'''
# 将list所有的元素排序完毕，递归结束
if len(lists) <= 1:
return lists
# 分治进行递归
mid = len(lists)//2
left = merge_sort(lists[:mid])
right = merge_sort(lists[mid:])
# 将两个有序数组进行合并
result = []
i,j = 0,0
while i < len(left) and j < len(right):
# 将较小值放入到result中
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 将未被遍历到的直接追加到result后面
if i == len(left):
result.extend(right[j:])
else:
result.extend(left[i:])
return result
三、贪心算法（Greedy Algorithm）
在对问题求解时，总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑，算法得到的结果是在某种意义上的局部最优解。
解题使用贪心算法有两个条件：
- 问题具有贪心选择性质，即使用当前最优解能够得到全局最优解；
- 问题的子问题具有最优子结构性质，即原问题的最优解可以通过对子问题的最优解组合而得到。
贪心算法的基本流程如下：
- 将问题分解为若干子问题；
- 对每个子问题求解，得到子问题的局部最优解；
- 将子问题的局部最优解合并成原问题的解。
3.1示例一：找零问题
def greedy_coin_change(coins, amount):
coins.sort(reverse=True)
result = []
if amount==0:
return 0
for coin in coins:
result += amount//coin
amount %= coin
return result
# 示例
coins = [25, 10, 5, 1]
amount = 63
print(greedy_coin_change(coins, amount))
贪心算法中的局部最优解就是每次找零使用数值最大的货币，全局最优解就是找零数量最少。
3.2示例二：背包问题
def knapsack(capacity, weights, values):
n = len(weights) # 物品的重量
# 对所有物品按照单位重量的价值从大到小排序
value_per_weight = sorted([(values[i] / weights[i], weights[i])
for i in range(n)], reverse=True)
value = 0
for v in value_per_weight:
if capacity == 0:
break
weight = min(v[1], capacity)
value += weight * v[0]
capacity -= weight
return value
weights = [4, 3, 5] # 物品的重量列表weights
values = [4000, 3500, 5000] # 物品的价值列表values
capacity = 10 # 背包容量C：capacity
print(knapsack(capacity, weights, values)) # 输出最大价值之和：10500.0
贪心算法中的局部最优解就是每次选择价值最大的物品，全局最优解就是放入背包的物品的重量之和不超过C并且价值之和最大。具体做法为：对所有物品按照单位重量的价值从大到小排序，然后依次选择单位重量价值最高的物品，直至背包中放不下为止。
def rec_opt(v,n):
if n==0:
return v
elif v==0:
return 0
elif v<v_thing[n-1]:#如果箱子的体积小于第n个物品的体积，那就直接判断放不放第n-1个物品
return rec_opt(v,n-1)
else:
A = rec_opt(v-v_thing[n-1],n-1) # 选第n件物品
B = rec_opt(v,n-1) # 不选第n件物品
return min(A,B)
3.3示例三：活动选择问题
活动选择问题是贪心算法在调度问题中的应用，通过选择结束时间最早的活动，实现最大化可安排活动数量。
def greedy_activity_selection(start_times, finish_times):
activities = list(zip(start_times, finish_times))
activities.sort(key=lambda x: x[1]) # 根据结束时间进行排序
selected_activities = [activities[0]] # 初始化计划单：选择第一个结束的活动
last_finish_time = activities[0][1] # 初始化结束时间：第一个活动结束的时间
# 遍历后续的活动，如果活动的开始时间晚于结束时间：将此次活动添加进计划单selected_activities
for activity in activities[1:]:
if activity[0] >= last_finish_time:
selected_activities.append(activity)
# 更新活动结束时间
last_finish_time = activity[1]
return selected_activities
# 示例
start_times = [1, 3, 0, 5, 8, 5]
finish_times = [2, 4, 6, 7, 9, 9]
print(greedy_activity_selection(start_times, finish_times))
贪心算法中的局部最优解就是每次选择活动结束最早的活动，全局最优解就是安排的活动次数最多。具体做法为：对所有活动按照活动结束时间从早到晚排序，然后在前后活动时间不重复的约束下，依次选择活动结束最早的活动，直至选择完毕。
3.4示例四：拼接数字问题
li = [32, 94, 128, 1286, 6, 71]
from functools import cmp_to_key
# 交换位置 32，94 --> 94 32
def xy_cmp(x, y):
if x + y < y + x:
return 1
elif x + y > y + x:
return -1
else:
return 0
def number_join(li):
# 将li中的数字转换为string类型
li = list(map(str, li))
# 通过函数xy_cmp对li进行排序
li.sort(key=cmp_to_key(xy_cmp))
# 返回将li中的字符串起来的数值
return ''.join(li)
贪心算法中的局部最优解就是每次比较两个值x和y，按照最大的顺序固定两个的位置，全局最优解就是最大化所有数字。具体做法为：对所有列表中的元素，按照组合起来最大的方式排序，最终返回整个列表。
四、双指针（Two Pointers）
双指针通过两个指针协同完成任务。这些指针可以指向不同的元素，具体应用取决于问题的性质。双指针算法主要包括：对撞指针、快慢指针、滑动窗口、双链遍历。
- 对撞指针：一左一右向中间逼近。一般左指针初始索引为0，右指针初始位置索引为n-1。
n=len(numbers) # 数量 l,r=0,n-1 # 左右指针
- 快慢指针：一快一慢，步长不同。一般用于检测环形链表。
# 快慢指针先指向head节点 slow=fast=head slow=slow.next # 移动1步 fast=fast.next.next # 移动2步
- 滑动窗口：两个指针，一前一后组成滑动窗口，并计算滑动窗口中的元素的问题。常见问题：字符串匹配问题等，用来解决一些查找满足一定条件的连续区间求值或长度的问题。
4.1对撞双指针
想要用对撞双指针，需要先对数组进行排序，或者本身输入就是有序的。
def twoSum(self, numbers, target):
"""
时间复杂度O(n)，空间复杂度O(1)，numbers为非递减排序的列表
"""
# 输入的已经排序
n=len(numbers) # 数量
l,r=0,n-1 # 左右指针
while l<r:
v=numbers[l]+numbers[r] # 两数之和
if v>target: # 移动指针
r-=1
elif v<target:
l+=1
else:
return [l+1,r+1]
def judgeSquareSum(self, c):
a, b = 0, floor(sqrt(c))
while a <= b:
sum = a ** 2 + b ** 2
if sum == c:
return True
elif sum < c:
a += 1
else:
b -= 1
return False
投递网易等公司10个岗位