常见算法与数据结构

数据结构/算法	链表	二维数组	栈/队列	树	图	字符串	map	堆
多指针	反转链表 ,反转链表II，两数相加,盛水最多的容器
滑动窗口							最小覆盖子串，无重复字符的最长子串
贪心算法			去除重复字母
动态规划
递归	合并两个有序列表			相同的树
分治
堆栈队列结构辅助				二叉树的层序遍历
数学公式模型法	环形链表I	Z 字形字符串变换

链表类

多指针

pre辅助指针法

反转链表

pre辅助指针法 + 链表拼接

反转链表II

简单运算

两数相加

删除链表的倒数第 N 个结点

快慢指针

环形链表I

快慢指针 + 环状链表特征深度剖析

环形链表II

递归

合并两个有序列表

引入额外数据结构

环形链表I
环形链表II

排序算法(由小到大排序)

参考

最大值交换排序：每次从n-m+1个元素里选出最大的一个，和倒数第m个元素交换位置，m的取值范围是[2,n-1],时间复杂度On2，最优情况是On1，最坏是On2，没有额外空间开销

插入排序：从左边第一个元素开始，默认左边是已经排好序的，由左向右便利，把右边的第m个元素按大小顺序插入左边，外层

冒泡排序，每次遍历，凡是右边比左边大就对两者swap，这样一趟下来，第m次遍历后，第n-m+1个位置是最大值

两端排序递归法：两个指针begin和end分别指向数组最左和最右，beign不能位于end右边，end也不能位于begin左边，选取一个位置作为key，key通常是等于beign，右指针end先走，遇到小于key的停下，左指针开始走，遇到大于key的停下，判断此时begin和end是否相遇，没相遇的话begin和end的位置swap，相遇的话则对begin和end的位置和key的位置swap，此时arr[beign]右边都是大于它的，右边都是小于他的

间隔排序：gap初始值是数组长度，每次间隔gap，对gap范围内的数做排序，gap=gap/2，直到gap=0才算排序完成

堆排序

大根堆：最大堆是父节点，反之是小根对，数据长度为n，叶子节点下标为i，那么左子树节点2i,右子树节点就是2i + 1，最后一个非叶子节点是n/2 - 1;

将数组调整为小根堆的方法是，从最后一个非叶子节点开始调整，即选取左右节点最小的值和根节点交换，如此调整直到根节点，

链表能力算法

链表反转

对链表head做反转，定义当前节点指针cur与上一节点指针pre，cur初始化值为head，pre初始化为null(对应的head的上一节点是null)

循环条件为cur不为null时，定义节点tmp保存cur的next节点，cur的next指针指向pre，pre指针挪动到cur，cur挪到下一个节点即tmp

当cur为null时，pre即为反转后的链表的头结点，返回pre作为最终结果

链表加法

两个链表l1和l2相加得到结果值链表result，定义结果值链表resultList的头结点resultHead并为其堆内存new开辟空间，定义指针cur指向resultHead，遍历l1和l2，创建cur的next节点，为其new分配空间，每次遍历对l1和l2当前节点的结果值相加，大于10则进位1，余数作为当前节点的value复制给cur.next节点的value，cur指针移动到下一节点即cur=cur.next，循环结束后，如果carry不为0则，则需要在创建一个节点放到最后的位置即cur.next位置，返回值则是通过返回这个结果值链表resultList的头结点resultHead

链表旋转(链表中的每个元素向右移动距离k)

环状链表法：使用临时指针tmp指向链表head，挪动tmp到链表最后一个接口，该过程中使用count计数链表长度，使用tmp.next = head将链表连接成环，计算需要挪动的位置为count - k -1,将tmp挪动count - k -1的距离，定义一个ret指针是tmp的下一节点，然后断开tmp的next节点，返回ret，即完成链表旋转

左右分段拼接
根据规律将链表分为左右两端，然后再拼起来

链表排序

因为链表没有下标可用，排序算法中的交换排序，gap排序，分段递归排序都设计到非相邻值交换，利用数组的特征排序时间复杂度可达到On2，但如果是链表的话时间复杂度会达到On3，适合链表的是通过相邻元素运算的方式，例如插入排序与冒泡排序，此处选择插入排序方案

遍历列表，从第一个开始视为排序

插入/删除链表第n个节点

判断是否环形链表/获取环形开始的节点

哈希表法
通过判重哈希表key值唯一性的方式判断是否环状链表，哈希表key存储节点，value作为计数器，可以判断出环形链表开始的节点即首次出现重复的节点

双指针法
快慢指针法，fast和slow指针从head除非，fast每次挪动两个节点，slow每次挪动一个节点，当fast和slow相遇即可判断这是第一个环状链表

设环的长度为a，非环的长度是b，fast和slow挪动次数为s，那么当快慢指针相遇时满足关系

(2s - b) % a = (s - b) % a

此时可以看做快慢指针在移动b个位置就可以回到起点了，即（s+b-b) % a = 0,但我们无法得知b的具体值，但我们可以利用一个特点，就是我们利用第三个指针thrid向右挪动b次，slow指针也同时挪动b次，third和slow指针会正好在起点相遇，通过此特征可以获取到环的起点位置

递归

运算递归

2的幂

Pow(x, n)

链表递归

树

二叉树

二叉树特征

例如二叉树的前中后序遍历、层序遍历、判断两个二叉树是否相等，判断二叉树是否对称，二叉树最大深度

二叉树结构转换与构造

数组转二叉搜索树，二叉树展开为链表

二叉搜素树

二叉搜索树是一种二叉树，需要在二叉树的基础上满足以下几个性质

• 左子树性质：对于任意一个节点，其左子树中所有节点的键值都小于该节点的键值。
• 右子树性质：对于同一个节点，其右子树中所有节点的键值都大于该节点的键值。
• 子树递归性：树的每个子树也是一棵二叉搜索树。

相关题目
数组转二叉搜索树，数量为n的节点所能构造出二叉搜索树的个数

二叉搜索树转为排好序的双向链表

按中序遍历，遍历结果是将二叉搜索树由小到大排列，使用中序遍历，定义一个指针cur，cur初始化值是树的头结点root，定义一个前序节点pre作为当前cur的上一节点，初始化值为null，的挪动cur遍历树，中序遍历输出的第一个节点（此时pre和head均为为null），即可作为链表的头结点head但如果pre不为null的话就让pre的right指向cur，cur的left指向right，挪动pre到cur，对右节点做遍历,当前节点cur为null作为递归结束条件

滑动窗口算法

最小覆盖子串

无重复字符的最长子串

动态规划

自底(初始化构建底部)向上构建问题解，往往涉及到二维数组结构的应用，也就是我们为了得到(m,n)这个点的最优解，往往需要把这前(m*n)个点的坐标都给求出来，然后取(m,n)

1、定义二维数组arr[i][j]，同时构建横纵坐标模型，i为纵坐标，j为衡坐标,需要思考i、j和arr[i][j]分别代表什么含义，即代表xxx长度为i、j时的最优解的结果填充二维数组中arr[i][j]的值；

案例1，最长回文子串

暴力破解，两个指针外层循环，取两个指针范围内的字符串分别对其判断是否是回文，然后取里面的最大值

• 机器人棋盘路径数量问题，i为长度m的变量，j为宽度n的变量，arr[i][j]为长度为i，宽度为j时的路径数量
• 寻找网格最短路径问题，i为长度m的
• 变量，j为宽度n的变量，arr[i][j]为为长度为i，宽度为j时的最短路径和
• 将 word1转换成 word2 所使用的最少操作数问题，i和j分别代表着两个字符串的长度m和n，arr[i][j]带两字符串长分别为i和j时最小的子串长度
• 找word1和word2最长公共子序列问题，i和j分别代表着两个字符串的长度m和n，arr[i][j]带两字符串长分别为i和j时最长子序列长度；
• 寻找word1和word2最长公共子串问题，i和j分别代表着两个字符串的长度m和n，arr[i][j]带两字符串长分别为i和j时当前最新的最长的共有子串的长度；如果中间有过中断，即非先相等的时候，就把当前点设置为0，代表重新最算最大联系的子串，当前最大值会被记录到变量max中，当后续联系子串长度超过max会更新max

2、初始化、

• 机器人棋盘路径数量问， 因为只能向下或向右行走，所以最下面的格子arr[i][0]和最上面arr[j][0]格子均初始化为 0<i<m 和arr[j][0] 0<j<n 初始化为1，代表只有1条路可走
• 寻找网格最短路径问题，因为只能向下或向右行走，所以最下面的格子arr[0][i] += arr[0][i-1] 0<i<m 和arr[j][0] += arr[j][0] + arr[j-1][0] 0<j<n 初始化为1，代表最上面和最左边的最大值就是横/纵的简单加和
• 将 word1转换成 word2 所使用的最少操作数问题，arr[0][j] = j; arr[i][0] = i;即把一个不存在的字符word1/word2替换为长度为i或j的另一个需要i或j步；
• 寻找word1和word2最长公共子序列问题，dp[i][0]和dp[0][j]均为0，即有一方为0，那么他们的最长子序列均为0
• 寻找word1和word2最长公共子序列问题，dp[i][0]和dp[0][j]均为0，即有一方为0，那么他们的最长子序列均为0

3、找规律填充所以非特殊（非坐标轴）数组

• 机器人棋盘路径数量问题符合规律，也就是到达坐标(i,j)的路径数等于到达坐标(i-1,j)的路径和+到达坐标(i,j-1)的坐标数的相加，也就是从坐标(i-1,j)向右一步或从(i,j-1)向下一步，即dp[i][j] = dp[i-1][j] + dp[i][j-1]

• 寻找网格最短路径问题，也就是到达坐标(i,j)的位置等价于从坐标(i-1,j)向右一步或从(i,j-1)向下一步，也就从这两步里选择一个总和最小的，arr[i][j] = Math.max(dp[i-1][j] + dp[i][j-1]+arr[i][j]

• 将 word1转换成 word2 所使用的最少操作数问题，将word1看做横坐标i，word2看做纵坐标j，当前位置的word1和字符和word2 字符相等(word1.charAt(i-1) == word2.charAt(j-1))时,那意味着不需要任何操作，即dp[i][j] = dp[i-1][j-1]，不相等时则要考虑三种操作机制

  • 替换操作，即(i,j)前的坐标点都已经被操作为相同字符的前提下的dp[i][j] = dp[i-1][j-1] + 1
  • 删除或增加word1一个字符同步word2，即dp[i][j] = dp[i-1][j] + 1
  • 删除或增加word2一个字符同步word1，即dp[i][j] = dp[i][j-1] + 1
    由于我们目前是获取最小操作步骤，所以最终在当前i,j位置 word1和word2字符串不相等时，我们取值内容即为Math.max(Math.max( dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;

• 寻找word1和word2最长公共子序列问题,首先考虑当前位置i和j(word1.charAt(i-1) == word2.charAt(j-1))相等时dp[i][j] = dp[i-1][j-1] + 1,不相等时，那么此时最长公共子序列即为，那么dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1])

• 寻找word1和word2最长公共子序列问题，首先考虑当前位置i和j(word1.charAt(i-1) == word2.charAt(j-1))相等时dp[i][j] = dp[i-1][j-1] +1，不相等时不做任何操作，即当前位置的dp[i][j]还是0，所以相当于重新开始计算最大子串；

例题

编辑距离
最短路径
最长公共子序列、最长公共子串问题、选数问题
最长回文子串
最小路径和
编辑距离

贪心算法

求解一个问题，不考虑全局最优解，而且考虑某种意义上的局部最优解，通过这一个个局部最优解来完成某种操作(选择排序)、得出最优解结论(最少纸币问题、最多无重叠区间、最高效机器调度问题、股票最高收益问题)、可行性分析(跳跃问题)

案例

• 选择排序：每次从未排序的数据中选取最小值，并把最小值放在未排序数据的起始位置，直到未排序的数据个是为0结束排序，问题解决
• 跳跃游戏：在可达范围内一顺序循环遍历，获取最大值max，当max >= arr.length-1即成功，否则均失败
• 无重叠区间/最大安排活动数问题：(先排序)，按活动结束时间遍历由早到晚进行遍历，判断前一个的结束时间是否大于后面的开始时间，如果大于等于则无冲突，小于则有冲突
• 机器最高效调度问题：两个数组，一个代表任务对应工作量，一个代表机器当前已被分配的总工作量①先按任务量由大到小进行排序②每次筛选出最早完成的机器，然后把当前还未分配的工作里取出当前最大的工作分配给该机器人(初试时把前三个最大的任务依次分配给前三个机器人)③工作任务全部分配完毕，从三台机器中取出工作量总和最大的

去除重复字母，且保证返回字典序最小

思路，需要保证元素如果一个字符的开头在结果字符串中不是最小的，且后面存在和它相同的字符，那么移除这个字符，

构建这个返回结果的过程中，循环判断，如果后面插入的字符字典序比临近的上一个元素小，且上一个字符在后面的字符串中还会出现，那么移除这个字符，继续循环，直到遇到

分治算法

双指针法

最大蓄水量问题：right和left分别指向左边和右边的墙体，计算出当前的面积，如果左墙高于右墙，那么right左移，反之，left左移，再次计算面积，然后每次对比当前面积大小；

三数之和：

/*** 三指针法** first指向第一个元素，初始值为0，second在first后，初始值为first+1，third在second后且用于不等于小于second,（相等时则退出循环）* 初始值为num.length-1即指向数组最后一个** 当second和上一个距离大于first至少1个位置的元素相同的元素要一个个跳出理防止重复，first如果当前元素和上一个相同，那么就要不断跳出** 我们的目标值取target = -nums[first];** 当三个元素所指向的数组之和等于0时，即nums[second] + nums[third] = target时记录这三个元素 nums[second] + nums[third] < target时，* 继续second下次循环，使得second +1即可，如果nums[second] + nums[third] > target,那么我们就得不断移动third直到至少nums[second]和nums[third]* 家和不大于target;***/

数字反转

两数之和

哈希表的应用

两数字和，暴力算法的话，需要n的2次方时间复杂度，即两层for循环，第一层for循环是在第一次循环中找到分别找到和这个数组成target，并在第二次的循环中找到target所在的数据，而hash表则根据判断，第一次循环中如果hashmap中存在other，那么任务结束，返回结果，否则就将其存储在map中等待下一次的匹配

## 专辑，字符串处理

• 最长回文串：寻找回文动态规划、自底向上构建，由里到外填充，双重循环
• KMP算法（jdk核心api）：维护一个str2匹配表，和例如str1在第12个位置首尾元素相同时，str2整体和str1第12个后面比较发生不相等的时候，不会再从第13个开始匹配，而是根据匹配表查找可跳跃位数，比如这里这里匹配表查出的值为3，那么此时直接跳跃3个位置，从第15个开始匹配，大大提高匹配效率
• 最大公共子串/子序列（jdk核心api）：动态规划算法
• 无重复字符的最长子串 滑动窗口

字符串处理算法

KMP算法

主串长度n，子串长度m

暴力匹配算法，最坏情况时间复杂度为（n-m + 1)*n

栈相关

StringBuilder栈（单向）+ 数组字符哈希映射表
不同字符的最小子序列

链表栈（双向）

移掉 K 位数字使得剩下的数最小
建立一个双向链表栈，从左向右，第一个数先入栈，容纳后循环处理，如果后面的比前面小（通过栈顶peek来做比较）且k>0,i > 0,且栈中元素不为空，就通过deque出栈移除，存入右边的，k–，循环处理完毕，剩下的数就是递增的了，移除最后面的k位

自底向上处理deque，如果首位是0直接移除

动态规划
最长回文子串

双指针

贪心算法

整数转罗马数字
由大到小去处理问题，本题要注意的是不能用哈希表来存储数字于罗马字符对应关系，因为哈希表是无须的，可以用数组来解决

数据模型法

Z 字形变换

二维数组法，长n宽m，m=numRows, 一个z等于 z = 2*numRows - 2

• 余数 length % z = leave; lenLeave = leave - numRows > 0 ? leave - numRows : 1
• 个数 length / z = num;

最终数组的长和宽分别是

• n = num * (numRows - 1) + lenLeave
• m = numRows

结合实际规律对数组填充，第gap*n列由上到下依次填充，中间的每列只有一个点被填充，该点的坐标是[mIndex,j]，mIndex标识这个点的行号，取值范围是[m-2, 0),j是当前列

填充过程中，一旦发现当前字符串指针超过了字符串s的长度就返回arr，终止处理流程，返回二维字符数组arr，防止数组下标越界异常,将arr转为字符串

性能优化
将二维数组模型优化为StringBuilder列表（rows）模型，时间复杂度由On2降到On
列表的长度即为numRows，通过巧立flag，初始值为-1，定义指针指向rows中的元素，遍历字符串字符，用指针i所指向的row中的StringBuilder拼接这个字符
当i指向第一个（i = 0）和最后一个元素（i = numRows - 1）flag = -flag，i挪动flag个距离 最终处理完毕返回结果值

滑动窗口

无重复字符的最长子串

通过用双指针和一个hashMap结构的集合来模拟一个滑动的窗口来解决该问题，将字符串拆分成字符数组循环，start和end初始值为0，分别指向窗口的头和尾的下标，同时窗口的end指针就等于当前循环的指针，start和end之间的内容代表的窗口，窗口是动态移动的，start取值需要注意，需要考虑判断滑动窗口是否包含end所指向的字符，方法是判断hashMap中所存储的该字符的下标 + 1是否大于start，大于start说明是滑动窗口中的字符，start被调整否则就不是，需要用一个变量max随着外层指针的移动记录到动态窗口最大值。

循环递归

至少k个字符重复子串

jdk场景数据结构

本体是一个数组
transient Object[] elementData

add即为顺序插入数组

内存开销方面

result.toString().contains(String.valueOf(s.charAt(1)));

内存消耗分析

逻辑优化，使用一个字符串数组映射表，用于判断当前字符是否存在于这个字符串中

if中有多个并集，需要把过滤性高的提前