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

《剑指offer》题目 C++详细题解

news 来源：原创 2024/9/20 4:03:04

JZ15 二进制中1的个数

核心考点：二进制计算

思路一：使用一个循环，因为我们知道整型变量只有32位，所以循环结束的条件就是到32，从最低位开始，逐位检查数字 n 的二进制表示，利用位运算中的与运算，将当前位移到最低位，然后与 1 进行按位与运算，判断结果是否为 1，如果当前位为 1，则计数器 count 加 1，循环结束后，计数器 count 中保存的就是数字 n 的二进制表示中 1 的个数。

class Solution {
public:int NumberOf1(int n) {int count = 0;int i = 0;while(i < 32){if((n >> i) & 1 == 1) // 使用按位与进行比较count++;i++;}return count;}
};

但是上面的算法的时间复杂度是O(N)的，有没有更简单更便捷的算法呢？

思路二：使用 while 循环，只要 n 不为 0，就继续循环。循环中，执行 n &= (n - 1) 操作。该操作利用了二进制数中 1 的性质：将一个数减 1，然后与原数进行按位与运算，可以将最右边的一个 1 变成 0，每次执行 n &= (n - 1) 操作后，n 中的 1 的个数减少 1，因此代码将计数器 count 加 1，循环结束后，计数器 count 中保存的就是 n 的二进制表示中 1 的个数，代码返回 count。

class Solution {
public:int NumberOf1(int n) {int count = 0;while(n){n &= (n - 1);count++;}return count;}
};

这种方法比直接遍历二进制位效率更高，因为每次循环都只进行一次位运算，可以更快地将 n 中的 1 个数进行统计。

JZ22 链表中倒数最后k个结点

核心考点：链表，前后指针的使用，边界条件的检查

由于题目中明确了这是一个单链表，所以我们不可以从后向前遍历找到最后k个节点，所以此时我们可以使用前后双指针的思路，前指针先走k步，随后前后两个指针同时向后走，当前指针到达结尾的时候，后指针所在的位置就是倒数最后k个节点。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* FindKthToTail(ListNode* pHead, int k) {ListNode* fast = pHead;ListNode* slow = pHead;// 前指针先走k步while(k--){if(fast == nullptr)return nullptr;fast = fast->next;} // 前后指针同时走while(fast){fast = fast->next;slow = slow->next;}return slow;}
};

JZ24 反转链表

核心考点：链表操作，思维缜密程度

这个题目的做法有很多种，我们依次来写一下。

思路一：定义三个指针，整体右移，边移动边翻转，保证不会断链

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* ReverseList(ListNode* head) {if(!head || !head->next)return head;// 至少两个节点ListNode* n1, *n2, *n3;n1 = head;n2 = head->next;n3 = head->next->next; // 可能为空while(n3 != nullptr){n2->next = n1; // 翻转// 向后移动n1 = n2;n2 = n3;n3 = n3->next; // 不断链}// 走到这里n3为空n2->next = n1;head->next = nullptr;return n2;}
};

思路二：采用头插的方法进行翻转，此时拿原始链表的时候注意不要断链

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* ReverseList(ListNode* head) {if(!head || !head->next)return head;// 至少两个节点ListNode* newhead = nullptr;ListNode* cur = head;while(cur){// 把原链表的第一个节点拿下来ListNode* tmp = cur;cur = cur->next;// 头插tmp->next = newhead;newhead = tmp;}return newhead;}
};

思路三：使用递归来解决，过程中出现重复子问题

如果我们先逆序前两个节点，会出现什么问题呢？

我们会发现此时会出现断链的情况，会把节点值为3的节点丢失，从而找不到后面的节点，会造成内存泄漏的问题，所以先直接修改前两个是不合理的，所以我们需要换一种思路，以一种宏观的思路，相信dfs一定可以能帮我们完成的逆序的任务，给dfs一个头节点，dfs帮我完成逆序，返回逆序之后的头节点，那么此时就有：

此时刚好就完成了我们的逆序工作，如果上面的思路不好理解，我们可以把链表当作一棵树，只不过此时是一个单边树，此时我们对这棵树仅需进行以此后序遍历即可

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* ReverseList(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;ListNode* newhead = ReverseList(head->next);head->next->next = head;head->next = nullptr;// 返回逆序之后的头节点return newhead;}
};

JZ25 合并两个排序的链表

核心考点：链表合并

对于这道题，解题的思路有很多种，我们可以一个一个节点的归并，当然，也可以采用递归完成。

思路一：通过循环遍历两个有序链表，每次选择较小的节点插入到新的链表，最终得到一个合并后的有序链表。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {if(pHead1 == nullptr)return pHead2;if(pHead2 == nullptr)return pHead1;ListNode* cur1 = pHead1;ListNode* cur2 = pHead2;// 标明新链表的头尾节点,闭区间ListNode* newhead = nullptr;ListNode* tail = nullptr;while(cur1 && cur2){// 选出较小的节点ListNode* tmp = nullptr;if(cur1->val >= cur2->val){tmp = cur2;cur2 = cur2->next;}else{tmp = cur1;cur1 = cur1->next;}// 尾插到新链表if(newhead == nullptr){newhead = tail = tmp;}else{tail->next = tmp;tail = tail->next;}}// 合并后,cur1或者cur2可能不为空,此时直接链接即可if(cur1)tail->next = cur1;if(cur2)tail->next = cur2;return newhead;}
};

思路二：通过递归调用 Merge 函数，每次将两个链表首节点进行比较，并将较小的节点作为合并后的新链表的头节点，并将较小的节点的 next 指针指向递归调用 Merge 函数的结果，最终得到一个合并后的有序链表。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {if(pHead1 == nullptr)return pHead2;if(pHead2 == nullptr)return pHead1;ListNode* head = nullptr;// 1.找到较小的节点,head// 并从原链表中删除该节点if(pHead1->val < pHead2->val){head = pHead1;pHead1 = pHead1->next;}else{head = pHead2;pHead2 = pHead2->next;}//2.出现子问题,此时变少了一个节点// 但是此时依然是合并链表head->next = Merge(pHead1, pHead2);return head;}
};

想清楚上面的方法，此时我们的代码就能更优化一点。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {if(pHead1 == nullptr)return pHead2;if(pHead2 == nullptr)return pHead1;if(pHead1->val < pHead2->val){pHead1->next = Merge(pHead1->next, pHead2);return pHead1;}else{pHead2->next = Merge(pHead1, pHead2->next);return pHead2;}}
};

JZ26 树的子结构

核心考点：二叉树理解，二叉树遍历

解题思路：二叉树都是递归定义的，所以递归操作是比较常见的做法，首先明白子结构怎么理解，可以理解成子结构是原树的子树（或者一部分)，也就是说，B要是A的子结构，B的根节点+左子树+右子树，都在A中存在且构成树形结构，所以我们比较的过程要分为两步

1.先确定起始位置
2.在确定从该位置开始，后续的左右子树的内容是否一致

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {private:bool IsSameTree(TreeNode* root1, TreeNode* root2) {if (!root2) // 子树已经遍历完毕return true;if (!root1) // 母树已经遍历完毕return false;if (root1->val != root2->val)return false;// 此位置处根节点值相等bool left = IsSameTree(root1->left, root2->left);bool right = IsSameTree(root1->right, root2->right);return left && right;}public:bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if (pRoot1 == nullptr || pRoot2 == nullptr)return false;bool result = false;// 先寻找起始位置if (pRoot1->val == pRoot2->val) {// 判断两棵树是否相同result = IsSameTree(pRoot1, pRoot2);}// 左子树和pRoot2比较if (result == false) {result = HasSubtree(pRoot1->left, pRoot2);}// 右子树和pRoot2比较if (result == false) {result = HasSubtree(pRoot1->right, pRoot2);}return result;}
};

JZ27 二叉树的镜像

核心考点：二叉树操作

这个题目我们仔细观察可以发现，所谓的二叉树镜像本质是自底向上进行左右左右子树交换的过程，既然是自底向上，那就说明这个题目的思想是后序遍历，这样这个题目就比较好写啦

class Solution {
public:TreeNode* Mirror(TreeNode* pRoot) {if(!pRoot)return pRoot;if(!pRoot->left && !pRoot->right)return pRoot;if(pRoot->left)Mirror(pRoot->left);if(pRoot->right)Mirror(pRoot->right);TreeNode* tmp = pRoot->left;pRoot->left = pRoot->right;pRoot->right = tmp;return pRoot;}
};

JZ76 删除链表中重复的结点

核心操作：链表操作，临界条件检查，特殊情况处理

解题思路：通过快慢指针的方式限定范围，从而达到去重的效果，这里需要注意处理全部相同，全部不同和部分相同的三种情况的方式。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead) {if(pHead == nullptr)return pHead;// 申请带头结点ListNode* head = new ListNode(0);head->next = pHead;// 定义重复区域的区间,左开右闭ListNode* prev = head;ListNode* tail = head->next;while(tail != nullptr){// 1.先确定重复区域的起始位置while(tail->next != nullptr && tail->val != tail->next->val){prev = tail;tail = tail->next;}// 2.确定重复区域的结束位置while(tail->next != nullptr && tail->val == tail->next->val){tail = tail->next;}// 走到这里有三种情况// 1.tail->next为空, 有重复区间// 2.tail->next不为空, 有重复区间// 3.链表没有重复结点,没有重复区间if (prev->next != tail){prev->next = tail->next;  }tail = tail->next;}ListNode* next = head->next;delete head;return next;}
};

JZ30 包含min函数的栈

核心考点：栈的规则性设计

解题思路：很容易想到，在栈内部保存min变量，每次更新的时候，都对min变量进行更新。//但是，面试官很容易就会问到：如果想拿出第二小，第三小的值怎么拿？用上面的办法就不行了，为了满足通用，我们使用一个辅助栈，内部保存元素的个数和数据栈完全一样，不过，辅助栈内部永远保存本次入栈的数为所有数据的最小值（注意：辅助栈内部元素可能会出现“必要性”重复)，我们这里是为了实现算法，所以就不从0开始实现stack了，我们直接使用c++库里面实现的栈就好，题面说了，保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法，所以，后面的代码对空的检验可有可无。

注意：最小栈的元素个数和数据栈的个数相同，最小栈的栈顶永远保存着当前个数的数据栈中的最小值，其中，最小栈可能出现重复的数组。

class Solution {
public:void push(int value) {st.push(value);if(minst.empty() || value < minst.top())minst.push(value); // 插入小值elseminst.push(minst.top());  // 插入栈顶的值}void pop() {st.pop();minst.pop();}int top() {return st.top();}int min() {return minst.top();}stack<int> st;  // 数据栈stack<int> minst; // 最小栈
};

JZ31 栈的压入、弹出序列

核心考点：栈的理解

思路：将入栈序列的元素压入辅助栈。检查辅助栈的栈顶元素是否等于出栈序列的元素，如果相等，则执行出栈操作，继续检查直到栈顶元素不再等于出栈序列的元素或者栈为空。当入栈序列中的所有元素都被处理完后，检查出栈序列是否也到达了末尾。如果出栈序列也到达了末尾，说明所有元素都按照正确的顺序弹出了栈，因此此时是一个有效的弹出序列；反之则不是。

class Solution {
public:bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {stack<int> st;int curpush = 0, curpop = 0;while(curpush < pushV.size()){// 入栈序列直接入栈st.push(pushV[curpush++]);// 出栈序列和栈顶元素相同,就一直出栈while(!st.empty() && st.top() == popV[curpop]){st.pop();curpop++;}}return curpop == pushV.size() ? true : false;}
};

JZ32 从上往下打印二叉树

核心考点：二叉树层序遍历

这个题目本质是二叉树的层序遍历，我们可以直接借助一个队列来完成这个题目，首先我们创建一个队列用来暂存待处理的节点，并创建一个用来存储层序遍历的结果的vector容器。将根节点压入队列，当队列不为空时，循环执行以下操作：从队列头部取出一个节点，将节点的值添加到结果中。如果节点有左子树，则将左子树节点加入队列。如果节点有右子树，则将右子树节点加入队列。当队列变为空时，所有节点都已经处理完毕，返回结果即可。

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:vector<int> PrintFromTopToBottom(TreeNode* root) {vector<int> ret; // 返回层序遍历的结果queue<TreeNode*> q;if(root == nullptr)return ret;// 根节点先入队列q.push(root);while(q.size()){// 访问当前结点并出队列TreeNode* t = q.front();q.pop();ret.push_back(t->val);// 左子树入队列if(t->left)q.push(t->left);// 右子树入队列if(t->right)q.push(t->right);}return ret;}
};