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

杨利霞

2020最新-精选基础算法100题（面试必备）
; }5 t4 `  e0 v! }( c+ A
0x01.概述
  |. l. \! Y: f: {2 x3 E4 T作为一个程序员，算法能力必不可少，虽然不一定是算法工程师，但是算法还是彰显着个人的编码能力，面试中也经常会被问到，甚至会被要求临场做算法题，所以，还是好好积累吧。
6 K3 R2 [$ D/ ?4 c( B5 L# H

个人其实对算法挺有兴趣的，从3月份开始，陆陆续续刷了一些算法题，把一些有意义的记录下来了，也顺便写了一些题解，个人认为，还是挺有收获的。
( s7 p2 f: j/ F: h; ~$ Q之前写了一篇算法文章的目录，不过后来就忘了实时去更新了，于是现在，想把之前做过的一些有意义的算法题分享出来，刚好整理了100篇比较有意义的。希望对大家有所帮助。
% q. R+ j9 E" F, j8 K+ ]8 z
/ U% h1 b$ \+ A$ T
% A4 U$ E! O" c/ g+ [2 x

0x02.说明
% z/ J* C: p' _" z' P9 N, v( J* K关于语言的选择：
- f0 |2 c% ^- ^9 h
* c2 F3 d( a% V' Z
前半段主要用C++写的，后半段主要用Java写的。
* Q2 p5 B* F) Z6 R0 g/ a0 n6 Y其实什么语言没有太大区别，主要是思想，用着顺手就行。
这里安利一波Java，哈哈，Java写算法题写多了，真的比较舒适。
2 F: N2 x" O& C0 Q. t- }关于文章类型的选择：
7 W; @# Z) e% s
  i- o# x. A& o5 R; H* v
选取了一些较为基本的算法类型，都是比较常见的。
不涉及ACM等难度太高的题，大佬们移步哈。
都是一些比较经典的问题。
关于题目的来源：
- X% X" _1 S9 k$ @
* L+ ^8 b# i; P! d
平时主要刷题的平台是Leetcode，因为是函数式的，比较方便。
还有一些是在《剑指offer》，《程序员面试金典》中看到比较好的，所有题目后面都给出了出处。
6 m5 {) m* ^# h关于题解的说明：
8 Q! M+ A+ T2 P4 r5 E3 P# }

# a8 V) V. L" m1 E6 [9 a" @题解是我自己所写，有时候也参考了一些官方题解的思想，可能更好理解。
$ P5 |& R+ S9 F题解的代码都提交测试过的，保证暂时没有问题。
  a" k* w- C3 A7 T" M个人水平有限，可能文章里面存在一些问题，还望大佬多多指点。
2 f" i5 `$ @7 R/ _) O* e% k每个题目附带了原文链接，不喜欢阅读我题解的小伙伴们也可以直接移步原出处哈。
( E! t: A3 ]8 I( O# X" h8 k  z2 d0 Y1 b关于算法能力提升的一些意见：
0 c1 j2 l+ Q+ D5 u! p" _9 C

; n; U2 V+ \) f$ U+ W6 Z个人认为，算法来说，思想最为重要，有算法的严谨思想，才是算法能力提升的基础。
刷题就是培养算法思想的一种实际行动。
好好理解透一个问题，或者一类问题，远胜于你麻木的刷大量的题。
9 d' F: Z/ n5 i. M7 z3 }算法确实也有模板题，只需要照着模板就能做出，但问题是，照着模板就一定能做出来嘛，是否真正理解了为什么这个模板可以通用。
; F  P4 a! b0 P' e7 j关于分类：
; V& v0 T' c! f3 y3 S. W' j. Z

有些分类确实不太好分，所以就单独列出来了。
+ `9 g- `4 {* B+ g% p! t, w! y( |主要的还是区分开来了。
+ y: g1 @+ }' ]0x03.正文–精选算法100题（附个人题解）
分类一：动态规划（dp）
/ j2 p! S3 t0 v. S% E* F$ T# Z2 v9 ?没错，就是你熟悉的dp，dp说简单也简单，说难也实在是太难了，重点是如何找到里面的状态转移方程。经过这些题目的训练，希望你能有一些初步的dp思路了。

+ _1 [6 v6 X. K3 Z$ S5 N0 o# N
题目名称        来源        个人题解        备注
01.打家劫舍        Leetcode题198：戳我前往        戳我前往        估计是最好的dp入门题型了
8 w& Z" Z4 {2 v9 }02.斐波拉契数列        经典问题        戳我前往        确实比较经典哦~
03.零钱兑换问题        Leetcode题322：戳我前往        戳我前往        也是一个比较经典的问题了
04.零钱兑换II        Leetcode题518：戳我前往        戳我前往        零钱问题通用解法
0 g* F1 d' P8 p: u! I! A- d05.最长上升子序列        Leetcode题300：戳我前往        戳我前往        堪称数组dp中的典范
06.牌型种数        蓝桥杯：链接暂无        戳我前往        二维动态规划，要仔细想想
07.最低票价        Leetcode题983：戳我前往        戳我前往        如何状态转移？
; A! f! k3 u+ {3 I: Q08.不同的二叉搜索树        Leetcode题152：戳我前往        戳我前往        你会发现dp的神奇之处
- P" U* |6 l+ o09.礼物的最大价值        《剑指offer》题47        戳我前往        优化dp的思路
10.接雨水        Leetcode题42：戳我前往        戳我前往        需要仔细思考以发现dp
" {" r! P, t/ G11.编辑距离        Leetcode题72：戳我前往        戳我前往        最为经典的二维dp题型
) W3 K5 \! Y- G, ?1 z" Z) N12.买卖股票的最佳时机（6题）        Leetcode6题：戳我前往        戳我前往        统一化的dp思维，棒
' R  k5 J  X4 D- c3 Q% Y3 |13.鸡蛋掉落        Leetcode题887：戳我前往        戳我前往        有些难度哦~
5 B- L! Q2 d# Y2 g14.最大正方形        Leetcode题221：戳我前往        戳我前往        矩阵中的dp思路
15.和为K的子数组        Leetcode题560：戳我前往        戳我前往        前缀和也是dp的思路
分类二：搜索类（DFS，BFS，回溯，暴力搜索）
搜索类的算法题应该是随便哪个算法比赛都可以看到，虽然经典，但在这上面还是会有比较难的问题，所以，掌握基本思路和套路就显得格外重要。

1 Y3 c+ @& p- g' k# g) E( p/ J
题目名称        来源        个人题解        备注
16.图的深搜和广搜        经典问题        戳我前往        搜索中的经典问题
& n7 f+ `: k6 S, I0 b5 E  z3 v5 G5 D17.方格填数        蓝桥杯：链接暂无        戳我前往        揣摩一下DFS的思路
/ G) R9 i/ I1 x+ I18.路径之谜        蓝桥杯：链接暂无        戳我前往        经典改编迷宫问题
19.岛屿的最大面积        Leetcode题695：戳我前往        戳我前往        最常见的矩阵中的DFS
! @5 B& v# \& l1 ^20.逃离大迷宫        Leetcode题1036：戳我前往        戳我前往        各种搜索思想都可以应用
& \2 p) m' u' X4 {3 m& m21.单词搜索        Leetcode题79：戳我前往        戳我前往        字符串中的搜索
22.检查网格中是否存在有效路径        Leetcode题1391：戳我前往        戳我前往        思考另类的搜索
. Y4 m! X: W6 Q3 J/ A4 t, [& S23.地图分析        Leetcode题1162：戳我前往        戳我前往        多源BFS
24.机器人的运动范围        《剑指offer》13题        戳我前往        DFS进行计数的基本思路
25.括号生成        Leetcode题22：戳我前往        戳我前往        用DFS生产括号
7 o( h. p. n% A1 p" x; l26.01 矩阵        Leetcode题542：戳我前往        戳我前往        矩阵中的搜索
27.岛屿数量        Leetcode题200：戳我前往        戳我前往        根据需求使用DFS
8 t; p) }7 k8 r9 e' b' [28.全排列问题        Leetcode题46：戳我前往        戳我前往        最经典的回溯算法
# \$ D8 O9 c. O  s' ]' v  F分类三：字符串
' Z% b2 _) a4 B- Q3 b, ^别忽视字符串的算法问题，它难起来可以非常难，简单的也很简单，面试喜欢提问，而且特别容易出错，需要引起重视。


题目名称        来源        个人题解        备注
. w0 F0 X4 C' B9 z29.KMP算法        经典算法        戳我前往        经典字符串匹配算法
7 J" u( q% @) o30.拼写单词        Leetcode题1160：戳我前往        戳我前往        很简单的字符串问题
31.竖直打印单词        Leetcode题1324：戳我前往        戳我前往        简单但值得思考
& |4 H: W* v3 t$ w32.不含 AAA 或 BBB 的字符串        Leetcode题984：戳我前往        戳我前往        巧妙构造出字符串
* b& c8 n3 a3 r# `33.实现Trie（前缀树）        Leetcode题208：戳我前往        戳我前往        字符串中经典的算法
1 s- H! i9 H; }7 [4 D* a34.最长快乐前缀        Leetcode题1392：戳我前往        戳我前往        如何处理字符串的前后缀
# C  r' A, \% f# {8 \/ H3 ^5 w2 _35.单词搜索II        Leetcode题212：戳我前往        戳我前往        前缀树的应用
- ]& K4 u! f& F; g! j* A36.单词的压缩编码        Leetcode题820：戳我前往        戳我前往        前缀树灵活运用
0 _4 J* E+ E% }6 Z0 c37.判定字符是否唯一        《程序员面试金典》01.02        戳我前往        简单但值得思考
38.判定是否互为字符重排        《程序员面试金典》 01.02        戳我前往        简单的面试题
- E& [7 `( \2 A3 V/ |) ]39.无重复字符的最长子串        Leetcode题3：戳我前往        戳我前往        字符串中的滑动窗口
+ O5 L& N3 x$ R) h% [0 s40.字符串转换整数        Leetcode题8：戳我前往        戳我前往        需要考虑的细节很多
41.翻转字符串里的单词        Leetcode题151：戳我前往        戳我前往        正则匹配
4 [3 ?( G. s- k+ I42.整数转换英文表示        Leetcode题273：戳我前往        戳我前往        非常实用的算法题
8 s/ ]$ K' t( J, q' c- p43.统计重复个数        Leetcode题466：戳我前往        戳我前往        循环结剪枝
$ Z/ G& L" x% R0 [44.超级回文数        Leetcode题906：戳我前往        戳我前往        字符串与大数的处理思路
7 ^+ f" v9 k% n8 d- x; M! d* F5 w45.单词子集        Leetcode题96：戳我前往        戳我前往        特征思想的应用
8 q; E# m; c& p, G. v分类四：容器类（哈希表，栈，队列，Map，Set）
容器类的算法题一般需要根据一些容器的特点来解决响应的问题，还有需要选择合适的容器进行新的数据结构的设计，掌握它们的使用，非常重要。
2 d& `  [+ N7 M

题目名称        来源        个人题解        备注
4 P6 e  B7 \3 x  T: X4 Y- R46.按位与为零的三元组        Leetcode题82：戳我前往        戳我前往        哈希表优化
47.设计地铁系统        Leetcode题1396：戳我前往        戳我前往        合理选择容器
# t+ I- X% o, g* f48.LFU缓存        《程序员面试金典》        戳我前往        选择容器来设计
49.设计推特        Leetcode题355：戳我前往        戳我前往        很实用的算法
, n/ I. p3 w" |- M. Y( o& S50.最小栈        Leetcode题155：戳我前往        戳我前往        两栈设计最小栈
51.子数组的最小值之和        Leetcode题907：戳我前往        戳我前往        单调栈的应用
52.栈的压入、弹出序列        《剑指offer》        戳我前往        栈的合法序列
: K* K# a6 w& w# b; `; w$ u+ y53.有效括号的嵌套深度        Leetcode题1111：戳我前往        戳我前往        模仿栈
54.逆波兰算法        经典算法        戳我前往        后缀表达式关键算法
分类五：数学思维类（含位运算思想）
6 _: T& r' v9 R4 K! V; o. ~% c- T" K数学思维类的题由于需要很强大的数学思维，但是这又不是一天可以练成的，所以，也常常在面试中会被问到，只有慢慢的积累，才是王道。
/ S; S( [* v) I9 f
' V+ E0 z6 W( ]- X
题目名称        来源        个人题解        备注
1 k( k) z" u$ ]& b55.水壶问题        Leetcode题365：戳我前往        戳我前往        经典数学问题
56.三维形体的表面积        Leetcode题892：戳我前往        戳我前往        空间思想解决算法问题
+ {9 P. c& g* A57.生命游戏        Leetcode题289：戳我前往        戳我前往        数学思维的运用
58.交点        《程序员面试金典》16.03        戳我前往        二维平面的交点问题
; _1 E" N0 L: h59.使数组唯一的最小增量        Leetcode题945：戳我前往        戳我前往        数学思维的运用
, K! \4 P, J. J' j, _. M3 p60.数值的整数次方        《剑指offer》题16        戳我前往        非常容易出错的面试题
0 |! V- S" V5 J; S7 M5 s61.求 1+2+…+n        《剑指offer》        戳我前往        短路原则
; Y6 G  h% Y+ |- a. n5 @4 ]+ @62.1～n整数中1出现的次数        《剑指offer》        戳我前往        数学思维找规律
63.数组中数字出现的次数        《剑指offer》        戳我前往        分组异或
分类六：链表
: j+ N2 }5 `. ]' h; a7 Y6 t* I链表是一种非常常见的数据结构，不管在实际应用还是算法竞赛中，都经常出现，掌握对它们的基本处理，非常重要。
* `' {# |2 W/ _8 G
( s! ~: S9 T. X1 c9 o8 @3 T
' `3 E  K6 }( g* C% u题目名称        来源        个人题解        备注
64.两数相加        Leetcode题2：戳我前往        戳我前往        链表的加法问题
65.链表的中间结点        Leetcode题876：戳我前往        戳我前往        快慢指针思想
1 b8 y3 }9 r8 e/ O7 `6 a66.删除链表的倒数第N个节点        Leetcode题19：戳我前往        戳我前往        哑节点和双指针
67.合并两个有序链表        Leetcode题21：戳我前往        戳我前往        链表的递归处理
9 M- }$ [9 P8 T; z8 U2 Q+ c68.合并K个排序链表        Leetcode题23：戳我前往        戳我前往        优先队列的使用
+ V' r2 i) X; R69.删除排序链表中的重复元素 II        Leetcode题82：戳我前往        戳我前往        链表基础指针操作
70.分隔链表        Leetcode题86：戳我前往        戳我前往        双指针操作
71.旋转链表        Leetcode题61：戳我前往        戳我前往        巧转循环链表
72.两两交换链表中的节点        Leetcode题24：戳我前往        戳我前往        递归解决
3 Z+ ?& j/ m9 h( D7 B  q- C73.反转链表        Leetcode题206：戳我前往        戳我前往        多种思路反转链表
4 K9 N! T! E0 p/ @74.K 个一组翻转链表        Leetcode题25：戳我前往        戳我前往        分组逆转
75.判断链表是否有环        《剑指offer》        戳我前往        多种思路判断链表是否有环
76.单链表的插入排序        Leetcode题147：戳我前往        戳我前往        链表的插入排序
; u6 a" K& g- b! u! a! p+ W77.两数相加 II        Leetcode题445：戳我前往        戳我前往        用栈翻转链表元素
& z! C9 U# b) {  R* U分类七：树
树也是一种非常重要的数据结构，因为很多容器的底层都设计到树，所以树也成了面试常问的重点了，你需要对他们的一些基本算法题，非常熟练。
. M$ S: T( x; [# T9 [
9 A5 U8 j, o; t$ l
题目名称        来源        个人题解        备注
78.删除给定值的叶子结点        Leetcode题1325：戳我前往        戳我前往        树的简单删除问题
" _6 `: J$ q) n$ \* b, A: e79.二叉树的最大最小深度        Leetcode题104：戳我前往        戳我前往        二叉树的深度问题
( x! l9 O- B2 h: F80.将有序数组转换为二叉搜索树        Leetcode题108：戳我前往        戳我前往        数组和二叉树的转换
81.二叉树的右视图        Leetcode题199：戳我前往        戳我前往        二叉树的视图转换
82.另一个树的子树        Leetcode题572：戳我前往        戳我前往        两树关系的判断
83.二叉树的最近公共祖先        《剑指offer》        戳我前往        公共祖先问题
: e0 Q/ D2 `( P2 I84.二叉树的层序遍历序列存储        Leetcode题102：戳我前往        戳我前往        二叉树遍历序列的存储
85.验证二叉搜索树        Leetcode题98：戳我前往        戳我前往        二叉搜索树的验证
2 n% R  R) x: n+ o分类八：数组（贪心，二分）
数组类的算法题也是，说难不难，说简单不简单，而且数组是平时编码用的最多的结构了，所以，需要对它的一些基本算法引起重视。

; j0 `# n  }) {8 L  b' L, W: l
' ?! S2 k; f8 F- v题目名称        来源        个人题解        备注
86.两个数组间的距离值        Leetcode题1385：戳我前往        戳我前往        二分法应用
4 S6 ?, C  E# F% S" p0 O87.旋转矩阵        《程序员面试金典》        戳我前往        原地修改
% \8 `+ O& N% ^- _1 j88.合并区间        Leetcode题56：戳我前往        戳我前往        排序处理数组问题
89.跳跃游戏        Leetcode题55：戳我前往        戳我前往        贪心思想运用
. ^+ `2 O5 ^% l' K& n+ G( t90.盛最多水的容器        Leetcode题11：戳我前往        戳我前往        双指针
91.统计「优美子数组」        Leetcode题1248：戳我前往        戳我前往        滑动窗口
# }5 i% c5 R. X! y3 z/ D- ~  I92.搜索旋转排序数组        Leetcode题33：戳我前往        戳我前往        二分搜索
93.山脉数组中查找目标值        Leetcode题1095：戳我前往        戳我前往        二分搜索
94.快乐数        Leetcode题202：戳我前往        戳我前往        快慢指针判断成环思路
+ C3 _& K) a+ l" m95.跳跃游戏 II        Leetcode题45：戳我前往        戳我前往        贪心思想
96.x 的平方根        Leetcode题69：戳我前往        戳我前往        二分法取平方根
8 C# x2 r* L- D# \97.数组中的逆序对        《剑指offer》题51        戳我前往        归并中的计数（分治）
98.课程表 II        Leetcode题210：戳我前往        戳我前往        数组中的拓扑排序
- f+ n) {' A1 l分类九：经典算法列举
# A% P' x/ i- J: w/ X/ e最后两个，凑个整，刚好100，是一些比较经典的算法列举。


" ^  D. Z& T% {% |题目名称        来源        个人题解        备注
99.普利姆算法        经典算法        戳我前往        最小生成树经典算法
100.约瑟夫环        经典算法        戳我前往        很经典的动态问题
0x04.End
, P# X& ?2 I& a, X& E  ~% Q  U希望这100个算法题能对正在看的你有所帮助！
后续还会继续更新更多的内容。
$ C2 M; B: `# q0 Q您的支持，是我分享的不竭动力！


– ATFWUS 2020-05-18
————————————————
8 z* O( w! e! O2 V+ z7 i6 Y, e& P+ ~版权声明：本文为CSDN博主「ATFWUS」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 F0 P. s6 j/ v& w) W, k原文链接：https://blog.csdn.net/ATFWUS/article/details/106193067


7 W: j8 _; A! `. E; e# R

1051373629

4 e! o: ~! @3 |/ I5 z* u1 v顶一个
顶一个
顶一个
( c% _- y0 H: W" V

huangma

感谢分享
8 I- `& U3 O3 ]2 J6 m- D- S