下一节:

  大厂学院 - 大厂算法和数据结构解析【百度云盘】

    • 算法和数据结构解析

      数组和字符串是最基本的数据结构，在很多编程语言中都有着十分相似的性质，而围绕着它们的算法面试题也是最多的。 很多时候，在分析字符串相关面试题的过程中，我们往往要针对字符串当中的每一个字符进行分析和处理，甚至有时候需要先把给定的字符串转换成字符数组之后再进行分析和处理，举个最简单的例子，让我们来翻转一个字符串吧。 一种比较快速和直观的方法就是我们用两个指针，一个指针指向字符串的第一个字符 a，另一个指针指向它的最后一个字符 m，然后互相交换，交换之后，两个指针向中央一步步地靠拢并相互交换字符，直到两个指针相遇。由于我们无法直接修改字符串里的字符，所以必须先把字符串变换为数组，然后再运用这个算法。 JVM Java中的内存泄漏
      Java工程师 2021版百度云盘 Java架构师-技术专家【百度网盘】 要掌握一种数据结构，就必须要懂得分析它的优点和缺点。

      • 数组的优点在于

        构建一个数组非常简单； 能让我们在 O(1) 的时间内根据数组的下标（index）查询某个元素。 而它的缺点在于： 构建时必须分配一段连续的空间； 查询某个元素是否存在时需要遍历整个数组，耗费 O(n) 的时间（其中，n 是元素的个数）； 删除和添加某个元素时，同样需要耗费 O(n) 的时间。 所以，当你在考虑是否应当采用数组去辅助算法时，请务必考虑它的优缺点，看看它的缺点是否会增加算法复杂度及空间复杂度。 例题分析 LeetCode第242题 Valid Anagram 判断两个字符串是否互为字谜？ 所谓字谜，也就是两个字符串中的相同字符的数量要对应相等。例如：s 等于 “anagram”，t 等于 “nagaram”, s 和 t 就互为字谜，因为它们都包含有三个字符 a，一个字符 g，一个字符m，一个字符 n，以及一个字符 r。而当 s 为“rat”，t 为“car”时，s 和 t 不互为字谜。 是一道经典的考题，怎么分析和处理呢？题目里有一个重要的前提：假设两个字符串只包含小写字母。我们都知道，小写字母一共只有 26 个，这意味着，我们可以利用两个个长度为26 的字符数组来统计每个字符串中小写字母出现的次数，然后再对比是否相等即可。 或者，我们也可以只利用一个长度为 26 的字符数组，将出现在字符串 s 里的字符个数加1，而出现在字符串 t 里的字符个数减 1，最后判断每个小写字母的个数是否都为 0 就可以了。 在这里，我们就不针对代码进行具体地剖析了，这道题是非常经典的考题，建议大家可以到LeetCode 上试试。
​

    • 02PART链表（LinkedList）

      链表的出现在某种程度上是为了避免数组的一大缺陷，即分配数组的时候需要开辟一段连续的内存空间，但鱼和熊掌不可兼得，链表也牺牲了数组的一些优点，链表不能通过下标进行快速查询。所以在考虑是否需要运用链表的时候，务必要想清楚你的算法是否需要经常进行查询和遍历。 总结一下链表的优点和缺点，优点如下： 链表能灵活地分配内存空间； 能在 O(1) 时间内删除或者添加元素，前提是该元素的前一个元素已知，当然也取决于是单链表还是双链表，在双链表中，如果已知该元素的后一个元素，同样可以在 O(1) 时间内删除或者添加该元素。 链表的缺点是： 查询第 k 个元素需要 O(k) 时间。 很显然，如果你要解决的问题里面需要很多快速的查询，链表可能并不适合。一般而言，如果你遇到的问题中，数据的元素个数不确定，而且需要经常进行数据的添加和删除，那么链表会比较合适，而如果数据元素大小确定，删除插入的操作并不多，那么数组可能更适合。 在链表的解题方法中，最经典的无外乎以下几种： 利用快慢指针（有时候需要用到三个指针）； 例如，链表的翻转，寻找倒数第 k 个元素，或者寻找链表中间位置的元素，判断链表是否有环等。 构建一个虚假的链表头； 这个方法一般用在要返回新的链表的题目中，例如，给定两个排好序的链表，要求将它们整合在一起并排好序，又比如，将一个链表中的奇数和偶数按照原定的顺序分开后重新组合成一个新的链表，链表的头一半是奇数，后一半是偶数。 在这类问题里，如果不用一个虚假的链表头，那么在创建新链表的第一个元素时，我们需要判断链表的头指针是否为空，也就是要多写一条 if else 语句，比较简洁的写法是创建一个空的链表头，直接往其后面添加元素即可，最后返回这个空的链表头的下一个节点即可。 另外，链表有单链表和双链表，它们是实现很多复杂数据结构的基础，在解决链表的题目时，我给的建议就是在纸上或者白板上画出节点之间的相互关系，然后画出修改的方法，这样可以有效地帮助你分析问题，凭空想象是比较困难的，而且，在面试的时候，如果你能把方法画在白板上，还能帮助面试官清楚地看到你的思路。 查看本节例题，详见300分钟搞定算法面试 300分钟搞定算法面试 - 资深软件工程师苏勇 - 拉勾教育x力扣（LeetCode） ​ kaiwu.lagou.com 03PART 栈（Stack） 栈是许多 LeetCode 中等难度偏上的题目里面经常需要用到的数据结构。掌握好它是十分必要的。 栈的最大特点就是后进先出（LIFO）。对于栈中的数据来说，所有操作都是在栈的顶部完成的，只可以查看栈顶部的数据，只能够向栈的顶部压入数据，也只能从栈的顶部弹出数据。 因此，我们可以利用一个单链表来实现栈的数据结构，而且，因为我们都只针对栈顶元素进行操作，所以借用单链表的头就能让所有栈的操作在 O(1) 的时间内完成。也许你可能会说，我可以用数组加指针的方式也能实现相似的效果，但是，一旦数组的长度发生了改变，哪怕只是在最后添加一个新的元素，时间复杂度不再是 O(1)，而且，空间复杂度也得不到优化。 围绕栈的算法面试题有很多，那么什么时候需要用到栈呢？基本的核心思想就是，当你在解决某个问题的时候，你只关心最近一次的操作，并且在操作完成了之后，你得向前查找到更前一次的操作。 例如，给你一串由左括号和右括号组成的字符串，让你判断这些括号的组成是否合法。方法就是我们可以利用一个栈，不断地往里压左括号，一旦遇上了一个右括号，我们就把栈顶的左括号弹出来，表示这是一个合法的组合，以此类推，直到最后判断栈里还有没有左括号剩余。 查看本节例题，详见300分钟搞定算法面试 300分钟搞定算法面试 - 资深软件工程师苏勇 - 拉勾教育x力扣（LeetCode） ​ kaiwu.lagou.com 04PART 队列（Queue） 和栈不同，队列的最大特点是先进先出（FIFO），就好像按顺序排队一样。对于队列的数据来说，我们只允许在队尾查看和添加数据，在队头查看和删除数据。 如何实现一个队列呢？可以借助双链表，双链表的头指针允许我们在队头查看和删除数据，而双链表的尾指针允许我们在队尾查看和添加数据。 那么我们在什么情况下需要利用队列来帮助解题呢？很直观的是，当我们需要按照一定的顺序来处理数据，而要处理的数据量在不断地变化时。 在算法面试题中，广度优先搜索（Breadth-First Search）是运用队列最多的地方，我们将在第 06 节详细介绍。 查看本节例题，详见300分钟搞定算法面试 300分钟搞定算法面试 - 资深软件工程师苏勇 - 拉勾教育x力扣（LeetCode） ​ kaiwu.lagou.com 05PART 双端队列（Deque） 双端队列和普通队列最大的不同在于，双端队列允许我们在队列的头尾两端都能在 O(1) 的时间内进行数据的查看、添加和删除。 与队列相似，我们可以利用一个双链表实现双端队列。双端队列最常用的地方就是实现一个长度动态变化的窗口或者连续区间，而动态窗口这种数据结构在很多题目里都有运用。下面让我们通过一道经典的例题来分析它的用法。 查看本节例题，详见300分钟搞定算法面试 300分钟搞定算法面试 - 资深软件工程师苏勇 - 拉勾教育x力扣（LeetCode） ​ kaiwu.lagou.com 06PART树（Tree） 树的结构十分直观，而树的很多概念定义都有一个相同的特点：递归，也就是说，一棵树要满足某种性质，往往要求每个节点都必须满足。例如，在定义一棵二叉搜索树时，每个节点也都必须是一棵二叉搜索树。 正因为树有这样的性质，大部分关于树的面试题都与递归有关，换句话说，面试官希望通过一道关于树的问题来考察你对于递归算法掌握的熟练程度。在面试中常考的树的形状有：普通二叉树、平衡二叉树、完全二叉树、二叉搜索树、四叉树（Quadtree）、多叉树（N-ary Tree）。 对于一些特殊的树，例如红黑树（Red-Black Tree）、自平衡二叉搜索树（AVL Tree），大家不必花费太多时间去准备，一般在面试中不会被问到，除非你所涉及的研究领域跟它们相关或者你十分感兴趣。 关于树的考题，无非就是要考查树的遍历及序列化（serialization)。树的基本遍历有三种： 前序遍历（Preorder Traversal） 中序遍历（Inorder Traversal） 后序遍历（Postorder Traversal）。 在这里就不一一详细介绍了，掌握好这三种遍历的递归写法和非递归写法是非常重要的，同时，懂得分析各种写法的时间复杂度和空间复杂度同样重要。 无论你是前端工程师，还是后端工程师，在准备面试时，树这个数据结构可以说是最应该花时间学习的。掌握好树，能证明你对递归有很好的认识，能帮助你学习图论（关于图论，我们将在下一节课一起讨论）。另外，树的许多性质都是面试的热门考点，尤其是二叉搜索树（BST）。
下一节: