2020最新-精选基础算法100题（面试必备）

杨利霞

2020最新-精选基础算法100题（面试必备）
8 p/ s5 a9 t' ]: N
1 g3 M9 d1 Z: Z- w  i" l2 }0x01.概述
作为一个程序员，算法能力必不可少，虽然不一定是算法工程师，但是算法还是彰显着个人的编码能力，面试中也经常会被问到，甚至会被要求临场做算法题，所以，还是好好积累吧。


) G) `1 o  p8 E8 L( K个人其实对算法挺有兴趣的，从3月份开始，陆陆续续刷了一些算法题，把一些有意义的记录下来了，也顺便写了一些题解，个人认为，还是挺有收获的。
! n! y% `" [" D' }# U$ W7 V之前写了一篇算法文章的目录，不过后来就忘了实时去更新了，于是现在，想把之前做过的一些有意义的算法题分享出来，刚好整理了100篇比较有意义的。希望对大家有所帮助。
' E; d& p5 T" \- _) z



0x02.说明
9 L9 u: s- q7 B! M* A关于语言的选择：
8 w5 j& u* L  x7 `+ F' \' k, ~( @

5 x& n/ a8 J4 D$ V: \1 P; J前半段主要用C++写的，后半段主要用Java写的。
) j4 G, w3 R1 ^& G5 t其实什么语言没有太大区别，主要是思想，用着顺手就行。
这里安利一波Java，哈哈，Java写算法题写多了，真的比较舒适。
6 j% s  L) {0 y- h& z关于文章类型的选择：


. b% X& m/ A% Y1 I选取了一些较为基本的算法类型，都是比较常见的。
6 z% c- B& ?8 N- W. D9 ~5 m不涉及ACM等难度太高的题，大佬们移步哈。
都是一些比较经典的问题。
8 v9 N5 T$ M, L关于题目的来源：

% z- `( k! b1 v/ C
平时主要刷题的平台是Leetcode，因为是函数式的，比较方便。
+ `5 J+ ^4 V# _还有一些是在《剑指offer》，《程序员面试金典》中看到比较好的，所有题目后面都给出了出处。
关于题解的说明：
' n3 h( R( G, m9 f3 Z
7 w1 K( y' b3 o7 R# _
题解是我自己所写，有时候也参考了一些官方题解的思想，可能更好理解。
题解的代码都提交测试过的，保证暂时没有问题。
" u- S  T, l; Z3 P- `2 s4 _- C个人水平有限，可能文章里面存在一些问题，还望大佬多多指点。
( P& N% m6 B0 E( q& g8 r每个题目附带了原文链接，不喜欢阅读我题解的小伙伴们也可以直接移步原出处哈。
8 J' i: w4 u: J关于算法能力提升的一些意见：
$ D4 J, O# U0 B3 |9 ]) @
  B- D8 u* g9 \: n, r8 e
个人认为，算法来说，思想最为重要，有算法的严谨思想，才是算法能力提升的基础。
刷题就是培养算法思想的一种实际行动。
好好理解透一个问题，或者一类问题，远胜于你麻木的刷大量的题。
2 ]  @; x5 l; e" g. j# t& H算法确实也有模板题，只需要照着模板就能做出，但问题是，照着模板就一定能做出来嘛，是否真正理解了为什么这个模板可以通用。
2 N* X% f/ S% k8 `/ x关于分类：


: j' R4 s( c& H1 x5 D  \有些分类确实不太好分，所以就单独列出来了。
" L1 l- _% r( ~7 x9 L' |主要的还是区分开来了。
. Y3 Y- w4 l' X0x03.正文–精选算法100题（附个人题解）
分类一：动态规划（dp）
& y% k8 R2 m/ X! S, R/ T没错，就是你熟悉的dp，dp说简单也简单，说难也实在是太难了，重点是如何找到里面的状态转移方程。经过这些题目的训练，希望你能有一些初步的dp思路了。
. D* @) Z* [7 m' k0 s% V
) L: _$ O. L, A: `4 p+ E
; U) d) J( ^2 ]7 W题目名称        来源        个人题解        备注
5 ^3 e5 d! \; |3 q9 _( E# G9 K$ O01.打家劫舍        Leetcode题198：戳我前往        戳我前往        估计是最好的dp入门题型了
02.斐波拉契数列        经典问题        戳我前往        确实比较经典哦~
) d7 f( c+ a0 r  h0 i- I03.零钱兑换问题        Leetcode题322：戳我前往        戳我前往        也是一个比较经典的问题了
04.零钱兑换II        Leetcode题518：戳我前往        戳我前往        零钱问题通用解法
2 ^& s3 O$ Q, ]* ^05.最长上升子序列        Leetcode题300：戳我前往        戳我前往        堪称数组dp中的典范
06.牌型种数        蓝桥杯：链接暂无        戳我前往        二维动态规划，要仔细想想
07.最低票价        Leetcode题983：戳我前往        戳我前往        如何状态转移？
! n: f, N% P7 S; X. S& L08.不同的二叉搜索树        Leetcode题152：戳我前往        戳我前往        你会发现dp的神奇之处
09.礼物的最大价值        《剑指offer》题47        戳我前往        优化dp的思路
" |5 c. Q0 o2 N5 Z10.接雨水        Leetcode题42：戳我前往        戳我前往        需要仔细思考以发现dp
5 P+ U  y* ^" o- X% c* Q  Q11.编辑距离        Leetcode题72：戳我前往        戳我前往        最为经典的二维dp题型
12.买卖股票的最佳时机（6题）        Leetcode6题：戳我前往        戳我前往        统一化的dp思维，棒
" w! v+ S9 u, `& m13.鸡蛋掉落        Leetcode题887：戳我前往        戳我前往        有些难度哦~
14.最大正方形        Leetcode题221：戳我前往        戳我前往        矩阵中的dp思路
6 ]& v/ {0 v* `% s15.和为K的子数组        Leetcode题560：戳我前往        戳我前往        前缀和也是dp的思路
9 t1 ]$ o3 q, y) O分类二：搜索类（DFS，BFS，回溯，暴力搜索）
搜索类的算法题应该是随便哪个算法比赛都可以看到，虽然经典，但在这上面还是会有比较难的问题，所以，掌握基本思路和套路就显得格外重要。

. o& f8 _" P- d& A# s4 c9 H
题目名称        来源        个人题解        备注
3 M5 q+ y: C2 Z* m16.图的深搜和广搜        经典问题        戳我前往        搜索中的经典问题
( u; W& @- e3 @17.方格填数        蓝桥杯：链接暂无        戳我前往        揣摩一下DFS的思路
18.路径之谜        蓝桥杯：链接暂无        戳我前往        经典改编迷宫问题
9 B7 {: M2 X9 F- J19.岛屿的最大面积        Leetcode题695：戳我前往        戳我前往        最常见的矩阵中的DFS
20.逃离大迷宫        Leetcode题1036：戳我前往        戳我前往        各种搜索思想都可以应用
3 R! `$ d$ I% x7 C5 j8 \21.单词搜索        Leetcode题79：戳我前往        戳我前往        字符串中的搜索
$ Y$ I0 G' z0 L22.检查网格中是否存在有效路径        Leetcode题1391：戳我前往        戳我前往        思考另类的搜索
23.地图分析        Leetcode题1162：戳我前往        戳我前往        多源BFS
24.机器人的运动范围        《剑指offer》13题        戳我前往        DFS进行计数的基本思路
25.括号生成        Leetcode题22：戳我前往        戳我前往        用DFS生产括号
26.01 矩阵        Leetcode题542：戳我前往        戳我前往        矩阵中的搜索
! J( z( ^9 f4 T) c* c& d27.岛屿数量        Leetcode题200：戳我前往        戳我前往        根据需求使用DFS
0 q9 Q$ C# A; b+ k- j28.全排列问题        Leetcode题46：戳我前往        戳我前往        最经典的回溯算法
分类三：字符串
别忽视字符串的算法问题，它难起来可以非常难，简单的也很简单，面试喜欢提问，而且特别容易出错，需要引起重视。
+ u& ]& @& j3 e4 u' v
$ B' j7 C- U0 L/ L7 U9 T9 x
题目名称        来源        个人题解        备注
4 r4 `  e6 X# {' L9 |! w/ w29.KMP算法        经典算法        戳我前往        经典字符串匹配算法
# T0 p. W: q# K, R8 {* ]- d4 j4 |* U30.拼写单词        Leetcode题1160：戳我前往        戳我前往        很简单的字符串问题
! D2 m/ T: E9 y" j31.竖直打印单词        Leetcode题1324：戳我前往        戳我前往        简单但值得思考
32.不含 AAA 或 BBB 的字符串        Leetcode题984：戳我前往        戳我前往        巧妙构造出字符串
8 H& R0 M( b  Z% t( m' {  ]1 w0 i33.实现Trie（前缀树）        Leetcode题208：戳我前往        戳我前往        字符串中经典的算法
34.最长快乐前缀        Leetcode题1392：戳我前往        戳我前往        如何处理字符串的前后缀
35.单词搜索II        Leetcode题212：戳我前往        戳我前往        前缀树的应用
; i; ~8 x. d( R& }5 [36.单词的压缩编码        Leetcode题820：戳我前往        戳我前往        前缀树灵活运用
$ ^, e6 j! ~0 n6 i; w5 X37.判定字符是否唯一        《程序员面试金典》01.02        戳我前往        简单但值得思考
1 V: x, }8 w! E. h0 S0 @/ q38.判定是否互为字符重排        《程序员面试金典》 01.02        戳我前往        简单的面试题
* s# ]+ r% E, Y; B% h4 V7 b4 d, W39.无重复字符的最长子串        Leetcode题3：戳我前往        戳我前往        字符串中的滑动窗口
  X. J5 A* p7 O7 D2 [2 T40.字符串转换整数        Leetcode题8：戳我前往        戳我前往        需要考虑的细节很多
1 q- o8 E6 x: R8 I: ^) @6 T41.翻转字符串里的单词        Leetcode题151：戳我前往        戳我前往        正则匹配
/ ^1 Q. {) q. K# s42.整数转换英文表示        Leetcode题273：戳我前往        戳我前往        非常实用的算法题
* A* g* X5 T! D# a& N: h43.统计重复个数        Leetcode题466：戳我前往        戳我前往        循环结剪枝
44.超级回文数        Leetcode题906：戳我前往        戳我前往        字符串与大数的处理思路
45.单词子集        Leetcode题96：戳我前往        戳我前往        特征思想的应用
分类四：容器类（哈希表，栈，队列，Map，Set）
* Z! g/ A( ]% p容器类的算法题一般需要根据一些容器的特点来解决响应的问题，还有需要选择合适的容器进行新的数据结构的设计，掌握它们的使用，非常重要。


题目名称        来源        个人题解        备注
46.按位与为零的三元组        Leetcode题82：戳我前往        戳我前往        哈希表优化
% F+ l) e# g9 L' ^& x* I% x47.设计地铁系统        Leetcode题1396：戳我前往        戳我前往        合理选择容器
5 J6 e" B1 a9 N3 C0 m+ ~. [! d48.LFU缓存        《程序员面试金典》        戳我前往        选择容器来设计
49.设计推特        Leetcode题355：戳我前往        戳我前往        很实用的算法
50.最小栈        Leetcode题155：戳我前往        戳我前往        两栈设计最小栈
51.子数组的最小值之和        Leetcode题907：戳我前往        戳我前往        单调栈的应用
; [" ]3 W# H# h9 _" w! v1 s/ R52.栈的压入、弹出序列        《剑指offer》        戳我前往        栈的合法序列
53.有效括号的嵌套深度        Leetcode题1111：戳我前往        戳我前往        模仿栈
54.逆波兰算法        经典算法        戳我前往        后缀表达式关键算法
5 ^6 \9 B& S2 l6 B* ~$ R- g( b分类五：数学思维类（含位运算思想）
数学思维类的题由于需要很强大的数学思维，但是这又不是一天可以练成的，所以，也常常在面试中会被问到，只有慢慢的积累，才是王道。

* h; R$ Y+ a, E" X
1 Y5 A3 H/ Y+ @1 x- H5 o( [: z) a题目名称        来源        个人题解        备注
55.水壶问题        Leetcode题365：戳我前往        戳我前往        经典数学问题
! |, S" `8 t$ k# ]6 u3 L+ B56.三维形体的表面积        Leetcode题892：戳我前往        戳我前往        空间思想解决算法问题
57.生命游戏        Leetcode题289：戳我前往        戳我前往        数学思维的运用
0 u- C. ^4 s7 b8 ]8 x) E4 s58.交点        《程序员面试金典》16.03        戳我前往        二维平面的交点问题
59.使数组唯一的最小增量        Leetcode题945：戳我前往        戳我前往        数学思维的运用
60.数值的整数次方        《剑指offer》题16        戳我前往        非常容易出错的面试题
61.求 1+2+…+n        《剑指offer》        戳我前往        短路原则
62.1～n整数中1出现的次数        《剑指offer》        戳我前往        数学思维找规律
63.数组中数字出现的次数        《剑指offer》        戳我前往        分组异或
分类六：链表
链表是一种非常常见的数据结构，不管在实际应用还是算法竞赛中，都经常出现，掌握对它们的基本处理，非常重要。

. _1 Y& E+ N" W0 |" V9 X
9 U% ^. P9 m' `9 y题目名称        来源        个人题解        备注
64.两数相加        Leetcode题2：戳我前往        戳我前往        链表的加法问题
65.链表的中间结点        Leetcode题876：戳我前往        戳我前往        快慢指针思想
  ^- X" W3 `; {& [66.删除链表的倒数第N个节点        Leetcode题19：戳我前往        戳我前往        哑节点和双指针
67.合并两个有序链表        Leetcode题21：戳我前往        戳我前往        链表的递归处理
. L: a  t9 {% b7 [7 Y4 O. P. Z68.合并K个排序链表        Leetcode题23：戳我前往        戳我前往        优先队列的使用
69.删除排序链表中的重复元素 II        Leetcode题82：戳我前往        戳我前往        链表基础指针操作
70.分隔链表        Leetcode题86：戳我前往        戳我前往        双指针操作
71.旋转链表        Leetcode题61：戳我前往        戳我前往        巧转循环链表
& b0 _) P: S4 _4 e72.两两交换链表中的节点        Leetcode题24：戳我前往        戳我前往        递归解决
6 @7 h: `- H0 M, M( N% m" ^- @0 F73.反转链表        Leetcode题206：戳我前往        戳我前往        多种思路反转链表
3 d+ `$ Y8 B% v: O74.K 个一组翻转链表        Leetcode题25：戳我前往        戳我前往        分组逆转
75.判断链表是否有环        《剑指offer》        戳我前往        多种思路判断链表是否有环
76.单链表的插入排序        Leetcode题147：戳我前往        戳我前往        链表的插入排序
77.两数相加 II        Leetcode题445：戳我前往        戳我前往        用栈翻转链表元素
2 Q9 m9 f4 q% {" u6 O- p分类七：树
树也是一种非常重要的数据结构，因为很多容器的底层都设计到树，所以树也成了面试常问的重点了，你需要对他们的一些基本算法题，非常熟练。


题目名称        来源        个人题解        备注
78.删除给定值的叶子结点        Leetcode题1325：戳我前往        戳我前往        树的简单删除问题
" D1 O# u9 s( w8 ^6 T* @' B79.二叉树的最大最小深度        Leetcode题104：戳我前往        戳我前往        二叉树的深度问题
5 g6 f6 p2 ?" q% f, l80.将有序数组转换为二叉搜索树        Leetcode题108：戳我前往        戳我前往        数组和二叉树的转换
/ T* f* ~4 M' Q4 t' S& C1 E5 l81.二叉树的右视图        Leetcode题199：戳我前往        戳我前往        二叉树的视图转换
82.另一个树的子树        Leetcode题572：戳我前往        戳我前往        两树关系的判断
83.二叉树的最近公共祖先        《剑指offer》        戳我前往        公共祖先问题
84.二叉树的层序遍历序列存储        Leetcode题102：戳我前往        戳我前往        二叉树遍历序列的存储
85.验证二叉搜索树        Leetcode题98：戳我前往        戳我前往        二叉搜索树的验证
( W  _$ {0 @8 [- P9 n7 h* ?8 b分类八：数组（贪心，二分）
数组类的算法题也是，说难不难，说简单不简单，而且数组是平时编码用的最多的结构了，所以，需要对它的一些基本算法引起重视。


+ B' I. G% V) E# F7 e题目名称        来源        个人题解        备注
2 m  o0 T2 _4 q4 r$ C86.两个数组间的距离值        Leetcode题1385：戳我前往        戳我前往        二分法应用
87.旋转矩阵        《程序员面试金典》        戳我前往        原地修改
88.合并区间        Leetcode题56：戳我前往        戳我前往        排序处理数组问题
89.跳跃游戏        Leetcode题55：戳我前往        戳我前往        贪心思想运用
' t( t0 Y0 g2 w6 L. C: M8 C) j, c90.盛最多水的容器        Leetcode题11：戳我前往        戳我前往        双指针
91.统计「优美子数组」        Leetcode题1248：戳我前往        戳我前往        滑动窗口
8 V2 }; i, @. A$ H3 S6 h; ]92.搜索旋转排序数组        Leetcode题33：戳我前往        戳我前往        二分搜索
93.山脉数组中查找目标值        Leetcode题1095：戳我前往        戳我前往        二分搜索
94.快乐数        Leetcode题202：戳我前往        戳我前往        快慢指针判断成环思路
95.跳跃游戏 II        Leetcode题45：戳我前往        戳我前往        贪心思想
96.x 的平方根        Leetcode题69：戳我前往        戳我前往        二分法取平方根
97.数组中的逆序对        《剑指offer》题51        戳我前往        归并中的计数（分治）
98.课程表 II        Leetcode题210：戳我前往        戳我前往        数组中的拓扑排序
分类九：经典算法列举
最后两个，凑个整，刚好100，是一些比较经典的算法列举。


8 Y, r9 o7 R+ T8 U( c1 W% ~9 H题目名称        来源        个人题解        备注
99.普利姆算法        经典算法        戳我前往        最小生成树经典算法
! }' L/ o3 p8 a: d100.约瑟夫环        经典算法        戳我前往        很经典的动态问题
2 I) J) K  x' S/ G1 B0x04.End
4 x6 D; T4 v2 l8 d) E希望这100个算法题能对正在看的你有所帮助！
后续还会继续更新更多的内容。
您的支持，是我分享的不竭动力！


- r9 v3 ^, ]1 ?" u– ATFWUS 2020-05-18
————————————————
版权声明：本文为CSDN博主「ATFWUS」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ATFWUS/article/details/106193067

1051373629

+ \0 W: ?9 k; I0 l' |5 S顶一个
9 g/ l& f) z6 Z0 j$ N* h$ O7 n顶一个
顶一个

huangma

感谢分享