接下来我将开设一个剑指 Offer 算法题解专栏专门记录书中高频算法题的详细思路、代码实现与关键点总结本篇为数据结构专题收录面试题 39面试题 1、2 非典型算法题暂不记录所有题解均保留最直观的解题思路代码可直接运行。三、数组中重复的数字数组中重复的数字_牛客题霸_牛客网思路1标记数组法这是最直观、最容易想到的解法。我们可以创建一个标记数组初始值全部为 0用 1 表示对应数字已经被访问过。遍历原数组时若当前数字对应的标记已经是 1说明该数字重复否则将其标记为 1。同时必须对非法输入数字小于 0 或大于等于数组长度进行判断。class Solution { public: int duplicate(vectorint numbers) { // write code here // 标志数组 int n numbers.size(); vectorint 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] 比较相等 → 找到重复数字不相等 → 交换两者让数字回到正确下标位置class Solution { public: int duplicate(vectorint 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, vectorvectorint 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, vectorvectorint 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²)空格越多移动次数越多效率极差。优化思路双指针从后往前核心思想先统计空格数量提前计算出新字符串长度从后往前遍历避免字符重复移动使用双指针一个指向原字符串末尾一个指向新空间末尾遇到非空格 → 直接复制遇到空格 → 依次写入 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: vectorint printListFromTailToHead(ListNode* head) { vectorint res; if (head nullptr) { // 空链表直接返回 return res; } stackint 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; } };七、重建二叉树难点重建二叉树_牛客题霸_牛客网思路不难难点在于代码实现核心思路找根节点序遍历数组的第一个元素就是当前树的根节点值划分左右子树在中序遍历中找到根节点根节点左侧为左子树右侧为右子树根据中序划分出的左右子树大小对应截取前序遍历数组递归构建分别递归构建左右子树连接到根节点/** * 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: stackint stack1; stackint stack2; };拓展用两个队列实现栈225. 用队列实现栈 - 力扣LeetCode思路1基础版两个队列queue1和queue2queue1 负责存数据pop /top 时将 queue1 前 n-1 个元素暂存到 queue2取出最后一个元素后再放回class MyStack { private: queueint queue1; queueint 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: queueint que1; queueint 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(); } };