剑指offer 66题 part3（13~18题）

本文主要是介绍剑指offer 66题 part3（13~18题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第十三题：调整数组顺序

题解：

方法一：

直接在vector中删除所有偶数，依次尾插到vector中即可

if(((*t)&1)==0)

注意这里判断奇偶，由于优先级问题，要多用括号

t=array.erase(t);

class Solution {
public:void reOrderArray(vector<int> &array) {vector<int>::iterator t=array.begin();int len=array.size(),num;while(size--){if(((*t)&1)==0){num=*t;t=array.erase(t);array.push_back(num);}else t++;}}
};

方法二：

先找到第一个偶数，然后再在偶数后面找第一个奇数，删除这个奇数，把所有偶数往后移动一位，然后把奇数往空格放，依次执行即可得到答案

第十四题：链表中倒数第K个节点

输出链表中倒数第K个节点

方法一：第一遍扫描计算有多少个节点，第二遍直接定位到这个点就行了

方法二：用两个指针，第一个指针先指向第 k 个节点，第二个节点指向第一个节点，然后同时往后移动到第一个节点不能移动的时候即可

代码的鲁棒性：（重要）

1 · 头结点指向NULL，如果我们试图访问空指针指向的内存，程序崩溃

2 · k 不能为 0   因为这里的k是无符号的数，k-1将会是一个很大的正数

3 · k不能大于链表的程度，如果这样也会出现指针指向空指针内存

注意：（ .    和  -> 的区别）

通过结构体指针变量访问用"->"
通过结构体变量访问用"."
比如说：
假设student是个结构体,有一个成员int age
struct student one;
struct student *ptr;
one.age               ptr->age

代码：

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {ListNode *p1=pListHead,*p2=pListHead;if(pListHead==NULL || k==0) return NULL;for(int i=1;i<k;i++){if(p1->next==NULL) return NULL;p1=p1->next;}while(p1->next!=NULL){p1=p1->next,p2=p2->next;}return p2;}
};

第十五题：反转链表

输入一个链表，反转链表后，输出链表的所有元素

题解：

思路很好理解，我们从中间开始理解，两边只是边界问题而已：

反转链表，我们这里的思路只是把指针的指向改变了而已，没有另外开辟很多内存去存

1、利用pre指针来记住反转链表的最后一个节点（这个节点不断在变换，因为会新添加节点进去）

2、利用temp来记住原始链表的第一个节点（这个节点不断在变换，因为会把这个节点放到反转链表中去）

3、把旧链表的头结点保存下来temp=pHead

4、把pHead指针指向新链表的最后一个节点，也就是pHead=pre

5、判断是否已经到了最后一个节点

6、跟新pre，temp指针（根据1、2的含义）

注意：

这里必须把while循环break掉才能return，不能直接在while循环里面return

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* ReverseList(ListNode* pHead) {if(pHead==NULL) return NULL;ListNode *pre=NULL,*temp=NULL;while(pHead!=NULL){temp=pHead->next;pHead->next=pre;if(temp==NULL) break;pre=pHead;pHead=temp;}return pHead;}
};

第十六题：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则

题解：

方法一：

递归（牛逼啊！！！感觉剑指offer可以学到好多脑洞大开的操作）

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

方法二：

一般性的合并

这里需要注意理解下面两者区别

pHead!=NULL

pHead->next!=NULL

下面代码用的前者

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

第十七题：树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

题意：就是判断B树是不是A树的一个分支

题解：

递归

分别去判断左右子树即可

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:bool IsSubtree(TreeNode* pRoot1,TreeNode* pRoot2){if(pRoot2==NULL) return true;if(pRoot1==NULL) return false;if(pRoot1->val == pRoot2->val)return IsSubtree(pRoot1->left,pRoot2->left)&&IsSubtree(pRoot1->right,pRoot2->right);else return false;}bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)  {if(pRoot1==NULL || pRoot2==NULL) return false;return (IsSubtree(pRoot1,pRoot2) ||IsSubtree(pRoot1->left,pRoot2) ||IsSubtree(pRoot1->right,pRoot2));}
};

第十八题：树的镜像

二叉树的镜像定义：源二叉树 8/  \6   10/ \  / \5  7 9 11镜像二叉树8/  \10   6/ \  / \11 9 7  5

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:void Mirror(TreeNode *pRoot) {if(pRoot==NULL) return;TreeNode* temp=pRoot->left;pRoot->left=pRoot->right;pRoot->right=temp;Mirror(pRoot->left);Mirror(pRoot->right);}
};

这篇关于剑指offer 66题 part3（13~18题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！