📖 剑指offer刷题笔记(二)
本文记录了牛客网剑指offer JZ16-JZ30的刷题过程。
文章中带*意味着二次做时需着重关注，特别是有其他方法待实现的。
*合并两个有序链表
描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
题解
第一思维是想尽可能利用有序链，但这带来额外开销太大放弃了。
有两种方法：
+++ 迭代求解
遍历两个链表
代码
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
if(pHead1==NULL&&pHead2==NULL)return NULL;
//新的头节点
ListNode * pHead = (ListNode*) malloc(sizeof(ListNode));
//三个链表的指针
ListNode *p1=pHead1, *p2=pHead2, *p3=pHead;
while(p1!=NULL&&p2!=NULL){
//两个链表都不为空时
//将链表较小的那个添加至新链表
if(p1->val<p2->val){
p3->next=p1;
p1=p1->next;
}
else{
p3->next=p2;
p2=p2->next;
}
p3=p3->next;
}
//若还有一个表没读完，则将其新添至新链表中
if(p1){
p3->next=p1;
}
if(p2){
p3->next=p2;
}
return pHead->next;
}
};+++
+++ 递归调用*
+++
树的子结构
描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
题解
第一次看还以为子结构就是子树的意思，原就按子树做的，发现子结构和子树还是有区别的，但问题不大只需要改动一点代码就行了。主要思想就是：设两个递归函数，一个递归函数寻找子结构开始的节点，一个递归函数检验是否为子结构。
代码
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
//两棵树任意一树空为false
if(pRoot1==NULL||pRoot2==NULL)return false;
bool isSame = false;
//从根节点往下寻找是否同根
//同根则开始判断是否部分一致
if(pRoot1->val==pRoot2->val){
isSame = IsSametree(pRoot1, pRoot2);
}
//有部分一致则返回true
if(isSame){
return true;
}
//否则看是否为左子树或右子树的结构
return HasSubtree(pRoot1->left, pRoot2)||HasSubtree(pRoot1->right, pRoot2);
}
bool IsSametree(TreeNode* pRoot1, TreeNode* pRoot2) {
//判断pRoot2是否是pRoot1的从根开始相同的部分结构
//递归结束条件pRoot2为空则一定是pRoot1的子结构
//- 注意这里与题设有矛盾，但这是递归函数
//- 为空子树需要在调用递归函数前判断
//pRoot1为空肯定false
if(pRoot2==NULL){
return true;
}
if(pRoot1==NULL){
return false;
}
//判断根节点是否一致
//一致递归看子树一不一致
//不一致返回false
if(pRoot1->val==pRoot2->val){
return IsSametree(pRoot1->left,pRoot2->left)&&IsSametree(pRoot1->right, pRoot2->right);
}
else return false;
}
};二叉树的镜像
描述
操作给定的二叉树，将其变换为源二叉树的镜像。
题解
递归求解：交换左右孩子，递归镜像左子树、右子树。
代码
class Solution {
public:
TreeNode* Mirror(TreeNode* pRoot) {
//树根为空结束
if(pRoot==NULL)return NULL;
//交换左右孩子
TreeNode* temp=pRoot->left;
pRoot->left=pRoot->right;
pRoot->right=temp;
//递归左右子树
Mirror(pRoot->left);
Mirror(pRoot->right);
//返回递归后的根
return pRoot;
}
};顺时针遍历二维数组
描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
题解
设置四个值模拟圈圈，判断坐标位于圈圈何处，以及根据位置变化坐标和缩小圈圈。
代码
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
//设置四个值，即限制了圈圈的值
int iMin=0, iMax= matrix.size()-1, jMin=0, jMax=matrix[0].size()-1;
//设置cnt为总元素个数
int cnt = matrix.size()*matrix[0].size();
//遍历的初值，i为横坐标，j为纵坐标，k为遍历数组的坐标
int i=0, j=0, k=0;
vector<int> v(cnt);
//cnt不为0说明未遍历完
while(cnt--){
//先将遍历的第一个元素加入
v[k++]=matrix[i][j];
//位于上圈
if(i==iMin){
//到转角出向下拐到右圈
if(j==jMax)i++;
//未到转角往右走
else j++;
}
//位于右圈
else if(j==jMax){
//到转角往左拐到下圈
if(i==iMax)j--;
//未到转角向下走
else i++;
}
//位于下圈
else if(i==iMax){
//到转角向上走到左圈
if(j==jMin)i--;
//未到转角向左走
else j--;
}
//位于左圈
else if(j==jMin){
//在圈起始值的下方，更新圈圈
//将坐标置为新圈圈的起始值
if(i==iMin+1){
iMin++;
jMin++;
iMax--;
jMax--;
i=iMin;
j=jMin;
}
//未到则向上走
else i--;
}
}
return v;
}
};*包含最小值的栈
描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数 及 pop函数 的时间复杂度都是 O(1)
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素
题解
用一个栈作为数据栈，另外维护一个最小值栈，即比栈顶更小或相等的元素新添进来是进栈（相当于保存了历史最小值）。这里相等直接进栈就好了，在这里走了一点*弯路还设置了一个结构一个指示有多少个相等的值。
代码（弯路版）
class Solution {
typedef struct{
int min;
int num;
}Min;
public:
void push(int value) {
if(data.empty()||value<min()){
Min val={ value, 1};
minData.push((val));
}
else if(value==min()){
minData.top().num++;
}
data.push(value);
}
void pop() {
if(top()==min()){
if(minData.top().num==1)minData.pop();
else minData.top().num--;
}
data.pop();
}
int top() {
return data.top();
}
int min() {
if(data.empty());////ERROR
return minData.top().min;
}
private:
stack<int> data;
stack<Min> minData;
};*栈的压栈弹出序列
描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
题解
法1：直接模拟一个栈就好了 *
法2：法2是当时陷入一个思维陷阱了，老是以数字上的规律来探索：即对于出栈序列中任意数，索引值比其小的索引值总是递减的。判断还是挺麻烦的，主要是从左往右遍历出栈序列，对每一个出栈元素在压栈序列中查找并维护一个最大下标，若新元素下标比最大下标大那么其后面比其小元素的数量是能够知道的，那么递减怎么校验呢，设置一个range，从[0, range]往下查找，找到了将range缩小，比其小元素数量减一。若到最后数量不为0说明比其小的不是递减的不符合规范。相当复杂也不好理解，权当不浪费这个思考时间，贴一下这个代码，模拟栈的先咕着，以后再看时写。
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
//序列数量不一致返回false
if(popV.size()!=pushV.size())return false;
//遍历出栈序列，对于序列中每一个元素后面的入栈次序应该都是递减的
//题设序列中数字均不一致
//用index记录下目前遍历最大的位置
int index=0;
for(int i=0;i<popV.size();i++){
//既然满足递减，则在入栈序列中从左往右查找
//设置查找成功标志查找单个元素检查该元素是否比目前元素还大，若还大则需要检验
bool finded = false;
int j=index;
while(j<popV.size()){
//找到了比原最大更大的，更新index
if(popV[i]==pushV[j]){
finded = true;
index=j;
break;
}
j++;
}
//没找到则确认是否真的更小
if(!finded){
for(int k=index-1;k>=0;k--){
if(popV[i]==pushV[k]){
finded = true;
break;
}
}
//在前面没找到意味着没有该元素，不可能为出栈序列返回false
//否则确实更小则跳过，跳出的是最外层的for循环
if(!finded){
return false;
}
else{
continue;
}
}
//运行到这里说明目前元素是索引值最大的元素
//找到后要校验在其后面入栈索引元素比其小的（共有index-i个）入栈索引值是递减的
int cnt =index-i;
int range=index-1;
for(int k=i+1;k<popV.size();k++){
//cnt为0说明后面没有更小的了不必再遍历
if(cnt ==0)break;
for(int n=range;n>=0;n--){
if(popV[k]==pushV[n]){
cnt--;
range=n;
continue;
}
}
}
//cnt不为0说明递增的序列数量少于则不符合规范
if(cnt!=0)return false;
}
return true;
}
};层序遍历二叉树
描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
题解
剑指offer惟二的困难题，因为之前上课有所提及反而不那么难了。思想是维护一个队列，根先进队。然后队不为空则循环，循环内容是出队打印出队节点内容，左子树不为空入队，右子树不为空入队。
代码
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> v;
//按层遍历，采用队列
if(!root)return v;
nodeList.push(root);
while(!nodeList.empty()){
//取出本节点内容
TreeNode* node=nodeList.front();
//打印，子节点加入队列
v.push_back(node->val);
if(node->left)nodeList.push(node->left);
if(node->right)nodeList.push(node->right);
//本节点出队
nodeList.pop();
}
return v;
}
private:
queue<TreeNode*> nodeList;
};*判断是否为二叉搜索树的后序遍历
描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜索树）
题解
法1递归：二叉搜索树的后序序列特征就是：最后的根是中值，能把前面的分成两个二叉搜索树便可以递归了。这里采用设立新的vector来保存显然是浪费，应该只需要左右索引限制便可以递归了。待优化代码如下。
法2上限约束法：*大佬的方法还没看码住 二叉搜索树后序遍历
代码
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size()==0)return false;
//若序列长度小于2则一定可以是二叉搜索树的后序序列
if(sequence.size()<=2)return true;
//否则设立两个子序列
vector<int> v1;
vector<int> v2;
//开始遍历到有比根即最后的数据大的放入v2，其使能端设为true
//题设数字互不相同
bool v2En=false;
for(int i=0;i<sequence.size()-1;i++){
if(sequence[i]<sequence.back()){
if(v2En)return false;
v1.push_back(sequence[i]);
}
else{
v2En=true;
v2.push_back(sequence[i]);
}
}
return (v1.empty()||VerifySquenceOfBST(v1))&&(v2.empty()||VerifySquenceOfBST(v2));
}
};二叉树中长度为某一值的路径
描述
输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
题解
设置一个应该返回的二维数组，一个临时的一维数组。递归遍历二叉树，递归过程是：进入一个节点将节点加入临时数组，判定expectNumber的值是否小于0，若到叶子节点则判定expectNumber是否相等，若相等则将临时数组加入二维数组中，注意跳出函数的时候要将末尾元素弹出（回溯）。
代码
class Solution {
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<vector<int> > vPath;
vector<int> temp;
if(root)DFSBtree(vPath, temp, root, expectNumber);
return vPath;
}
void DFSBtree(vector<vector<int>>& vPath, vector<int>& path, TreeNode* node, int expectNumber){
//路径先加入列表
//注意返回时要退出
path.push_back(node->val);
//调用此函数是node不应为空
//路径小于0直接返回
if(expectNumber<0){
path.pop_back();
return;
}
//若到叶子节点则判定是否添加
//叶子节点结束
if(node->left==NULL&&node->right==NULL){
if(expectNumber==node->val){
vPath.push_back(path);
}
path.pop_back();
return;
}
//如果没到叶子节点
if(node->left)DFSBtree(vPath, path, node->left, expectNumber-node->val);
if(node->right)DFSBtree(vPath, path, node->right, expectNumber-node->val);
//遍历完毕这里还有return
path.pop_back();
return;
}
};复杂链表的复制
描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。
题解
之前自己只能想到先用数组把他们存下来，后面看到评论中的方法太巧妙了：
(1) 复制链表成这样的形式先不考虑随机节点
A->A1->B->B1->C->C1
(2) 根据关系确定随机节点
比如说非空的兄弟节点 A1->random = A->random->next
这个方法真的太惊艳啦
(3) 拆分成 A->B->C 和 A1->B1->C1
返回 A1
代码
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead) {
if(!pHead)
return NULL;
RandomListNode* p=pHead;
//第一步：复制 并且 A->A1->B->B1->C->C1
while(p){
RandomListNode* node=(RandomListNode*)malloc(sizeof(RandomListNode));
node->label=p->label;
node->next=p->next;
p->next=node;
p=node->next;
}
//第二步：形成随机节点
p = pHead;
while(p){
if(p->random)
p->next->random=p->random->next;
p=p->next->next;
}
//第三步：拆分链表
p=pHead;
RandomListNode* qHead=p->next;
RandomListNode* q=qHead;
while(p){
//后面还有元素
if(q->next){
p->next=q->next;
q->next=p->next->next;
}
//后面没有元素
else{
p->next=NULL;
q->next=NULL;
}
//更新p, q
p=p->next;
q=q->next;
}
return qHead;
}
};二叉搜索树转换成双向链表
描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构 4.你不用输出或者处理，示例中输出里面的英文，比如"From left to right are:"这样的，程序会根据你的返回值自动打印输出
题解
中序遍历即可。设置头指针和前驱指针，初始值为空。中序遍历的遍历操作是，先判断是否有头节点，没有则设置。若有，则将现节点和前一节点的前驱后继关系确立。然后保存现节点至前驱指针。即：左子树不为空进入左子树->遍历操作->右子树不为空进入右子树。
代码
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree) {
if(!pRootOfTree)return NULL;
inOrder(pRootOfTree);
return head;
}
private:
TreeNode* head=NULL;
TreeNode* temp=NULL;
void inOrder(TreeNode* node){
//有左子树进入左子树
if(node->left)inOrder(node->left);
//出了左子树
//判定head是否为空
//为空则遍历刚开始，确定头指针
if(head==NULL)head=node;
else{
//否则将上一节点右指针指向现节点
//将现节点左指针指向上一节点
//由于后序操作只有关于现指针的右节点
//所以并不会影响到树的遍历过程
temp->right=node;
node->left=temp;
}
//保存最近遍历的节点
temp=node;
//有右子树进入右子树
if(node->right)inOrder(node->right);
}
};*字符串的全排列
描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。有可能有重复字符。
题解
递归方法：*
这题有关于离散数学学过的一个下一个全排列算法：从右往左寻找相邻两个的递增元素设为 ..., A, B, ... 其中 A<B；若找不到说明已经是最大的全排列了；再次从右往左寻找第一个比 A大的数 C (可能是B但不影响) ，交换 A, C. 将 [B, end()] 的串逆序就是下一个全排列。
代码
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> strs;
string str1=str;
while(!str1.empty()){
strs.push_back(str1);
str1=nextString(str1);
}
return strs;
}
private:
string nextString(string str){
bool hasNext=false;
int i=str.length()-1;
//从右往左找到第一个左比右小的相邻元素
//找到了则证明不是最大的
//--找到时左元素下标i-1，右元素下标i
//否则最大输出NULL
while(i){
if(str[i-1]<str[i]){
hasNext=true;
break;
}
i--;
}
//下一个全排列
//从右往左搜索第一个比左元素大的元素交换
//从右元素到尾开始reverse
if(hasNext){
for(int j=str.length()-1;j>=i;j--){
//第一个大的找到后交换
//交换后reverse
if(str[j]>str[i-1]){
std::swap(str[j],str[i-1]);
std::reverse(str.begin()+i,str.end());
break;
}
}
}
else{
str.clear();
}
return str;
}
};数组中超过一半的数
描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000
题解
(1) 采用 hash 表
(2) 采用数数的方法，设置数量 cnt 和数字 val，cnt初值为0。遍历数组：若 cnt 为0，意味着当前可能数字不存在，则将当前数字赋值给 val, 令cnt为1. 若 cnt 不为0，则令 val 与当前数字相比较，若相等 cnt 加1，否则减1. 这样最差的结果是消去一个普通数和多数数，最后的 val 才有可能是这个数。依题意存在就可以直接返回这个数了，不放心可以 check 一下。但如果说就算知道了没有这个数该返回什么呢？
代码
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
//约定不存在返回-1
//但-1具有歧义性
//但题意应该是一定存在的只是找出来
int cnt=0;
int val=-1;
for(int number: numbers){
//cnt=0意味着目前没有元素
if(cnt==0){
val=number;
cnt++;
}
else{
//消去或者增加cnt
if(val==number)cnt++;
else cnt--;
}
}
//如果存在，那么一定是val，依题意可以返回了
//如果不存在，check 一遍是否是val即可
if(cnt>0){
cnt=0;
for(int number: numbers){
if(val==number)
cnt++;
}
}
if(cnt>numbers.size()/2)
return val;
else return -1;
}
};*最小的 k 个数
描述
给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4
题解
第一次看见这里有一个堆的字样首先手写了一个堆排序，就当复习堆了2333. 最后这里的堆应该是维护一个 k - 大顶堆，将最大的元素将其与更小的交换。
额外思路
快排-------*
代码
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> ret(k);
if(k==0)return ret;
//建立一个大顶堆
for(int i=0;i<input.size();i++){
if(i<k){
//建堆上浮
ret[i]=input[i];
heapFloat(ret, i);
}
else{
//若小于堆顶，则堆顶交换，然后下沉
if(ret[0]>input[i]){
ret[0]=input[i];
heapSink(ret, k);
}
}
}
return ret;
}
private:
bool heapCompare(vector<int> v, int i, int j){
//这里可以切换大顶堆小顶堆
return v[i]<v[j];
}
void heapSwap(vector<int>& v, int i, int j){
int temp = v[i];
v[i]=v[j];
v[j]=temp;
}
void heapFloat(vector<int>& v, int i){
//i为需要上浮的元素下标
//(i+1)/2-1为其父节点下标
while(i>0&&heapCompare(v, (i+1)/2-1, i)){
heapSwap(v, (i+1)/2-1, i);
i=(i+1)/2-1;
}
}
void heapSink(vector<int>&v, int size){
//size为目前堆的规模
int i=0;
//左孩子在堆中进入循环
while((2*i+1)<size){
//右孩子在堆中，先比较出左右孩子较小的一个
//再将其与可能需要下沉元素比较，若更大则交换
//交换后更新下沉元素下标为交换的孩子
//若不大了则无需再下沉break即可
if(2*i+2<size){
if(heapCompare(v, 2*i+1, 2*i+2)){
if(heapCompare(v, i, 2*i+2)){
heapSwap(v, i, 2*i+2);
i=2*i+2;
}
else break;
}
else{
if(heapCompare(v, i, 2*i+1)){
heapSwap(v, i, 2*i+1);
i=2*i+1;
}
else break;
}
}
//右孩子不在堆中则直接与左孩子比较
else{
if(heapCompare(v, i, 2*i+1)){
heapSwap(v, i, 2*i+1);
i=2*i+1;
}
else break;
}
}
}
};连续子数组的最大和
描述
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
题解
设置一个 partial 为中间的子数组和初值为0，ret 表示目前位置数组和最大值：初值设为第一个数字。partial 是先加上当前数字，ret 取目前 partial 和 ret 的最大值，partial 每小于0就被置0.
代码
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
//如果数组为空返回报错
//partial部分和大于0的部分
int partial = 0;
int ret=array[0];
for(int num: array){
partial+=num;
ret=max(ret,partial);
//patial小于0忽略
if(partial<0)partial=0;
}
return ret;
}
};