前言 数据结构和算法可以让程序员脱胎换骨,刷算法题可以帮助我们通过面试和笔试,找到梦寐以求的工作,进入一线大厂或者拿高薪。怎么刷题呢?LeetCode上有2000多道题目,难道要全部刷完? 国内的一线大厂在面试和笔试的时候会考察什么样的题目?于是提莫抽取8个公司Top20的高频题目做了一个合并统计: 内容略长,选择直接查看面试题?还是不要了,耐心看完扒~ 发现存在着很大的重复性,有些题目甚至所有的公司都有考察,比如LeetCode-206.反转链表。同时这些题目所属的类别包括了基础的数组、链表、排序,高阶的位运算、动态规划也有考察。从题目的难度来说,中等难度占了一半以上,困难的只有十分之一不到。 这就提示我们,刷题要刷,但不是盲目的刷,要有针对性,重点的去刷,所以除了上面的大厂Top20的高频题,还从LeetCode《LeetCode 热题 HOT 100》中精选了题目,一起对这些题目进行讲解。 但是请注意,在讲解这些题目时,默认大家已经具备了Java的基础知识,所以数组、ArrayList、链表LinkedList、HashMap等常见常用的数据结构不再解释它们的具体含义、区别和用法,如果需要会在解题过程中直接使用。 但是对于位运算、动态规划、并查集等不是特别常见的数据结构和算法,则会解释具体的概念和含义后,再进入题目的讲解。 > 但是在正式进入学习之前,我们首先要知道为什么我们要学习数据结构和算法,怎么正确的学习数据结构和算法,怎么正确的刷题。为什么要学习数据结构和算法? 首先,程序员这个群体也是有金字塔结构的。如果连基本的算法和数据结构都不会,基本上就比较底层,底层就意味着低薪酬。付出同样时长的脑力劳动,赚得就会比别人少。 其次,作为团队里的一员,很多时候不光要做好自己的本职工作,也要和其他团队进行技术问题上的沟通,如果没有扎实的算法和数据结构基础,很难及时发现问题并提出独到的见解。 另外,技术栈本身每天都在变化,同时也会随着不同行业不同公司改变。能否快速适应新技术和新环境就显得尤为重要。这就要求你必须具有以不变应万变的的计算机思维、算法思维和逻辑思维能力。 所以数据结构与算法能力的考核在以 BAT 为代表的国内大厂,乃至硅谷大厂等硅谷高科技公司的面试里占了相当大的比重。总结起来,考察的原因有: - 算法能力能够准确辨别一个程序员的技术功底是否扎实; - 算法能力是发掘程序员的学习能力与成长潜力的关键手段; - 算法能力能够协助判断程序员在面对新问题时,分析并解决问题的能力,通过算法问题能够看出候选人的解题思路,以及能将思路迅速地变成代码的能力; - 算法能力是设计一个高性能系统、性能优化的必备基础。怎么样学习数据结构和算法 学习 范围 数据结构和算法?很多人就会联想到"数学",觉得算法会涉及到很多深奥的数学知识。数据结构和算法课程确实会涉及一些数学方面的推理、证明,尤其是在分析某个算法的时间、空间复杂度的时候,但是这个不需要担心。 如果你是算法工程师或者去学习《算法导论》,里面有非常复杂的数学证明和推理,确实需要很好的数学功底。但是对于我们大多数程序员来说,特别是学习本堂课的同学来说,只要有高中数学水平,就完全可以没有任何问题。 数据结构和算法包含的内容很多,很多高级的数据结构与算法,比如二分图、最大流等,这些在我们平常的开发中很少会用到,也就没有必要投入精力去学习。 不管是应付面试还是工作需要,只要集中精力逐一攻克最常用的、最基础数据结构与算法主要包括: 数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie[traɪ] 树; 算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。 掌握了这些基础的数据结构和算法,再学更加复杂的数据结构和算法,就会比较容易了。 虽然校招算法会考的比社招多,但是考来考去,基本不考这种例如B树,B+树,KMP 的具体实现的,对于这些,我们只需要知道它的原理和应用即可。但是红黑树之类,在某些大厂面试中是有可能出现。、 学习方式 知识沉淀 知识需要沉淀,不要想试图一下子掌握所有。在学习的过程中,一定会碰到"拦路虎"。如果哪个知识点没有怎么学懂,不要着急,这是正常的。因为,想听一遍、看一遍就把所有知识掌握,这肯定是不可能的。学习知识的过程是反复迭代、不断沉淀的过程。 多练习 "边学边练"这一招非常有用,也就是要多动手,常用的数据结构和算法,用代码实现一遍,也要在专门的刷题网站,比如LeetCode上进行刷题。这些都是打好基本功,想要达到顶尖的水平,基本功非常重要。不管什么运动,基本功是区别业余和职业选手的根本,所以一个算法题只写一遍是绝对不够的。 必须要刻意练习,怎么样刻意练习? 具体的题目求解 首先对某个具体的题目求解来说,可以使用下面的解法: 1、读题,分析看清楚题目到底要你做什么? 2、多解,一个题目尽可能的想到几种解法,然后从方方面面去分析这几种解法的优劣,从中选择一个较好的解法。 3、代码实现。 4、运行测试用例,测试用例的选择上,除了一些正常的数据,还要有意识的构造一些边界数据来检测程序是否运行正常。 5步解题法 对刷题练习来说,可以使用5步解题法,任何一个题目至少需要做5遍。 刷题第一遍 ·5~10分钟:读题 思考 ·有思路,可以上手实现,没有思路怎么办?可以直接看解法,这个没有任何问题,但是注意因为一个题目可能有多种解法,比较解法优劣后,背诵、默写好的解法。有自己的思路,依然可以去看别人的解法,在比较解法优劣,找到差距后,背诵、默写。背诵、默写很重要,是你理解的基础。同时没有必要在一个题目上花费很多时间,比如一天、两天去琢磨一个题目的实现。 刷题第二遍 马上自己写,这就是不看别人的解法,自己动手写,写完后提交到LeetCode运行,依然要去看看自己的实现和别人解法的差距,并思考差距在什么地方,比如你的解法明明和别人的思路一样,但是速度却很不理想,就要看看为什么我的实现要慢,并且着手优化,争取要让你的解法领先80%的人,当然越高越好。 刷题第三遍 ·过了24小时后,再重复做题 刷题第四遍 过了一周:反复回来练习相同题目 刷题第五遍 面试前一周或半个月专门性进行恢复性训练。并且在面试前强烈推荐大家在纸上和黑板上练习写代码,这对书写清晰可读的代码是非常有帮助的。 刷题的目的 刷题不能为刷题而刷题,那是无效的努力,只会感动自己。刷题的目的是通过刷一个题搞清楚一类题目的解法并且建立正确的解题能力和技巧,每做一个题都要有自己的深入的思考和总结。否则就会陷入无效的"题海战术"而收效甚微。 面试 有了前面的刻意练习,面试中的算法题基本上就不是大问题了。为了提高算法面试通过率,还需要把自己的状态调整到最佳,包括和面试官交谈时的状态、是否能清晰地分析问题、如何把自己的思路完美地告诉给面试官,最后是书写代码的水平,也就是能否能流畅地写出可读性高的代码。 如果在面试过程中很紧张,一时半会想不到什么好解法好思路,怎么办?没有关系,我们不妨说出一种最差劲的解法。 要知道完全做不出来和做不出优秀的解法是不一样的。所以大家做题的过程不要忽略"暴力解法",而且暴力解法通常是好解法好思路的起点。另外"暴力解法"可以给我们缓冲的时间,通过和面试官的沟通,向面试官展示你的思考方式,思维能力,沟通能力,并在沟通的过程中一步步优化原来的解法。 这是因为:第一,无法在规定时间内完美地写出代码并不是世界末日,只要求职者对问题分析正确,把握了正确的思路,代码能清晰地看到输入和输出的逻辑、结构,最重要的是能迅速地将思路转变成部分代码,就能让大部分面试官满意。第二,在解决问题的过程中缺乏和面试官的交流,甚至对面试官的疑问不屑一顾,那又怎能让面试官放心跟他一起工作呢?所以面试者的沟通能力也是一个考察点。 刷题 - 算法时间复杂度分析 - 什么是递归 - (LeetCode-70) 爬楼梯 - (剑指Offer 10) 斐波那契数列 - (LeetCode-1)两数之和 - (LeetCode-88) 合并两个有序数组 - (LeetCode-283)移动零 - (LeetCode-448)找到所有数组中消失的数字 - (LeetCode-21)合并两个有序链表 - (LeetCode-83) 删除排序链表中的重复元素 - (LeetCode-141) 环形链表 - (LeetCode-142) 环形链表II - (LeetCode-160) 相交链表 - (LeetCode-206) 反转链表 - (LeetCode-234) 回文链表 - (LeetCode-876) 链表的中间结点 - 剑指Offer 22:链表中倒数第k个节点 - 什么是栈与队列 - (LeetCode-232) 用栈实现队列 - (LeetCode-394) 字符串解码 - 树的相关概念 - 二叉树的相关概念 - (LeetCode-94) 二叉树的中序遍历 - (LeetCode-144) 二叉树的前序遍历 - (LeetCode-145) 二叉树的后序遍历 - (LeetCode-101) 对称二叉树 - (LeetCode-104) 二叉树的最大深度 - (LeetCode-110) 平衡二叉树 - (LeetCode-226) 翻转二叉树 - 十大排序算法之冒泡排序 - 十大排序算法之选择排序 - 十大排序算法之插入排序 - 十大排序算法之快速排序 - 十大排序算法之希尔排序 - 十大排序算法之归并排序 - 十大排序算法之堆排序 - 十大排序算法之计数排序 - 十大排序算法之桶排序 - 十大排序算法之基数排序 - (LeetCode- 912) 排序数组和排序算法总结 - 二分查找和查找算法概论 - 二进制辨析和负数的补码表示 - 常见的位运算 - 位运算运用场景和优劣势 - 位运算常见简单面试题 - (LeetCode-136) 只出现一次的数字 - (LeetCode-338) 比特位计数 - (LeetCode-461) 汉明距离 - (LeetCode-20) 有效的括号 - (LeetCode-415) 字符串相加 - 字符串匹配之BF(Brute Force)算法 - 字符串匹配之BM(Boyer-Moore)算法 - 字符串匹配之KMP(Knuth-Morris-Pratt)算法 - 从游戏了解动态规划 - 从旅游安排继续了解动态规划 - 二维数组实现游戏背包 - 优化二维数组的实现 - 一维数组实现 - 动态规划的定义 - 通过(LeetCode-509)熟悉动态规划的解题步骤 - (LeetCode-53) 最大子序和 - (LeetCode-121) 买卖股票的最佳时机 - 什么样的问题适合用动态规划? - (LeetCode-470) 用 Rand7() 实现 Rand10()答案 由于写上答案篇幅内容过长,可能会影响可读性,大家就自行领取参考扒~ 关注我后私信"大厂"即可! 彦祖,都看到这了,点赞,收藏,叨叨一下扒~