写在前面

BAT 等国内的一线名企，在招聘工程师的过程中，对算法和数据结构都会重点考察。但算法易学难精，我的很多粉丝技术能力不错，但面试时总败在算法这一关，拿不到好 Offer。但说实话，数据结构和算法花点时间，用对方法，很容易解决。面试官为什么爱问数据结构与算法，答案很简单：

  • 算法能力能够准确辨别一个程序员的技术功底是否扎实；
  • 算法能力是发掘程序员的学习能力与成长潜力的关键手段；
  • 算法能力能够协助判断程序员在面对新问题时，分析并解决问题的能力；
  • 算法能力是设计一个高性能系统、性能优化的必备基础。

很多人力扣（ LeetCode）上狂刷题，还炫耀自己刷了多少，但这样反而学不到东西。我建议你在刷题的过程中，把问题拆解、解题分析、得出结论、举一反三，每一个环节都要想的清清楚楚，这样才是高效的刷题方式。

第一份力扣算法刷题宝典（标星60k）

 

目录

 

 

 

 

这份算法刷题宝典大概有1400+题目，为了不影响大家的阅读体验，这里就不一一例举出来了完整版的笔记在文末，有需要的朋友可以自取

算法专题

Backtracking

 

  • 排列问题Permutations。第46题，第47题。第60题，第526题，第996题。
  • 组合问题Combination。第39题，第40题，第77题，第216题。
  • 排列和组合杂交问题。第1079题。
  • N皇后终极解法(=进制解法)。第51题，第52题。
  • 数独问题。第37题。
  • 四个方向搜索。第79题，第212题，第980题。
  • 子集合问题。第78题，第90题。
  • Trie。第208题，第211题。
  • BFS优化。第126题，第127题。
  • DFS模板。(只是一个例子，不对应任何题)

 

 

Bit Manipulation

 

  • 异或的特性。第136题，第268题，第389题，第421题，

 

 

Linked List

 

  • 巧妙的构造虚拟头结点。可以使遍历处理逻辑更加统一。
  • 灵活使用递归。构造递归条件，使用递归可以巧妙的解题。不过需要注意有些题目不能使用递归，因为递归深度太深会导致超时和栈溢出。
  • 链表区间逆序。第92题。
  • 链表寻找中间节点。第876题。链表寻找倒数第n个节点。第19题。只需要-次遍历就可以得到答案。
  • 合并K个有序链表。第21题，第23题。
  • 链表归类。第86题，第328题。
  • 链表排序，时间复杂度要求O(n * logn),空间复杂度0(1)。只有一种做法，归并排序，至顶向下归并。第148题。
  • 判断链表是否存在环，如果有环，输出环的交叉点的下标;判断2个链表是否有交叉点，如果有交叉点，输出交叉点。第141题，第142题，第160题。

Segment Tree

 

  • 线段数的经典数组实现写法。将合并两个节点pushUp逻辑抽象出来了，可以实现任意操作(常见的操作有:加法，取max, min等等)。第218题，第303题，第307题，第699题。
  • 计数线段树的经典写法。第315题，第327题，第493题。
  • 线段树的树的实现写法。第715题，第732题。
  • 区间懒惰更新。第218题，第699题。
  • 离散化。离散化需要注意一个特殊情况:假如三个区间为[1,10] [1,4] [6,10]，离散化后x[1]=1,x[2]=4,x[3]=6,x[4]=10。第一个区间为[1,4],第二个区间为[1,2],第三个区间为[3,4],这样一来，区间一=区间二+区间三，这和离散前的模型不符，离散前，很明显，区间一>区间二+区间三。正确的做法是:在相差大于1的数间加一个数，例如在上面1 46 10中间加5，即可x[1]=1,x[2]=4,x[3]=5,x[4]=6,x[5]=10。这样处理之后，区间一是1-5，区间二是1-2，区间三是4-5。
  • 灵活构建线段树。线段树节点可以存储多条信息，合并两个节点的pushUp操作也可以是多样的。第850题，第1157题。

Sliding Window

 

  • 双指针滑动窗口的经典写法。右指针不断往右移，移动到不能往右移动为止(具体条件根据题目而定)。当右指针到最右边以后，开始挪动左指针，释放窗口左边界。第3题，第76题，第209题，第424题，第438题，第567题，第713题，第763题，第845题，第881题，第904题，第978题，第992题，第1004题，第1040题，第1052题。

Sort

 

  • 深刻的理解多路快排。第75题。
  • 链表的排序，插入排序(第147题)和归并排序(第148题)
  • 桶排序和基数排序。第164题。
  • "摆动排序"。第324题。
  • 两两不相邻的排序。第767题，第1054题。
  • "饼子排序"。第969题。

 

Union Find

 

  • 灵活使用并查集的思想，熟练掌握并查集的模板，模板中有两种并查集的实现方式，-种是路径压缩+秩优化的版本，另外一种是计算每个集合中元素的个数+最大集合元素个数的版本，这两种版本都有各自使用的地方。能使用第一类并查集模板的题目有:第128题，第130题，第547题，第684题，第721题，第765题，第778题，第839题，第924题，第928题，第947题，第952题，第959题，第990题。能使用第二类并查集模板的题目有:第803题，第952题。第803题秩优化和统计集合个数这些地方会卡时间，如果不优化，会TLE。
  • 并查集是一种思想，有些题需要灵活使用这种思想，而不是死套模板，如第399题，这一题是stringUnionFind,利用并查集思想实现的。这里每个节点是基于字符串和map的，而不是单纯的用int节点编号实现的。
  • 有些题死套模板反而做不出来，比如第685题，这一题不能路径压缩和秩优化，因为题目中涉及到有向图，需要知道节点的前驱节点，如果路径压缩了，这一题就没法做了。这一题不需要路径压缩和秩优化。
  • 灵活的抽象题目给的信息，将给定的信息合理的编号，使用并查集解题，并用map降低时间复杂度，如第721题，第959题。
  • 关于地图，砖块，网格的题目，可以新建一个特殊节点，将四周边缘的砖块或者网格都union()到这个特殊节点上。第130题，第803题。
  • 能用并查集的题目，一般也可以用DFS和BFS解答，只不过时间复杂度会高一点。

 

 

Leetcode题解

4. Median of Two Sorted Arrays

 

 

 

17. Letter Combinations of a Phone Num ber

 

 

51. N-Queens

 

 

84. Largest Rectangle in Histogram

 

 

114. Flatten Binary Tree to Linked List

 

 

 

 

199. Binary Tree Right Side View

 

 

237. Delete Node in a Linked List

 

 

463. lsland Perimeter

 

 

500. Keyboard Row

 

 

1105. Filling, Bookcase Shelves

 

 

 

1145. Binary Tree Coloring Game

 

 

 

1302. Deepest Leaves Sum

第二份力扣算法刷题宝典（标星68k）

 

第一章、动态规划系列

 

 

背包问题之零钱兑换

 

 

经典动态规划问题:高楼扔鸡蛋(进阶)

 

 

贪心算法之区间调度问题

 

团灭LeetCode股票买卖问题

 

 

第二章、数据结构系列

 

二叉堆详解实现优先级队列

 

 

LRU算法详解

 

 

特殊数据结构:单调队列

 

 

 

队列实现栈|栈实现队列

 

 

第三章、算法思维系列

 

 

滑动窗口技巧

 

烧饼排序

 

 

 

字符串乘法

 

 

FloodFill算法详解及应用

 

 

第四章、高频面试系列

 

 

如何k个一组反转链表

 

随机算法之水塘抽样算法

 

 

Union-Find算法详解

 

-行代码就能解决的算法题

 

二分查找高效判定子序列

 

第五章、计算机技术

 

Linux的进程、线程、文件描述符是什么？

 

一文读懂session和cookie

 

 

密码算法的前世今生

 

由于内容涉及到的知识点实在太多，小编就不一一展示给大家了，这两份【力扣算法刷题宝典】文档分别为1121与666页，需要完整版的朋友，可以转发此文关注小编，添加小助理来获取！！

最后

我们刷算法就是为了面试，说白了，算法不过是手段，是套路，是策略，而不是最终目的。我们的最终目的是赚钱，是让我们自己以及我们的家庭过上更好的生活，所以熟练掌握工作中的常用工具，得心应手地做业务赚钱才是王道。希望读者不要舍本逐末，被各种培训机构对算法的鼓吹所迷惑，看我们的算法小抄足够你学算法了，更重要的是要多写代码，多做工程。