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

杨利霞

1 @  [2 i4 _' p( e/ \2020最新-精选基础算法100题（面试必备）

5 _0 w: O! }$ x0x01.概述
3 @5 h- z9 W7 {: v作为一个程序员，算法能力必不可少，虽然不一定是算法工程师，但是算法还是彰显着个人的编码能力，面试中也经常会被问到，甚至会被要求临场做算法题，所以，还是好好积累吧。
+ k+ g4 Z/ i* J1 R

个人其实对算法挺有兴趣的，从3月份开始，陆陆续续刷了一些算法题，把一些有意义的记录下来了，也顺便写了一些题解，个人认为，还是挺有收获的。
之前写了一篇算法文章的目录，不过后来就忘了实时去更新了，于是现在，想把之前做过的一些有意义的算法题分享出来，刚好整理了100篇比较有意义的。希望对大家有所帮助。
% ?" ^9 x3 L: D- J6 f
# m& G5 m& U9 f! s1 ?. w3 ]4 M
! o- P/ t. H1 ?: L4 C6 B! F: B

* S6 _# R  O( `' C2 x6 ~2 ^0x02.说明
关于语言的选择：
/ H) X2 B. N* n% S

前半段主要用C++写的，后半段主要用Java写的。
其实什么语言没有太大区别，主要是思想，用着顺手就行。
这里安利一波Java，哈哈，Java写算法题写多了，真的比较舒适。
9 c! d# D$ P" K8 I关于文章类型的选择：
+ g9 A, i$ d: x8 w8 e- X% S

, [0 p( ?7 u! Y! ?选取了一些较为基本的算法类型，都是比较常见的。
; s' h- T" R# x不涉及ACM等难度太高的题，大佬们移步哈。
' [, L8 }8 H8 ^$ h# Y7 f都是一些比较经典的问题。
& H/ a( X% n1 e  l关于题目的来源：

1 c6 k8 W! r' N$ l
平时主要刷题的平台是Leetcode，因为是函数式的，比较方便。
7 _$ D% g2 K9 `& d# Q( g还有一些是在《剑指offer》，《程序员面试金典》中看到比较好的，所有题目后面都给出了出处。
关于题解的说明：


题解是我自己所写，有时候也参考了一些官方题解的思想，可能更好理解。
题解的代码都提交测试过的，保证暂时没有问题。
7 E6 h7 Y/ a' g个人水平有限，可能文章里面存在一些问题，还望大佬多多指点。
! g  G$ Q: f; g0 G5 W( o3 }每个题目附带了原文链接，不喜欢阅读我题解的小伙伴们也可以直接移步原出处哈。
关于算法能力提升的一些意见：


个人认为，算法来说，思想最为重要，有算法的严谨思想，才是算法能力提升的基础。
刷题就是培养算法思想的一种实际行动。
3 W# |6 H9 K  p好好理解透一个问题，或者一类问题，远胜于你麻木的刷大量的题。
算法确实也有模板题，只需要照着模板就能做出，但问题是，照着模板就一定能做出来嘛，是否真正理解了为什么这个模板可以通用。
* v* @7 g/ C- j  f9 R/ y5 B5 g  y关于分类：
4 L7 F! [0 m/ L. k

& i' ~. g7 N# I0 T有些分类确实不太好分，所以就单独列出来了。
5 P0 B: B, |" P$ @4 N7 X主要的还是区分开来了。
0x03.正文–精选算法100题（附个人题解）
! [* \/ d8 p. Y) @5 E$ ]. {: y: e分类一：动态规划（dp）
' M4 g/ T. Z4 G5 s+ s没错，就是你熟悉的dp，dp说简单也简单，说难也实在是太难了，重点是如何找到里面的状态转移方程。经过这些题目的训练，希望你能有一些初步的dp思路了。


- N! o% V9 ^( b- `' |& P题目名称        来源        个人题解        备注
1 n* i% d5 Q& [6 F01.打家劫舍        Leetcode题198：戳我前往        戳我前往        估计是最好的dp入门题型了
02.斐波拉契数列        经典问题        戳我前往        确实比较经典哦~
+ N, M7 U6 k* L7 ?5 x* x4 ^03.零钱兑换问题        Leetcode题322：戳我前往        戳我前往        也是一个比较经典的问题了
04.零钱兑换II        Leetcode题518：戳我前往        戳我前往        零钱问题通用解法
2 V" w; n8 T! X& I  R+ q) @05.最长上升子序列        Leetcode题300：戳我前往        戳我前往        堪称数组dp中的典范
06.牌型种数        蓝桥杯：链接暂无        戳我前往        二维动态规划，要仔细想想
' }. d. a0 p  g+ y  f07.最低票价        Leetcode题983：戳我前往        戳我前往        如何状态转移？
08.不同的二叉搜索树        Leetcode题152：戳我前往        戳我前往        你会发现dp的神奇之处
09.礼物的最大价值        《剑指offer》题47        戳我前往        优化dp的思路
10.接雨水        Leetcode题42：戳我前往        戳我前往        需要仔细思考以发现dp
11.编辑距离        Leetcode题72：戳我前往        戳我前往        最为经典的二维dp题型
5 A+ I4 {7 ?/ H' V* r( w1 W* K; \12.买卖股票的最佳时机（6题）        Leetcode6题：戳我前往        戳我前往        统一化的dp思维，棒
13.鸡蛋掉落        Leetcode题887：戳我前往        戳我前往        有些难度哦~
14.最大正方形        Leetcode题221：戳我前往        戳我前往        矩阵中的dp思路
1 E$ o" G. `- ^& M( |6 k) Q% G15.和为K的子数组        Leetcode题560：戳我前往        戳我前往        前缀和也是dp的思路
分类二：搜索类（DFS，BFS，回溯，暴力搜索）
+ P6 Q4 [- t6 t% [, S2 ?' S搜索类的算法题应该是随便哪个算法比赛都可以看到，虽然经典，但在这上面还是会有比较难的问题，所以，掌握基本思路和套路就显得格外重要。
9 T" ]/ g6 v, ^# }  Q" Y! `

题目名称        来源        个人题解        备注
$ b( n9 V( \6 X- b* m1 s8 ~16.图的深搜和广搜        经典问题        戳我前往        搜索中的经典问题
17.方格填数        蓝桥杯：链接暂无        戳我前往        揣摩一下DFS的思路
+ q2 _5 Z5 ]. B8 e& K, U2 p18.路径之谜        蓝桥杯：链接暂无        戳我前往        经典改编迷宫问题
19.岛屿的最大面积        Leetcode题695：戳我前往        戳我前往        最常见的矩阵中的DFS
20.逃离大迷宫        Leetcode题1036：戳我前往        戳我前往        各种搜索思想都可以应用
3 Z! ^: x8 l& k/ Y; o  |+ R21.单词搜索        Leetcode题79：戳我前往        戳我前往        字符串中的搜索
22.检查网格中是否存在有效路径        Leetcode题1391：戳我前往        戳我前往        思考另类的搜索
23.地图分析        Leetcode题1162：戳我前往        戳我前往        多源BFS
* z- f  U. p; ?$ Q2 P& I! m24.机器人的运动范围        《剑指offer》13题        戳我前往        DFS进行计数的基本思路
25.括号生成        Leetcode题22：戳我前往        戳我前往        用DFS生产括号
3 f) z/ l% [9 Y1 r26.01 矩阵        Leetcode题542：戳我前往        戳我前往        矩阵中的搜索
27.岛屿数量        Leetcode题200：戳我前往        戳我前往        根据需求使用DFS
$ l6 }; i, |( Z& m  [2 R# o+ f/ O, Y- u28.全排列问题        Leetcode题46：戳我前往        戳我前往        最经典的回溯算法
分类三：字符串
别忽视字符串的算法问题，它难起来可以非常难，简单的也很简单，面试喜欢提问，而且特别容易出错，需要引起重视。


3 c" t6 t/ Y' A. b" s题目名称        来源        个人题解        备注
29.KMP算法        经典算法        戳我前往        经典字符串匹配算法
7 t: q) t& m) J6 b2 u. `1 C# s30.拼写单词        Leetcode题1160：戳我前往        戳我前往        很简单的字符串问题
31.竖直打印单词        Leetcode题1324：戳我前往        戳我前往        简单但值得思考
8 N* A: x& p. k* g32.不含 AAA 或 BBB 的字符串        Leetcode题984：戳我前往        戳我前往        巧妙构造出字符串
6 G/ f& O' W8 ?/ o7 c6 ~- W33.实现Trie（前缀树）        Leetcode题208：戳我前往        戳我前往        字符串中经典的算法
+ M, l, e. c$ b  F, I6 ?. J/ S5 s& `34.最长快乐前缀        Leetcode题1392：戳我前往        戳我前往        如何处理字符串的前后缀
35.单词搜索II        Leetcode题212：戳我前往        戳我前往        前缀树的应用
36.单词的压缩编码        Leetcode题820：戳我前往        戳我前往        前缀树灵活运用
37.判定字符是否唯一        《程序员面试金典》01.02        戳我前往        简单但值得思考
$ ]6 ^7 J0 U& u* {2 x38.判定是否互为字符重排        《程序员面试金典》 01.02        戳我前往        简单的面试题
39.无重复字符的最长子串        Leetcode题3：戳我前往        戳我前往        字符串中的滑动窗口
$ V# F/ Q  [7 ~40.字符串转换整数        Leetcode题8：戳我前往        戳我前往        需要考虑的细节很多
41.翻转字符串里的单词        Leetcode题151：戳我前往        戳我前往        正则匹配
3 S0 `/ e) T# `! x: ~42.整数转换英文表示        Leetcode题273：戳我前往        戳我前往        非常实用的算法题
43.统计重复个数        Leetcode题466：戳我前往        戳我前往        循环结剪枝
44.超级回文数        Leetcode题906：戳我前往        戳我前往        字符串与大数的处理思路
! N6 w# ~$ V% [* a1 L! U0 @45.单词子集        Leetcode题96：戳我前往        戳我前往        特征思想的应用
分类四：容器类（哈希表，栈，队列，Map，Set）
/ H3 t1 Z# b$ G) h1 e% P容器类的算法题一般需要根据一些容器的特点来解决响应的问题，还有需要选择合适的容器进行新的数据结构的设计，掌握它们的使用，非常重要。

+ N& M5 \. O, c! h& ~
  h$ B6 m. z0 U题目名称        来源        个人题解        备注
5 L: [0 U( E" u# D( @/ q46.按位与为零的三元组        Leetcode题82：戳我前往        戳我前往        哈希表优化
5 Y+ S% ^* T# N2 p; I0 t, b47.设计地铁系统        Leetcode题1396：戳我前往        戳我前往        合理选择容器
/ G$ z3 O/ J  ?) x48.LFU缓存        《程序员面试金典》        戳我前往        选择容器来设计
- K! M: v4 l# W( ?49.设计推特        Leetcode题355：戳我前往        戳我前往        很实用的算法
50.最小栈        Leetcode题155：戳我前往        戳我前往        两栈设计最小栈
51.子数组的最小值之和        Leetcode题907：戳我前往        戳我前往        单调栈的应用
52.栈的压入、弹出序列        《剑指offer》        戳我前往        栈的合法序列
53.有效括号的嵌套深度        Leetcode题1111：戳我前往        戳我前往        模仿栈
8 Z( d. }- \+ X5 J54.逆波兰算法        经典算法        戳我前往        后缀表达式关键算法
+ u3 D1 e$ k3 a3 `. n分类五：数学思维类（含位运算思想）
# ^5 s+ v' u+ [8 k  Q数学思维类的题由于需要很强大的数学思维，但是这又不是一天可以练成的，所以，也常常在面试中会被问到，只有慢慢的积累，才是王道。
' x* q/ s6 d& |
) i" Z# z; Z. _$ e' S) N8 {
* G/ u/ S: i7 a! a8 k3 k( E6 w* ?0 q题目名称        来源        个人题解        备注
+ d! M* s; Y* _1 L8 I55.水壶问题        Leetcode题365：戳我前往        戳我前往        经典数学问题
9 J0 t! ]( ~" S: v4 _56.三维形体的表面积        Leetcode题892：戳我前往        戳我前往        空间思想解决算法问题
57.生命游戏        Leetcode题289：戳我前往        戳我前往        数学思维的运用
! }% L1 {) Y) ^( B7 K, }5 c58.交点        《程序员面试金典》16.03        戳我前往        二维平面的交点问题
) W1 M5 ~- H) g" t) O59.使数组唯一的最小增量        Leetcode题945：戳我前往        戳我前往        数学思维的运用
60.数值的整数次方        《剑指offer》题16        戳我前往        非常容易出错的面试题
61.求 1+2+…+n        《剑指offer》        戳我前往        短路原则
% G: Q, k$ q5 g0 Y62.1～n整数中1出现的次数        《剑指offer》        戳我前往        数学思维找规律
63.数组中数字出现的次数        《剑指offer》        戳我前往        分组异或
分类六：链表
2 Y9 k1 A1 ^% G7 K" s链表是一种非常常见的数据结构，不管在实际应用还是算法竞赛中，都经常出现，掌握对它们的基本处理，非常重要。
, S. j( Q. m$ T4 f; w
9 ?/ A. H9 F9 k* ?) b& e
题目名称        来源        个人题解        备注
64.两数相加        Leetcode题2：戳我前往        戳我前往        链表的加法问题
! t, W3 b* g  Q& F65.链表的中间结点        Leetcode题876：戳我前往        戳我前往        快慢指针思想
66.删除链表的倒数第N个节点        Leetcode题19：戳我前往        戳我前往        哑节点和双指针
# O; O8 S2 d; z, ]$ ~/ e67.合并两个有序链表        Leetcode题21：戳我前往        戳我前往        链表的递归处理
' O" l1 a0 @9 A4 o, Y& o: K3 g68.合并K个排序链表        Leetcode题23：戳我前往        戳我前往        优先队列的使用
69.删除排序链表中的重复元素 II        Leetcode题82：戳我前往        戳我前往        链表基础指针操作
70.分隔链表        Leetcode题86：戳我前往        戳我前往        双指针操作
* j; E& H3 ?) X; d9 ]  P# [, \0 _% C- j71.旋转链表        Leetcode题61：戳我前往        戳我前往        巧转循环链表
+ W9 A6 j0 Y' M, t" {. C% }72.两两交换链表中的节点        Leetcode题24：戳我前往        戳我前往        递归解决
73.反转链表        Leetcode题206：戳我前往        戳我前往        多种思路反转链表
74.K 个一组翻转链表        Leetcode题25：戳我前往        戳我前往        分组逆转
2 ?/ `- X; M+ b# Z2 [75.判断链表是否有环        《剑指offer》        戳我前往        多种思路判断链表是否有环
: z* z- h% F4 e' h2 _1 J: C76.单链表的插入排序        Leetcode题147：戳我前往        戳我前往        链表的插入排序
77.两数相加 II        Leetcode题445：戳我前往        戳我前往        用栈翻转链表元素
7 p& S( i1 C9 y1 M2 O. F+ V, I分类七：树
+ T. g* |2 C. T7 J5 p/ `$ P5 v( r9 p树也是一种非常重要的数据结构，因为很多容器的底层都设计到树，所以树也成了面试常问的重点了，你需要对他们的一些基本算法题，非常熟练。
8 M' c- [. e# Q1 ^

: Z* _# I! `# S1 a- P题目名称        来源        个人题解        备注
78.删除给定值的叶子结点        Leetcode题1325：戳我前往        戳我前往        树的简单删除问题
79.二叉树的最大最小深度        Leetcode题104：戳我前往        戳我前往        二叉树的深度问题
80.将有序数组转换为二叉搜索树        Leetcode题108：戳我前往        戳我前往        数组和二叉树的转换
* M' _% ]; \% s2 R81.二叉树的右视图        Leetcode题199：戳我前往        戳我前往        二叉树的视图转换
$ s# N8 |* O, ], N9 Q% E82.另一个树的子树        Leetcode题572：戳我前往        戳我前往        两树关系的判断
5 Y: M1 ~2 m3 E2 J+ g& J$ l" k83.二叉树的最近公共祖先        《剑指offer》        戳我前往        公共祖先问题
2 B# H/ \, w: C6 s* }84.二叉树的层序遍历序列存储        Leetcode题102：戳我前往        戳我前往        二叉树遍历序列的存储
5 w* D" ?8 h: b1 u& g2 K85.验证二叉搜索树        Leetcode题98：戳我前往        戳我前往        二叉搜索树的验证
- k3 u7 E3 o3 B3 n/ O/ R& \分类八：数组（贪心，二分）
数组类的算法题也是，说难不难，说简单不简单，而且数组是平时编码用的最多的结构了，所以，需要对它的一些基本算法引起重视。
# `# n0 x# O1 W8 ?: ~/ m% U# c1 \
( U/ b5 q: ]& }3 x4 A+ b' D$ s
( d+ k8 H0 C$ ~0 o4 g' M题目名称        来源        个人题解        备注
! _2 X6 M5 L2 h2 _* _8 }% G  K' h  c86.两个数组间的距离值        Leetcode题1385：戳我前往        戳我前往        二分法应用
$ O8 r* A3 F6 c& h87.旋转矩阵        《程序员面试金典》        戳我前往        原地修改
4 z% D( H3 t3 ~1 j4 L: i88.合并区间        Leetcode题56：戳我前往        戳我前往        排序处理数组问题
89.跳跃游戏        Leetcode题55：戳我前往        戳我前往        贪心思想运用
90.盛最多水的容器        Leetcode题11：戳我前往        戳我前往        双指针
91.统计「优美子数组」        Leetcode题1248：戳我前往        戳我前往        滑动窗口
92.搜索旋转排序数组        Leetcode题33：戳我前往        戳我前往        二分搜索
- C1 e8 ~! x0 \1 r% O4 u! r93.山脉数组中查找目标值        Leetcode题1095：戳我前往        戳我前往        二分搜索
5 _6 \% _+ n" x& k+ z# ^94.快乐数        Leetcode题202：戳我前往        戳我前往        快慢指针判断成环思路
& D/ F) [3 k# E! u$ {! g4 G95.跳跃游戏 II        Leetcode题45：戳我前往        戳我前往        贪心思想
96.x 的平方根        Leetcode题69：戳我前往        戳我前往        二分法取平方根
; t& m$ y0 l. u6 A# m* D( G0 y97.数组中的逆序对        《剑指offer》题51        戳我前往        归并中的计数（分治）
98.课程表 II        Leetcode题210：戳我前往        戳我前往        数组中的拓扑排序
分类九：经典算法列举
最后两个，凑个整，刚好100，是一些比较经典的算法列举。
0 E5 Z  L& r0 E1 B% C: S

( g/ }  k& b( ^2 D9 G题目名称        来源        个人题解        备注
9 k$ j: o% Q. P+ [' U: [99.普利姆算法        经典算法        戳我前往        最小生成树经典算法
100.约瑟夫环        经典算法        戳我前往        很经典的动态问题
0x04.End
希望这100个算法题能对正在看的你有所帮助！
7 q& S4 i/ u( }$ }" f- {后续还会继续更新更多的内容。
6 A8 T1 o& K  i3 n$ c& h您的支持，是我分享的不竭动力！
3 k9 {  M6 j9 e- F5 ^5 H6 L# z* M
2 X( m# Y' W/ p1 ]$ B; i
) h8 Y* ~; h" y  X* r– ATFWUS 2020-05-18
————————————————
% f8 |8 O5 t$ G7 Y- W( c' {, k版权声明：本文为CSDN博主「ATFWUS」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 B9 x$ \: c3 m4 s- ]; S7 p原文链接：https://blog.csdn.net/ATFWUS/article/details/106193067
* n8 u  t  Q  z  C3 P% Z2 d

1051373629

2 L( ]( [4 A4 B/ y顶一个
; G0 C* q. F( k( ~9 L5 k) G4 \6 F顶一个
+ Y! }) n: h% {5 U3 \0 I+ ]3 y顶一个

huangma

感谢分享