# 数据结构与算法大全（四）算法技巧

## 目录

六、双指针相关

七、栈相关算法

八、链表相关算法

九、二叉树相关

十、深度优先和广度优先算法

十一、贪心算法

十二、回溯算法

十三、动态规划

## 六、双指针相关

### 1. 相关算法题目

- 527，两个数组的交集 II

- 1. 题目

- 给定两个数组，编写一个函数来计算它们的交集。

- 示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]

输出:[2,2]

- 解题思路

- 先对两个数组进行排序，然后使用两个指针，分别指向两个数组开始的位置。

- 如果两个指针指向的值相同，说明这个值是他们的交集，就把这个值加入到集合list 中，然后两个指针在分别往后移一步。

- 如果两个指针指向的值不同，那么指向的值相对小的往后移一步，相对大的先不 动，然后再比较

- 514，双指针解替换后的最长重复字符

- 1. 题目

- 给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字 符，总共可最多替换k次。在执行上述操作后，找到包含重复字母的最长子串的长度。

- 497，双指针验证回文串

- 1. 题目

- 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小 写。

- 2. 解题思路

-

“回文串”是一个正读和反读都一样的字符串，也就是说他是左右两边对称的。验证一个 字符串是否是回文串，最简单的一种方式就是使用两个指针，一个从前开始，一个从后 开始，两个指针同时往中间走，如果他们指向的字符不一样，那么这个字符串肯定不是 回文字符串，直接返回false即可，如果这两个指针相遇了，直接返回true。

- 466， 使用快慢指针把有序链表转换二叉搜索树

- 1. 题目

- 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对

值不超过 1。

- 2. 解题思路

- 二叉搜索树的特点是当前节点大于左子树的所有节点，并且小于右子树的所有节点，并 且每个节点都具有这个特性。

- 题中说了，是按照升序排列的单链表，我们只需要找到链表的中间节点，让他成为树的 根节点，中间节点前面的就是根节点左子树的所有节点，中间节点后面的就是根节点右 子树的所有节点，然后使用递归的方式再分别对左右子树进行相同的操作......

## 七、栈相关算法

### 1. 相关题目

- 523，单调栈解下一个更大元素 II

- 1. 题目

- 给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素)，输出每个元素的 下一个更大元素。数字x的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个 比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输 出-1。

- 2. 解题思路

- 具体操作是，首先遍历数组中的所有元素，遍历的时候判断栈是否为空:

一，如果栈为空，就把遍历的元素下标加入到栈中。 二，如果栈不为空，查看栈顶元素在数组中对应的值是否小于这个遍历的元素:

1，如果小于，说明栈顶元素遇到右边第一个比他大的值，然后栈顶元素出栈，记录 下这个值。如果栈还不为空，继续判断......

2，如果不小于，把当前遍历的元素下标加入到栈中。

- 416，剑指 Offer-用两个栈实现队列

- 1. 题目

- 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列 中没有元素，deleteHead 操作返回 -1 )

- 2. 解题思路

- 做这题之前我们首先要明白一点就是，栈是先进后出的，队列是先进先出的。我们可以 使用两个栈stackPop和stackPush，往队列中添加元素的时候直接把要添加的值压入 到stackPush栈中。往队列中删除元素的时候如果stackPop中有元素我们就直接删 除，如果没有元素，我们需要把stackPush中的元素全部出栈放到stackPop中，然后 再删除stackPop中的元素。这样做的目的我们就可以保证stackPop中的元素永远都是 比stackPush中的元素更老。

## 八、链表相关算法

### 1. 相关题目

- 502，分隔链表的解决方式

- 1. 题目

- 给你一个链表和一个特定值x，请你对链表进行分隔，使得所有小于x的节点都出现在大 于或等于x的节点之前。

- 你应当保留两个分区中每个节点的初始相对位置。

- 2. 解题思路

- 这题是让把节点值小于x的节点都放到前面，最简单的一种解决方式就是把原链表的节点 分隔为两个链表，其中一个链表节点的值都是小于x的，另一个链表节点的值都是大于或 等于x的，最后再把这两个链表合并即可。

- 463， 判断回文链表的3种方式

- 1. 题目

- 请判断一个链表是否为回文链表。链表为单向无环链表

- 2. 解题思路

- 1. 反转后半部分链表

- 这题是让判断链表是否是回文链表，所谓的回文链表就是以链表中间为中心点两边对 称。我们常见的有判断一个字符串是否是回文字符串，这个比较简单，可以使用两个指 针，一个最左边一个最右边，两个指针同时往中间靠，判断所指的字符是否相等。

## 九、二叉树相关

### 1. 相关题目

- 464. BFS和DFS解二叉树的所有路径

- 1. 题目

- 给定一个二叉树，返回所有从根节点到叶子节点的路径。

- 2. 解题思路

- 1. DFS解决

- 这题让求的是从根节点到叶子节点的所有路径，最常见的一种方式就是DFS(深度优先 搜索)，也就是从根节点沿着最左边节点一直走下去(如果没有左子节点，有右子节 点，会沿着右子节点走下去)，当到达叶子节点的时候在返回到父节点，然后沿着父节 点的右子节点开始走下去

- 2. BFS解决

- 只需要使用一个队列，把每层的节点都存放到队列中，然后再一个个出队，顺便把子节 点在一个个存放到队列中......一直这样循环下去，直到队列为空为止

- 3. 递归实现

- 我们来思考这样一个问题，如果知道了左子树和右子树的所有路径，我们在用根节点和 他们连在一起，是不是就是从根节点到所有叶子节点的所有路径，所以这里最容易想到 的就是递归

- 4. 总结

- 二叉树的遍历常见的也就是前序遍历，中序遍历，后续遍历，BFS，DFS，以及莫里斯 的前序，中序和后续这几种，有的还说前序遍历就是DFS，其实可以这么说。但DFS却 不是前序遍历，因为DFS不光可以先从左子树开始遍历还可以先从右子树开始遍历。

## 十、深度优先和广度优先算法

### 1. 相关题目

- 507，BFS和DFS解二叉树的层序遍历 II

- 1. 题目

- 给定一个二叉树，返回其节点值自底向上的层序遍历。(即按从叶子节点所在层到根节点 所在的层，逐层从左向右遍历)

- 2. 解题思路

- 1. BFS解决

- 这题类似于二叉树的BFS打印，就是一层一层的打印，一般情况下对于二叉树我们都是从 上往下打印，但这题是从下往上打印。直接从下往上不太好操作，可以换种思路，因为题 目要求的结果是从下往上就可以了，并没有要求打印的过程。

- 2. DFS解决

- 对于这道题我们从根节点往下走的时候，每一层都会有一 个集合list，用来存放当前层的节点值，如果当前层的list没有创建，就先创建。

## 十一、贪心算法

### 1. 相关题目

- 516，贪心算法解按要求补齐数组

- 1. 题目

-

给定一个已排序的正整数数组nums，和一个正整数n。从[1, n]区间内选取任意个数字 补充到nums中，使得[1,n]区间内的任何数字都可以用 nums中某几个数字的和来表 示。请输出满足上述要求的最少需要补充的数字个数。

- 2. 解题思路

- 假设数组中前k个数字能组成的数字范围是[1,total]，当我们添加数组中第k+1个数字 nums[k]( 数 组 的 下 标 是 从 0 开 始 的 ) 的 时 候 ， 范 围 就 变 成 了 [1,total]U[nums[k],nums[k]]U[1+nums[k]，total+nums[k]]，这是个并集，可 以合并成[1,total]U[nums[k],total+nums[k]]，我们仔细观察一下

- 1，如果左边的total<nums[k]-1，那么他们中间肯定会有空缺，不能构成完整的[1， total+nums[k]]。

- 举个例子 [1,5]U[7,10]，因为5<7-1，所以是没法构成[1,10]的

- 这个时候我们需要添加一个数字total+1。先构成一个更大的范围[1，total*2+1]。 这里为什么是添加total+1而不是添加total，我举个例子，比如可以构成的数字范围是 [1,5]，如果需要添加一个构成更大范围的，我们应该选择6而不是选择5。

- 2，如果左边的total>=nums[k]-1，那么就可以构成完整的[1，total+nums[k]]，就 不需要在添加数字了。

## 十二、回溯算法

### 1. 相关题目

- 520，回溯算法解火柴拼正方形

- 1. 题目

- 还记得童话《卖火柴的小女孩》吗?现在，你知道小女孩有多少根火柴，请找出一种能使 用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴 都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼 成正方形。

- 2. 解题思路

- 首先先求出所有火柴的长度，然后判断是否是4的倍数，如果不是，直接返回false，表 示不能拼接成正方形，如果是4的倍数然后在往下走。

把每一根火柴都尝试往4条边上放，如果最终能构成正方形，直接返回true。

## 十三、动态规划

### 1. 相关题目

- 517，最长回文子串的3种解决方式

- 1. 题目

- 给你一个字符串s，找到s中最长的回文子串。

- 2. 解题思路

- 1. 暴力求解

- 暴力求解是最容易想到的，要截取字符串的所有子串，然后再判断这些子串中哪些是回文 的，最后返回回文子串中最长的即可。

- 这里我们可以使用两个变量，一个记录最长回文子串开始的位置，一个记录最长回文子串 的长度，最后再截取。

- 2. 动态规划

- 定义二维数组dp[length][length]，如果dp[left][right]为true，则表示字符串从 left到right是回文子串，如果dp[left][right]为false，则表示字符串从left到right不 是回文子串。

- 如果dp[left+1][right-1]为true，我们判断s.charAt(left)和s.charAt(right)是否相 等，如果相等，那么dp[left][right]肯定也是回文子串，否则dp[left][right]一定不是 回文子串。

- 所以我们可以找出递推公式

- 1 dp[left][right]=s.charAt(left)==s.charAt(right)&&dp[left+1][right-1] 有了递推公式，还要确定边界条件:

- 如果s.charAt(left)!=s.charAt(right)，那么字符串从left到right是不可能构成子串 的，直接跳过即可。

- 如果s.charAt(left)==s.charAt(right)，字符串从left到right能不能构成回文子串还

- 需要进一步判断 如果left==right，也就是说只有一个字符，我们认为他是回文子串。即dp[left] [right]=true(left==right)

- 如 果 right-left<=2 ， 类 似 于 "aa" ， 或 者 "aba" ， 我 们 认 为 他 是 回 文 子 串 。 即 dp[left][right]=true(right-left<=2) 如果right-left>2，我们只需要判断dp[left+1][right-1]是否是回文子串，才能 确定dp[left][right]是否为true还是false。即dp[left][right]=dp[left+1] [right-1]

## 参考资料

- [数据结构和算法试题大全](
https://www.toutiao.com/i6903421300237353476)

历史文章和思维导图

https://gitee.com/zeus-maker/hunter