数据结构和算法面试的终极指南🔥 为什么要读这个？如何阅读指南结论：

2025-05-26

数据结构和算法面试的终极指南🔥

为什么你应该读这个？

如何阅读指南

结论：

作者：Rahul Arora，Intervue创始人

--

为什么你应该读这个？

准备技术面试时，有无数个方向可供选择。本指南总结了我的经验，并指出了一个可以确保你获得成功且不会偏离正轨的方向。
它可以节省你的时间，因为你不必在网上查阅多个资源。

我根据自己在准备进入 Uber、谷歌、Flipkart、亚马逊、微软和 Facebook 等公司时的个人经历，整理了一份清单。
在为期两个月的时间里，我每天大约花 2 个小时进行准备，以下是总结。

--

如何阅读指南

每个部分包含两件事：

  • 关于可以应用于解决问题的技术的一些粗略笔记。
  • 每个部分都需要解答的问题。问题的多样性足以培养出一种自然的本能，能够解决这类公司提出的大多数问题。

每个问题都有一个 Github 链接，其中包含其解决方案和解释，以及解决问题的多种方法。

--

数组

数组

可以应用的方法（粗略记录）：

  • 排序后执行某些操作、哈希表、循环中的两个指针都是解决算法的常用操作。哈希表也可以用来存储和等。
  • 要找到所有组合，请使用嵌套 for 循环（最差的算法）
  • 另一种方法是停在一个元素上并遍历其所有前面的元素
  • 固定一个数字，并有两个指针，一个在开始，一个在结束，以进行某些操作
  • 如果任何方法不起作用或不满足要求，请考虑创建新数组。这些数组可以包含从左到右或从右到左的累积和，或者算法的核心部分，这可以简化计算。
  • 有时比较这些数组来找到算法
  • 累积和或乘积可以解决算法
  • 可以应用 XOR 运算来查看重复奇数次的数字，因为仅当有一个数字重复奇数次时，XOR 才会返回该数字
  • 如果要查找数组中的元素，且长度已知，则使用二分查找。查找时间约为 O(logn)。如果无法使用二分查找，则每次查找 k 个元素，以限制搜索范围。
  • 我们无法找到输入大小未知的事物的时间复杂度。
  • 如果某个数字像 0 和 1 的例子那样重复，那么对于某些操作，0 可以更改为 -1。
  • 要查找包含 1 到 n 个元素的数组中的重复项，请进行迭代。假设值为 3，则转到第三个索引并将值更改为负数。如果值已经为负数，则表示 3 重复了，依此类推，检查所有重复项。
  • 您还可以使用外部变量或通过某种计算将数组元素划分为相关组来解决算法
  • 对于有重复子问题的问题，尝试使用递归思考
  • 返回一个递归调用的函数最终将返回必须返回的基值
  • 有时，如果算法看起来很复杂，可以转到一种通用格式，其中结果假设为 N，并且通过从解决方案到问题来求解某个 x，然后尝试找出算法。（有关更多说明，请参阅问题 28.c）
  • 循环数组可用于实现队列。这里的增量不是简单地加 1，而是先加 1，然后取数组大小的模。像这样循环数组。更多信息，请参阅问题 2 中的堆栈和队列。
  • 对于涉及子阵列的问题：
    • 幼稚的方法
    • 有时可以维护另一个数据结构（可能是队列）来解决算法
    • 可以维护一个哈希表来解决算法
    • 可以维护多个变量来解决算法
    • 可以维护两个指针来解决算法
    • 卡巴内算法

问题

--

链表

链表

可应用的方法：

  • 使用多个变量来跟踪链接列表，并保持它们向前移动，以便可以在链接列表上执行各种操作
  • 如果您不希望函数返回某个值，只需将该值发送到变量的地址，方法是将变量的地址作为参数传递并访问它**
  • 维护不同节点地址的哈希表（第一个节点具有此地址，依此类推），以便稍后访问该值而无需遍历
  • 维护多个指针。指针可以根据需求以不同的速度移动。
  • 有时，链表在设计时可以带有标志，以使算法成为可能
  • 如果链表存在循环，并且两个指针以两倍于另一个的速度移动，它们会在循环内的某个点相遇。从链表的起始点到循环起始的第一个节点的距离，等于它们相遇点到第一个节点的距离。
  • 链表通常用于存储无法用 int 类型存储的大数，或者用于存储多项式。如果将数字存储在链表中，则必须自行执行相应的操作（例如加法、减法等等）。
  • 有时使用堆栈、队列或数组等通用数据结构来解决算法。
  • 尝试将链接列表的末尾连接到前面或形成循环来解决算法。
  • 要制作类似蛇梯棋的游戏，我们可以使用一个包含随机指针、下一个指针和数据的链表。每当出现梯子或蛇时，随机指针就会指向那里，否则它将为 NULL。
  • 当涉及多个对象（例如随机节点）时，考虑创建额外的连接（链接到新列表或旧列表），以便遍历或作为参考点。有时可以在两个节点中间添加新节点以维持连接，依此类推。
  • 在涉及分割或合并的程序中，始终将中间值作为 start+end/2，而不是减法，因为这样总能得到正确的值。减法可能无法给出正确的值，因为你不断地将数组拆分成更小的部分。

问题：

--

哈希

哈希图

可应用的方法：

  • 解答问题时，用 hashTable 的大小除以 value。保持 hashTable 的大小比需要存储的元素大小大 1。
  • 使用链接或线性探测解决
  • 堆、BBST-AVL 是一些流行的数据结构，也可以用于涉及哈希表的问题。
  • 二分查找法应用非常广泛。但只有在数组长度已知且已排序的情况下才适用。
  • 有时，扫描一次并搜索并保留额外的变量以供检查就可以完成工作。
  • 在哈希算法中，结构可以根据需求变化。它可以存储任何内容，从和到频率，再到指针。因此，请始终按照需求确定结构。
  • 对于哈希表，取现有元素数量的模。
  • 如果问题涉及使用递归构建树的单个数组，请确保选择正确的数组起点和终点（特别是数组被一次又一次分割的地方）

问题：

--

堆栈和队列

堆栈
队列

可应用的方法：

  • 对于每个实现或算法的堆栈和队列，其核心功能应该始终保持正确。例如，堆栈的出栈和入栈操作需要 O(1) 的时间复杂度。
  • 使用两个队列构建堆栈或反之，负担可以放在推送操作或弹出操作上。有负担的队列将负责入队和出队，以将其移动到其他堆栈或队列。更多信息，请参阅堆栈和队列问题 4。
  • 对于堆栈和队列中的问题，使用额外的堆栈/队列作为数据结构来实现一些算法
  • 您可以将每次推送和弹出操作的最小值或最大值存储在其他堆栈/队列或数据结构中，依此类推。例如，将目前的最小值存储在另一个堆栈中，这样每次弹出一个数字时，如果我们从另一个堆栈中弹出最小值，我们就能从位于另一个堆栈顶部的剩余元素中得到最小值。类似地，可以应用许多类似的操作。
  • 您还可以修改被推送到堆栈的数字，并通过执行一些计算来维护外部引用，以使算法发挥作用。（例如问题 5）。
  • 当需要为每个元素计算某些内容，但在迭代其他元素后计算会比较晚时，堆栈就非常有用。由于计算必须遵循顺序，因此可以将目前无法完成计算的元素压入堆栈。已完成计算的元素可以从堆栈中弹出（例如问题 6）。
  • 某些算法可能需要使用不同的数据结构来实现堆栈。例如，使用双向链表而非单向链表，或者使用单向链表而非数组等等。（问题 7）

问题：

--

堆

堆

可应用的方法：

  • 可以声明一个大堆，但堆操作中始终只能包含其中的一小部分。
  • 每当构建堆时，如果元素不遵循堆属性（最大值或最小值），就会发生交换等
  • 有时为了找到数组中的最大元素，可以对少数几个第一个元素进行最小堆，每次与剩余元素进行比较以消除最小元素。
  • 可以应用最小和最大堆的方法也可以使用 BST（取决于问题）
  • 有时，可以使用最小堆和最大堆的组合来解决问题。最小堆可以容纳数组中的最大元素，而最大堆可以容纳数组中的最小元素（这可以在运行时知道，无需对数组进行排序）。（参见问题 7）
  • 由于每个数据结构都有其自身的重要性，因此有时最好使用多个数据结构（例如最小堆+最大堆+链表作为 BST 等）来执行一系列操作
  • 假设要将最大堆转换为最小堆，如果每次删除最大堆并将其插入最小堆，则每个元素都需要 logn 时间，因此总共有 n 个元素。这将花费 nlogn 时间。因此，如果您将数组视为随机数组而不是将其视为最大堆，则可以在 O(n) 时间内构建最小堆，这是一种更好的方法。

问题

--

树木

树木

可应用的方法：

  • 当使用树来实现任何事情时，通常都会使用递归。
  • 前序遍历可以给出从顶部到任意节点的路径。
  • 有时将路径存储在数组中以解决某些算法是很好的
  • 层序遍历使用队列。每次父节点被压入队列时，弹出父节点时，其子节点也会被压入队列
  • 树中的大多数问题都涉及在 LST 上执行核心算法，然后在 RST 上执行核心算法，最后使用递归获得所需的结果。
  • 有时，在树中，如果要为某个 DLL 返回两个指针，我们只会返回一个，并将另一个指针指向同样需要的那个指针，以便我们可以使用返回的那个指针来获取它。请参阅问题 7 中的方法 2。
  • 在应用递归时，返回的内容将返回该特定函数堆栈，并将其赋值给调用该执行堆栈的变量或对象。如果在递归中使用局部变量，则应将其作为地址传递，并且赋值时参数应为指针类型。
  • 遍历时增加级别有两种方式，一种是在访问 LST 和 RST 时增加一次，从 LST 或 RST 返回时减少一次，或者在访问 LST 时将级别作为参数传递为 level+1，依此类推。
  • 当您必须使用某种逻辑打印节点或访问与另一个节点或根给定距离的任何节点时，前序遍历是最好的选择。（对于垂直树顺序遍历也是如此）
  • 有时，哈希表可用于在遍历时存储元素。在使用特定逻辑搜索元素时，哈希会非常有用。因此，哈希表可以与树一起实现。
  • 有时，如果难以确定哈希表的大小，可以使用链表来代替，链表会将每个节点附加到主链表上。因此，主链表的每个节点都将充当哈希表的一个单元。
  • 在递归中删除路径意味着只释放根。
  • 有时递归中也可以使用其他函数。
  • 子树的节点在遍历时总是会同时出现。顺序可能不同，但不会出现交错。
  • 有时为了比较两棵子树，我们可以应用中序和前序遍历，或者中序或后序遍历，最后比较字符串。正如之前所研究的，前序和中序遍历或后序和中序遍历总会生成一棵唯一的树。
  • 如果问题涉及使用递归构建树的单个数组，请确保选择正确的数组起点和终点（特别是数组被一次又一次分割的地方）

问题：

--

字符串

字符串

可应用的方法

  • 所有数组概念都适用于字符串，因为它们是字符数组（通用的，不仅适用于数字）
  • 对于搜索，可以应用 BST 和哈希表。
  • 可以为字符数组（字符串）创建哈希表。哈希表的长度应为 256，因为 ASCII 值从零开始最大为 255，因此最多只占用 256 个字节的空间。
  • 循环中的两个指针都在同一侧，一个跟踪重复项，一个跟踪唯一项，可用于从字符串中删除重复项。
  • 对于字符串 arr 的大小，应使用 strlen 来测量，而不是使用 sizeof，因为 sizeof 还包括 \0
  • 有时，一个字符串可以与自身或另一个字符串合并来解决某些算法。例如：如果一个字符串是另一个字符串的旋转，则将一个字符串与自身连接起来可以得到一个字符串，其中第二个字符串将是该字符串的子字符串。
  • 在哈希表中存储解决算法所需的尽可能多的内容，因为它是一个结构
  • 在程序结束后释放分配给 hashTable 的内存总是好的
  • 有时，哈希表值可以减少而不是增加来解决算法，例如，查找字谜
  • Excel 列号和名称的关系与数字系统有关。Excel 的数字系统基数为 26。因此，数字的范围是 1-26。不同之处在于，Excel 的数字从 1 开始，而不是从 0 开始，而其他基数则不同，例如 2 包含 0 和 1，以此类推。因此，给定一个数字，我们可以不断将其除以 26，直到得到小于 26 的余数。然后，我们从下到上依次取余数和商，并根据它们的值赋予对应的字母。

问题

--

贪婪的

贪婪的

可应用的方法：

  • 用于优化问题（最大化或最小化某些东西）
  • 何时使用堆与何时使用排序：当问题仅需要找到最小值或最大值时，我们可以使用排序，但如果找到某些内容后需要再次插入，则在排序的情况下需要花费 O（n）时间，因为它需要找到位置，而堆更好，因为它们只需要 O（logn）时间来做同样的事情。
  • 为了使用位等来表示节点（例如：哈夫曼编码），我们使用树。
  • 霍夫曼编码或最佳合并模式需要最小化某些内容，始终选择最大值位于树的顶部，具有最小边长（或要遍历的路径），最小值位于底部，具有最大边或要遍历的路径，以最小化工作量。
  • 最小成本生成树和最短路径问题是两码事。最短路径问题需要给定一个起点，然后根据每条边的权重，以尽可能短的路径到达终点。而最小成本生成树问题则需要构建一个连接所有节点的权重尽可能小的图。因此，算法的优先级会有所不同。
  • 在贪婪算法中，为了最小化或最大化某些值（不同的方法），我们可以对某些值贪婪地求解算法，并引入一些不符合我们方法的情况。总有一种情况会奏效。
  • 哈希表以及最小堆和最大堆等数据结构的混合搭配也可用于解决贪婪算法

问题

--

分而治之

可应用的方法：

  • 对于大小固定且有序的重复元素，我们可以使用二分查找。也可以使用线性查找，即如果某个元素应该重复给定的次数，可以先检查它在 i 处的值，然后再检查 i+给定次数的值，看看是否正确。
  • 在分治法中，偶数乘法可以从 n 减少到 logn，但结果相同。例如，pow 函数，其底数每次都是平方，幂每次减半，在 logn 次乘法中得到相同的结果。如果幂值为奇数，则将结果赋给底数，使幂值转换为偶数，然后进行相同的运算。
  • 在二分查找中，无论算法是什么，总是从中间开始，然后比较左侧或右侧的值。你甚至可以比较最左侧和最右侧的值，以查看上下限或某种模式来求解算法。但在二分查找中，总是从中间开始。此外，为了中断递归并返回结果，成功条件将是该索引处根据算法独有的属性特征。找到这个特征。
  • 有时，与其在左数组或右数组中搜索，不如将其分成两个组件/组并应用各种操作，如比较、合并等。注意：由于其分治次数应一直进行到最后，直到每个组只剩下一个元素。
  • 有时，我们会使用二分查找，找到中间元素后，再将算法的核心逻辑应用于中间元素，以确定是在右数组还是左数组中搜索。例如：如果算法的核心是交换，我们就交换；如果是比较，我们就比较；如果是应用某个公式，我们就执行该操作。
  • 要编写递归版本的迭代版本，请按照以下步骤操作
    • 将递归中断条件替换为将运行的 while 循环
    • 应用相同的条件并更新该条件中变量的值。这些变量也将成为 while 循环的一部分。与其使用更新后的值调用函数，不如直接更新变量的值，while 循环会处理剩下的事情。
    • 确保在 while 循环中迭代时，将传入函数的两个变量值都赋值
    • 错误条件（如果要返回任何错误值进行验证）将在 while 循环结束后出现
  • 要从迭代编写递归，请替换 while 循环条件，其对立面应为递归的中断条件并反转子步骤

问题：

--

动态规划

可应用的方法

  • 这种编程意味着使用一个表，我们动态地决定是否调用一个函数来进行计算或使用这个表
  • 动态规划就像分而治之，可以应用于任何具有最优子结构的问题（给定的问题应该可以分解为较小的问题，并且子问题的解是主问题解的一部分）以及重叠子问题和递归方程
  • 在涉及动态规划的问题中，我们首先从基本情况开始（例如 0/1 背包），我们查看背包的重量是否为 1 且物体重量是否为 1，然后查看重量是否为 2 且物体重量是否为 1 等等，我们不断寻找每个基本问题的解决方案以得出主要问题的解决方案。
  • 涉及子序列的问题，可以应用 Kadane 算法，或者使用哈希表或指针
  • 在涉及矩阵的问题中，为了按照算法计算下一个数字，它将涉及对角线、上或左元素，就像我们在大多数算法中所做的那样。
  • 有时我们会从另一个角度将大问题分解成小问题。例如：如果一个数需要满足除以 2/3/5 的条件，我们宁愿用基数乘以 2/3/5 来生成下一个数。因此，一个生成序列的大问题被分解成一个每次生成下一个数的小问题。有时，为了跟踪多个生成过程，可以使用多个变量。
  • 有时，可以通过将给定问题简化为另一个已知且已知解决方案的问题来解决。
  • 对于涉及子序列的问题，我们可以将其分解为更小的问题。具体来说，对于线性数组，可以取长度小于总长度 1 的数组，并找到动态规划的规律，从而构造递归方程。
  • 有时可以使用某些算法合并两个 DP 解决方案的结果以找到最终结果。
  • 要将任何问题分解为 DP（递归方程），请遵循问题的关键并将其分解成一个故事，然后概括为递归方程。例如：在查找给定字符串中的最长回文子序列的情况下，我们比较最后两个元素以查看它们是否匹配，这也是我们在普通回文问题中所做的事情。在此基础上，我们能够推导出方程，如果它们匹配，我们将两个指针都移动到下一个位置，如果不匹配，我们移动其中一个（两种情况）并找出最大值。然后使用这些递归方程，我们在脑海中构建一棵树。然后我们发现重叠的问题。为了看到独特的问题，我们将创建树的问题概括为 i 和 j，而是每次找出对于 i 的每个值可以存在多少个 j 值。通过这种计算，我们找到了独特的解决方案并解决了该问题，并制作了一个该大小的表格。
  • 看看动态规划 (DP) 是否正在变成斐波那契数列。例如：在楼梯问题中，到达第 n 级台阶的总路径数为 f(n) = f(n-1) + f(n-2)，也就是说，从 n-1 级台阶开始，可以走 1 级台阶；从 n-2 级台阶开始，只能走 1 级台阶，台阶长度为 2。因此，这完全就是斐波那契数列。
  • 在一些涉及 DP 的算法中，您可以从 n 开始，在这种情况下，n 的答案取决于 n-1，依此类推。
  • 大多数涉及字符串的问题都可以视为 S(i,j)，要么我们比较最后一个字符，如果相等，则将其转换为 i-1,j-1，要么我们取 i,j-1 和 i-1,j 中的最小值或最大值
  • 有时，如果问题本身就是一个表格，你需要对其进行逆向工程，找到完成某件事的最小方法数。例如，创建一个新表格，从最底层开始，向上构建解决方案。在这种情况下，答案将是单元格 0,0
  • 如果一个字符串和它的反转有一个公共子序列，那么这个公共子序列肯定是回文
  • 每当出现涉及字符串的问题时，检查是否可以使用 LCS
  • 每当提出一个一般问题时，请检查它是否正在变成斐波那契数列或其某种形式。

问题

--

图表

图表

可应用的方法：

  • 大多数图论题都围绕着寻找相邻节点并对其进行操作。寻找相邻节点很容易，因为你可以很容易地从矩阵中得到它，只需查看该顶点对应的值是否为 1，以及某个 i 是否未被访问过即可。所以基本上我们要么进行深度优先搜索 (DFS)，要么进行广度优先搜索 (BFS)。
  • 当需要寻找两个顶点之间的路径时，它们不需要直接连接。它们之间可能存在一些顶点/节点。
  • 有时可以将给定的矩阵假定为具有一组不同规则的图，并且可以对其应用 DFS 或 BFS。
  • 检查问题 6 graphh 以检查如何使用两个数组访问矩阵中单元格的所有周围元素的技巧
  • 在二分图中，循环的长度始终是偶数

问题：

--

模式匹配

可应用的方法：

  • 为了让 KMP 找到字符串中某个模式的所有出现位置，每当找到匹配项时，我们都会将模式变量值的指针分配到前缀后缀数组中小于指针当前值的索引处，然后我们再次开始比较。
  • 在待搜索模式包含尽可能不同的字符的情况下，Boyer-Moore 算法比 KMP 算法效率更高。如果字符相同，则在最坏情况下，时间复杂度为 O(mn)，最终会比较大多数字符。因此，如果字符大部分相同，请使用 KMP。

问题：

--

回溯

可应用的方法：

  • 排列意味着有序的组合。例如，我的果汁是由10种水果组合而成的（顺序无关紧要），但在排列的情况下，顺序很重要。基本上，改变顺序可以改变结果，这意味着排列。改变顺序对结果没有影响，这意味着组合
  • 回溯使用递归，其中堆栈中的每个调用都有其存储的值，并且回溯利用这些值在递归树中的特定级别进行决策

问题：

--

杂项

一般问题

--

高级数据

  • 使用 KMP 查找文本中是否存在模式
  • 对于图而言，拓扑排序仅适用于有向无环图（无环）。当一个任务依赖于另一个任务时很有用。

--

高级数据结构

  • 不相交集：如果两个节点相连或属于同一类别，则它们属于同一集合。不相交集可以用两种方式表示。1) 链表 2) 树

有三种操作可以应用于这样的集合。1
）查找
2）并集
3）创建

使用树形结构实现更好，因为我们可以应用按秩并集和路径压缩，以确保查找操作在 logn 或常数时间内完成，而创建操作则仅发生在常数时间内。
对于链表，查找操作需要 O(n) 时间，并集操作也需要 O(n) 时间，而创建操作需要 O(1) 时间。

问题

--

位操作

位操作

--

特里树

特里树

更好地解决算法的方法

  • 对于极值，请参考 C 给出的 limits.h 常数
  • XOR表示取位之和并除以二，余数即为答案 = 'XOR' 是可交换的
  • 一个数字与其自身进行“异或”运算的结果为 0
  • 零与数字的“异或”结果是数字本身
  • “1 的补码是通过反转数字的二进制表示中的所有位而获得的数字。o 为 1，1 为 0”
  • 线性散列是 (h(k) + i)modm （其中 m 是散列表的大小，h(k) 是接受键 k 并返回值的散列函数，i 是递增以获得不同值的参数）
  • 数组的子数组始终是连续的，而子序列可以不连续，但必须按升序排列。字符串也是如此。
  • 任何数据结构都只有两种实现方式：一是使用数组（大小固定且内存连续）；二是使用堆内存（结构体和链表）。因此，数组和链表，或者两者的组合，都可以用来实现任何数据结构。在大多数情况下，如果使用链表来实现数据结构，那么操作会耗时更长。但链表的优势在于动态内存分配。
  • 对于中缀到后缀的转换，使用的数据结构是堆栈。所有运算符都存储在堆栈中。对于后缀的求值，堆栈用于存储操作数
  • 求值表达式 = 将中缀转换为后缀 --> 求值后缀。时间复杂度：O(n)
  • 堆可以实现为二叉树、三叉树或 n 叉树。堆是近乎完全的二叉树。堆中的叶子节点应始终从左到右填充。
  • 插入时应使用堆，查找最小值并删除最小值或最大值，以便在更短的时间内完成
  • 在最小/最大堆中，根元素与其子元素相比，包含最小/最大元素。适用于所有层级。
  • 为了创建堆而不是创建链表（因为它涉及大量存储），我们创建一个数组。
  • 每个具有一个节点或叶子（具有零个子节点）的树已经是最小堆或最大堆。
  • 如果要从数组构建堆，请按照以下步骤操作：


    LEFT(i) = 2i + 1;
    RIGHT(i) = 2i + 2;
    PARENT(i) = (i-1) / 2; (valid for array with index 0)
  //Go level by level from left to right and write elements from the array or to the array basically.
  //Note dividing by two means right shift in binary and multiplying means left shift in binary
  //There can be more than 1 max or min heap of a given array
  //In a complete or almost complete binary tree, leaves start from floor(n/2+1) to n
Enter fullscreen mode Exit fullscreen mode
  • 按降序排列的数组是 MAX HEAP，按升序排列的数组是 MIN HEAP。
  • 将元素转换为堆的算法时间为 O(n)。因此无需排序，因为排序的复杂度为 O(nlogn)。
  • 递归增加了空间复杂度和时间复杂度。
  • 在最大堆中，查找最小值、删除随机元素或搜索元素将花费 O(n) 时间，因为这里最大堆与数组一样好。
  • 对于使用数组实现的二叉搜索树，空间复杂度为 O(2^n)，但使用链表实现时，空间复杂度为 O(n)
  • 数字流意味着数字一个接一个地出现，对于每个输入变化，您必须找到问题中所述的内容。
  • 遍历任何二叉树有三种方法（经过一些修改后也可以应用于 3 元树或 n 元树）


//all nodes should have children, even leafs
INORDER //left root right - second visit
PREORDER//root left right - first visit
POSTORDER //left right root - third visit
Enter fullscreen mode Exit fullscreen mode
  • 二叉树是一种正常树，它将元素按照数组中给定的顺序从左到右按父子关系排列，但二叉搜索树遵循特定的顺序。
  • 二叉搜索树通常用于存储键。键通常指向一条特定的记录。因此，键必须是唯一的。
  • BST 的 IORDER 遍历使我们按升序排列所有元素。（最小元素最左边，最大元素最右边）
  • 为了更好地理解递归，或者进行一次练习或编写递归程序，请遵循 123 的方法。即，按照树双序遍历或间接递归中的说明，在一个地方依次执行所有行
  • 间接递归是指某个函数 A 调用 B，B 再次调用 A，依此类推。
  • 具有 N 个无标记节点的可能结构数量为 2ncn/n+1
  • 如果标记的 n 个节点为 n！则每个结构可能的树数为 n！（树总数为 2ncn/n+1 * n！）
  • 给定 PRE ORDER POST AND IN ORDER，只有 1 棵树能够满足所有条件（给定 pre post 并且只有 1 棵树中有 n 个节点的树的数量是可能的。即使任何与 INRODER 的组合都将唯一地生成一棵二叉树）
  • 表达式树是一种树，其中运算符占据根节点，左侧或右侧节点也位于根节点。（可以通过中序遍历检查正确的一侧）。运算符也必须按照其优先级在树上排列。
  • 表达式树的前序、后序和中序遍历给出相应的形式。
  • LCRS（左孩子右兄弟节点）左指针指向左孩子，右指针指向与该节点同为父节点的兄弟节点。表示法用于表示具有随机子节点数量（不必相等）的树。
  • 当需要上下移动的堆结构时，可以使用树的数组表示。使用数组的缺点是，如果树是倾斜的，则数组必须达到 2^n 才能存储给定父节点和子节点索引的 n 个值，而堆则不需要。
  • 递归会持续填充堆栈，直到处理完要执行的语句。一旦返回确定的真值或假值，它就会弹出返回该值的执行上下文。返回一个函数也很重要，因为这样堆栈就能知道这个函数将返回某个值，可能是另一个函数的返回值，也可能是一个值。这就是递归持续进行的方式。注意，如果没有写 return 语句，则应使用 if else 语句，以避免程序控制在不满足条件的情况下向下运行。因此，return 语句只是递归中 if else 的替代。
  • 层序遍历使用一个队列，父节点被压入队列，然后弹出（出队），其子节点按从左到右的顺序压入队列，重复相同的过程。因此，我们不断地逐层扫描节点。
  • 层序遍历类似于 BFS（图中的广度优先搜索），其他遍历（如中序、前序和后序）类似于 DFS（图中的深度优先搜索）
  • 垂直树顺序遍历：根节点与自身的距离为 0。当我们移动到左孩子时，它与根节点的距离为 -1，右孩子与根节点的距离为 1。如果我们对每个左孩子都执行 -1 操作，对每个右孩子都执行 +1 操作，则将有多个节点的距离值相同。距离值相同的节点落在一条垂直线上。如果我们遍历这条线，则称为垂直树顺序遍历。
  • 和树是指 LST 中的值和 RST 中的值和等于根的树。这适用于除树之外的所有节点
  • 递归执行栈只有在没有return语句的情况下才会记住下一行，否则会返回执行栈
  • 如果树中的两个节点位于同一级别且具有相同的父节点，则它们为兄弟节点；如果两个节点位于同一级别但没有相同的父节点，则它们为表兄弟节点
  • O(1) 表示时间复杂度或空间复杂度与输入大小无关
  • 如果一个字符串的旋转之一与另一个字符串的旋转相匹配，则该字符串是另一个字符串的旋转。
  • 游程编码是指遍历给定的字符数组，并显示每个字符重复了多少次，以及输出该字符。例如：SSMMMAAARRT => S2M3A3R2T1
  • 如果两个字符串的字符数相同，且由相同的字母组成，则它们为字母重排的字符串。即使重复出现，它们也仍然是相同的。
  • 编写程序的理想方法是从函数返回并将字符串保存在一个地方而不是分散的
  • 贪婪方法和DP是两种可用于解决优化问题的编程范式
  • 允许使用贪婪方法计算分数
  • 为了使哈夫曼编码有效，字母必须不均匀分布
  • 生成树是图中存在的边的最小数量，使得所有节点都连通。生成树始终是主图的子图，并且不能包含主图中不存在的边。
  • 在无向图中，与节点关联的边数称为节点的度。在有向图中，没有度，只有入度和出度
  • 基尔霍夫定理用于寻找非加权无向简单图的生成树
  • 给定一个加权图，可以使用两种算法 PRIMS 和 KRUSKALS 来查找最小成本生成树。这两种算法都是贪婪方法
  • 在 PRIMS 中，只要边的权重重复，我们就有可能得到多棵生成树。但在这种情况下，最终成本将保持不变。
  • Dijsktra 算法无法应用于具有负权重边的图，因为该算法无法判断该边是负权重边还是正在转换为负权重环。如果图中存在负权重环，则最短路径将不存在，因为每个环的路径都会不断减少。
  • 树是一种无环图
  • 贪婪法和动态规划是仅有的两种可用于求解优化问题的方法。贪婪法可能无法每次都为每个问题提供正确的解决方案，但对某些问题有效，并且耗时更短。另一方面，动态规划虽然耗时稍长，但总能为此类问题提供正确答案。
  • n 的阶乘不过是 n 的幂 n
  • 在成本矩阵表示的图中，如果两个顶点有边，则会赋予权重，否则，如果它们没有边，则权重为无穷大。
  • 旅行商问题时间复杂度O(n^2^2^n)
  • 丑数是可以写成 2、3 或 5 的乘积或这些数字的组合的数字。1 也被认为是丑数，因为它是一个例外。
  • 每当要找到 2 的最高或最低幂时，使用对数运算

--

结论：

希望本指南能在您任何涉及数据结构和算法的面试中派上用场。
想随时了解最新动态，请关注我的Twitter。

文章来源：https://dev.to/rahhularora/the-ultimate-guide-for-data-structs-algorithm-interviews-npo
Devto 翻译
PREV
2023 年程序员的顶级开发项目：掌握最新技术的完整教程和工具列表
NEXT
React.js 的最佳 UI 框架