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

杨利霞

: i+ A8 Y8 F" o' p1 v2020最新-精选基础算法100题（面试必备）

0x01.概述
5 l/ w9 M  \$ m0 o5 ^4 k作为一个程序员，算法能力必不可少，虽然不一定是算法工程师，但是算法还是彰显着个人的编码能力，面试中也经常会被问到，甚至会被要求临场做算法题，所以，还是好好积累吧。
7 U0 [# x6 G' M( X6 _$ J

个人其实对算法挺有兴趣的，从3月份开始，陆陆续续刷了一些算法题，把一些有意义的记录下来了，也顺便写了一些题解，个人认为，还是挺有收获的。
  J% \! ~2 z* W# j& D, s之前写了一篇算法文章的目录，不过后来就忘了实时去更新了，于是现在，想把之前做过的一些有意义的算法题分享出来，刚好整理了100篇比较有意义的。希望对大家有所帮助。
" z3 a! {8 _: C' i/ U2 o) `' V- y
0 @( M2 v* _" `) |2 N2 O
7 F7 _/ `: E: H

7 r  _1 g9 D6 O4 v! A8 ?% x0x02.说明
2 N/ u) S, e0 S关于语言的选择：

4 S: ~" {* }+ m* G3 H
. G0 c  R7 {" i8 y# R1 }3 p前半段主要用C++写的，后半段主要用Java写的。
% F/ d$ x* M1 s5 E( K4 `0 c3 X其实什么语言没有太大区别，主要是思想，用着顺手就行。
% a5 K2 r$ L$ l这里安利一波Java，哈哈，Java写算法题写多了，真的比较舒适。
  j* s/ z- ^5 y$ l- i- h, J关于文章类型的选择：
9 |% p2 t3 s( d, V5 H
2 w: P- i& r+ I' C. ]$ y, j/ F
选取了一些较为基本的算法类型，都是比较常见的。
( `8 }" c% C( R* g不涉及ACM等难度太高的题，大佬们移步哈。
# ?" W- Q: b' a3 ?5 j2 m; ]5 |/ J都是一些比较经典的问题。
% K0 P5 E; R/ L5 x关于题目的来源：

( e& @. f  d5 T- w" m: b) x
5 p) {# I+ R: ?- ^平时主要刷题的平台是Leetcode，因为是函数式的，比较方便。
还有一些是在《剑指offer》，《程序员面试金典》中看到比较好的，所有题目后面都给出了出处。
关于题解的说明：

7 S0 G5 u+ _2 F, W$ Y; I  w
. J4 u! T2 v! `& ?' H( _0 m2 L& `题解是我自己所写，有时候也参考了一些官方题解的思想，可能更好理解。
题解的代码都提交测试过的，保证暂时没有问题。
个人水平有限，可能文章里面存在一些问题，还望大佬多多指点。
每个题目附带了原文链接，不喜欢阅读我题解的小伙伴们也可以直接移步原出处哈。
关于算法能力提升的一些意见：
% q2 W1 S4 S' {

& @6 D; e4 B+ v* \7 P个人认为，算法来说，思想最为重要，有算法的严谨思想，才是算法能力提升的基础。
  S; {9 X6 e1 E5 Q; a) V1 P刷题就是培养算法思想的一种实际行动。
6 x+ ?8 r: i) f+ e' T) Q好好理解透一个问题，或者一类问题，远胜于你麻木的刷大量的题。
- c% F; K* ]3 k' o$ E算法确实也有模板题，只需要照着模板就能做出，但问题是，照着模板就一定能做出来嘛，是否真正理解了为什么这个模板可以通用。
& |- n- ?8 K5 N1 ?0 X关于分类：
$ N- d8 K( R- I, \

有些分类确实不太好分，所以就单独列出来了。
5 O" w$ h; B+ |# c5 J主要的还是区分开来了。
1 I: I7 v. t' B& }0x03.正文–精选算法100题（附个人题解）
分类一：动态规划（dp）
) t% I# @* B; n$ ^' A# }. B没错，就是你熟悉的dp，dp说简单也简单，说难也实在是太难了，重点是如何找到里面的状态转移方程。经过这些题目的训练，希望你能有一些初步的dp思路了。
5 K) y4 h6 [2 f* q' @+ t; f( z
$ s3 v5 b0 G  A. E7 F5 E
题目名称        来源        个人题解        备注
3 S2 j4 s# L6 P* H/ t$ ^& X2 T01.打家劫舍        Leetcode题198：戳我前往        戳我前往        估计是最好的dp入门题型了
' i( Z$ g  k& m7 A& _02.斐波拉契数列        经典问题        戳我前往        确实比较经典哦~
03.零钱兑换问题        Leetcode题322：戳我前往        戳我前往        也是一个比较经典的问题了
! I, @( k2 }3 Z1 V9 [* L04.零钱兑换II        Leetcode题518：戳我前往        戳我前往        零钱问题通用解法
05.最长上升子序列        Leetcode题300：戳我前往        戳我前往        堪称数组dp中的典范
06.牌型种数        蓝桥杯：链接暂无        戳我前往        二维动态规划，要仔细想想
$ |" t, f8 p/ [) a" }/ J07.最低票价        Leetcode题983：戳我前往        戳我前往        如何状态转移？
) G% u) d) j. F2 @" B' G08.不同的二叉搜索树        Leetcode题152：戳我前往        戳我前往        你会发现dp的神奇之处
2 e* _8 X* P9 a0 @0 b; x# g9 Q09.礼物的最大价值        《剑指offer》题47        戳我前往        优化dp的思路
( F8 p3 L: D. K10.接雨水        Leetcode题42：戳我前往        戳我前往        需要仔细思考以发现dp
11.编辑距离        Leetcode题72：戳我前往        戳我前往        最为经典的二维dp题型
, V9 d5 P4 R* j9 i3 t12.买卖股票的最佳时机（6题）        Leetcode6题：戳我前往        戳我前往        统一化的dp思维，棒
13.鸡蛋掉落        Leetcode题887：戳我前往        戳我前往        有些难度哦~
' i- t6 H% K# _$ N9 F14.最大正方形        Leetcode题221：戳我前往        戳我前往        矩阵中的dp思路
9 A) v4 p! b* Y9 A& R0 |15.和为K的子数组        Leetcode题560：戳我前往        戳我前往        前缀和也是dp的思路
分类二：搜索类（DFS，BFS，回溯，暴力搜索）
7 l! u3 q, o3 q( }3 x' u搜索类的算法题应该是随便哪个算法比赛都可以看到，虽然经典，但在这上面还是会有比较难的问题，所以，掌握基本思路和套路就显得格外重要。
) i( D3 X0 C$ _7 r+ c
$ Z2 G/ }- J# L8 s. Y' H: b2 K
题目名称        来源        个人题解        备注
* T& {- ?; Q6 D; S0 {5 [0 _16.图的深搜和广搜        经典问题        戳我前往        搜索中的经典问题
17.方格填数        蓝桥杯：链接暂无        戳我前往        揣摩一下DFS的思路
' P+ S+ P) v1 y, Q  Y1 `18.路径之谜        蓝桥杯：链接暂无        戳我前往        经典改编迷宫问题
19.岛屿的最大面积        Leetcode题695：戳我前往        戳我前往        最常见的矩阵中的DFS
$ [3 n0 t6 Q* _. h5 h20.逃离大迷宫        Leetcode题1036：戳我前往        戳我前往        各种搜索思想都可以应用
" b" @) k; }, U21.单词搜索        Leetcode题79：戳我前往        戳我前往        字符串中的搜索
' a; `% e& I) C0 l+ m- I/ L* ~22.检查网格中是否存在有效路径        Leetcode题1391：戳我前往        戳我前往        思考另类的搜索
- {! q! S3 w( \8 o+ |! h* t' s23.地图分析        Leetcode题1162：戳我前往        戳我前往        多源BFS
3 Q; n0 m* y( x( S0 W24.机器人的运动范围        《剑指offer》13题        戳我前往        DFS进行计数的基本思路
- \. W2 c- I: L/ ?# D25.括号生成        Leetcode题22：戳我前往        戳我前往        用DFS生产括号
26.01 矩阵        Leetcode题542：戳我前往        戳我前往        矩阵中的搜索
8 Q6 q5 q& j  E+ g/ s5 E- H27.岛屿数量        Leetcode题200：戳我前往        戳我前往        根据需求使用DFS
28.全排列问题        Leetcode题46：戳我前往        戳我前往        最经典的回溯算法
分类三：字符串
别忽视字符串的算法问题，它难起来可以非常难，简单的也很简单，面试喜欢提问，而且特别容易出错，需要引起重视。
) g6 P( F! e3 S+ a% A. o  U

( s4 X. E4 R/ M: q, `题目名称        来源        个人题解        备注
29.KMP算法        经典算法        戳我前往        经典字符串匹配算法
; p% l; p7 `6 s" {! J30.拼写单词        Leetcode题1160：戳我前往        戳我前往        很简单的字符串问题
  v  g* @1 o3 Q! D% i1 q& _. V31.竖直打印单词        Leetcode题1324：戳我前往        戳我前往        简单但值得思考
$ N: q% o. B8 M/ @1 W32.不含 AAA 或 BBB 的字符串        Leetcode题984：戳我前往        戳我前往        巧妙构造出字符串
" _( ^$ O/ M+ P/ i33.实现Trie（前缀树）        Leetcode题208：戳我前往        戳我前往        字符串中经典的算法
6 |) h4 P9 B. O6 B34.最长快乐前缀        Leetcode题1392：戳我前往        戳我前往        如何处理字符串的前后缀
9 D8 }7 c# v) h$ t7 T35.单词搜索II        Leetcode题212：戳我前往        戳我前往        前缀树的应用
8 z7 c3 K+ s, n3 f# v6 C36.单词的压缩编码        Leetcode题820：戳我前往        戳我前往        前缀树灵活运用
5 `5 o9 U- Y) B% _37.判定字符是否唯一        《程序员面试金典》01.02        戳我前往        简单但值得思考
8 q% k; j# Y4 |38.判定是否互为字符重排        《程序员面试金典》 01.02        戳我前往        简单的面试题
5 |8 T9 d& _2 ^" J, `) M' {39.无重复字符的最长子串        Leetcode题3：戳我前往        戳我前往        字符串中的滑动窗口
40.字符串转换整数        Leetcode题8：戳我前往        戳我前往        需要考虑的细节很多
  Y9 \: c5 S6 g6 ?  O41.翻转字符串里的单词        Leetcode题151：戳我前往        戳我前往        正则匹配
- ]/ Q) f9 j8 T! T" v; e42.整数转换英文表示        Leetcode题273：戳我前往        戳我前往        非常实用的算法题
; P. o0 U( X  R) ^43.统计重复个数        Leetcode题466：戳我前往        戳我前往        循环结剪枝
3 t4 w/ \( k7 @& ]7 ^( c6 u# c44.超级回文数        Leetcode题906：戳我前往        戳我前往        字符串与大数的处理思路
; w4 x% }) q% k8 P# i: i45.单词子集        Leetcode题96：戳我前往        戳我前往        特征思想的应用
' }" ]: @2 W; H; w4 N: Q8 w6 x分类四：容器类（哈希表，栈，队列，Map，Set）
0 ]% S; y' B  i9 {) R容器类的算法题一般需要根据一些容器的特点来解决响应的问题，还有需要选择合适的容器进行新的数据结构的设计，掌握它们的使用，非常重要。
) Y  ]1 D/ Q" p: x8 z
9 b* U9 O  n. H( Y" i5 u8 @, b' j
题目名称        来源        个人题解        备注
46.按位与为零的三元组        Leetcode题82：戳我前往        戳我前往        哈希表优化
  }3 ]' r# q5 p! p& R  V/ j- W47.设计地铁系统        Leetcode题1396：戳我前往        戳我前往        合理选择容器
48.LFU缓存        《程序员面试金典》        戳我前往        选择容器来设计
$ T( _9 ~7 p! D& S49.设计推特        Leetcode题355：戳我前往        戳我前往        很实用的算法
50.最小栈        Leetcode题155：戳我前往        戳我前往        两栈设计最小栈
51.子数组的最小值之和        Leetcode题907：戳我前往        戳我前往        单调栈的应用
" w0 ~2 r' P% i5 w52.栈的压入、弹出序列        《剑指offer》        戳我前往        栈的合法序列
+ n4 i' _2 ]% M; h1 g53.有效括号的嵌套深度        Leetcode题1111：戳我前往        戳我前往        模仿栈
54.逆波兰算法        经典算法        戳我前往        后缀表达式关键算法
" X. W# C4 r3 j1 t  J分类五：数学思维类（含位运算思想）
数学思维类的题由于需要很强大的数学思维，但是这又不是一天可以练成的，所以，也常常在面试中会被问到，只有慢慢的积累，才是王道。

4 e, d; d- u* S# V3 z2 ~( f
题目名称        来源        个人题解        备注
55.水壶问题        Leetcode题365：戳我前往        戳我前往        经典数学问题
56.三维形体的表面积        Leetcode题892：戳我前往        戳我前往        空间思想解决算法问题
: i$ H0 t( E: ~/ h" P57.生命游戏        Leetcode题289：戳我前往        戳我前往        数学思维的运用
  b. m0 q' J' c% A- s* {# v) o58.交点        《程序员面试金典》16.03        戳我前往        二维平面的交点问题
2 h: P0 A  a9 t( R) K$ _0 Z59.使数组唯一的最小增量        Leetcode题945：戳我前往        戳我前往        数学思维的运用
+ M" Q7 P8 x. v' B3 K+ A0 Z( {60.数值的整数次方        《剑指offer》题16        戳我前往        非常容易出错的面试题
61.求 1+2+…+n        《剑指offer》        戳我前往        短路原则
+ s, D+ z% z! {9 H# A# F2 J62.1～n整数中1出现的次数        《剑指offer》        戳我前往        数学思维找规律
+ Y+ e+ c/ O) |; X9 m$ a, Q63.数组中数字出现的次数        《剑指offer》        戳我前往        分组异或
分类六：链表
# T" Q/ P8 ]8 i  [/ n链表是一种非常常见的数据结构，不管在实际应用还是算法竞赛中，都经常出现，掌握对它们的基本处理，非常重要。
! n; H& s# D* l, P: @" ^
6 q# l( H8 i9 I4 P
题目名称        来源        个人题解        备注
9 F5 Q6 F" _- P5 `  V0 b0 @; P2 @64.两数相加        Leetcode题2：戳我前往        戳我前往        链表的加法问题
2 T& \' f9 N1 o) a2 L' A  q65.链表的中间结点        Leetcode题876：戳我前往        戳我前往        快慢指针思想
66.删除链表的倒数第N个节点        Leetcode题19：戳我前往        戳我前往        哑节点和双指针
67.合并两个有序链表        Leetcode题21：戳我前往        戳我前往        链表的递归处理
68.合并K个排序链表        Leetcode题23：戳我前往        戳我前往        优先队列的使用
+ a1 k6 H7 \1 G6 A: I) `. u69.删除排序链表中的重复元素 II        Leetcode题82：戳我前往        戳我前往        链表基础指针操作
  C6 _- h0 p) K' v6 y70.分隔链表        Leetcode题86：戳我前往        戳我前往        双指针操作
71.旋转链表        Leetcode题61：戳我前往        戳我前往        巧转循环链表
2 A: X1 X- e2 W' g' \72.两两交换链表中的节点        Leetcode题24：戳我前往        戳我前往        递归解决
0 T5 Y6 Y. K  E& o, w: p73.反转链表        Leetcode题206：戳我前往        戳我前往        多种思路反转链表
. K9 y* t5 f3 _4 c74.K 个一组翻转链表        Leetcode题25：戳我前往        戳我前往        分组逆转
1 k% z  L( f! o+ [  S9 i% N75.判断链表是否有环        《剑指offer》        戳我前往        多种思路判断链表是否有环
, l% S% H% s9 h+ H- j6 r2 H! O# n76.单链表的插入排序        Leetcode题147：戳我前往        戳我前往        链表的插入排序
/ Y2 J$ R/ X: ?& |77.两数相加 II        Leetcode题445：戳我前往        戳我前往        用栈翻转链表元素
5 O# g: A% p8 f$ D1 T2 ]; m分类七：树
树也是一种非常重要的数据结构，因为很多容器的底层都设计到树，所以树也成了面试常问的重点了，你需要对他们的一些基本算法题，非常熟练。
( P/ N. z" B. H9 i, J+ a

! g6 t, w7 S. o. Q! Y题目名称        来源        个人题解        备注
% l7 S0 V6 Z* o" v" p78.删除给定值的叶子结点        Leetcode题1325：戳我前往        戳我前往        树的简单删除问题
79.二叉树的最大最小深度        Leetcode题104：戳我前往        戳我前往        二叉树的深度问题
- q- p4 H+ g2 P80.将有序数组转换为二叉搜索树        Leetcode题108：戳我前往        戳我前往        数组和二叉树的转换
& d6 P/ E5 a4 D: f( g4 h- b9 |81.二叉树的右视图        Leetcode题199：戳我前往        戳我前往        二叉树的视图转换
82.另一个树的子树        Leetcode题572：戳我前往        戳我前往        两树关系的判断
83.二叉树的最近公共祖先        《剑指offer》        戳我前往        公共祖先问题
( d) p4 S0 b9 K/ a2 l# q& `84.二叉树的层序遍历序列存储        Leetcode题102：戳我前往        戳我前往        二叉树遍历序列的存储
85.验证二叉搜索树        Leetcode题98：戳我前往        戳我前往        二叉搜索树的验证
分类八：数组（贪心，二分）
数组类的算法题也是，说难不难，说简单不简单，而且数组是平时编码用的最多的结构了，所以，需要对它的一些基本算法引起重视。
4 s6 K: m; s$ b( }

题目名称        来源        个人题解        备注
7 H( J, d7 ]& z- s86.两个数组间的距离值        Leetcode题1385：戳我前往        戳我前往        二分法应用
# s8 `6 k: J% O$ W0 V1 n87.旋转矩阵        《程序员面试金典》        戳我前往        原地修改
88.合并区间        Leetcode题56：戳我前往        戳我前往        排序处理数组问题
89.跳跃游戏        Leetcode题55：戳我前往        戳我前往        贪心思想运用
90.盛最多水的容器        Leetcode题11：戳我前往        戳我前往        双指针
- c3 Y7 p' R1 \7 X% l/ }0 L# E91.统计「优美子数组」        Leetcode题1248：戳我前往        戳我前往        滑动窗口
92.搜索旋转排序数组        Leetcode题33：戳我前往        戳我前往        二分搜索
7 G/ |# f+ r7 U* _5 N: ]93.山脉数组中查找目标值        Leetcode题1095：戳我前往        戳我前往        二分搜索
94.快乐数        Leetcode题202：戳我前往        戳我前往        快慢指针判断成环思路
95.跳跃游戏 II        Leetcode题45：戳我前往        戳我前往        贪心思想
) f+ v9 ~, s: g1 n96.x 的平方根        Leetcode题69：戳我前往        戳我前往        二分法取平方根
/ K* ~) [; d* M3 w1 U97.数组中的逆序对        《剑指offer》题51        戳我前往        归并中的计数（分治）
7 l3 f* z* \# U6 E5 _$ {& k98.课程表 II        Leetcode题210：戳我前往        戳我前往        数组中的拓扑排序
分类九：经典算法列举
最后两个，凑个整，刚好100，是一些比较经典的算法列举。
9 l# L: W! i' [; B& @

题目名称        来源        个人题解        备注
5 u1 G# m/ V% c; B! X3 p4 H6 s9 w2 m99.普利姆算法        经典算法        戳我前往        最小生成树经典算法
* ?9 u" D3 T' n! B, q" C100.约瑟夫环        经典算法        戳我前往        很经典的动态问题
7 C# o# ], |4 U% x# d7 ?- j0x04.End
- S% K. R! R. [2 W/ y希望这100个算法题能对正在看的你有所帮助！
后续还会继续更新更多的内容。
您的支持，是我分享的不竭动力！

! N0 C# H$ f! B8 Q* I$ [
! F1 b" I/ c% ^* k0 R+ n+ I– ATFWUS 2020-05-18
————————————————
: A! A2 ~4 k4 \: N3 y; |版权声明：本文为CSDN博主「ATFWUS」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
/ |: s& ?2 X' K: A原文链接：https://blog.csdn.net/ATFWUS/article/details/106193067
& P- d- V. U4 ]& @: ?+ K) V1 }
) X% p  x5 ^$ P9 d6 F# J+ w. G
" c& }& l3 f7 K9 M7 d

1051373629

% `3 n  ?2 J. B" G2 V6 b顶一个
顶一个
+ x( t/ V) d! d& X顶一个

huangma

感谢分享
9 f+ M2 G0 T; f& u) i6 `* G