

首页  思维导图  详情



算法总结

2023-06-06 15:19:39   6  举报





AI智能生成

数据结构与算法，leetcode刷题笔记

数据结构与算法

leetcode

模版推荐

作者其他创作

大纲/内容

基础数据结构

1. 双指针

1. 快慢指针

1.1 链表问题

141.环形链表

142.环形链表2

160.相交链表

19.删除链表的倒数第n个节点

21.合并两个有序链表

23.合并k个有序链表

876.链表的中间节点

1.2 数组

26.原地删除数组中的重复项

2. 左右指针

1. 二分查找

167.两数之和

344.反转数组

5.最长回文子串：从中心 --> 两端

66.剑指offer-52.两个链表的第一个公共节点

3. 滑动窗口

5.最长回文子串

76.最小覆盖子串

567.字符串的排列

438.找到字符串中所有字母异位词（排列）

3.无重复字符的最长子串

1477.找到和为目标值且不重叠的子数组

771.字符串中最长的连续出现的字符

799.最长连续不重复子序列

800.数组元素的目标和

4. 二分搜索

4.1 寻找一个数

4.2 寻找左右边界

2. 前缀和 && 差分数组

2.1 前缀和 preSum [n + 1]

原理

preSum[i] = num[i - 1] + preSum[i - 1]

2.1.1 一维数组

2.1.2 二维数组

2.2 差分 diff[ n ]

原理

多次、区间内的、加减操作（比如航班预定、公交车等问题）

[l, r]：diff[l] += k， diff[r + 1] -= k

计算原数组的某个值：a[i] = diff[i] + a[i-1]

计算原数组：对diff数组求前缀和

应用

1094.拼车

1109.航班预定系统

5. 单调栈

6. 单调队列

二叉树

1. 通用思路

分析题目，选择算法

1. 是否可以通过遍历一遍得到答案？—— 外部变量 + void dfs()

2. 是否可以定义一个dfs，设计返回值，通过子问题推导出答案？int dfs()

ps：如何设计？：单独一个二叉树节点，它需要做什么事情？需要在什么时候做？（前/中/后序位置）

ps：注意baseCase！

算法1：遍历思维

297.序列化与反序列化二叉树

算法2：分解子问题思维

1. 最值问题（利用后序位置）

104. 最大深度、543直径

124. 最大路径和

687. 最大同值路径

652. 寻找重复的子树

2. 构造新的二叉树

654. 最大二叉树

105. 前中序序列构造二叉树

106. 后中序序列构造二叉树

889. 前后序序列构造二叉树

2. BST二叉搜索树

原理

左节点 < 根 < 右节点

中序遍历序列：升序

复杂度：logN

应用

1038.从BST到更大和树

230.从BST中第K小的元素

538.把BST转换为累加树

450.删除BST树中的节点

700.BST中的搜索

701.BST中的插入操作

98.验证BST树

3. 归并排序

原理

二分 + 二叉树后序遍历 + merge合并（双指针）

应用

912.排序数组

315。计算右侧小于当前元素的个数

493.翻转对

327.区间和的个数

回溯与BFS

回溯

原理

1. 维护【选择列表】（可以通过boolean数组记录状态）

2. 前序位置：做选择

3. 后序位置：撤销选择

4. 结束条件：添加结果、可以提前返回、累加次数等

应用

46.全排列

51.N皇后

52.N皇后2

数学形式

1. 组合问题（子集）

标准框架

场景

无重复元素：backtrack（nums, i+1）

有重复元素：要排序，再剪枝

1. 先对nums排序

2. 剪枝：如果发现 nums[i] == nums[i-1] ，则跳过

无重可复选

backtrack（nums, i）

base case：trackSum > target, return（因为重复选，不添加base case会无限循环）

应用

216.组合总和3

39.组合总和

40.组合总和2

77.组合

78.子集

90.子集2

2. 排列问题

场景

无重复元素

全排列：base case：track.size() == nums.length

k个元素全排：base case：track.size() == k

有重复元素

固定相同元素在排列中的相对位置，不同的排列即变成一种排列

if (i > 0 && nums[i] == nums[i-1] && !used[i-1])

无重可复选

去除boolean[] uesd 控制即可

应用

46.全排列

47.全排列2

BFS

动态规划

贪心

 Collect

Get Started

Dijkstra算法

 Collect

Get Started

Android知识总结

 Collect

Get Started

数据结构与算法

 Collect

Get Started

预测算法流程图





0 条评论

下一页