[数据结构与算法] leetcode解题常见思路

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> leetcode解题常见思路 -> 正文阅读

[数据结构与算法]leetcode解题常见思路

（梳理框架主要由up主提供）

前言

解题思路是解题过程中最关键的一步，即使最终没做出来，能大概知道解题思路甚至有多个解题思路也是挽救方法
以下提及题目不止对应技巧一种思路，但建议先按对应思路去解题，再考虑其他思路优化
个人认为最重要的标了★
题目尽量按难度从低到高排序，题目挑选后续也会随着我的刷题经验进行调整

双指针

双指针常用于数组、链表两种线性表（有序）数据结构相关的题，具体又分为

相向双指针：
- 两个指针一头一尾往中间移动
- 多应用于数组的连续子序列或两两组合，有规律的缩小范围
单向双指针
- 两个指针往同一个方向移动（没想到什么场景后续补充吧）
快慢指针：
- 通常慢指针向前走一步，快指针向前走两步
- 多用于链表、因为链表无法直接通过索引访问
- 通常利用快慢指针找到链表的中点或公共节点

881. 救生艇
 11. 盛最多水的容器
 141. 环形链表

二分法

常用于有序数组，取中点二分后按一定规则只取其中一边再继续二分，多用于查数

704. 二分查找
 35. 搜索插入位置
 162. 寻找峰值

滑动窗口

常用于连续子序列的长度、统计量例如总和、计数等最优值问题

209. 长度最小的子数组
 1456. 定长子串中元音的最大数目

递归★

递归是指一个函数在运行时调用自己，框架如下

def recursion(params):		   #1.函数输入参数
	if params==1:			   #2.递归终止条件
		return 0
	params=params-1
	res=1+recursion(params)    #3.调用自身
	return res                 #4.返回值

递归有时不是直接的最优解题方法，但却是最基本、一定能解题的思想。
509. 斐波那契数
 206. 反转链表
 344. 反转字符串

分治法

是一种特殊的递归，将问题进行分解，每个分解部分都有可能调用自己即递归到下一层，总结就是一个函数会同时多次或有选择性地调用自己、只是入参具体值不相同

我推荐实现归并排序
912. 排序数组

以下是up主推荐的可以用分治技巧的题，试了一下一道也无法一次性顺利按分治解出QAQ，建议大家做题熟练后再回来试试
169. 多数元素
 215. 数组中的第K个最大元素
 53. 最大子序和

回溯法★

一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。(力扣定义)
是一种特殊的递归，常用于枚举组合+过滤或去重（可选）场景：
1.尝试一种路径，层层递归（调用自己）
2.找到答案并返回答案（返回值）
3.找不到答案返回上一层（终止条件）
4.尝试其他路径（调用自己）
去重前需保证枚举集有序

46. 全排列
 47. 全排列 II
78. 子集
 90. 子集 II
39. 组合总和
 40. 组合总和 II

做题tips：个人习惯用入口函数全局结果变量+内嵌递归函数的方式来完成

深度优先搜索（Depth First Search, DFS）★

针对树结构，从根节点走一个分支到底后，返回最近的非叶子节点再走另一个分支走到底，这样直到把所有节点遍历完成
up主总结是回溯=DFS+剪枝，但我觉得回溯也不必须剪枝（上方回溯定义），所以是不是更合适的说DFS也是一种回溯。
深度优先搜索与广度优先搜索过程对比

# 基本框架
def dfs(root):
	if not root:return None
	dfs(root.left)
	dfs(root.right)
	return None

有些题目既能用DFS也能用BFS

938. 二叉搜索树的范围和

广度优先搜索（Breadth First Search, BFS）

针对树结构，从根节点一层一层遍历子节点，直到所有节点遍历完成。
比起DFS，BFS应用偏少，常用于层序遍历、最短路径场景。

# 基本框架
def bfs(root):
	if not root: return None
	q=collections.deque([root])
	while q:
		root=q.popleft()
		if root.left:
			q.append(root.left)
		if root.right:
			q.append(root.right)
	return None

102. 二叉树的层序遍历
 107. 二叉树的层序遍历 II

贪心算法

每一步都优先当前时刻最优选择走，实现局部最优。

55. 跳跃游戏

记忆化搜索

是一个辅助递归的技巧，通常用字典记录下不同入参下递归函数的返回值，这样碰到同样入参，则直接调出返回值。

509. 斐波那契数

动态规划（Dynamic Programming, DP）★★★

动态规划是每一步的状态/最优解基于上一步的状态/最优解，即存在最优子结构，所以最重要的是找到状态转移方程，基本框架如下（以斐波那契数列为例）

def dynamic_programming():
	dp=[None for i in range(n)] #用于后续存储每个状态下的结果
	dp[0],dp[1]=0,1 #初始状态
	for i in range(2,n):
		dp[i]=dp[i-1]+dp[i-2] #状态转移方程
	return dp[-1] #最终状态