干货！高频手撕算法合集来了
The following article is from 我是程序员小贱 Author L的存在
我是程序员小贱
从面试出发，解剖各个知识点，让我们向上成长！这里除了学习，还有音乐，生活摄影，篮球等，期待你的加入！
基础数据结构的融合是成为庞大系统的基石。比如Redis中的跳跃表，数据库索引B+树等，只有对基础的数据结构足够的熟悉才能更容易去理解稍微复杂的结构，就仿佛我们闯关打怪一样，一步一步解锁直到结局。今天想和大家一起分享的是常见数据结构以及面试中的高频手撕算法题，一定要去手动写这些代码，可说百分之七八十都是这些题，一定要好好掌握。
数据结构
链表属于数据结构中的线性结构的一种，我们先看看什么是数据结构
数据结构是：结构的定义+结构的操作
想必大伙儿应该玩儿过拼图，拼图之前我们先看看说明书，看看包含几个部分，然后对这些部分进行拼装，随后拼好候进行组合直到完成。
一个链表是由1个或者多个节点组成，每个节点包含两个信息，一个是数据信息，用来存储数据，一个是地址信息，用来存储下个节点的地址。
那在代码中是什么样子呢？
struct Node {
int data;
struct Node *next;
};
链表操作
说到链表结构，我们习惯性的和数组联系在一起。只是数组结构在内存中是连续的，而链表结构因为指针域的存在，每个节点在内存中存储的位置未必连续。下面我们按照数组的方式给链表也编个号。
struct Node *insert(struct Node *head, int ind, struct Node *a);
第一个参数为待操作的链表的头结点地址，也就是第一个节点的地址。 第二个参数为插入位置。 第三个参数为指针变量，指向要插入的新节点。
struct Node *insert(struct Node *head, int ind, struct Node *a) {
struct Node ret, *p = &ret;
ret.next = head;
// 从虚拟头节点开始向后走 ind 步
while (ind--) p = p->next;
// 完成节点的插入操作
a->next = p->next;
p->next = a;
// 返回真正的链表头节点地址
return ret.next;
}
案例
我们看个题吧，定义一个快乐数，什么是快乐数，所谓快乐数即通过有限次变换后等于1 的数字。怎么变换呢，给出一个非1的数字，然后出去位数，求各个位数的平方和，得到数字A，假设A不死1，那就继续对元素A的每一位进行平方和，得到数字B。。。。知道最后能够=1。
在上面我们介绍了最后一个节点指向空，可是你有没有想过如果链表的最后一个节点不是空地址而是指向链表中的一个节点，这不就是环了？
使用数组标记的方法。记录出现过的节点信息，每次遍历新节点就去数组查看记录，这样的时间复杂度不给力。经过第一个节点，需要在数组查找0次，第2个节点，数组查找1次，第i个节点，在数组查找i-1次，直到遍历第n+1个节点，查找的总次数为(n + 1) * n / 2，这样时间复杂度为O(n^2)。太慢了，给我优化。 快慢指针法。
AB两位同学跑步，A同学速度快，B同学速度慢，他们并不知道跑道是环形的，如果是环形，跑得快的，在足够的时间终究会从速度慢的B同学经过，形成相遇的情况。如果不是环形，速度快的先到重点，不会相遇---快慢指针法。
int hasCycle(struct Node *head) {
if (head == NULL) return 0;
// p 是慢指针，q 是快指针
struct Node *p = head, *q = head;
// 每次循环，p 走1步，q 走2步
do {
p = p->next;
q = q->next;
if (q == NULL) return 0;
q = q->next;
} while (p != q && q);
return p == q;
}
二分查找初探
说到二分查找，这里就有个笑话了。
二分查找基础
最简单的二分算法即在一个有序数组中，查找一个数字X是否存在。注意有序性。那么如何在数组中查找一个数。
从头到尾一个一个查找，找到即有数字x。 二分算法即通过确定一个区间，然后查找区间的一半和x比较，如果比x大则在x前半段查找。如果比x小则在后半段查找，只需要log2n的比较即可确定结果。
int BinarySerach(vector<int>& nums,int n, int target) {
int left = 0, right = n-1;
while (left <= right) {
int mid = (left+right)/2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid-1;
}
return -1;
}
如果right和left比较的时候，两者之和可能溢出。那么改进的方法是mid=left+(right-left)/2.还可以继续优化，我们将除以2这种操作转换为位运算mid=left+((right-left)>>1).
哪有这么简单的事儿，大多数的笔试面试中可能会出现下面的几种情况。
二分的各种变种
思路
首先7与中间值a[4]比较，发现小于7，于是在5到9中继续查找，中间a[7]=7,但是这个数7不是第一次出现的。那么我们检查这个值的前面是不是等于7，如果等于7，说明目前这个值不是第一次出现的7，此时更新rihgt=mid-1。ok我们看看代码。
int BinarySerach(vector<int>& nums, int n,int target) {
int left = 0, right = n-1;
while (left <= right) {
int mid = left+((right-left)>>1);
if (nums[mid]>value)
{
right=mid-1;
} else if(nums[mid]<value)
{
left=mid+1;
}else
{
if((mid==0)||(nums[mid-1]!=value))
{
return mid;
}else
{
left=mid-1;
}
}
return -1;
}
假设nums[mid]这个值已经是最后一个元素了，那么它肯定是要找到最后一个值。如果nums[mid]的下一个不等于value，那说明nums[mid]就是我们需要找到最后一个等于给定值的值。
int BinarySerach(vector<int>& nums, int n,int target) {
int left = 0, right = n-1;
while (left <= right) {
int mid = left+((right-left)>>1);
if (nums[mid]>value)
{
right=mid-1;
} else if(nums[mid]<value)
{
left=mid+1;
}else
{
if((mid==n-1)||(nums[mid+1]!=value))
{
return mid;
}else
{
left=mid+1;
}
}
return -1;
}
如果nums[mid]小于要查找的值，那么我们需要查找在[mid+1,right]之间，所以此时更新为left=mid+1。 如果nums[mid]大于给定值value,这个时候需要查看nums[mid]是不是我们需要找的第一个值大于等于给定值元素，如果nums[mid]前面没有元素或者前面一个元素小于查找的值，那么nums[mid]就是我们需要查找的值。 如果nums[mid-1]也是大于等于查找的值，那么说明查找的元素在[left,mid-1]之间，所以我们需要将right更新为mid-1。
int BinarySerach(vector<int>& nums, int n,int target) {
int left = 0, right = n-1;
while (left <= right) {
int mid = left+((right-left)>>1);
if (nums[mid]>value)
{
right=mid-1;
} else if(nums[mid]<value)
{
left=mid+1;
}else
{
if((mid==n-1)||(nums[mid+1]!=value))
{
return mid;
}else
{
left=mid+1;
}
}
return -1;
}
如果nums[mid]小于要查找的值，那么我们需要查找在[mid+1,right]之间，所以此时更新为left=mid+1。 如果nums[mid]大于给定值value,这个时候需要查看nums[mid]是不是我们需要找的第一个值大于等于给定值元素，如果nums[mid]前面没有元素或者前面一个元素小于查找的值，那么nums[mid]就是我们需要查找的值。 如果nums[mid-1]也是大于等于查找的值，那么说明查找的元素在[left,mid-1]之间，所以我们需要将right更新为mid-1。
int BinarySerach(vector<int>& nums, int n,int target) {
int left = 0, right = n-1;
while (left <= right) {
int mid = left+((right-left)>>1);
if (nums[mid]>=value)
{
if(mid==0||nums[mid-1]<value)
{
return mid;
}else
{
right=mid-1;
}
}else
{
left=mid+1;
}
return -1;
}
如果nums[mid]小于查找的值，那么需要查找的值肯定在[mid+1,right]之间，所以我们需要更新left=mid+1。 如果nums[mid]大于等于给定的value，检查nums[mid]是不是我们的第一个值大于等于给定值的元素。
int BinarySerach(vector<int>& nums, int n,int target) {
int left = 0, right = n-1;
while (left <= right) {
int mid = left+((right-left)>>1);
if (nums[mid]>value)
{
right=mid-1;
}else
{
if(mid==n-1||(nums[mid+1]>value))
{
return mid;
}else
{
left=mid+1;
}
}
return -1;
}
队列
例子：滑动窗口最大值
火车站买票应该都经历过，窗口小姐姐每次服务排在最前面的那个人，买完票则从头部离开，后面人往前一步接替离开的人继续购票，这就是典型的队列结构。
假设将学生从高年级到低年级排列，随着时间的推移，高年级同学从队列头部毕业，低年级从尾部进入。大部分学校都有校队，假设小林高三，我高二，小七高一，小林毕业接班的是我，我毕业，很可能就是小七接班，而当我进队的那一刻，小七即使进的早但是战斗力没我高，所以小七是永远没计划被选中啦。所以，纵观全队，不仅有着队列的性质，也有着单调的性质，所以就是单调队列。
比较明显的作用是，用来维护队列处理顺序中的区间最大值。
滑动窗口没向后滑动一位，就有一个元素从队首出队，同时也会有个元素从队尾入队。这个题需要求区间的最大值：意味着需要维护在队列处理顺序中的区间最大值，直接上代码附上注释。
#define MAX_N 1000
int q[MAX_N + 5], head, tail;
void interval_max_number(int *a, int n, int m) {
head = tail = 0;
for (int i = 0; i < n; i++) {
// a[i] 入队，将违反单调性的从队列 q 中踢出
while (head < tail && a[q[tail - 1]] < a[i]) tail--;
q[tail++] = i; // i 入队
// 判断队列头部元素是否出了窗口范围
if (i - m == q[head]) head++;
// 输出区间内最大值
if (i + 1 >= m) {
printf("interval(%d, %d)", i - m + 1, i);
printf(" = %d\n", a[q[head]]);
}
}
return ;
}
栈与单调栈
栈结构对应于队列，可以将栈想象为一个只有单出口的羽毛球筒，羽毛球只能从单一的入口放入和取出。假设我们将1，2,3三个球放进球桶，如果取出来此时就是3,2,1。性质就很明显了，先进后出的结构。
({})
{()}
([)]
(((){}
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
Map<Character,Character> map = new HashMap<>();
char[] chars = s.toCharArray();
map.put(')','(');
map.put('}','{');
map.put(']','[');
for(int i=0;i < s.length();i++){
if(!map.containsKey(chars[i])) {
//为左括号时直接入栈
stack.push(chars[i]);
}else{
//为右括号时，如果栈为空或者栈顶与该括号类型不匹配返回false
if(stack.empty() || map.get(chars[i]) != stack.pop()){
return false;
}
}
}
//字符串遍历完毕后，如果栈为空返回true，反之返回false
return stack.empty();
}
递推套路
在分享递推之前，先和大家分享与之紧密的数学原理：容斥原理。
容斥原理是什么？
假设有一片草原上，莫名其妙来了一只外星兔子，这种外星兔子呢，第一个月的时候是幼体，第二个月成长为成体，从第三个月开始，成体兔子每个月都会产生出一只克隆体的幼体兔子，而且这种兔子不会衰老，一旦成体以后，就会一直生下去。按照这种情况，请你计算出第 n 个月，草原上有多少只兔子？
确定递推的状态，多画图前面几步。 推导递推公式。 程序的编写。
我们根据三步走的方式来阐释解决兔子的这个问题。
f(n)表示n个月兔子的数量。 递推公式(第一个月合第二个月兔子的数量为1，到了第三个月即等于前面两个月之和)。 递推公式
用 1 元、2 元、5 元、10 元、20 元、50 元和 100元凑成 1000 元钱，总共有多少种方案？
确定递推状态，需要分析自变量与因变量，自变量两个分别为币种种类和拼凑的钱币数量，因变量1个为方案总数，因此我们的状态定义为f(i,j)，i种钱币，拼凑j元钱的方案总数。比如f [3][10]即使用三种钱币，凑出10元的方案总数。 假设我们不使用第三种钱币，那么此时等价于使用前两种钱币拼凑10元钱的方案总数，即f[2][10]。如果使用至少1张5块钱，那么我们在这些方案中去掉一张5元钱，剩下的方案数为f[3][5]，所以此时的递推公式为f[3][10] = f[2][10] + f[3][5]。这只是一般情况，假设我们没有使用第i种钱币，拼凑j元的方案为f(i-1,j)，代表使用前i-1种钱币的方案总数。剩下的使用了第i中钱币，由于都存在第i钱币1张，假设第i种钱币的面额为val[i]，那么此时我们的前i种钱币，凑j-val[i]的钱数，此时方案总数为f(i,j-val[i])；所以公式为f(i,j)=f(i-1,j)+f(i,j-val[i])。
动态规划
动态规划通常简称DP(dynamic programming)，如果按照问题类型来划分，将分为线性DP、区间DP，数位DP等等，每当说到动态规划就会想最优子结构，重叠子问题等等，这些词汇苦涩难懂，不要慌，再难的问题也是建立在基础问题上，逐步拆分，这也是动态规划的思想，相信通过下面动态规划四步走的方式，加上习题的练习，一定会让你对动态规划有个新的理解。
状态定义
其实上面说递推的时候就已经有所涉及状态定义，通常在推导的过程中，如果感觉推不下去了，很有可能就是我们的状态定义出现了问题。
状态转移方程
上面的两种状态定义对应这里两个转移方向。
正确性证明
数学归纳法通常采用三步走的方式，常用的正确性证明方法为数学归纳法。
状态定义
状态方程
正确性证明
实现
#define MAX_V 10000
#define MAX_N 100
int v[MAX_N + 5], w[MAX_N + 5];
int dp[MAX_N + 5][MAX_V + 5];
int get_dp(int n, int W) {
// 初始化 dp[0] 阶段
for (int i = 0; i <= W; i++) dp[0][i] = 0;
// 假设 dp[i - 1] 成立，计算得到 dp[i]
// 状态转移过程，i 代表物品，j 代表背包限重
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
// 不选择第 i 种物品时的最大值
dp[i][j] = dp[i - 1][j];
// 与选择第 i 种物品的最大值作比较，并更新
if (j >= w[i] && dp[i][j] < dp[i - 1][j - w[i]] + v[i]) {
dp[i][j] = dp[i - 1][j - w[i]] + v[i];
}
}
}
return dp[n][W];
}贪心
其实我们大学学习的好几种应用都是采用了贪心的算法啊，比如Huffman Coding，Prim最小生成树等。
有n个盒子排成一行，每个盒子上面有一个数字a[i]，表示最多能向右跳a[i]个盒子；小林站在左边第一个盒子，请问能否到达最右边的盒子？比如说：[1, 2, 3, 0, 4] 可以到达第5个盒子；[3, 2, 1, 0, 4] 无法到达第5个盒子；
我们有 m 个糖果和 n 个孩子。我们现在要把糖果分给这些孩子吃，但是糖果少，孩子多（m<n），所以糖果只能分配给一部分孩子。 每个糖果的大小不等，这 m 个糖果的大小分别是 s1，s2，s3，……，sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。假设这 n 个孩子对糖果大小的需求分别是 g1，g2，g3，……，gn。
我的问题是，如何分配糖果，能尽可能满足最多数量的孩子？
对于一个孩子来说，如果小的糖果可以满足，那么就没必要用更大的糖果。 对糖果的大小需求的孩子更容易被满足，所以我们可以从需求小得孩子开始分配糖果。 因为满足一个需求大的孩子跟满足一个需求小的孩子，对我们期望值的贡献是一样的。 我们每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
解题思路：
遍历两边，首先每个人得一块糖，第一遍从左到右，若当前点比前一个点高就比前者多一块。
这样保证了在一个方向上满足了要求。第二遍从右往左，若左右两点，左侧高于右侧，但
左侧的糖果数不多于右侧，则左侧糖果数等于右侧糖果数+1，这就保证了另一个方向上满足要求。
最后将各个位置的糖果数累加起来就可以了。
*/
int candyCount(vector<int>&rating) {
int res = 0;
//孩子总数
int n = rating.size();
//糖果集合
vector<int> candy(n, 1);
//从左往右遍历
for (int i = 0;i < n - 1;i++) {
if (rating[i + 1] > rating[i])candy[i + 1] = candy[i] + 1;
}
//从右往左
for (int i = n - 1;i > 0;i--) {
if (rating[i - 1] > rating[i] && candy[i - 1] <= candy[i])
candy[i - 1] = candy[i] + 1;
}
//累加结果
for (auto a : candy) {
res += a;
}
return res;
}
//测试函数
int main() {
vector<int> rating{1,3,2,1,4,5,2};
cout << candyCount(rating) << endl;
return 0;
}
唠嗑
也许当我们工作了以后，才知道如果有一小段时间可以安心的思考一道算法题目是多么美好的事儿。算法的技巧文章太多太多，可谓眼花缭乱，以致于自己都不知道看什么资料。 看太多的书真不如"刀枪实战"，直接去Leetcode或者其他算法平台练习，不过练习真的需要章法，毕竟咋们时间也有限，在我看来分类刷比较好，最好可以从树来刷题，咋们不能靠数量取胜，需要读题思考，写代码，看看是否有其他方法来优化，以致于让自己更深入的了解这代码逻辑以及优化原理。
更多精彩推荐
Go to "Discover" > "Top Stories" > "Wow"