Leetcode和蓝桥算法思路整理

数据结构

链表

双向链表

循环链表

链表栈

堆链表

栈

堆

队列

二叉树

平衡二叉树

二叉搜索树

平衡二叉搜索树

哈夫曼树

堆—优先队列

最小堆

最大堆

B树

B+树

并查集

红黑树

线段树

邻接表

邻接矩阵

集合

哈希表

有序集合

字典树

数组

二分查找

移除元素

双指针

快慢指针

双向指针

前后指针

区间和

滑动窗口

链表

设计链表

反转链表

删除链表

删除链表倒数第N个结点

链表相交

两两交换链表的结点

约瑟夫问题

环形链表

哈希表

字符串

栈与队列

逆波兰表达式求值

二叉树

dfs

前序遍历

中序遍历

后序遍历

bfs

层序遍历

非递归遍历—迭代法

二叉树 相同 对称 平衡

二叉树最近公共祖先

递归

汉诺塔

分治

回溯算法

暴力剪枝

子集问题

组合数

全排列

N皇后

贪心算法

启发式算法

动态规划

从记忆化搜索到递推

背包

01背包

完全背包

多重背包

线性dp

树形dp

状态机dp

区间dp

滚动数组

编辑距离

图论

图的数据结构实现

dfs

bfs

岛屿问题

Dijastra算法

floyd算法

bellman_ford算法

Spfa算法

a*算法

最小生成树之kruskal算法

最小生成树之prim算法

并查集

有向图—无向图

冗余连接

拓扑排序

枚举右维护左

欧拉质数筛

循环数组

添加哨兵节点：在每个元素的位置列表前后各添加一个哨兵节点。前哨兵是最后一个出现位置减去数组长度，后哨兵是第一个出现位置加上数组长度。这样处理是为了将数组视为循环结构，方便处理边界情况。 for (auto& [_, p] : indices) { // 前后各加一个哨兵 int i0 = p[0]; p.insert(p.begin(), p.back() - n); p.push_back(i0 + n); } 由于 nums 是循环数组：

在下标列表前面添加 4−n=−3，相当于认为在 −3 下标处也有一个 1。 在下标列表末尾添加 0+n=7，相当于认为在 7 下标处也有一个 1

螺旋矩阵套路

有空结合hot100和代码随想录整理

模拟

按层模拟

单调栈套路

单调队列套路

入（元素进入队尾，同时维护队列单调性） 出（元素离开队首） 记录/维护答案（根据队首） 移除最左边的元素 移除最右边的元素 双端队列 在最右边插入元素 单调队列 从队首到队尾单调递减 单调性

总结:及时去掉无用数据,保证双端队列有序 当前数字 >= 队尾,弹出队尾(和单调栈一样) 弹出队首不在窗口内的元素

对角线遍历

3446 51N皇后

BM算法

坏字符规则 1.模式串中没有出现文本串中的那个坏字符d，将模式串整体对齐到这个字符的后方，继续比较 2.模式串有对应的坏字符，而且有两个 让模式串中最靠右的对应字符与坏字符相对 好后缀规则 1.如果模式串中存在已经匹配成功的好后缀，则把目标串与好后缀对齐， 2.如果无法找到匹配好的后缀，找一个匹配的最长的前缀，让目标串与最长的前缀对齐

KMP算法

辗转相除法—gcd—lcm

位运算

数学技巧

博弈论

模拟

排序

1.插入排序 2.冒泡排序 3.选择排序 4.堆排序 5.希尔排序 6.归并排序 7.桶排序 8.基数排序 9.物理排序 10.拓扑排序

例题

回文子串

中心扩展法 本题最容易想到的一种方法应该就是 中心扩散法。 中心扩散法怎么去找回文串？ 枚举所有回文中心并且尝试扩展 从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。举个例子，str=acdbbdaa 我们需要寻找从第一个 b（位置为 3）出发最长回文串为多少。怎么寻找？ 首先往左寻找与当期位置相同的字符，直到遇到不相等为止。 然后往右寻找与当期位置相同的字符，直到遇到不相等为止。 最后左右双向扩散，直到左和右不相等。 由于回文子串存在以单个字符和两个连续字符为中心的回文子串所以有两种中心扩展法 dp 状态定义dp[i][j]i到j的字符串是否是回文子串 遍历方向从下到上，从左到右 初始值全为false 递推公式如果dp[i] == dp[j]如果j - i <= 1说明为回文子串,如果dp[i+1][j-1]是回文子串所以dp[i][j]也是回文子串