04.算法模型
# 01.递归
# 1.1 求树的高度
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if root is None: return 0
l = maxDepth(root.left)
r = maxDepth(root.right)
return max(l, r) + 1
if __name__ == '__main__':
root = TreeNode(3,
left=TreeNode(9),
right=TreeNode(20, TreeNode(15), TreeNode(7, TreeNode(10)))
)
print(maxDepth(root)) # 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 1.2 步骤解释
- 第一步:在节点1执行第一句代码
- 很明显1节点不为None,执行
l = maxDepth(root.left)
- 很明显1节点不为None,执行
- 第二步:递归节点2
- 节点2有左子树,继续执行
l = maxDepth(root.left)
- 节点2有左子树,继续执行
- 第三步:递归节点4
- 节点4没有左子树,执行
if root is None: return 0
,4节点的 L=0 - 然后执行
r = maxDepth(root.right)
4节点没有右子树,4 节点的 R=0 - 最后执行
return max(l, r) + 1
此时L=0,R=0,所以返回1 - 此时返回到调用节点2,节点2的 L=1
- 节点4没有左子树,执行
- 第四步:此时出栈,返回到调用节点2,节点2的 L=1
- 执行
r = maxDepth(root.right)
,2节点有右节点,递归到节点5
- 执行
- 第五步:此时递归节点5
- 节点5没有左子树,执行
if root is None: return 0
,5节点的 L=0 - 然后执行
r = maxDepth(root.right)
5节点没有右子树,5 节点的 R=0 - 最后执行
return max(l, r) + 1
此时L=0,R=0,所以返回1 - 此时返回到调用节点2,节点2的 L=1
- 节点5没有左子树,执行
- 第六步:此时返回到调用节点2,节点2的 L=1,R=1
- 执行节点2上的,
return max(l, r) + 1
- 此时的 L=1,R=1所以 return 2
- 执行节点2上的,
- 第七步:此时返回到调用节点 1,1节点的 L=2
- 然后执行
r = maxDepth(root.right)
- 递归1节点的右节点
- 然后执行
- 第八步:递归节点3
- 节点3有左子树,继续执行
l = maxDepth(root.left)
- 递归节点6
- 节点3有左子树,继续执行
- 第九步:递归节点6
- 节点6没有左子树,执行
if root is None: return 0
,6节点的 L=0 - 然后执行
r = maxDepth(root.right)
6节点没有右子树,6节点的 R=0 - 最后执行
return max(l, r) + 1
此时L=0,R=0,所以返回1 - 此时返回到调用节点3,节点3的 L=1
- 节点6没有左子树,执行
- 第十步:此时出栈,返回到调用节点3,节点3的 L=1
- 节点7没有左子树,执行
if root is None: return 0
,7节点的 L=0 - 然后执行
r = maxDepth(root.right)
7节点没有右子树,7 节点的 R=0 - 最后执行
return max(l, r) + 1
此时L=0,R=0,所以返回1 - 此时返回到调用节点3,节点3的R=1
- 节点7没有左子树,执行
- 第十一步:此时返回到调用节点3,节点3的 L=1,R=1
- 执行节点3上的,
return max(l, r) + 1
- 此时的 L=1,R=1所以 return 2
- 执行节点3上的,
- 第十二步:此时返回到调用节点 1,1节点的 L=2,R=2
- 执行节点3上的,
return max(l, r) + 1
- 此时L=2,R=2,所以return 3
- 执行节点3上的,
第十三步:所以最终返回二叉树的高为 3
# 02.分治
# 2.1 分治算法
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题
求出子问题的解,就可得到原问题的解
这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序)
分治算法的解题步骤一般如下:
- 1)分解,将要解决的问题划分成若干规模较小的同类问题;
- 2)求解,当子问题划分得足够小时,用较简单的方法解决;
- 3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解。
# 2.2 求列表最小值
- 如果这个问题的数据规模小于等于2的时候,我们可以经过一个判断就找到其中的最小值
- 所以我们需要做的就是想办法把这若干个数据变成两个数据进行比较,那么我们可以先把数据从中间划分为左右两部分
- 然后通过递归再把每一部分再划分为左右两部分,直到数据规模小于等于2的时候,返回结果
- 然后通过递归到最后为两个数据对比,我们就可以找到最小值
def get_max(number): # 寻最小值函数
if len(number) == 1: return number[0]
return min(number[0],number[1])
# 分治法
def solve(number):
n = len(number)
if n <= 2: return get_max(number) # 数据规模小于等于2使用get_max()函数
left_list, right_list = number[:n // 2], number[n // 2:] # 1) 分解(子问题规模为 n/2)
left_max, right_max = solve(left_list), solve(right_list) # 2) 递归(树),分治
return get_max([left_max, right_max]) # 3) 合并
if __name__ == "__main__":
test_list = [33, 52, 2, 25, 63, 75, 43, 72, 45, 97, 53, 25, 14, 18, 3, 5]
print(solve(test_list)) # 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 03.动态规划
# 3.1 动态规划定义
- 动态规划(Dynamic Programming)是求多阶段决策过程最优化的一种数学方法
- 它将问题的整体按时间或空间的特征分成若干个前后衔接的时空阶段
- 把多阶段决策问题表示为前后有关的一系列单阶段决策问题,然后逐个求解
- 从而求出整个问题的最有决策序列,它强调了时间和空间的连续性。
# 3.2 最大和连续子数组
- 题目描述:
给定一个整数数组
nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
- 解题思路:
- 1、定义两个变量
- tempSum:存储之前的累加和
- maxSum: 存储当前的最大和
- 2、遍历数组,当第i个数时,主要更新两个变量就可以
- 判断前面累加和是否为负值(tempSum小于0)
- 如果为负值,则累加和更新为当前值;否则,继续累加当前值
- 判断累加和是否大于最大和(tempSun与maxSum那个大)
- 如果大于最大和,则更新为累加和;否则,继续保留之前的最大和。
- 判断前面累加和是否为负值(tempSum小于0)
- 1、定义两个变量
def maxSub( nums):
maxSum = None
tempSum = 0
for i in nums:
if maxSum == None: maxSum = i # 第一次开始,设置0位置为最大值
tempSum = max(i, tempSum + i) # 比较 累加和 与 累加和+下一个元素 取大的为新 累加和
maxSum = max(maxSum, tempSum) # 比较累加和与最大值那个大,更大就更新
return maxSum
if __name__ == "__main__":
nums = [-2,1,-3,4,-1,2,1,-5,4]
print(maxSub(nums)) # 6
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 04.双指针
# 4.1 双指针概念
- 双指针,顾名思义,就是利用两个指针去遍历数组
- 一个放首,一个放尾,同时向中间遍历,直到两个指针相交,完成遍历,时间复杂度也是O(n)
# 4.2 两数之和II
题目描述
- 给定一个已按照 升序排列 的整数数组
numbers
- 请你从数组中找出两个数满足相加之和等于目标数
target
- 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素
- 给定一个已按照 升序排列 的整数数组
输入:numbers = [2,3,4], target = 6
输出:[1,3]
输入:numbers = [-1,0], target = -1
输出:[1,2]
1
2
3
4
2
3
4
- 解题思路
- 初始时两个指针分别指向第一个元素位置和最后一个元素的位置。
- 每次计算两个指针指向的两个元素之和,并和目标值比较。
- 如果两个元素之和等于目标值,则发现了唯一解。
- 如果两个元素之和小于目标值,则将左侧指针右移一位。
- 如果两个元素之和大于目标值,则将右侧指针左移一位
def twoSum(numbers, target):
low, high = 0, len(numbers) - 1
while low < high:
total = numbers[low] + numbers[high]
if total == target:
return [low + 1, high + 1]
elif total < target:
low += 1
else:
high -= 1
return [-1, -1]
if __name__ == '__main__':
numbers = [2,3,4]
target = 6
print( twoSum(numbers, target) )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
编辑 (opens new window)
上次更新: 2024/3/13 15:35:10