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

杨利霞

2020最新-精选基础算法100题（面试必备）
( p2 j/ _9 Y7 Q8 x! `' C
0x01.概述
作为一个程序员，算法能力必不可少，虽然不一定是算法工程师，但是算法还是彰显着个人的编码能力，面试中也经常会被问到，甚至会被要求临场做算法题，所以，还是好好积累吧。

  X( i/ {# k) c: M, N# B
个人其实对算法挺有兴趣的，从3月份开始，陆陆续续刷了一些算法题，把一些有意义的记录下来了，也顺便写了一些题解，个人认为，还是挺有收获的。
2 ^; [3 y) X1 e3 J4 `% l+ l* L0 A& F9 n之前写了一篇算法文章的目录，不过后来就忘了实时去更新了，于是现在，想把之前做过的一些有意义的算法题分享出来，刚好整理了100篇比较有意义的。希望对大家有所帮助。
1 v6 Z% P9 z* l5 O
; I& P* t, a" D& }" b, M9 f* i
0 N' ]! h& d1 K4 C; I, [3 o

: H5 Q" ?8 N+ g" @+ j+ A0 Y0x02.说明
关于语言的选择：
! m0 J" o5 P0 m- t1 H8 m( D

前半段主要用C++写的，后半段主要用Java写的。
6 H$ m( G, t! G& u2 b  s其实什么语言没有太大区别，主要是思想，用着顺手就行。
这里安利一波Java，哈哈，Java写算法题写多了，真的比较舒适。
) C/ E1 X& c6 W" U2 ]关于文章类型的选择：


选取了一些较为基本的算法类型，都是比较常见的。
不涉及ACM等难度太高的题，大佬们移步哈。
1 r  Y$ e+ s! Y2 W! c. t. u2 o/ C! U都是一些比较经典的问题。
关于题目的来源：
. w5 N  y& d$ W) W- y$ J

* z$ W; s. [8 p平时主要刷题的平台是Leetcode，因为是函数式的，比较方便。
4 ]5 _% b) \. f: l: y% p6 L$ Y6 \还有一些是在《剑指offer》，《程序员面试金典》中看到比较好的，所有题目后面都给出了出处。
! L& ~5 k1 t& z# M3 u% a$ p关于题解的说明：
0 c! U' [8 V0 a. C9 k# _6 @

题解是我自己所写，有时候也参考了一些官方题解的思想，可能更好理解。
( c$ }& Y' w7 k题解的代码都提交测试过的，保证暂时没有问题。
( C2 [( A3 f7 l3 s! Z0 ]6 H个人水平有限，可能文章里面存在一些问题，还望大佬多多指点。
每个题目附带了原文链接，不喜欢阅读我题解的小伙伴们也可以直接移步原出处哈。
关于算法能力提升的一些意见：


+ M, D3 ~' D$ d3 c$ Z7 W/ H个人认为，算法来说，思想最为重要，有算法的严谨思想，才是算法能力提升的基础。
8 Z$ C( p6 D, s5 |' ]刷题就是培养算法思想的一种实际行动。
% ^0 _) N/ w+ D( H4 S7 g3 V好好理解透一个问题，或者一类问题，远胜于你麻木的刷大量的题。
0 v2 }' w; H4 O  u算法确实也有模板题，只需要照着模板就能做出，但问题是，照着模板就一定能做出来嘛，是否真正理解了为什么这个模板可以通用。
关于分类：


6 E& }; g, I! g" |- q& R有些分类确实不太好分，所以就单独列出来了。
主要的还是区分开来了。
' b. Q% T) g: l$ W' S4 A0x03.正文–精选算法100题（附个人题解）
分类一：动态规划（dp）
, S- Q3 h/ i$ k* V1 E没错，就是你熟悉的dp，dp说简单也简单，说难也实在是太难了，重点是如何找到里面的状态转移方程。经过这些题目的训练，希望你能有一些初步的dp思路了。

  a$ M- [6 `9 I" l& f7 }
题目名称        来源        个人题解        备注
$ `  a& N8 S1 c$ W01.打家劫舍        Leetcode题198：戳我前往        戳我前往        估计是最好的dp入门题型了
5 H: p4 d+ s& A/ Y0 m02.斐波拉契数列        经典问题        戳我前往        确实比较经典哦~
6 ~- v& L, j. Y8 M: a, M) E03.零钱兑换问题        Leetcode题322：戳我前往        戳我前往        也是一个比较经典的问题了
! K; Q6 B( L& W% A9 T04.零钱兑换II        Leetcode题518：戳我前往        戳我前往        零钱问题通用解法
05.最长上升子序列        Leetcode题300：戳我前往        戳我前往        堪称数组dp中的典范
" j! B' M. d$ P0 r06.牌型种数        蓝桥杯：链接暂无        戳我前往        二维动态规划，要仔细想想
07.最低票价        Leetcode题983：戳我前往        戳我前往        如何状态转移？
) y  Y6 D8 B0 e( r' m08.不同的二叉搜索树        Leetcode题152：戳我前往        戳我前往        你会发现dp的神奇之处
09.礼物的最大价值        《剑指offer》题47        戳我前往        优化dp的思路
  z8 ^8 E- k/ m8 E9 d2 g10.接雨水        Leetcode题42：戳我前往        戳我前往        需要仔细思考以发现dp
11.编辑距离        Leetcode题72：戳我前往        戳我前往        最为经典的二维dp题型
12.买卖股票的最佳时机（6题）        Leetcode6题：戳我前往        戳我前往        统一化的dp思维，棒
: m( r( L, ]0 P. _6 f& C4 d# J0 X13.鸡蛋掉落        Leetcode题887：戳我前往        戳我前往        有些难度哦~
14.最大正方形        Leetcode题221：戳我前往        戳我前往        矩阵中的dp思路
15.和为K的子数组        Leetcode题560：戳我前往        戳我前往        前缀和也是dp的思路
$ `/ I2 q- n/ L. `0 `分类二：搜索类（DFS，BFS，回溯，暴力搜索）
  G2 Q9 h: |* Z5 r$ A( S搜索类的算法题应该是随便哪个算法比赛都可以看到，虽然经典，但在这上面还是会有比较难的问题，所以，掌握基本思路和套路就显得格外重要。
) i5 M: S5 S9 S/ K7 Y- M: y1 O7 u
: h9 W0 T# e$ I, Z' T+ f; O
题目名称        来源        个人题解        备注
0 A2 a3 W( C) a4 [5 R  U% [( o16.图的深搜和广搜        经典问题        戳我前往        搜索中的经典问题
17.方格填数        蓝桥杯：链接暂无        戳我前往        揣摩一下DFS的思路
18.路径之谜        蓝桥杯：链接暂无        戳我前往        经典改编迷宫问题
+ A# y$ b4 V# `( V! ^5 W19.岛屿的最大面积        Leetcode题695：戳我前往        戳我前往        最常见的矩阵中的DFS
20.逃离大迷宫        Leetcode题1036：戳我前往        戳我前往        各种搜索思想都可以应用
21.单词搜索        Leetcode题79：戳我前往        戳我前往        字符串中的搜索
3 Q7 {, e. S% k22.检查网格中是否存在有效路径        Leetcode题1391：戳我前往        戳我前往        思考另类的搜索
* L$ O8 D# E) d8 m2 ^2 f23.地图分析        Leetcode题1162：戳我前往        戳我前往        多源BFS
/ j0 [4 j& P2 t  s  p* H8 @% W8 ~24.机器人的运动范围        《剑指offer》13题        戳我前往        DFS进行计数的基本思路
25.括号生成        Leetcode题22：戳我前往        戳我前往        用DFS生产括号
7 z5 {' w! b* F; ^# m26.01 矩阵        Leetcode题542：戳我前往        戳我前往        矩阵中的搜索
( L  j0 g7 \) J# @27.岛屿数量        Leetcode题200：戳我前往        戳我前往        根据需求使用DFS
1 ~- Z- K& a' m+ y2 U28.全排列问题        Leetcode题46：戳我前往        戳我前往        最经典的回溯算法
# ^, F1 O8 J$ [$ V分类三：字符串
别忽视字符串的算法问题，它难起来可以非常难，简单的也很简单，面试喜欢提问，而且特别容易出错，需要引起重视。


" h  S. D: y! n2 q题目名称        来源        个人题解        备注
29.KMP算法        经典算法        戳我前往        经典字符串匹配算法
) |# }- s) k# k' H4 i0 S30.拼写单词        Leetcode题1160：戳我前往        戳我前往        很简单的字符串问题
31.竖直打印单词        Leetcode题1324：戳我前往        戳我前往        简单但值得思考
32.不含 AAA 或 BBB 的字符串        Leetcode题984：戳我前往        戳我前往        巧妙构造出字符串
+ i  Y; g/ J6 M33.实现Trie（前缀树）        Leetcode题208：戳我前往        戳我前往        字符串中经典的算法
34.最长快乐前缀        Leetcode题1392：戳我前往        戳我前往        如何处理字符串的前后缀
: l- \& }9 p3 g7 [5 @35.单词搜索II        Leetcode题212：戳我前往        戳我前往        前缀树的应用
36.单词的压缩编码        Leetcode题820：戳我前往        戳我前往        前缀树灵活运用
) C0 v5 H& r3 o! B& ?  t37.判定字符是否唯一        《程序员面试金典》01.02        戳我前往        简单但值得思考
38.判定是否互为字符重排        《程序员面试金典》 01.02        戳我前往        简单的面试题
39.无重复字符的最长子串        Leetcode题3：戳我前往        戳我前往        字符串中的滑动窗口
40.字符串转换整数        Leetcode题8：戳我前往        戳我前往        需要考虑的细节很多
41.翻转字符串里的单词        Leetcode题151：戳我前往        戳我前往        正则匹配
42.整数转换英文表示        Leetcode题273：戳我前往        戳我前往        非常实用的算法题
1 h' V; O5 j. x- W43.统计重复个数        Leetcode题466：戳我前往        戳我前往        循环结剪枝
44.超级回文数        Leetcode题906：戳我前往        戳我前往        字符串与大数的处理思路
45.单词子集        Leetcode题96：戳我前往        戳我前往        特征思想的应用
分类四：容器类（哈希表，栈，队列，Map，Set）
容器类的算法题一般需要根据一些容器的特点来解决响应的问题，还有需要选择合适的容器进行新的数据结构的设计，掌握它们的使用，非常重要。

  C9 I  Q: {# I2 Q8 O
4 {* ?0 e0 N. k, s: _8 p3 A题目名称        来源        个人题解        备注
46.按位与为零的三元组        Leetcode题82：戳我前往        戳我前往        哈希表优化
7 R* R. B) @: H/ Y" Y* V( F" q47.设计地铁系统        Leetcode题1396：戳我前往        戳我前往        合理选择容器
48.LFU缓存        《程序员面试金典》        戳我前往        选择容器来设计
49.设计推特        Leetcode题355：戳我前往        戳我前往        很实用的算法
! f  V; O. t3 k0 X. }50.最小栈        Leetcode题155：戳我前往        戳我前往        两栈设计最小栈
$ W# R0 i/ J: ~$ j51.子数组的最小值之和        Leetcode题907：戳我前往        戳我前往        单调栈的应用
52.栈的压入、弹出序列        《剑指offer》        戳我前往        栈的合法序列
! p! P' S# P- }: P  F1 L1 Q53.有效括号的嵌套深度        Leetcode题1111：戳我前往        戳我前往        模仿栈
+ {& V, _! S/ M1 i2 x/ I2 z& B5 |) ?54.逆波兰算法        经典算法        戳我前往        后缀表达式关键算法
, ?% B  i$ j. _' Y  Q# ~) ]分类五：数学思维类（含位运算思想）
数学思维类的题由于需要很强大的数学思维，但是这又不是一天可以练成的，所以，也常常在面试中会被问到，只有慢慢的积累，才是王道。


4 p7 }8 l9 p# j2 s' ~% _7 I, e题目名称        来源        个人题解        备注
2 E- u0 `! a( ~- `  E2 L55.水壶问题        Leetcode题365：戳我前往        戳我前往        经典数学问题
' L3 S1 r4 p, R7 _* |5 t6 H  y56.三维形体的表面积        Leetcode题892：戳我前往        戳我前往        空间思想解决算法问题
57.生命游戏        Leetcode题289：戳我前往        戳我前往        数学思维的运用
& l3 L1 H$ G! m) z4 p. t! K58.交点        《程序员面试金典》16.03        戳我前往        二维平面的交点问题
$ @% o$ O$ p& \/ x6 S59.使数组唯一的最小增量        Leetcode题945：戳我前往        戳我前往        数学思维的运用
60.数值的整数次方        《剑指offer》题16        戳我前往        非常容易出错的面试题
61.求 1+2+…+n        《剑指offer》        戳我前往        短路原则
4 W& Y. m; \* R  K9 [2 T- e& M62.1～n整数中1出现的次数        《剑指offer》        戳我前往        数学思维找规律
8 l6 O4 Z) G( ]5 K$ [9 _63.数组中数字出现的次数        《剑指offer》        戳我前往        分组异或
" x2 v9 {$ y" {% O8 ^分类六：链表
& y2 ~* s6 e0 ^5 G5 }链表是一种非常常见的数据结构，不管在实际应用还是算法竞赛中，都经常出现，掌握对它们的基本处理，非常重要。


- H! P# o7 E8 N1 @0 [+ i题目名称        来源        个人题解        备注
3 s% \% F  p/ y6 v7 C; x64.两数相加        Leetcode题2：戳我前往        戳我前往        链表的加法问题
5 q4 W; b! C0 S3 R# m65.链表的中间结点        Leetcode题876：戳我前往        戳我前往        快慢指针思想
9 ^6 a9 n8 T3 I9 J% K; A+ F66.删除链表的倒数第N个节点        Leetcode题19：戳我前往        戳我前往        哑节点和双指针
67.合并两个有序链表        Leetcode题21：戳我前往        戳我前往        链表的递归处理
68.合并K个排序链表        Leetcode题23：戳我前往        戳我前往        优先队列的使用
+ O% d9 H% D! K4 U9 X" e# S4 P$ U69.删除排序链表中的重复元素 II        Leetcode题82：戳我前往        戳我前往        链表基础指针操作
) I9 q. k* M; [70.分隔链表        Leetcode题86：戳我前往        戳我前往        双指针操作
, z$ ^9 j0 r" X" V5 P71.旋转链表        Leetcode题61：戳我前往        戳我前往        巧转循环链表
* v! w# r- B! e9 `72.两两交换链表中的节点        Leetcode题24：戳我前往        戳我前往        递归解决
$ o9 D  U8 H8 J# M73.反转链表        Leetcode题206：戳我前往        戳我前往        多种思路反转链表
74.K 个一组翻转链表        Leetcode题25：戳我前往        戳我前往        分组逆转
% }5 E$ {% I- G' a75.判断链表是否有环        《剑指offer》        戳我前往        多种思路判断链表是否有环
! }& Y, {# j8 |, I9 O& A3 s76.单链表的插入排序        Leetcode题147：戳我前往        戳我前往        链表的插入排序
, U# `3 O7 x  A' F) M77.两数相加 II        Leetcode题445：戳我前往        戳我前往        用栈翻转链表元素
分类七：树
. G, m2 Y  D+ G2 U4 _树也是一种非常重要的数据结构，因为很多容器的底层都设计到树，所以树也成了面试常问的重点了，你需要对他们的一些基本算法题，非常熟练。

6 r4 H" t, y6 W, ?. ?! J; |
4 c3 L2 s( @* A* X5 R* }( }* a- R+ J题目名称        来源        个人题解        备注
78.删除给定值的叶子结点        Leetcode题1325：戳我前往        戳我前往        树的简单删除问题
1 c9 }4 a2 I+ f1 v- {' k0 D7 I79.二叉树的最大最小深度        Leetcode题104：戳我前往        戳我前往        二叉树的深度问题
80.将有序数组转换为二叉搜索树        Leetcode题108：戳我前往        戳我前往        数组和二叉树的转换
! x, l- k$ \3 I$ d6 f* M, u2 G# R+ {81.二叉树的右视图        Leetcode题199：戳我前往        戳我前往        二叉树的视图转换
% H7 n( |5 L% `( v. D5 i0 \0 t$ L82.另一个树的子树        Leetcode题572：戳我前往        戳我前往        两树关系的判断
0 f! e$ |& M, C0 D! l& [& s' J4 F/ N83.二叉树的最近公共祖先        《剑指offer》        戳我前往        公共祖先问题
84.二叉树的层序遍历序列存储        Leetcode题102：戳我前往        戳我前往        二叉树遍历序列的存储
85.验证二叉搜索树        Leetcode题98：戳我前往        戳我前往        二叉搜索树的验证
分类八：数组（贪心，二分）
数组类的算法题也是，说难不难，说简单不简单，而且数组是平时编码用的最多的结构了，所以，需要对它的一些基本算法引起重视。
* x& C2 e  |0 G7 Y1 Q+ t+ q
5 M7 ^' P4 j* ^; L9 C$ v9 b+ ?9 P
' j: Q$ W7 m. D6 N9 ~题目名称        来源        个人题解        备注
86.两个数组间的距离值        Leetcode题1385：戳我前往        戳我前往        二分法应用
87.旋转矩阵        《程序员面试金典》        戳我前往        原地修改
. E3 t# R3 o4 g/ i9 k. u+ X88.合并区间        Leetcode题56：戳我前往        戳我前往        排序处理数组问题
89.跳跃游戏        Leetcode题55：戳我前往        戳我前往        贪心思想运用
90.盛最多水的容器        Leetcode题11：戳我前往        戳我前往        双指针
6 ~8 a5 s+ b6 N4 ], n3 `91.统计「优美子数组」        Leetcode题1248：戳我前往        戳我前往        滑动窗口
92.搜索旋转排序数组        Leetcode题33：戳我前往        戳我前往        二分搜索
93.山脉数组中查找目标值        Leetcode题1095：戳我前往        戳我前往        二分搜索
94.快乐数        Leetcode题202：戳我前往        戳我前往        快慢指针判断成环思路
  b) x2 h6 `/ Y- v& b9 @95.跳跃游戏 II        Leetcode题45：戳我前往        戳我前往        贪心思想
0 i: y2 y  ?2 a96.x 的平方根        Leetcode题69：戳我前往        戳我前往        二分法取平方根
0 V5 W4 f6 k( Q9 N/ b6 q# ^* n9 j- L97.数组中的逆序对        《剑指offer》题51        戳我前往        归并中的计数（分治）
) H4 G+ @* t! T& M, F98.课程表 II        Leetcode题210：戳我前往        戳我前往        数组中的拓扑排序
分类九：经典算法列举
最后两个，凑个整，刚好100，是一些比较经典的算法列举。

6 o0 U, u' ^' F; T
  f2 ?+ d: A  N3 N* M题目名称        来源        个人题解        备注
99.普利姆算法        经典算法        戳我前往        最小生成树经典算法
* B1 u" k2 Z8 V. Q& T$ W* f' D100.约瑟夫环        经典算法        戳我前往        很经典的动态问题
8 v6 [; @8 I) C) M5 S# j+ ]0x04.End
希望这100个算法题能对正在看的你有所帮助！
后续还会继续更新更多的内容。
2 Z9 X$ l& l" o您的支持，是我分享的不竭动力！


– ATFWUS 2020-05-18
9 b+ \' a, {' U. E8 D————————————————
版权声明：本文为CSDN博主「ATFWUS」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ATFWUS/article/details/106193067

huangma

感谢分享

1051373629

# S4 d2 L8 \+ O! ^1 v5 _5 k顶一个
4 V0 }; A8 C0 B7 p顶一个
, l( s# b3 ]( X顶一个