# 面试算法总结

**Repository Path**: itmwuma/algorithm-summary

## Basic Information

- **Project Name**: 面试算法总结
- **Description**: 总结校招面试经常出现的算法题，汇总题型以及解题思路
参考“剑指Offer”和“Leetcode热题100道”部分内容
- **Primary Language**: C++
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2022-09-06
- **Last Updated**: 2022-10-09

## Categories & Tags

**Categories**: Uncategorized

**Tags**: 算法, Cpp, 面试

## README

# 面试算法总结

### 介绍

总结校招面试经常出现的算法题，汇总题型以及解题思路
参考`剑指Offer`和`Leetcode热题100道`部分内容



### 算法汇总

相应数据结构定义如下：

> ```cpp
> // 二叉树结点
> struct TreeNode
> {
> 	int val;
> 	TreeNode* left;
> 	TreeNode* right;
> 
> 	TreeNode() : val(0), left(nullptr), right(nullptr) {}
> 	TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
> };
> 
> // 链表结点
> struct ListNode
> {
> 	int val;
> 	ListNode* next;
> 
> 	ListNode() : val(0), next(nullptr) {}
> 	ListNode(int val) : val(val), next(nullptr) {}
> };
> ```



#### 1. 数组

技巧：

- 左右指针法
- 快慢指针法
- 从后向前扫描
- 滑动窗口
- 二分思想
- partition思想
- merge思想



题目：

1. 两数之和
2. 两数之和（数组已排序）
3. 合并有序数组
4. 移动零
5. 找到所有数组消失的数字
6. 二分查找
7. 数组中心位置
8. 统计素数个数
9. 平方根
10. 三个数的最大乘积
11. 子数组的最大平均值
12. 排列硬币问题
13. 数组中重复的数字
14. 二维数组的查找
15. 旋转数组的最小数字
16. 调整数组顺序使奇数位于偶数前面
17. 数组中出现次数超过一半的数字
18. 最小的k个数
19. 数据流中的中位数
20. 连续子数组的最大和
21. 1~n整数中1出现的次数
22. 数字序列中某一位的数字
23. 把数组排成最小的数
24. 丑数
25. 数组中的逆序对



#### 2. 链表

技巧：

- 快慢指针法
- dummyHead



题目：

1. 合并有序链表
2. 删除链表重复元素
3. 环形链表判断
4. 找到入环结点
5. 无环链表相交结点
6. 回文链表
7. 从尾到头打印链表
8. 删除链表结点
9. 链表的倒数第k个结点
10. 翻转链表
11. 复杂链表的复制



#### 3. 二叉树

技巧：

- 回溯思想
- 分解思想



题目：

1. 二叉树的三种遍历（递归|非递归）
2. 二叉树层次遍历
3. 平衡二叉树
4. 完全二叉树
5. 翻转二叉树（二叉树的镜像）
6. 树的子结构
7. 对称二叉树
8. 之字形打印二叉树
9. 二叉搜索树的后序遍历序列
10. 二叉搜索树与双向链表
11. 二叉搜索树的第k大结点
12. 二叉树的最小深度
13. 二叉树的最大深度
14. 两个结点的最低公共祖先
15. Morris遍历



#### 4. 图

题目：

1. 图结构的转化
2. DFS
3. BFS
4. 拓扑排序
5. P算法
6. K算法
7. D算法



#### 5. 字符串

技巧：

- 快慢指针法
- 左右指针法
- 滑动窗口



题目：

1. 大数加法
2. 字符串解码
3. 有效括号（有通配符版本）
4. 字符串匹配
5. 替换空格
6. 最长不含重复字符的子字符串
7. 翻转单词顺序
8. 实现atoi()函数



#### 6. DFS & 回溯

技巧：

访问  =>  记录  =>  选择  =>  回退



题目：

1. 全排列问题
2. 组合问题
3. 岛问题
4. 矩阵中的路径
5. 机器人运动范围



#### 7. 动态规划

技巧：

暴力递归  =>  记忆化搜索  =>  迭代



题目：

1. 斐波那契数列
2. 爬楼梯问题
3. 01背包
4. 完全背包
5. 最大子序和
6. 最长公共子串
7. 零钱兑换问题
8. 礼物的最大价值
9. 打家劫舍问题



#### 8. 位运算

技巧：

- 异或运算：交换律、结合律、0与任何数异或均为该数本身、任何数与自身异或均为0
- 奇偶判断：& 1
- *2：<< 1
- /2：>> 1
- 取模：& (n-1)
- 清除最右1：x = x&(x-1)



题目：

1. 只出现一次的数字
2. 比特位计数
3. 汉明距离



#### 9. 贪心算法

题目：

1. 买股票的最佳时机



#### 10. 排序

题目：
1. 冒泡排序
2. 选择排序
3. 插入排序
4. 归并排序
5. 快速排序
6. 堆排序


#### 11. 其它

题目：

1. 两个栈实现队列
2. 队列实现栈
3. 包含min函数的栈
4. 队列的最大值



### 参与贡献

***itmWuma***：https://gitee.com/itmwuma