当前位置：首页 > news >正文

剑指offer | 2.3 数据结构相关题目

news 2026/4/18 15:15:28

接下来，我将开设一个剑指 Offer 算法题解专栏，专门记录书中高频算法题的详细思路、代码实现与关键点总结

本篇为数据结构专题，收录面试题 3～9（面试题 1、2 非典型算法题，暂不记录），所有题解均保留最直观的解题思路，代码可直接运行。

三、数组中重复的数字

数组中重复的数字_牛客题霸_牛客网

思路1：标记数组法

这是最直观、最容易想到的解法。

我们可以创建一个标记数组，初始值全部为 0，用 1 表示对应数字已经被访问过。遍历原数组时，若当前数字对应的标记已经是 1，说明该数字重复；否则将其标记为 1。同时必须对非法输入（数字小于 0 或大于等于数组长度）进行判断。

class Solution { public: int duplicate(vector<int>& numbers) { // write code here // 标志数组 int n = numbers.size(); vector<int> flag(n); // 遍历数组 for (auto num : numbers) { // 不合理的输入 if (num < 0 || num >= n) { return -1; } if (flag[num] != 0) {// 遇到的数字已被标记 return num; } else { flag[num] = 1;// 标记当前数字 } } return -1; } };

复杂度

时间复杂度：O (n)，只需遍历一次数组

空间复杂度：O (n)，额外开辟了标记数组

思路2：下标定位法（原地算法，最优解）

仔细观察题目规律：如果数组中没有重复数字，那么排序后数字与下标一一对应，即 numbers[i] == i，我们可以利用这一规则，在原数组上直接交换、排序，不需要额外空间。

核心逻辑

遍历数组，取当前数字 num = numbers[i]
若 num == i，说明位置正确，继续下一个
若 num != i，将 num 与 numbers[num] 比较
1. 相等 → 找到重复数字
2. 不相等 → 交换两者，让数字回到正确下标位置

class Solution { public: int duplicate(vector<int>& numbers) { // write code here // 就地查找 // 遇到数字m，如果它等于当前下标i，继续比较下一个数字 // 不等于下标i，将下标m处的数字和数字m比较，如果相等→重复；不相等则继续交换 int n = numbers.size(); for (int i = 0; i < n; i++) { int num = numbers[i]; // 不合法的数字 if (num < 0 || num >= n) { return -1; } // 当前数字刚好等于下标 if (num == i) { continue; } // 当前数字num等于下标num处的数字→重复 if (num == numbers[num]) { return num; } else { // 不等于→交换两处的数字 swap(numbers[i], numbers[num]); } } return -1; } };

复杂度

时间复杂度：O (n)

空间复杂度：O (1)，无需额外空间

四、二维数组中的查找

二维数组中的查找_牛客题霸_牛客网

暴力解法/一般解法：从左上角或右下角逐个遍历，每次比较只能排除一个元素，时间复杂度 O (n²)，效率极低。

优化思路（选点排除）

利用数组有序的特性，选择右上角或左下角作为起点：

右上角：比目标小 → 排除本行；比目标大 → 排除本列
左下角：比目标大 → 排除本行；比目标小 → 排除本列每次比较都能排除一行或一列，效率大幅提升。

从右上角开始查找

class Solution { public: bool Find(int target, vector<vector<int> >& array) { // write code here if (array.size() == 0) { // 空数组 return false; } // 右上角开始寻找 int i = 0; // 行号 int j = array[0].size() - 1; // 列号 while (i < array.size() && j >= 0) { if (target == array[i][j]) { return true; } else if (target > array[i][j]) { i++;// 抛弃一行数据 } else { j--;// 抛弃一列 } } return false; } };

从左下角开始查找

class Solution { public: bool Find(int target, vector<vector<int> >& array) { // write code here if (array.size() == 0) { // 空数组 return false; } // 左下角开始寻找 int i = array.size() - 1; // 行号 int j = 0; // 列号 while (i >= 0 && j < array[0].size()) { if (target == array[i][j]) { return true; } else if (target < array[i][j]) { i--;// 抛弃一行数据 } else { j++;// 抛弃一列 } } return false; } };

复杂度

时间复杂度：O (n + m)（n 行 m 列）

空间复杂度：O (1)

五、替换空格

替换空格_牛客题霸_牛客网

常规思路：从前往后遍历字符串，遇到空格就扩容2个空间，并将后面的元素全部向后移动2位，再在当前位置放入%20，时间复杂度：O(n²)，空格越多，移动次数越多，效率极差。

优化思路（双指针+从后往前）

核心思想

先统计空格数量，提前计算出新字符串长度
从后往前遍历，避免字符重复移动
使用双指针：一个指向原字符串末尾，一个指向新空间末尾
1. 遇到非空格 → 直接复制
2. 遇到空格 → 依次写入 0 2 %

class Solution { public: string replaceSpace(string s) { // write code here // 从后往前遍历+双指针 if (s.size() == 0) {// 特殊情况处理：空字符串 return s; } // 计算空格的个数 int count = 0; for (const auto& x : s) { if (x == ' ') { count++; } } if (count == 0) { //没有空格，直接返回s return s; } int p = s.size(); // 扩容 s.resize(s.size() + 2 * count); // 从后往前遍历+双指针 int q = s.size(); while (p >= 0) { if (s[p] == ' ') { s[q--] = '0'; s[q--] = '2'; s[q--] = '%'; p--; } else { s[q--] = s[p--]; } } return s; } };

复杂度

时间复杂度：O (n)

空间复杂度：O (n)（字符串本身需要扩容）

六、从尾到头打印链表

从尾到头打印链表_牛客题霸_牛客网

利用栈“先进后出”的特性，先遍历链表，将所有节点入栈，再依次出栈存入结果数组，即可实现逆序输出

class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { vector<int> res; if (head == nullptr) { // 空链表，直接返回 return res; } stack<int> st; ListNode* p = head; // 遍历链表，全部入栈 while (p != nullptr) { st.push(p->val); p = p->next; } // 出栈，实现逆序 while (!st.empty()) { res.push_back(st.top()); st.pop(); } return res; } };

七、重建二叉树（难点）

重建二叉树_牛客题霸_牛客网

思路不难，难点在于代码实现

核心思路：

找根节点：序遍历数组的第一个元素，就是当前树的根节点值
划分左右子树：
1. 在中序遍历中找到根节点，根节点左侧为左子树，右侧为右子树
2. 根据中序划分出的左右子树大小，对应截取前序遍历数组
递归构建：分别递归构建左右子树，连接到根节点

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ #include <limits.h> struct TreeNode* reConstructBinaryTree(int* preOrder, int preOrderLen, int* vinOrder, int vinOrderLen ) { // write code here // 遍历数组为空→叶结点 if (preOrderLen == 0 || vinOrderLen == 0) { return NULL; } // 创建根节点，需要手动申请空间 struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); root->val = preOrder[0];// 根节点的值前序遍历数组的第一个值 root->left = NULL; root->right = NULL; // 在中序数组中寻找根节点 int rootIdx = 0; while (vinOrder[rootIdx] != root->val) { rootIdx++; } // 递归构建左子树 root->left = reConstructBinaryTree(preOrder + 1, rootIdx, vinOrder, rootIdx); // 递归构建右子树 root->right = reConstructBinaryTree( preOrder + 1 + rootIdx, // 右子树前序起点 preOrderLen - rootIdx - 1, // 右子树前序长度 vinOrder + rootIdx + 1, // 右子树中序起点 vinOrderLen - rootIdx - 1 // 右子树中序长度 ); return root; }

八、二叉树的下一个节点

二叉树的下一个结点_牛客题霸_牛客网

核心思路

分两种核心情况：

当前节点有右子树：右孩子的最左节点，即为下一个节点
当前节点无右子树：向上遍历父节点，找到第一个作为左孩子的节点的父节点

代码1（基础版）

class Solution { public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { // 当前节点有右子树→找到右子树的最左节点 if (pNode->right != nullptr) { TreeLinkNode* p = pNode -> right; while (p->left != nullptr) { p = p->left; } return p; } else { TreeLinkNode* parent = pNode -> next; // 父节点 // 判断当前节点是父节点的左孩子还是右孩子 if (parent->left == pNode) { // 左孩子，直接返回父节点 return parent; } else { // 右孩子，找第一个为左孩子节点的父节点 TreeLinkNode* child = parent; parent = parent->next; while (parent->next != nullptr && child == parent->right) { child = parent; parent = parent->next; } // 没有节点为左孩子节点→返回空 if (parent->next == nullptr) { return nullptr; } return parent; } } return nullptr; } };

代码2（判空）

在指针使用前增加判空，避免空指针访问

class Solution { public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { // 需要对指针判空 if (pNode == nullptr) { return nullptr; } // 当前节点有右子树→找到右子树的最左节点 if (pNode->right != nullptr) { TreeLinkNode* p = pNode -> right; while (p->left != nullptr) { p = p->left; } return p; } else { TreeLinkNode* parent = pNode -> next; // 父节点 // 在使用left/righ/next前，都需要对指针判空 if (parent == nullptr) { return nullptr; } // 判断当前节点是父节点的左孩子还是右孩子 if (parent->left == pNode) { // 左孩子，直接返回父节点 return parent; } else { // 右孩子，找第一个为左孩子节点的父节点 TreeLinkNode* child = parent; parent = parent->next; // 在使用left/righ/next前，都需要对指针判空 if (parent == nullptr) { return nullptr; } while (parent->next != nullptr && child == parent->right) { child = parent; parent = parent->next; } // 没有节点为左孩子节点→返回空 if (child == parent->right) { return nullptr; } else return parent; } } return nullptr; } };

代码3（最优版）

合并重复逻辑：对于当前节点是左孩子节点的第一次判断，可以和后面的找是左孩子的节点融合

#include <pthread.h> class Solution { public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { // 需要对指针判空 if (pNode == nullptr) { return nullptr; } TreeLinkNode* pNext = nullptr;// 下一节点 // 当前节点有右子树→找到右子树的最左节点 if (pNode->right != nullptr) { TreeLinkNode* p = pNode -> right; while (p->left != nullptr) { p = p->left; } pNext = p; } else if (pNode->next != nullptr) { // 父节点不为空 TreeLinkNode* parent = pNode -> next; // 父节点 TreeLinkNode* cur = pNode; while (parent != nullptr && cur == parent->right) { cur = parent; parent = parent->next; } pNext = parent; } return pNext; } };

九、用两个栈实现队列

用两个栈实现队列_牛客题霸_牛客网

核心思路

stack1：专门负责入队
stack2：专门负责出队
当stack2为空时，将stack1所有元素倒入stack2，实现先进先出顺序

class Solution { public: void push(int node) { stack1.push(node); } int pop() { // 栈2为空，把栈1全部倒入栈2 if (stack2.empty()) { while (!stack1.empty()) { int top = stack1.top(); stack1.pop(); stack2.push(top); } } // 出队：出栈2的栈顶元素 int res = stack2.top(); stack2.pop(); return res; } private: stack<int> stack1; stack<int> stack2; };

拓展：用两个队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

思路1（基础版）

两个队列：queue1和queue2

queue1 负责存数据
pop /top 时，将 queue1 前 n-1 个元素暂存到 queue2，取出最后一个元素后再放回

class MyStack { private: queue<int> queue1; queue<int> queue2; public: MyStack() {} void push(int x) { queue1.push(x); } int pop() { // 保留队尾元素，其余进队2 while (queue1.size() > 1) { queue2.push(queue1.front()); queue1.pop(); } int res = queue1.front(); queue1.pop(); // 队尾元素出队 // 将队2所有元素放回队1 while (!queue2.empty()) { queue1.push(queue2.front()); queue2.pop(); } return res; } int top() { // 将队1的所有元素放入队2 int res = queue1.front(); // 记录队1的队尾元素 while (!queue1.empty()) { res = queue1.front(); queue2.push(res); queue1.pop(); } // 将队2所有元素放回队1 while (!queue2.empty()) { queue1.push(queue2.front()); queue2.pop(); } return res; } bool empty() { return queue1.empty(); } };

官方最优思路

入队时直接维护队头始终为栈顶，出队直接 pop 即可

入栈：先将元素入队2，然后将队1所有元素放入队2，再交互两队列元素，这样队1的队头元素始终是最后“入栈”的元素
出栈：直接将队1的队头元素出队即可

class MyStack { private: queue<int> que1; queue<int> que2; public: MyStack() {} void push(int x) { // 入队2 que2.push(x); // 队1元素全部放入队2 while (!que1.empty()) { que2.push(que1.front()); que1.pop(); } // 两队列元素交换 swap(que1, que2); } int pop() { // 出队1的队头元素 int res = que1.front(); que1.pop(); return res; } int top() { return que1.front(); } bool empty() { return que1.empty(); } };

查看全文

http://www.jsqmd.com/news/661344/