数据结构经典面试题80题.docx

### 数据结构经典面试题知识点解析 #### 1. 把二元查找树转变成排序的双向链表 **题目描述**： 输入一棵二元查找树（BST），将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。 **解题思路**： - 本题的关键在于如何利用二叉树的中序遍历特性来构造排序的双向链表。 - 首先定义二元查找树节点的数据结构如下： ```c++ struct BSTreeNode { int m_nValue; // value of node BSTreeNode* m_pLeft; // left child of node BSTreeNode* m_pRight; // right child of node }; ``` - 使用中序遍历来访问二叉树的节点，并在遍历过程中修改节点之间的连接，将左子节点变为前驱节点，右子节点变为后继节点。 - 在遍历过程中，维护两个指针：一个记录当前遍历到的节点，另一个记录已处理的最后一个节点（用于构建双向链表）。 - 最终，返回链表的头结点即可。 **代码示例**： ```c++ BSTreeNode* convertBSTToDoublyLinkedList(BSTreeNode* root) { BSTreeNode *lastVisited = nullptr, *head = nullptr; inorderTraversal(root, &lastVisited, &head); return head; } void inorderTraversal(BSTreeNode* node, BSTreeNode** lastVisited, BSTreeNode** head) { if (node == nullptr) return; inorderTraversal(node->m_pLeft, lastVisited, head); if (*lastVisited == nullptr) { // 如果是第一个节点，则设置头结点 *head = node; } else { node->m_pLeft = *lastVisited; // 当前节点的左指针指向已处理的最后一个节点 (*lastVisited)->m_pRight = node; // 已处理的最后一个节点的右指针指向当前节点 } *lastVisited = node; // 更新已处理的最后一个节点 inorderTraversal(node->m_pRight, lastVisited, head); } ``` --- #### 2. 设计包含min函数的栈 **题目描述**： 定义栈的数据结构，要求添加一个`min`函数，能够得到栈的最小元素。要求函数`min`、`push`以及`pop`的时间复杂度都是O(1)。 **解题思路**： - 除了使用常规的栈来存储元素之外，还需要一个额外的辅助栈来存储当前栈中的最小值。 - 每当新元素入栈时，同时更新辅助栈中的最小值。 - 出栈时，也从辅助栈中移除相应的元素。 **代码示例**： ```c++ class MinStack { public: stack<int> dataStack; stack<int> minStack; void push(int value) { dataStack.push(value); if (minStack.empty() || value <= minStack.top()) { minStack.push(value); } } int pop() { if (dataStack.top() == minStack.top()) { minStack.pop(); } return dataStack.pop(); } int getMin() { return minStack.top(); } }; ``` --- #### 3. 求子数组的最大和 **题目描述**： 输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。 **解题思路**： - 可以使用动态规划的思想来解决这个问题。 - 定义一个变量`currentSum`来存储当前子数组的和，一个变量`maxSum`来存储迄今为止找到的最大子数组的和。 - 遍历数组的过程中，对于每一个元素，如果加入它后的`currentSum`仍然比它自身大，则更新`currentSum`；否则，`currentSum`设为该元素的值。 - 每次遍历完一个元素后，更新`maxSum`。 **代码示例**： ```c++ int maxSubArraySum(const vector<int>& nums) { int currentSum = nums[0]; int maxSum = nums[0]; for (int i = 1; i < nums.size(); i++) { currentSum = max(nums[i], currentSum + nums[i]); maxSum = max(maxSum, currentSum); } return maxSum; } ``` --- #### 4. 在二元树中找出和为某一值的所有路径 **题目描述**： 输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 **解题思路**： - 采用深度优先搜索（DFS）的方式遍历二叉树。 - 在遍历过程中记录当前路径和当前路径的和。 - 当到达叶子节点时，检查路径的和是否等于目标值，如果是，则打印该路径。 **代码示例**： ```c++ struct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; void findPaths(BinaryTreeNode* root, int target, vector<int>& path, vector<vector<int>>& result) { if (root == nullptr) return; path.push_back(root->m_nValue); if (root->m_pLeft == nullptr && root->m_pRight == nullptr && target == root->m_nValue) { result.push_back(path); } findPaths(root->m_pLeft, target - root->m_nValue, path, result); findPaths(root->m_pRight, target - root->m_nValue, path, result); path.pop_back(); } ``` --- #### 5. 查找最小的k个元素 **题目描述**： 输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。 **解题思路**： - 可以使用最小堆（优先队列）来解决这个问题。 - 首先将前k个元素放入最小堆中。 - 对于剩余的每个元素，如果它比堆顶元素小，则替换堆顶元素并重新调整堆。 - 最后堆中的元素即为最小的k个元素。 **代码示例**： ```c++ vector<int> findSmallestKElements(const vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> pq; for (int i = 0; i < k; i++) { pq.push(nums[i]); } for (int i = k; i < nums.size(); i++) { if (nums[i] < pq.top()) { pq.pop(); pq.push(nums[i]); } } vector<int> smallestKElements; while (!pq.empty()) { smallestKElements.push_back(pq.top()); pq.pop(); } return smallestKElements; } ``` 以上五个题目覆盖了数据结构面试中常见的几个方面，包括二叉树的变换、栈的设计、数组的最大子数组和、二叉树路径查找以及寻找数组中最小的k个元素。通过这些题目，可以很好地考察应聘者在数据结构方面的基本功和逻辑思维能力。