学习算法先看算法书还是先刷题？ |
您所在的位置：网站首页 › 算法导论适合什么水平的人看书 › 学习算法先看算法书还是先刷题？ |
学习算法先看算法书还是先刷题？
|
刚上大学的时候傻乎乎的，直接拿着算法书就去啃，最后打开 Leetcode，Two Sum都卡了好久，刷了大半年也不见什么效果。 一直在刷了忘、、忘了刷....死循环。 直到后来，我才知道算法导论这些书并不适合一开始就去硬啃，题也不是直接上来一道道傻乎乎的去刷，要讲究方法的。 其它好多回答都在一味的让答主去看书刷题，简直是误导非科班的同学！那不是坑人吗？刷题不是目的！！刷题不是目的！！刷题不是目的！！重要的是通过刷题掌握数据结构与算法，所有我的建议是： 先掌握一门语言，掌握到什么程度呢？你熟悉这个语言的常用标准库，比如如何输入、输出，set、map、list、vector用法，然后自己能完成几百行的程序就可以了！再系统的学习数据结构与算法算法的重要性真的不言而喻！现在大厂面试必考算法，算法不过关的话基本和大厂无缘了，在这里也送大家一本帮助我拿到BAT 等一线大厂 offer 的算法笔记，是一位阿里大神写的，对于算法薄弱或者需要提高的同学都十分受用，算法一定是计算机学习的重中之重： BAT面试官编写的leetcode刷题笔记，看完秒杀80%的题目 在校同学算法刷题的话可以去牛客网，上面很多针对国内互联网大厂的题库Top100，还有各种分类专项刷题，基本上把上面面试高频题刷了，技术面试算法题这块就算比较稳了：  这些数据结构与算法是必须掌握的： 八大排序：冒泡、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序、桶排序、基数排序暴力枚举法图、树、线性表分治法递归动态规划贪心后面两个动态规划和贪心可以先了解，后面刷题的时候再去强化！我大学的时候刷了很多题，尤其是校招前那段时间，刷遍了Leetcode 常见的题型，大概刷了近六百来道：  不知道多少人刷 Leetcode 永远停在了 Two Sum，到现在我才明白力扣（LeetCode）刷题顺序真的很重要！！！不然的话，对于小白可能会有比较强烈的挫败感！ LeetCode题目实在太多了，从最初几百道到现在上千道，我们没有必要全刷，题永远是刷不完的，但是这些解题所需要的知识其实是变化不大的。 所以在刷题的时候一定要刷经典题，要举一反三，从一类题抽象出共通的解法，才能以不变应万变，这才是刷题的本质，而不是单单为了刷题而刷题。接下来，手把手教大家如何正确打开 Leetcode！全程干货，注意收藏点赞（双击屏幕~~）哈（适合算法一般的同学，ACM大佬赶紧退散）刷题最重要的是选出典型的题目，分门别类的刷，以下8个门类是面试中最常考的算法与数据结构知识点。排序类（Sort）： 基础知识：快速排序（Quick Sort）， 归并排序（Merge Sort）的原理与代码实现。需要能讲明白代码中每一行的目的。快速排序时间复杂度平均状态下O（NlogN），空间复杂度O（1），归并排序最坏情况下时间复杂度O（NlogN），空间复杂度O（N）入门题目：Leetcode 148. Sort ListLeetcode 56. Merge Intervals进阶题目：Leetcode 179. Largest NumberLeetcode 75. Sort ColorsLeetcode 215. Kth Largest ElementLeetcode 4. Median of Two Sorted Arrays注意：后两题是与快速排序非常相似的快速选择（Quick Select）算法，面试中很常考链表类（Linked List）： 基础知识：链表如何实现，如何遍历链表。链表可以保证头部尾部插入删除操作都是O（1），查找任意元素位置O（N）基础题目：Leetcode 206. Reverse Linked ListLeetcode 876. Middle of the Linked List注意：快慢指针和链表反转几乎是所有链表类问题的基础，尤其是反转链表，代码很短，建议直接背熟。 进阶题目:Leetcode 160. Intersection of Two Linked ListsLeetcode 141. Linked List Cycle (Linked List Cycle II)Leetcode 92. Reverse Linked List IILeetcode 328. Odd Even Linked List堆（Heap or Priority Queue）、栈（Stack）、队列（Queue）、哈希表类（Hashmap、Hashset）： 基础知识：各个数据结构的基本原理，增删查改复杂度。Queue题目：Leetcode 225. Implement Stack using QueuesLeetcode 346. Moving Average from Data StreamLeetcode 281. Zigzag IteratorLeetcode 1429. First Unique NumberLeetcode 54. Spiral MatrixLeetcode 362. Design Hit CounterStack题目：Leetcode 232. Implement Queue using StacksLeetcode 150. Evaluate Reverse Polish NotationLeetcode 224. Basic Calculator II (I, II, III, IV)Leetcode 20. Valid ParenthesesLeetcode 1472. Design Browser HistoryLeetcode 1209. Remove All Adjacent Duplicates in String IILeetcode 1249. Minimum Remove to Make Valid ParenthesesLeetcode 735. Asteroid CollisionHashmap/ Hashset题目：Leetcode 1. Two SumLeetcode 146. LRU Cache (Python中可以使用OrderedDict来代替)Leetcode 128. Longest Consecutive SequenceLeetcode 73. Set Matrix ZeroesLeetcode 380. Insert Delete GetRandom O(1)Leetcode 49. Group AnagramsLeetcode 350. Intersection of Two Arrays IILeetcode 299. Bulls and CowsLeetcode 348 Design Tic-Tac-ToeHeap／Priority Queue题目：Leetcode 973. K Closest PointsLeetcode 347. Top k Largest ElementsLeetcode 23. Merge K Sorted ListsLeetcode 264. Ugly Number IILeetcode 1086. High FiveLeetcode 68. Merge Sorted ArraysLeetcode 692. Top K Frequent WordsLeetcode 378. Kth Smallest Element in a Sorted MatrixLeetcode 295. Find Median from Data StreamLeetcode 767. Reorganize StringLeetcode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to LimitLeetcode 895. Maximum Frequency Stack二分法（Binary Search）： 基础知识：二分法是用来解法基本模板，时间复杂度logN；常见的二分法题目可以分为两大类，显式与隐式，即是否能从字面上一眼看出二分法的特点：要查找的数据是否可以分为两部分，前半部分为X，后半部分为O显式二分法：Leetcode 34. Find First and Last Position of Element in Sorted ArrayLeetcode 33. Search in Rotated Sorted ArrayLeetcode 1095. Find in Mountain ArrayLeetcode 162. Find Peak ElementLeetcode 278. First Bad VersionLeetcode 74. Search a 2D MatrixLeetcode 240. Search a 2D Matrix II隐式二分法：Leetcode 69. Sqrt(x)Leetcode 540. Single Element in a Sorted ArrayLeetcode 644. Maximum Average Subarray IILeetcode 528. Random Pick with WeightLeetcode 1300. Sum of Mutated Array Closest to TargetLeetcode 1060. Missing Element in Sorted Array双指针（2 Pointer）： 基础知识：常见双指针算法分为三类，同向（即两个指针都相同一个方向移动），背向（两个指针从相同或者相邻的位置出发，背向移动直到其中一根指针到达边界为止），相向（两个指针从两边出发一起向中间移动直到两个指针相遇）背向双指针：(基本上全是回文串的题)Leetcode 409. Longest PalindromeLeetcode 125. Valid PalindromeLeetcode 5. Longest Palindromic Substring相向双指针：(以two sum为基础的一系列题)Leetcode 1. Two Sum (这里使用的是先排序的双指针算法，不同于hashmap做法)Leetcode 167. Two Sum II - Input array is sortedLeetcode 15. 3SumLeetcode 16. 3Sum ClosestLeetcode 18. 4SumLeetcode 454. 4Sum IILeetcode 277. Find the Celebrity同向双指针：（个人觉得最难的一类题）Leetcode 283. Move ZeroesLeetcode 26. Remove Duplicate Numbers in ArrayLeetcode 395. Longest Substring with At Least K Repeating CharactersLeetcode 340. Longest Substring with At Most K Distinct CharactersLeetcode 76. Minimum Window SubstringLeetcode 3. Longest Substring Without Repeating Characters宽度优先搜索（BFS）：面试中与DFS都为几乎必考的题目 基础知识：常见的BFS用来解决什么问题？(1) 简单图（有向无向皆可）的最短路径长度（2）拓扑排序 （3） 遍历一个图（或者树）BFS基本模板（需要记录层数或者不需要记录层数）多数情况下时间复杂度空间复杂度都是O（N+M），N为节点个数，M为边的个数基于树的BFS：不需要专门一个set来记录访问过的节点Leetcode 102 Binary Tree Level Order TraversalLeetcode 103 Binary Tree Zigzag Level Order TraversalLeetcode 297 Serialize and Deserialize Binary Tree （很好的BFS和双指针结合的题）Leetcode 314 Binary Tree Vertical Order Traversal基于图的BFS：（一般需要一个set来记录访问过的节点）Leetcode 200. Number of IslandsLeetcode 133. Clone GraphLeetcode 127. Word LadderLeetcode 490. The MazeLeetcode 323. Connected Component in Undirected GraphLeetcode 130. Surrounded RegionsLeetcode 752. Open the LockLeetcode 815. Bus RoutesLeetcode 1091. Shortest Path in Binary MatrixLeetcode 542. 01 MatrixLeetcode 1293. Shortest Path in a Grid with Obstacles Elimination拓扑排序：（https://zh.wikipedia.org/wiki/%E6%8B%93%E6%92%B2%E6%8E%92%E5%BA%8F）Leetcode 207 Course Schedule （I, II）Leetcode 444 Sequence ReconstructionLeetcode 269 Alien Dictionary深度优先搜索（DFS）：面试中与BFS都为几乎必考的题目 基础知识：常见的DFS用来解决什么问题？(1) 图中（有向无向皆可）的符合某种特征（比如最长）的路径以及长度（2）排列组合（3） 遍历一个图（或者树）（4）找出图或者树中符合题目要求的全部方案DFS基本模板（需要记录路径，不需要返回值 and 不需要记录路径，但需要记录某些特征的返回值）除了遍历之外多数情况下时间复杂度是指数级别，一般是O(方案数×找到每个方案的时间复杂度)递归题目都可以用非递归迭代的方法写，但一般实现起来非常麻烦基于树的DFS：需要记住递归写前序中序后序遍历二叉树的模板Leetcode 543 Diameter of Binary TreeLeetcode 226 Invert Binary TreeLeetcode 124 Binary Tree Maximum Path SumLeetcode 236 Lowest Common Ancestor of a Binary TreeLeetcode 101 Symmetric TreeLeetcode 105 Construct Binary Tree from Preorder and Inorder TraversalLeetcode 104 Maximum Depth of Binary TreeLeetcode 951 Flip Equivalent Binary TreesLeetcode 987 Vertical Order Traversal of a Binary TreeLeetcode 1485 Clone Binary Tree With Random PointerLeetcode 572 Subtree of Another TreeLeetcode 863 All Nodes Distance K in Binary Tree二叉搜索树（BST）：BST特征：中序遍历为单调递增的二叉树，换句话说，根节点的值比左子树任意节点值都大，比右子树任意节点值都小，增删查改均为O（h）复杂度，h为树的高度；注意不是所有的BST题目都需要递归，有的题目只需要while循环即可Leetcode 230 Kth Smallest element in a BSTLeetcode 98 Validate Binary Search TreeLeetcode 270 Cloest Binary Search Tree ValueLeetcode 235 Lowest Common Ancestor of a Binary Search TreeLeetcode 669 Trim a Binary Search TreeLeetcode 700 Search Range in Binary Search TreeLeetcode 108 Convert Sorted Array to Binary Search TreeLeetcode 333 Largest BST SubtreeLeetcode 510 Inorder Successor in BST II基于图的DFS: 和BFS一样一般需要一个set来记录访问过的节点，避免重复访问造成死循环Leetcode 341 Flatten Nested List IteratorLeetcode 394 Decode StringLeetcode 51 N-QueensLeetcode 291 Word Pattern II (I为简单的Hashmap题)Leetcode 126 Word Ladder II （I为BFS题目）Leetcode 1110 Delete Nodes And Return ForestLeetcode 93 Restore IP AddressesLeetcode 22 Generate ParenthesesLeetcode 37 Sodoku SolverLeetcode 301 Remove Invalid ParenthesesLeetcode 212 Word Search II （I, II）Leetcode 1087 Brace ExpansionLeetcode 399 Evaluate DivisionLeetcode 1274 Number of Ships in a RectangleLeetcode 1376 Time Needed to Inform All EmployeesLeetcode 694 Number of Distinct IslandsLeetcode 586 Score of Parentheses基于排列组合的DFS: 其实与图类DFS方法一致，但是排列组合的特征更明显Leetcode 17 Letter Combinations of a Phone NumberLeetcode 39 Combination Sum （I, II, III, IV）Leetcode 90 Subsets II （重点在于如何去重）Leetcode 47 Permutation IILeetcode 77 CombinationsLeetcode 526 Beautiful Arrangement记忆化搜索（DFS + Memoization Search）：算是动态规划的一种，递归每次返回时同时记录下已访问过的节点特征，避免重复访问同一个节点，可以有效的把指数级别的DFS时间复杂度降为多项式级别Leetcode 139 Word Break IILeetcode 131 Palindrome PartitioningLeetcode 72 Edit DistanceLeetcode 377 Combination Sum IVLeetcode 1335 Minimum Difficulty of a Job Schedule前缀和（Prefix Sum） 基础知识：前缀和本质上是在一个list当中，用O（N）的时间提前算好从第0个数字到第i个数字之和，在后续使用中可以在O（1）时间内计算出第i到第j个数字之和，一般很少单独作为一道题出现，而是很多题目中的用到的一个小技巧常见题目：Leetcode 53 Maximum SubarrayLeetcode 1423 Maximum Points You Can Obtain from CardsLeetcode 1031 Maximum Sum of Two Non-Overlapping SubarraysLeetcode 523 Continuous Subarray Sum以上内容皆为面试中高频的知识点，以下知识点和题目在面试中属于中等频率（大概面10道题会遇到一次），时间不足的情况下，请以准备上面的知识点为主。并查集（Union Find）：把两个或者多个集合合并为一个集合 基础知识：如果数据不是实时变化，本类问题可以用BFS或者DFS的方式遍历，如果数据实时变化（data stream）则并查集每次的时间复杂度可以视为O（1）；需要牢记合并与查找两个操作的模板常见题目：Leetcode 721 Accounts MergeLeetcode 547 Number of ProvincesLeetcode 737 Sentence Similarity IILeetcode 434 Number of Islands II字典树（Trie） 基础知识：（https://zh.wikipedia.org/wiki/Trie）；多数情况下可以通过用一个set来记录所有单词的prefix来替代，时间复杂度不变，但空间复杂度略高常见题目：Leetcode 208 Implement Trie (Prefix Tree)Leetcode 211 Design Add and Search Words Data StructureLeetcode 1268 Search Suggestions SystemLeetcode 79 Word Search单调栈与单调队列（Monotone Stack／Queue） 基础知识：单调栈一般用于解决数组中找出每个数字的第一个大于／小于该数字的位置或者数字；单调队列只见过一道题需要使用；不论单调栈还是单调队列，单调的意思是保留在栈或者队列中的数字是单调递增或者单调递减的常见题目：Leetcode 85 Maximum RectangleLeetcode 84 Largest Rectangle in HistogramLeetcode 739 Daily TemperaturesLeetcode 901 Online Stock SpanLeetcode 503 Next Greater Element IILeetcode 239 Sliding Window Maximum （唯一的单调队列题）扫描线算法（Sweep Line） 基础知识：一个很巧妙的解决时间安排冲突的算法，本身比较容易些也很容易理解常见题目：Leetcode 253 Meeting Room II（Meeting Room I也可以使用）Leetcode 218 The Skyline ProblemLeetcode 759 Employee Free TimeTreeMap 基础知识：基于红黑树（平衡二叉搜索树）的一种树状 hashmap，增删查改、找求大最小均为logN复杂度，Python当中可以使用SortedDict替代常见题目：Leetcode 729 My Calendar ILeetcode 981 Time Based Key-Value StoreLeetcode 846 Hand of StraightsLeetcode 826 Most Profit Assigning Work动态规划（Dynamic Programming） 基础知识：这里指的是用for循环方式的动态规划，非Memoization Search方式。DP可以在多项式时间复杂度内解决DFS需要指数级别的问题。常见的题目包括找最大最小，找可行性，找总方案数等，一般结果是一个Integer或者Boolean。动态规划有很多分支，暂时还没想好怎么去写这部分，后面想好了再具体写吧。常见题目：Leetcode 674 Longest Continuous Increasing SubsequenceLeetcode 62 Unique Paths IILeetcode 70 Climbing StairsLeetcode 64 Minimum Path SumLeetcode 368 Largest Divisible SubsetLeetcode 300 Longest Increasing SubsequenceLeetcode 354 Russian Doll EnvelopesLeetcode 256 Paint HouseLeetcode 121 Best Time to Buy and Sell StockLeetcode 55 Jump GameLeetcode 45 Jump Game IILeetcode 403 Frog JumpLeetcode 132 Palindrome Partitioning IILeetcode 312 Burst BalloonsLeetcode 1143 Longest Common SubsequenceLeetcode 115 Distinct SubsequencesLeetcode 72 Edit DistanceLeetcode 91 Decode WaysLeetcode 639 Decode Ways IILeetcode 712 Minimum ASCII Delete Sum for Two StringsLeetcode 221 Maximal SquareLeetcode 198 House RobberLeetcode 213 House Robber IILeetcode 87 Scramble StringLeetcode 1062 Longest Repeating SubstringLeetcode 1140 Stone Game IILeetcode 322 Coin ChangeLeetcode 518 Coin Change IILeetcode 97 Interleaving String这是TimothyL大佬总结的，原文：https://zhuanlan.zhihu.com/p/349940945 来源：知乎说完了高频题目，再来说下刷题前如何学习基础的数据结构与算法一、刷题前首先，大家要明白一个点，那就是我们刷题不是为了去刷题，刷题的目的是为了巩固数据结构与算法，那么也就是说刷题前我们就要学完一遍常见的数据结构与算法，不然你去巩固啥呢？是吧 在这里我就要强调数据结构如何学习了。 首先要明白，不管是数组、树、堆还是啥，最终对应在内存中的存储方式只有两种: 数组(顺序存储)链表(链式存储)数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所 以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过 去，时间复杂度 O(N);而且你如果想在数组中间进行插入和删除，每次必 须搬移后面的所有数据以保持连续，时间复杂度 O(N)。链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组 的扩容问题;如果知道某一元素的前驱和后驱，操作指针即可删除该元素或 者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根 据一个索引算出对应元素的地址，所以不能随机访问;而且由于每个元素必 须存储指向前后元素位置的指针，会消耗相对更多的储存空间。 那么基于这两种最基本的数据结构我们就可以构建： 线性表：队列（FIFO）、栈：树：二叉查找树、AVL树、伸展树、红黑树、哈弗曼树等堆：二叉堆、左倾堆、二项堆：图：有向图、无向图常见算法： 基于图的算法：深度优先DFS、广度优先BFS、拓扑排序、Kruskal算法、Prim算法、Dijkstra算法等八大排序：冒泡、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序、桶排序、基数排序暴力枚举法分治法递归动态规划贪心....推荐大家学习这些数据结构和算法可以看看《算法4》这本书，这本书比较适合初学者，算法讲解也比较清晰易懂且全面。这本书看起来挺厚的，但是前面几十⻚是教你 Java 的;每章后面还有习 题，占了不少⻚数;每章还有一些数学证明，这些都可以忽略。这样算下 来，剩下的就是基础知识和疑难解答之类的内容，含金量很高，把这些基础 知识动手实践一遍，真的就可以达到不错的水平了。  这本书在豆瓣的评价也很高，一个是因为讲解详细，还有大量配图，另一个原因就是书中把一些算法和现实生活中的使用场景联系起来，你不仅知道某个算法怎么实现，也知道它大概能运用到什么场景。这些经典的算法学习书，我都汇总了，有需要的同学可以看下这里下载：  书单： 或者去这个 Github 开源仓库，基本包含了常见的 CS 编程学习书籍，可以 star 一下，需要的时候直接去上面找书： 二、刷题，起航！ 刷题之前，我们需要知道怎么去刷，按什么顺序刷题，应该根据需求来： 如果是为了拿大厂offer，那么在LeetCode上刷够大概 200 道经典题就差不多了，注意不是重复刷简单题，是分门别类的刷，具体的下文会讲到；如果是想长期系统的学习算法，提升自己的学科素养，建议按类型刷题，分门别类的学习、总结，有针对性的提升；下面列一些典型的题型吧：1. 线性表：1.1 Remove Duplicates from Sorted Array1.2 Remove Duplicates from Sorted Array II1.3 Search in Rotated Sorted Array II1.4 Median of Two Sorted Arrays1.5 Longest Consecutive Sequence1.6 Two Sum1.7 Valid Sudoku1.8 Trapping Rain Water1.9 Swap Nodes in Pairs1.10 Reverse Nodes in k-Group2. 字符串2.1 Valid Palindrome2.2 Implement strStr()3.3 String to Integer (atoi)3.4 Add Binary3.5 Longest Palindromic Substring3.6 Regular Expression Matching3.7 Wildcard Matching3.8 Longest Common Prefix3.9 Valid Number3.10 Integer to Roman 3. 树、二叉树3.1 Binary Tree Preorder Traversal3.2 Binary Tree Inorder Traversal3.3 Binary Tree Postorder Traversal3.4 Binary Tree Level Order Traversal II3.5 Binary Tree Zigzag Level Order Traversal3.6 Construct Binary Tree from Preorder and Inorder Traversal3.7 Unique Binary Search Trees3.8 Validate Binary Search Tree3.9 Convert Sorted Array to Binary Search Tree 4. 排序4.1 Merge Sorted Array4.2 Merge Two Sorted Lists 4.3 Merge k Sorted Lists4.4 Insertion Sort List4.5 Sort List4.6 First Missing Positive 5. 暴力枚举5.1 Subsets5.1 Subsets II5.3 Permutations5.4 Letter Combinations of a Phone Number 6. 深度优先搜索6.1 Palindrome Partitioning6.2 Unique Paths6.3 Unique Paths II 7. 回溯 8. 深搜与递归的区别 9. 分治法 10. 贪心法10.1 Jump Game10.2 Best Time to Buy and Sell Stock10.3 Best Time to Buy and Sell Stock II10.4 Longest Substring Without Repeating Characters10.5 Container With Most Water 11. 动态规划11.1 Triangle11.2 Maximum Subarray11.3 Palindrome Partitioning II11.4 Maximal Rectangle11.5 Best Time to Buy and Sell Stock III11.6 Interleaving String........持续更新中....这些都是我分类节选的一些题，在这里推荐一个谷歌大佬的刷题笔记,每一道题的题解都写得非常清楚.去年校招前，我也被刷题效率低下的问题所困扰，直到看完这本刷题笔记，按照笔记上分类的去刷，每一个章节都先讲解框架思维，然后挑选非常典型的十几道LeetCode题进行实战讲解：  大家可以去下载下这本刷题笔记： 另外，我复习过程中还看了阿里大佬的笔记：  在这里一并分享给大家： |
【本文地址】
今日新闻 |
推荐新闻 |