常见笔试，基础笔试

【知识点详解】 1. **二元查找树转双向链表** 在二元查找树（BST）中，每个节点都包含左子节点和右子节点。要将其转换为排序的双向链表，我们需要遵循以下步骤： - 从树的最小节点（即左子树为空的节点）开始，按顺序遍历节点。 - 当遍历到当前节点时，将其左子节点链接到前一个节点，然后将前一个节点设置为当前节点。 - 遍历右子树，重复以上步骤，直到遍历完整棵树。根节点的左指针应指向双向链表的第一个节点，而最后一个节点的右指针应指向根节点。 2. **设计包含 min 函数的栈** 要在栈中添加一个 min 函数，同时保持 push 和 pop 操作的时间复杂度为 O(1)，我们可以使用辅助栈。每当一个新元素入栈时，如果它的值小于或等于当前栈中的最小值，就将它也压入辅助栈。pop 操作时，若弹出的元素等于辅助栈顶元素，也需将其从辅助栈中弹出。这样，辅助栈的栈顶元素始终是栈中当前的最小值。 3. **求子数组的最大和** 该问题可以通过动态规划解决，使用 Kadane's Algorithm。初始化两个变量，`max_current` 用于跟踪当前子数组的最大和，`max_global` 用于记录全局最大和。遍历数组，每次更新 `max_current` 为 `max(current + arr[i], arr[i])`，并比较 `max_current` 与 `max_global`，如果 `max_current` 更大，则更新 `max_global`。`max_global` 即为最大子数组和。 4. **二元树中找出和为某一值的所有路径** 使用深度优先搜索（DFS）策略来解决这个问题。对于每个节点，计算从根节点到该节点的路径和。如果路径和加上当前节点的值等于目标和，将路径添加到结果列表。然后继续遍历左右子节点。返回时，如果路径和减去当前节点的值仍等于目标和，将当前节点移除路径。这样可以找到所有符合条件的路径。 5. **查找最小的 k 个元素** 使用快速选择算法或堆（如最小堆）可以高效地找出数组中的最小 k 个元素。快速选择在平均情况下具有 O(n) 的时间复杂度，堆可以在 O(n log k) 的时间复杂度内找到最小 k 个元素。 6. **腾讯面试题 - 分配问题** 这是一个计数问题，可以使用哈希映射来解决。遍历上排的数字，对每个数字计数，然后遍历计数结果，生成下排的数字序列。 7. **判断两链表是否相交** 若要判断两个链表是否相交，可以分别遍历两个链表，记录它们的长度，然后从长度较长的链表头部开始，步长为两链表长度之差，与短链表头部开始同步遍历。如果两者相遇，说明链表相交；否则，不相交。对于链表有环的情况，可以使用快慢指针（Floyd 环检测算法）来判断是否存在环，然后再判断相交。 8. **算法题目** - **房间与开关问题**：关闭所有灯，进入房间1，打开所有灯，然后离开。等待一段时间（例如1分钟），再次进入房间1，关闭所有灯，然后离开。再进入房间2，此时，处于开启状态的灯就是由第二个开关控制的，因为其他开关在最近的操作中没有改变它们的状态。 - **金条分割问题**：将金条切成三块，第一块和第二块相等，第三块是剩余部分。第一天给第一块，第二天给第一块和第三块，第三天收回第一块，第四天给第二块，以此类推。 - **链表反转**：可以使用迭代或递归的方法实现。迭代方法通常涉及三个指针：当前节点、前一个节点和临时节点。 - **循环链表插入节点**：先找到循环链表的尾节点，然后从尾节点开始，每次向前一步，同时从头节点开始，每次向前两步，当两个指针相遇时，相遇点就是插入位置。 - **字符串匹配、字符串翻转、子字符串查找、字符串比较等问题**：这些问题涉及到字符串处理的基本算法，如 KMP 算法、双指针法、滑动窗口等。 这些题目涵盖了许多基本的算法和数据结构概念，如树、链表、数组、栈、动态规划、哈希映射等，是面试和笔试中常见的问题。熟练掌握这些知识点对于IT行业的求职者来说至关重要。