[置顶] 刷题记录---每日更新----7月29日

day1

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

循环

/*
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*  pNewHead = NULL;

// 比较两个链表头，找出头结点
if( pHead1->val < pHead2->val){
            pNewHead = pHead1;
            pHead1 = pHead1->next;
        }
else{
            pNewHead = pHeada2;
            pHead2 = pHead2->next;
        }

// 循环在两个链表中找出最小值，连接到pNewHead
        ListNode* pTail = pNewHead;
while(pHead1 && pHead2){
if(pHead1->val < pHead2->val){
                pTail->next = pHead1;
                pHead1 = pHead1->next;
            }
else{
                pTail->next = pHead2;
                pHead2 = pHead2->next;
            }
            pTail = pTail->next;
        }

// 处理一个链表元素和并完毕，另一个链表还有元素的情况。
if(pHead1 == NULL){
            pTail->next = pHead2;
        }
else if(pHead2 == NULL)
            pTail->next = pHead1;

return pNewHead;
    }
};

递归

/*
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* pNewHead = NULL;
// 比较两个链表的第一个元素，将pNewHead 指向最小的，然后继续向后推进
if( pHead1->val < pHead2->val){
            pNewHead = pHead1;
            pNewHead->next = Merge(pHead1->next, pHead2);
        }
else{
            pNewHead = pHead2;
            pNewHead->next = Merge(pHead1, pHead2->next);
        }
return pNewHead;
    }
};

---

2、求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

递归

class Solution {
public:
int Sum_Solution(int n) {
int ret = n;
        ret && (ret = ret + Sum_Solution(n-1));
return ret;
    }
};

构造函数

#include <iostream>
using namespace std;

class Sum
{
public:
    Sum()
    {
        i++;
sum += i;
    }
static int i;
static int sum;
};

int Sum::sum = 0;
int Sum::i = 0;
int main()
{
    Sum s[100];
    cout << Sum::sum << endl;
return 0;
}

奇淫技巧，VS 编译通不过，GCC 可以

class Solution {
public:
int Sum_Solution(int n) {
bool a[n][n+1];
return sizeof(a)>>1;
    }
};

---

3、输入一个链表，反转链表后，输出链表的所有元素。
答：一个指针保存当前结点，初始值为 pHead，一个指针保存上一个结点初始值为 NULL，一个指针保存新链表的头初始值为NULL。在循环内用一个临时指针保存链表下一个结点。如果当前结点不为空则继续循环，在循环内首先保存链表的下一个结点，然后将当前结点的next 指向pRev，更新pRev，然后判断是否走的最后一个结点（next为空），如果是，则循环结束，更新newHead 的指向，否则向后推进当前指针。

/*
struct ListNode {
int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {

        ListNode* pRev = NULL;
        ListNode* pCur = pHead;
        ListNode* pNewHead = NULL;
while(pCur){
            ListNode* pNext = pCur->next;
            pCur->next = pRev;
            pRev = pCur;
if (pNext == NULL){
                pNewHead = pRev;
                break;
            }
            pCur = pNext;
        }
        return pNewHead;
    }
};

---

4、输入一个链表，输出该链表中倒数第k个结点。
答：考虑 k 和 链表为空和只有一个结点的情况，1.先让快指针走 K 步，2. 快慢指针一起走，直到快指针为空，返回慢指针

/*
struct ListNode {
int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if (pListHead == NULL || pListHead->next == NULL)
            return pListHead;
        ListNode* fast = pListHead;
while(k--){
if(fast == NULL)
                return NULL;           
            fast = fast->next;

        }   
while(fast){
            fast = fast->next;
            pListHead = pListHead->next;
        }
        return pListHead;      
    }
};

---

5、写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
答：1. 无进位加（异或）2.取得进位(与运算，左移) 3.累加（直到进位为0）

class Solution {
public:
int Add(int num1, int num2)
    {
int sum,carry;
        do{
sum = num1^num2;
            carry = (num1&num2)<<1;
            num1 = sum;
            num2 = carry;
        }while(carry!=0);
return sum;
    }
};

---

6、判断链表否带环，不带环返回空，带环返回环上节点。
答：一个指针走两步一个指针走一步，如果快指针与慢指针相遇，则返回，否则向后走。循环继续条件是fast 和 fast->next 不为空。

ListNode* HasCircle (ListNode* pHead)
{
    ListNode* pFast = pHead;
    ListNode* pSlow = pHead;
while(pFast && pFast->next)
    {
        pFast = pFast->next->next;
        pSlow = pSlow->next;
if(pSlow == pFast)
return pSlow;
    }
return NULL;
}

---

7、 求带环链表环的长度

int CircleLength(ListNode* meetNode)
{
    ListNode* pCur = meetNode->next;
int length = 1;

while (meetNode != pCur)
    {
length++;
        pCur = pCur->next;
    }

return length;
}

---

8、带环链表的入口点

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* GetMeetNode(ListNode* pHead){
        ListNode* pFast = pHead;
        ListNode* pSlow = pHead;

while( pFast && pFast->next){
            pFast = pFast->next->next;
            pSlow = pSlow->next;
if(pSlow == pFast)
return pSlow;
        }
return NULL;
    }


    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode* pMeetNode = GetMeetNode(pHead);
if(pMeetNode == NULL)
return NULL;

        ListNode* pBegin = pHead;
while(pMeetNode != pBegin){
            pMeetNode = pMeetNode->next;
            pBegin = pBegin->next;
        }
return pMeetNode;
    }
};

---

9、不能被继承的类

// 虚拟继承，虚基类会由派生类构造
// 友元不能被继承
// 模板参数设置为友元
template<class T>
class A
{
friend T;
private:
    A(){}
    ~A(){}
};

class B : virtual A<B>
{
public:
    B(){}
    ~B(){}
};

---

10、只能在堆上创建

// OnlyHeap
// 将构造函数设置为私有，显示提供一个接口 delete this
class OnlyHeap
{
public:
OnlyHeap()
    {}

void Destory()
    {
        delete this;
    }
private:
    ~OnlyHeap()
    {}
};

int main()
{
    OnlyHeap* p = new OnlyHeap();
return 0;
}

---

11、 只能在栈创建
重载 new 和 delete 并设置为私有

class OnlyStack
{
public:
OnlyStack()
    {}
    ~OnlyStack()
    {}
private:
void* operator new(size_t);
void operator delete(void*);
}

---

12、判断两个单链表链表是否相交，若相交，求交点。【基础版：不考虑带环】

答：1. 先判断连个链表是否相交：都走到最后一个结点，然后比较是否相等，如果相交，则最后一个结点肯定相同。PS：不要想到 X 形交叉， 因为这是单链表！只有一个next指针。
2.如果在 1. 中判断相交的情况，然后求出两个链表的长度，让较长的链表向前走 两个链表长度差 的步数，然后同时出发，相遇时就是相交点。

/*
struct ListNode {
 int val;
 struct ListNode *next;
 ListNode(int x) :
 val(x), next(NULL) {
 }
};*/
class Solution {
public:
// 判断链表是否相交
    bool isCross(ListNode* pHead1, ListNode* pHead2){
if(pHead1 == NULL || pHead2 == NULL)
return false;
while(pHead1->next)
            pHead1 = pHead1->next;
while(pHead2->next)
            pHead2 = pHead2->next;

if(pHead1 == pHead2 )
return true;
return false;
    }

// 获取链表长度
    int getSize(ListNode* pHead){
        int i = 0;
while(pHead){
            i++;
            pHead = pHead->next;
        }
return i;
    }

// 找出公共结点
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(pHead1 == NULL || pHead2 == NULL)
return NULL;
// 特殊处理一下，两个指针指向同一个链表，且链表只有一个结点的情况
if(pHead1  == pHead2 )
return pHead1;


if(!isCross(pHead1, pHead2)){
return NULL;
        }
        int step = 0;
         int size1 = getSize(pHead1);
         int size2 = getSize(pHead2);
         step = size1-size2;

if(step > 0){
while(step--)
                pHead1 = pHead1->next;
        }
else if (step < 0){
while(step++)
                pHead2 = pHead2->next;
        }

while(pHead1 != pHead2){
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
return pHead1;
    }
};

---

13、判断两个单链表链表是否相交，若相交，求交点。【升级版：考虑带环】

/*
struct ListNode {
 int val;
 struct ListNode *next;
 ListNode(int x) :
 val(x), next(NULL) {
 }
};*/
class Solution {
public:
// 找出链表的第一个公共结点
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {

// 第一个公共结点
        ListNode* commonNode = NULL;

if(pHead1  ==  NULL || pHead2 == NULL )
return NULL;

// (1) 判断是否都有环
        ListNode* circleNode1; // 链表1 环上的结点(快慢指针相遇点），如果无环则为空
        ListNode* circleNode2; // 链表2 环上的结点（快慢指针相遇点），如果无环则为空

        circleNode1 = GetMeetNode(pHead1);
        circleNode2 = GetMeetNode(pHead2);

// (2) 如果都有环 or 如果都无环 or 只有一个有环

// 1. 都有环
if (circleNode1 && circleNode2){
// 链表1 环的入口点
            ListNode* circleEnterNode1 = GetCircleEnterNode(pHead1, circleNode1);
// 链表2 环的入口点
            ListNode* circleEnterNode2 = GetCircleEnterNode(pHead2, circleNode2);
// 如果入口点相同，临时修改链表为 Y 形状，处理完毕后恢复
if(circleEnterNode1 == circleEnterNode2){
// 保存
                ListNode* enterNodeNext = circleEnterNode1->next;
// 设置为 Y 形，即无环
                circleEnterNode1->next = NULL;

// 调用处理无环情况的函数
                commonNode =  GetFirstCommonNodeNoCircle(pHead1, pHead2);

// 恢复
                circleEnterNode1->next = enterNodeNext;

            }// 如果入口点不同，将一个环遍历一周看是否能遇到另外一个环的入口点
else{
// 获取其中一个环的长度
                int circleLength = GetCircleLength(circleNode2);
// 遍历一周看是否能遇到另外一个环的入口点，如果遇到则找到，否则未找到返回环
                ListNode* next = circleEnterNode2->next;
// 遍历一圈
while(circleLength--){
// 找到公共结点
if(next == circleEnterNode1){
                        commonNode = circleEnterNode1;     
                        break;
                    }
                    next = next->next;
                }
// 未找到公共结点
if(circleLength <= 0)
return NULL;

            }
        } // 2. 都无环
else if (circleNode1 == NULL && circleNode2 == NULL){
            commonNode = GetFirstCommonNodeNoCircle(pHead1, pHead2);
        }


// (3).其中一个无环， 肯定无公共结点
return commonNode;
    }

private:


// 获取带环链表环上的一个结点(快慢指针相遇点)，如果不带环则返回空
    ListNode* GetMeetNode(ListNode* pHead){
if(pHead == NULL)
return NULL;
        ListNode* pFast = pHead;
        ListNode* pSlow = pHead;
// 快慢指针法
while(pFast && pFast->next){
            pFast = pFast->next->next;
            pSlow = pSlow->next;
if(pFast == pSlow){
return pFast;
            }
        }
return NULL;
    }

// 根据快慢指针相遇点，过去环的入口点
    ListNode* GetCircleEnterNode(ListNode* pHead, ListNode* meetNode){
if(pHead == NULL || meetNode == NULL)
return NULL;

while(pHead != meetNode){
            pHead = pHead->next;
            meetNode = meetNode->next;
        }
return pHead;
    }

// 判断两个链表是否相交
    bool isCross(ListNode* pHead1, ListNode* pHead2){

if(pHead1 == NULL  || pHead2 == NULL){
return false;
        }

while(pHead1->next)
            pHead1 = pHead1->next;
while(pHead2->next)
            pHead2 = pHead2->next;
if(pHead1 == pHead2)
return true;
return false;
    }

// 获取链表长度
    int getListLength(ListNode* pHead){
        int length = 0;
while(pHead){
            length++;
            pHead = pHead->next;
        }
return length;
    }

// 处理 Y 形状
    ListNode* GetFirstCommonNodeNoCircle(ListNode* pHead1, ListNode* pHead2){

if(pHead1 == NULL  || pHead2 == NULL)
return NULL;


// 如果不相交，直接返回NULL
if (!isCross(pHead1, pHead2))
return NULL;


        int step = 0;
        int lengthList1 = getListLength(pHead1);
        int lengthList2 = getListLength(pHead2);
        step = lengthList1 - lengthList2;

if(step > 0){
while(step--)
                pHead1 = pHead1->next;
        }
else if(step<0){
while(step++)
                pHead2 = pHead2->next;
        }

while(pHead1 != pHead2){
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
return pHead1;    
    }

// 获取带环链表环的长度
    int GetCircleLength(ListNode* meetNode){
        int length = 0;
if(meetNode == NULL)
return length;
        ListNode* next = meetNode->next;
while(next != meetNode){
            length++;
            next = next->next;
        }
return length;
    }

};

---

14、从尾到头打印单链表

 void print_list_reverse(ListNode* pNode)
    {
if (pNode == NULL)
return;
        print_list_reverse(pNode->next);
        cout << pNode->data << " ";
    }

---

15、 删除一个无头单链表的非尾结点

   void delete_not_tail(ListNode* pNode)
    {
        assert(pNode);
        assert(pNode->next);

        pNode->data = pNode->next->data;
        ListNode* temp = pNode->next;
        pNode->next = temp->next;
        delete temp;
    }

---

16、输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

/*
struct RandomListNode {
 int label;
 struct RandomListNode *next, *random;
 RandomListNode(int x) :
 label(x), next(NULL), random(NULL) {
 }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
if( NULL == pHead){
return NULL;
        }

// 保存新链表的头
        RandomListNode* new_head = new RandomListNode(pHead->label);
        RandomListNode* cur_node_new_list = new_head;// 指向新链表的当前结点，用来遍历
        RandomListNode* cur_node_old_list = pHead;   // 指向旧链表的当前结点，用来遍历

// 构建一个 map ，保存两个链表相同位置上的结点指针
map<RandomListNode*, RandomListNode*> map_random;
        map_random.insert(make_pair( cur_node_old_list, cur_node_new_list));// 插入第一个结点

while(cur_node_old_list->next != NULL){
// 创建一个新的结点
            RandomListNode* temp = new RandomListNode(cur_node_old_list->next->label);
// 连接到新链表，并向后移动 cur 指针
            cur_node_new_list->next = temp;
            cur_node_new_list = temp;

// 当前结点数据复制后，向后推进原链表的 cur
            cur_node_old_list = cur_node_old_list->next;
// 将新节点与对应原结点指针插入 map
            map_random.insert(make_pair(cur_node_old_list, cur_node_new_list));
        }
// 遍历原链表，复制随机指针指向
        cur_node_old_list = pHead;
        cur_node_new_list = new_head;

while(cur_node_old_list){
// 在map中取原结点的随机指针指向
            cur_node_new_list->random = map_random[cur_node_old_list->random];
            cur_node_new_list = cur_node_new_list->next;
            cur_node_old_list = cur_node_old_list->next;
        }

return new_head;
    }
};

---

17、两个栈实现一个队列

class Solution
{
public:
void push(int node) {
        stack1.push(node);
    }

int pop() {
if(stack2.empty()){
while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
int ret = stack2.top();
        stack2.pop();
return ret;
    }


private:
stack<int> stack1;
stack<int> stack2;
};

---

18、两个队列实现一个栈

#include<queue>
class Stack
{
public:
void push(int data)
    {
if (queue1.empty())
            queue2.push(data);
else if (queue2.empty())
            queue1.push(data);
    }
int pop()
    {
int ret;
if (queue1.empty())
        {
while (queue2.size() > 1)
            {
                queue1.push(queue2.front());
                queue2.pop();
            }
            ret = queue2.front();
            queue2.pop();
        }
else if (queue2.empty())
        {
while (queue1.size() > 1)
            {
                queue2.push(queue1.front());
                queue1.pop();
            }
            ret = queue1.front();
            queue1.pop();
        }
return ret;
    }
private:
queue<int> queue1;
queue<int> queue2;
};

void test_queue()
{
    Stack q;
    q.push(1);
    q.push(2);
    q.pop();
    q.push(3);
    q.pop();
    q.push(4);
    q.push(5);
    q.pop();
    q.pop();
    q.pop();
}

---

19、替换字符串中的空格为$$$。要求时间复杂度为O(N)
例如：将”talk is cheap show me the code”替换
为”talk$$$is$$$cheap$$$show$$$me$$$the$$$code”。

void space_to_symbol()
{
char str[100] = "talk is cheap show me the code";
    cout << str << endl;
char* start = str;

int space_count = 0;
int old_length = 0;
while (*start)
    {
if (*start == ' ')
            space_count++;
        old_length++;
        start++;
    }
int new_length = old_length + space_count * 2;
while (old_length >= 0)
    {
if (str[old_length] == ' ')
        {
str[new_length--] = '$';
str[new_length--] = '$';
str[new_length--] = '$';
        }
else
        {
str[new_length--] = str[old_length];
        }
        old_length--;
    }
    cout << str << endl;
}

---

20、实现一个栈，要求push pop，min的时间复杂度为O(1)
答：入栈时data 栈每次都需要压入，min 栈，如果为空则压入，如果不为空，用min栈顶元素和压入的元素比较，如果压入的元素小于min栈顶的值，则压入min栈，并且压入data栈。
出栈，如果两个栈数据相同，则同时pop，否则只有data出栈

class Solution {
public:
void push(int value) {
if(s_min.empty()){
            s_min.push(value);
        }
else{
if(s_min.top() > value)
                s_min.push(value);
        }
        data.push(value);
    }
void pop() {
if(data.top() == s_min.top()){
            data.pop();
            s_min.pop();
        }
else{
            data.pop();
        }
    }
int top() {
return data.top();
    }
int min() {
return s_min.top();
    }
private:
stack<int> s_min;
stack<int> data;
};

---

21、查找一个字符串中第一个只出现两次的字符。
比如 “abcdefabcdefabc” 中第一个只出现两次为‘d’,
要求空间复杂度O(1),时间复杂度O(1)

char find_char_two(const char* str)
{
    assert(str);
    const char* start = str;
char count[256]; // 因为字符只有256 不管你字符串多长，都是O(1)的空间复杂度
    memset(count, 0, sizeof(count));
// 统计次数
while (*start)
    {
count[*start]++;
        start++;
    }
    start = str;
while (*start)
    {
if (count[*start] == 2)
        {
return *start;
        }
        start++;
    }
return -1;
}

int main()
{
//space_to_symbol();
char c = find_char_two("abcdefabcdefabc");
    cout << c << endl;
return 0;
}

---

22、输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

class Solution {
public:
bool IsPopOrder(vector<int> v_push,vector<int> v_pop) {
if(v_push.size() == 0 || v_pop.size() == 0 || v_push.size() != v_pop.size())
return false;

int idx_push = 0;
int idx_pop = 0;
int size = v_push.size();
stack<int> s;
while(idx_push < size)
        {
            s.push(v_push[idx_push++]);
while(!s.empty() && s.top() == v_pop[idx_pop] && idx_pop < size)
            {
                s.pop();
                idx_pop++;
            }
        }
return s.empty();
    }
};

---

23、输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

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

---

24、 二叉树的层序遍历

/*
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> v;
if ( NULL == root)
return v;
queue<TreeNode*> q;
        q.push(root);
while(!q.empty()){
            TreeNode* temp = q.front();
            v.push_back(temp->val);
            q.pop();
if(temp->left)
                q.push(temp->left);
if(temp->right)
                q.push(temp->right);
        }
return v;

    }
};

---

25、给定一个整数N， 那么N的阶乘N！，末尾有多少个0呢？例如：N=10，N！ = 3628800，末尾有两个0。

int fac_zero_num(int num)
{
int count = 0;
int i = 1;
for (; i <= num; i++)
    {
int j = i;
while (j % 5 == 0){
count++;
            j /= 5;
        }
    }
return count;
}

int fac_zero_num_2(int num)
{
int ret = 0;
while (num)
    {
        ret += num / 5;
        num /= 5;
    }
return ret;
}

---

26、求二叉树叶子结点的个数

int leaf_size(node* pnode)
    {
if (NULL == pnode)
return 0;
if (NULL == pnode->left && NULL == pnode->right)
return 1;
return leaf_size(pnode->left) + leaf_size(pnode->right);
    }

---

27、求二叉树第K层结点个数，设定根节点为第一层

int num_K_node(node*pnode, int k)
    {
if (pnode == NULL || k <= 0)
return 0;
if (pnode && k == 1)
return 1;
return num_K_node(pnode->left, k-1) + num_K_node(pnode->right, k-1);
    }

---

28、一个数组中有一个数字的次数超过了数组的一般，求出这个数字。如：int a[] = {2，3，2，2，2，2，2，4，1，2，3};

class Solution {
public:

bool check(const vector<int>& v, int num){
int count = 0;
for(int i = 0; i < v.size(); ++i){
if(num == v[i])
                count++;
        }
if( count*2<=v.size())
return false;
return true;
    }
int MoreThanHalfNum_Solution(vector<int> numbers) {

if(numbers.size() == 0){
cout << 0;
return 0;
        }
int count = 1;

int length = numbers.size();

int ret = numbers[0];
int i = 1;
for(; i < length; ++i){
if(count == 0){
                ret = numbers[i];
                count = 1;
            }
else if (ret == numbers[i])
                count++;
else
                count--;
        }

if(check(numbers, ret)){
cout << ret;
return ret;
        }
cout << 0;
return 0;
    }
};

---

day11

29、求二叉树的高度

int TreeHeight(Node* pnode)
{
if( NULL == pnode)
        return 0;
int left= 1 + height(pnode->left);
int right = 1 + height(pnode->right);
    return left > right ? left : right;
}

---

30、销毁一颗二叉树

void  Destroy(Node*& root)
{
if(root)
    {
        Destroy(root->left);
        Destroy(root->right);
delete root;
        root = NULL;
    }
}

---

31、链表翻转。给出一个链表和一个数K，比如链表1->2->3->4->5->6->NULL，K=2，翻转后 2->1->4->3->6->5->NULL，若K=3，翻转后3->2->1->6->5->4->NULL，若K=4，翻转后4->3->2->1->5->6->NULL，用程序实现ListNode* RotateList(ListNode* list, size_t k)。

递归实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
// 为空或一个结点或 K 不符合 规范直接返回原head
if( NULL == head || NULL == head->next || k < 2)
return head;

// 以k为步数，找到逆置前下一组的头指针
        ListNode* next_group_head = head;
for(int i = 0; i < k; ++i){
if(next_group_head)   
                next_group_head = next_group_head->next;
else // 剩余结点数小于K 不够分一组时，下一组的头指针就是head
return head;
        }

// 递归去处理剩余组，直到不够 K 个结点，即求出下一组逆置后的头指针
        ListNode* new_next_group_head = reverseKGroup(next_group_head, k);
        ListNode* prev = NULL ,* cur = head;
// 开始逆置处理当前组，从 head --- next_group_head下一组逆置前的第一个结点
while(cur != next_group_head){
            ListNode* next = cur->next; // 保存下一个结点
if(prev == NULL)      // 为空则将当前组的一个结点指向下一组逆置后的第一个结点
                cur->next = new_next_group_head;
else                  // 不为空则表示逆置当前组的结点，指向prev即可
                cur->next = prev;
            prev = cur;   // 向后推进，直到走完当前组
            cur = next;           
        }
// 返回逆置后的头指针
return prev;
    }
};

迭代解法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
     ListNode *reverseKGroup(ListNode *head, int k)
    {
// 特殊情况处理
if (NULL == head || NULL == head->next || k < 2)
return head;

        ListNode* prev = NULL, *pcur = head, *newhead = NULL;

// 遍历链表，处理每一组
while (pcur){

// 找到下一组的头
            ListNode* next_group_head = pcur;
int i = 0;
for (; next_group_head && i < k; i++){
                next_group_head = next_group_head->next;
            }
// 处理不足K 个元素的组
if (i < k ){
// 防止K 大于链表结点
if (newhead == NULL)
                    newhead = head;
break;
            }
// 将当前分组[pcur, next_group_head) 逆置，并返回逆置后的头指针
            ListNode* tmp = reverse(pcur, next_group_head);

if (prev == NULL) // 第一个分组需要更新新的头指针
                newhead = tmp;
else  // 后续只需要将上一个分组的最后一个结点next 指向当前分组逆序后的的头指针
                prev->next = tmp;
// 当前分组的最后一个结点next 指向下一个分组开始
            pcur->next = next_group_head;
// prev 保存当前分组的最后一个结点
            prev = pcur;
// pcur 向后推进到下一个分组的开始
            pcur = next_group_head;
        }
return newhead;
    }
// [start, end)
    ListNode* reverse(ListNode* start, ListNode* end)
    {
        ListNode* prev = NULL;
        ListNode* pcur = start;
while (pcur != end){
            ListNode* next = pcur->next;
            pcur->next = prev;
            prev = pcur;
            pcur = next;
        }
return prev;
    }
};

---

day12

32、输入一棵二叉树，判断该二叉树是否是平衡二叉树。
（1）、方法1
前序遍历的思想，每到一个结点求出其左右子树的深度，判断差是否大于-1或小于1。
然后递归判断左右子树。效率较低，因为求高度时有很多结点被重复遍历。

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot == NULL)
            return true;

int left_depth = Depth(pRoot->left);
int right_depth = Depth(pRoot->right);
int diff =  left_depth - right_depth;
if( diff > 1 || diff < -1)
            return false;
        return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);

    }

int Depth(TreeNode* node){
if( NULL == node)
            return 0;
int left = Depth(node->left);
int right = Depth(node->right);

        return (left > right ? left + 1 : right + 1);
    }
};

（2）、方法2
采用后序遍历的方式，通过一个引用参数从叶子结点往上求树的高度，较少遍历结点次数。如果差符合条件时，更新参数中传来的height，并返回true。

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
int index = 0;
        return IsBalanced(pRoot, index);
    }

    bool IsBalanced(TreeNode* node, int& height){
if( node == NULL){
            height = 0;
            return true;
        }

int left = 0;
int right = 0;
if( IsBalanced(node->left, left) && IsBalanced(node->right, right)){
int diff = left - right;
if(diff >= -1 && diff <= 1)
            {
                height = 1 + (left > right ? left : right);
                return true;
            }
        }
        return false;
    }
};

---

33、求一颗二叉树的镜像

class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot == NULL)
return;
        std::swap(pRoot->left, pRoot->right);
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
};

---

34、在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

从右上角开始

class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if( array.size() == 0)
return false;
int rows = array.size();
int cols = array[0].size();

int idx_row = 0;
int idx_col = cols-1;
while( idx_row <rows && idx_col >= 0){
if(array[idx_row][idx_col] == target){
return true;
            }
else if(array[idx_row][idx_col] < target )
                    idx_row++;
else
                    idx_col--;
        }
return false;
    }
};

从左下角开始

class Solution {
public:
bool Find(int target, vector<vector<int> > array) {

if(array.size() == 0)
return false;
int row_size = array.size();
int col_size = array[0].size();


int idx_row = row_size - 1;
int idx_col = 0;

while(idx_col < col_size && idx_row >= 0)
        {
if(target == array[idx_row][idx_col])
return true;
else if( target > array[idx_row][idx_col])
                ++idx_col;
else
                --idx_row;
        }
return false;
    }
};

---

day13

35、二叉树的前序、中序和后序非递归遍历

前序
借助栈来实现。

 void PreOrder( node* pnode)
    {
if (pnode == NULL)
return;
stack<node*> s;
        s.push(pnode);
while (!s.empty())
        {
const node* tmp = s.top();
cout << tmp->data << " ";
            s.pop();
if (tmp->right)
                s.push(tmp->right);
if (tmp->left)
                s.push(tmp->left);
        }
    }

中序

void inOrder(node* root)
{
if (root == NULL)
return;
stack<node*> s;
    node*  pcur = root;
while (!s.empty() || pcur)
    {
while (pcur)
        {
            s.push(pcur);
            pcur = pcur->left;
        }
        node* tmp = s.top();
cout << tmp->data << " ";
        s.pop();
if (tmp->right)
        {
            pcur = tmp->right;
        }
    }
}

后序

void postOrder(node* root)
{
if (root == NULL)
return;
stack<node*> s;
    node* pcur = root;
    node* prev = NULL;

while (pcur || !s.empty())
    {
while (pcur)
        {
            s.push(pcur);
            pcur = pcur->left;
        }
        node* tmp = s.top();
if (NULL == tmp->right || prev == tmp->r
        {
cout << tmp->data << " ";
            s.pop();
            prev = tmp;
        }
else
        {
            pcur = tmp->right;
        }
    }

}

---

36、已知集合A和B的元素分别用不含头结点的单链表存储，函数difference(
)用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A={5,10,20,15,25,30}，集合B={5,15,35,25}，完成计算后A={10,20,30}。

void difference(node* & l1, node* l2)
{
    node* pa = l1;
    node* pb = l2;
    node* prev = NULL;
while(pa)
    {
        node* pfind = pb;
while(pfind && pa->data != pfind->data)
            pfind = pfind->next;
if(pfind)
        {
if(prev == NULL)
            {
                l1 = pa->next;
            }
else
            {
                prev->next = pa->next;
            }
            node* tmp = pa;
            pa = pa->next;
            delete tmp;
        }
else
        {
            prev = pa;
            pa = pa->next;
        }
    }
}

---

day14

37、判断一个节点是否在一棵二叉树中/在二叉树中查找某个值

// 查找某个值
 node* Find(node* root, const T& key)
 {
if (root == NULL)
return NULL;
if (root->data == key)
return root;
     TreeNode<T>* ret = Find(root->left, key);
if (ret)
return ret;
return Find(root->right, key);
 }

// 判断某个结点是否存在
bool InTree(TreeNode<T>* root, TreeNode<T>* pnode)
{
if (root == NULL || pnode == NULL)
return false;
if (root == pnode)
return true;
    bool ret = InTree(root->left,pnode);
if (ret)
return ret;
return InTree(root->right, pnode);
}

---

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

/*
struct TreeNode {
 int val;
 struct TreeNode *left;
 struct TreeNode *right;
 TreeNode(int x) :
 val(x), left(NULL), right(NULL) {
 }
};*/
class Solution {

    bool is_subtree(TreeNode* pRoot1, TreeNode* pRoot2){
if( NULL == pRoot2 )
return true;
if (NULL == pRoot1  || pRoot1->val != pRoot2->val)
return false;
return is_subtree(pRoot1->left, pRoot2->left) && is_subtree(pRoot1->right, pRoot2->right);
    }
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
if( NULL == pRoot1 || NULL == pRoot2)
return false;
        bool ret = false;
if(pRoot1->val == pRoot2->val )
            ret = is_subtree(pRoot1, pRoot2);
if(!ret)
            ret = HasSubtree(pRoot1->left, pRoot2);
if(!ret)
            ret = HasSubtree(pRoot1->right, pRoot2);
return ret;
    }
};

---

day15

39、判断一棵树是否是完全二叉树

bool judge_full_binary_tree(TreeNode<char>* proot)
{
if (NULL == proot)
return true;
bool must_has_child = false;
queue<TreeNode<char>*> q;
    q.push(proot);
while (!q.empty())
    {
        TreeNode<char>* tmp = q.front();
        q.pop();
if (must_has_child)
        {
if (tmp->left || tmp->right)
return false;
        }
else
        {
if (tmp->left && tmp->right)
            {
                q.push(tmp->left);
                q.push(tmp->right);
            }
else if (tmp->left && tmp->right == NULL)
            {
                must_has_child = true;
                q.push(tmp->left);
            }
else if (tmp->left == NULL && tmp->right)
return false;
        }
    }
return true;
}

---

40、求二叉树中两个节点的最近公共祖先。

要求考虑以下三种种情况，给出解决方案，并解决：

1：二叉树每个节点有parent（三叉链）

2：二叉树是搜索二叉树。

3：就是普通二叉树。（尽可能实现时间复杂度为O（N））

（1）、二叉树每个节点有parent（三叉链）

// 获取链表长度
int GetLength(TreeNode* pnode)
{
    int length = 0;

while (pnode)
    {
        length++;
        pnode = pnode->parent;
    }

return length;
}

// 两个节点的最近公共祖先。 
TreeNode* common_ancestor(TreeNode* node1, TreeNode* node2)
{
if (NULL == node1 || NULL == node2)
return NULL;

    int list1_length = GetLength(node1);
    int list2_length = GetLength(node2);
    int diff = list1_length - list2_length;
if (diff > 0)
    {
while (diff--)
            node1 = node1->parent;
    }
else if (diff < 0)
    {
while (diff++)
            node2 = node2->parent;
    }

while (node1 != node2)
    {
        node1 = node1->parent;
        node2 = node2->parent;
    }

return node1;
}

（2）、二叉树是搜索二叉树

循环

BSTreeNode* common_ancestor(BSTreeNode* root,BSTreeNode* node1, BSTreeNode* node2)
{
if (node1 == NULL || node2 == NULL || root == NULL)
return NULL;


    BSTreeNode* pcur = root;

while (pcur)
    {

if (pcur->data < node1->data &&
            pcur->data < node2->data)
            pcur = pcur->right;
else if (pcur->data > node1->data &&
            pcur->data > node2->data)
            pcur = pcur->left;
else
return pcur;
    }
return NULL;
}

---

3：就是普通二叉树。（尽可能实现时间复杂度为O（N））

普通方法时间复杂度高一些

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {

bool GetPath(vector<TreeNode*>& v, TreeNode* root, TreeNode* p)
    {
if(root == p)
        {
            v.push_back(root);
return true;
        }

if(NULL == root)
return false;

        v.push_back(root);
if(GetPath(v,root->left,p))
return true;
if(GetPath(v,root->right,p))
return true;
        v.pop_back();
return false;
    }

    TreeNode* GetCommNode(vector<TreeNode*>& v1, vector<TreeNode*>& v2)
    {
        TreeNode* ret = NULL;

int i = 0;
int j = 0;
while(i < v1.size() && j < v2.size())
        {
if(v1[i] == v2[j])
                ret = v1[i];
            i++;
            j++;
        }
return ret;
    }

public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

if( NULL == root || p == NULL || q == NULL)
return NULL;
vector<TreeNode*> path1;
        GetPath(path1,root, p);

vector<TreeNode*> path2;
        GetPath(path2,root, q);

return GetCommNode(path1,path2);


    }
};

递归方法O(N)

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if( NULL == root)
            return NULL;
if( root == p || root == q )
            return root;

        TreeNode* left = lowestCommonAncestor(root->left, p,q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

if(left && right)
            return root;
else 
            return left ? left : right;
    }
};

---

day16

---

41、由前序遍历和中序遍历重建二叉树（前序:1 2 3 4 5 6 中序 3 2 4 1 6 5）

class Solution 
{
private:
    TreeNode* ConTree(const vector<int>& pre, int startPre, int endPre, 
const vector<int>& vin, int startIn,  int endIn )
    {
if(startPre > endPre || startIn > endIn)
return NULL;
        TreeNode* root = new TreeNode(pre[startPre]);

for(int i = startIn; i <= endIn; ++i)
        {
if (vin[i] == root->val){
                root->left = ConTree(pre, startPre + 1, startPre+i-startIn,
                                     vin, startIn,  i - 1);
                root->right = ConTree(pre, startPre+i-startIn+1, endPre, 
                                      vin, i+1, endIn);
            }
        }
return root;
    }
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) 
    {

if( pre.size() != vin.size() || pre.empty() || vin.empty())
return NULL;
        TreeNode* root = ConTree(pre, 0, pre.size() - 1, vin, 0, vin.size()-1);
return root;
    }


};

---

42、C语言模拟实现C++继承和多态

提示：C 实现一个 struct A 和 stuct B 包含一个 int 成员 a 和 b，要求达到B 继承 A 的效果，也就是 B里面包含一个 A，并且能达到多态的效果，也就是一个 A* p 指向一个指向A 调的是 A 的函数，指向 B 调的是 B 的函数。

// 父类虚表
typedef struct vtblA
{
void(*pfun1)();
}vtblA;

// 子类虚表
typedef struct vtblB
{
    vtblA vtbl;
// 指向子类特有的成员函数
void(*fun2_B)(int);
}vtblB;

// 父类虚函数
void fun1()
{
printf("父类fun1\n");
}
// 子类重写父类虚函数fun1
void fun1_B()
{
printf("子类重写fun1\n");
}

// 子类特有函数
void fun2_B(int)
{   
printf("子类特有fun2\n");
}

// 父类
typedef struct A
{
    vtblA* pvtl;// 父类虚表指针
int a;      // 父类数据成员
}A;

// 子类
typedef struct B
{
    A base_a; // 从父类继承而来的基类A
int b;    // 子类数据成员
}B;

// 父类虚表结构
vtblA g_vtbl_A = {&fun1};
// 子类虚表结构
vtblB g_btbl_B = { {&fun1_B}, &fun2_B };

// 父类构造函数
void init_A(A* pa)
{
    pa->a = 10;
    pa->pvtl = &g_vtbl_A;
}
// 子类构造函数
void init_B(B* pb)
{
    init_A((A*)pb);
    pb->base_a.pvtl = (vtblA*)&g_btbl_B;
    pb->b = 20;
}
// 测试多态函数
void dosomething(A* p)
{
// 如果p指向子类对象那么输出结果就是重写后的函数pfun1
    vtblA* pvtbl = (vtblA*)p->pvtl;
    (*pvtbl).pfun1();
}
int main()
{

// 定义子类对象并构造
    B b;
    init_B(&b);
// 调用父类自己的函数
    vtblB* pvtvl = (vtblB*)b.base_a.pvtl;
    (*pvtvl).fun2_B(5);
// 定义父类指针
    A* pa = (A*)&b;
// 测试多态
    dosomething(pa);
return 0;
}