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;}
};