@ShawnNg 2018-07-25T05:05:13.000000Z 字数 32453 阅读 1369

剑指 offer面试题

面试

1. 二维数组中的查找

题目描述

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

解题思路

从矩阵的左下角开始搜索，因为左下角的元素往右是递增，往左是递减。如果遇到比target大，就往上找，如果比tagert小就往右走，如果找到了则直接输出。时间复杂度是O(n+m)。

代码

class Solution{
public:
    bool Find(int target, vector<vector<int> > array){
        if(array.size()==0) return false;
        int n=array.size(), m=array[0].size();
        int i=n-1, j=0;
        while(i>=0 && j<m){
            if(target==array[i][j]) return true;
            else if(target>array[i][j]) ++j;
            else --i;
        }
        return false;
    }
};

2. 替换空格

题目描述

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

解题思路

先计算好替换后的字符串长度，然后将字符串从后开始拷贝到替换后的位置，遇到空格就替换%20，当两个指针相遇的时候就是替换成功。

代码

class Solution{
public:
    void replaceSpace(char *str, int length){
        if(length==0) return;
        int countSpace=0;
        for(int i=0; i<length; ++i){
            if(str[i]==' ') ++countSpace;
        }
        int j=length+countSpace*2-1, i=length-1;
        while(i!=j){
            if(str[i]==' ') {
                str[j--]='0';
                str[j--]='2';
                str[j--]='%';
            }else{
                str[j--]=str[i];
            }
            --i;
        }
    }
};

3.从尾到头打印链表

题目描述

输入一个链表，从尾到头打印链表每个节点的值。

解题思路

方法1：直接用递归，从最后一个节点开始打印起。
方法2: 用栈来存储，然后全部弹出，放入数组。

代码

方法1

class Solution{
public:
    vector<int> printListFromTailToHead(ListNode* head){
        vector<int> result;
        printListFromTailToHeadCore(head, result);
        return result;
    }
    void printListFromTailToHeadCore(ListNode* head, vector<int> &array){
        if(head==NULL) return ;
        printListFromTailToHeadCore(head->next, array);
        array.push_back(head->val);
    }
};

方法2

class Solution{
public:
    vector<int> printListFromTailToHead(ListNode* head){
        vector<int> array;
        if(head==NULL) return array;
        stack<int> stk;
        while(head){
            stk.push(head->val);
        }
        while(!stk.empty()){
            array.push_back(stk.top());
            stk.pop();
        }
        return array;
    }
};

4.重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解题思路

前序的第一个节点为根结点，按照根节点将中序一分为二，再根据中序左右节点数将前序一分为二。然后将左右部分递归，返回根节点即可。

代码

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return reConstructCore(pre, 0, pre.size()-1, vin, 0, vin.size()-1);
    }
    TreeNode* reConstructCore(vector<int> pre, int preLeft, int preRight, vector<int> vin, int vinLeft, int vinRight){
        if(preLeft>preRight) return NULL;
        // find the split point of vin.
        int vinMid = vinLeft;
        for(;vinMid<=vinRight; ++vinMid){
            if(pre[preLeft]==vin[vinMid]) break;
        }
        // construct the tree.
        TreeNode *root = new TreeNode(pre[preLeft]);
        root->left = reConstructCore(pre, preLeft+1, preLeft+vinMid-vinLeft, vin, vinLeft, vinMid-1);
        root->right = reConstructCore(pre, preLeft+vinMid-vinLeft+1, preRight, vin, vinMid+1, vinRight);
        return root;
    }
};

5.用两个栈实现队列

题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

解题思路

用一个栈来接受push，一次性pop出来，一次性push到另外一个栈。

代码

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 result = stack2.top();
        stack2.pop();
        return result;
    }
private:
    stack<int> stack1;
    stack<int> stack2;
};

6. 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路

由于数组旋转部分永远在后面，所以我们只需要找到原数组和旋转部分的交界处即可。用二分法，中间元素不断跟最右的元素比较。如果大于最右，则交界处在右边，如果小于最右，交界处在左边，如果等于最右，则最右往左走一步。

代码

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int low=0, high=rotateArray.size()-1;
        while(low<high){
            int mid = low + (high-low)/2;
            if(rotateArray[mid]>rotateArray[high]){
                low=mid+1;
            }else if(rotateArray[mid]<rotateArray[high]){
                high=mid;
            }else {
                --high;
            }
        }
        return rotateArray[low];
    }
};

7.斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39

解题思路

斐波那契数列 $f(n)=f(n-1)+f(n-2)$ ，当 $n\le1$ 时， $f(n)=n$ 。所以直接用递推公式写出结果。不过需要思考一下停止条件。

代码

class Solution {
public:
    int Fibonacci(int n) {
        if(n<2) return n;
        int f0=0, f1=1;
        for(int i=2; i<=n; ++i){
            int f2=f0+f1;
            f0=f1;
            f1=f2;
        }
        return f1;
    }
};

8.跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解题思路

这题就是斐波那契数列。

9.矩形覆盖

题目描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

解题思路

还是一个斐波那契数列。

10. 变态跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解题思路

递推公式为 $f(n)=f(n-1)+f(n-2)+...+f(1)$ ，可以推出 $f(n)=2f(n-1)$ ，由于 $f(1)=1$ ，可以退出等比数列 $f(n)=2^{(n-1)}$ 。需要注意n=0的情况。

代码

class Solution {
public:
    int jumpFloorII(int number) {
        if(number==0) return 0;
        return pow(2, number-1);
    }
};

11. 二进制中1的个数

题目描述

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

解题思路

每次 $x=x \& (x-1)$ 的操作都会让x少一个1，重复此操作直到x为0。但是要注意x是负数的情况，要将其转为正数。

代码

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

12. 数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

解题思路

要考虑base=0的情况，exponent=0的情况，还有exponent正负数的情况。用二进制去移位，得到结果。

代码

class Solution {
public:
    double Power(double base, int exponent) {
        if(base==0) return 0;
        if(exponent==0) return 1;
        double result=1;
        int exp=abs(exponent);
        while(exp){
            if(exp&1) result*=base;
            base *=base;
            exp >>=1;
        }
        return exponent>0?result:1/result;
    }
};

13. 调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

解题思路

因为要求数字的相对位置不能变，如果可以变的话直接用快排的思想，O(n)的时间复杂度，O(1)的空间复杂度。
方法1: O(n)的时间复杂度和O(n)的空间复杂度，用另外一个数组存储。
方法2: O(n^2)的时间复杂度和O(1)的空间复杂度，用冒泡排序，遇到一个偶数后面是奇数就交换。

代码

方法1:

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        if(array.size()<2) return;
        vector<int> result(array.size());
        int low=0, high=array.size()-1;
        for(int i=0, j=array.size()-1;i<array.size(); ++i, --j){
            if(array[i]%2==1) result[low++]=array[i];
            if(array[j]%2==0) result[high--]=array[j];
        }
        for(int i=0; i<array.size(); ++i) array[i] = result[i];
    }
};

方法2:

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int length = array.size();
        for(int i=0; i<length-1; ++i){
            for(int j=0; j<length-1-i; ++j){
                if(array[j]%2==0&&array[j+1]%2==1) 
                    swap(array[j], array[j+1]);
            }
        }
    }
};

14.链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

解题思路

先用一个快指针往前走k步，然后头指针跟快指针一起走，快指针到尾的时候头指针就是倒数第
k个。但是要注意少于k个结点的情况。

代码

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* fast=pListHead;
        while(fast&&k>0){
            fast=fast->next;
            --k;
        }
        if(k>0) return NULL;
        while(fast){
            fast=fast->next;
            pListHead=pListHead->next;
        }
        return pListHead;
    }
};

15.反转链表

题目描述

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

解题思路

要注意一个结点的情况

代码

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL||pHead->next==NULL) return pHead;
        ListNode* pre=pHead, *mid=pHead->next, *next;
        pre->next=NULL;
        while(mid){
            next=mid->next;
            mid->next=pre;
            pre=mid;
            mid=next;
        }
        return pre;
    }
};

16. 合并两个排序得链表

题目描述

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

解题思路

用两个指针指向未扫描的位置，一个指针指向新链表最后一个。要注意得是，要新建一个辅助头实体。

代码

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==NULL) return pHead2;
        if(pHead2==NULL) return pHead1;
        ListNode *newHead=new ListNode(-1);
        ListNode *p = newHead;
        while(pHead1&&pHead2){
            if(pHead1->val < pHead2->val) {
                p->next=pHead1;
                pHead1=pHead1->next;
            }else{
                p->next=pHead2;
                pHead2=pHead2->next;
            }
            p=p->next;
        }
        while(pHead1){
            p->next=pHead1;
            pHead1=pHead1->next;
        } 
        while(pHead2){
            p->next=pHead2;
            pHead2=pHead2->next;
        }
        return newHead->next;
    }
};

17.树的子结构

题目描述

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

解题思路

先将两棵树序列化，然后判断小的树是否在大的树里面。要注意把序列化后的最后的空结点剪掉。并且空树不是子结构，要特殊处理。

代码

class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(pRoot2==NULL) return false;
        string str1=cutEnd(serialize(pRoot1));
        string str2=cutEnd(serialize(pRoot2));
        return str1.find(str2) != string::npos;
    }
    string serialize(TreeNode* root){
        if(root==NULL) return "#";
        string rootStr=to_string(root->val);
        string leftStr=serialize(root->left);
        string rightStr=serialize(root->right);
        return rootStr + "," + leftStr + "," + rightStr;
    }
    string cutEnd(string str){
        int i=str.size()-1;
        for(; i>=0; --i){
            if(str[i]!='#'&&str[i]!=',') break;
        }
        return str.substr(0, i+1);
    }
};

18.二叉树的镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:

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

解题思路

后序遍历，将二叉树的左右结点交换。

代码

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

19. 顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

解题思路

对于0的情况先处理，然后得到宽、高和层数。按照层数做四个循环，边界条件一定要注意，而且要注意的是只有一行或者一竖的情况。

代码

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> result;
        if(matrix.size()==0) return result;
        if(matrix[0].size()==0) return result;
        int n=matrix.size(), m=matrix[0].size(), level = (min(n,m)+1)/2;
        for(int i=0; i<level; ++i){
            int left=i, right=m-1-i, top=i, bottom=n-1-i;
            int j=left, k=top;
            for(;j<=right; ++j) result.push_back(matrix[k][j]);
            for(--j, ++k;k<=bottom; ++k) result.push_back(matrix[k][j]);
            for(--k, --j;top!=bottom&&j>=left; --j) result.push_back(matrix[k][j]);
            for(++j, --k;left!=right&&k>=top+1; --k) result.push_back(matrix[k][j]);
        }
        return result;
    }
};

20. 包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

解题思路

每次push用另外一个栈来记录min。一定要注意栈为空的时候要做判断。

代码

class Solution {
public:
    stack<int> stk;
    stack<int> minStk;
    void push(int value) {
        stk.push(value);
        if(minStk.empty()||minStk.top()>value)
            minStk.push(value);
        else
            minStk.push(minStk.top());
    }
    void pop() {
        stk.pop();
        minStk.pop();
    }
    int top() {
        return stk.top();
    }
    int min() {
        return minStk.top();
    }
};

21. 栈的压入、弹出序列

题目描述

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

解题思路

用一个栈来模拟push，每次栈顶遇到弹出序列的未弹出首元素时，就将栈顶弹出，最终如果栈为空，则说明是存在该弹出序列的。

代码

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size()==0||pushV.size()!=popV.size()) return false;
        stack<int> stk;
        int i=0, j=0;
        while(i<popV.size()){
            if(stk.empty()||stk.top()!=popV[i]){
                stk.push(pushV[j]);
                ++j;
            }else{
                stk.pop();
                ++i;
            }
        }
        return stk.empty();
    }
};

22. 从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

解题思路

用队列来实现层次遍历，注意异常检测。

代码

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

23. 二叉搜索树的后序遍历序列

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

解题思路

二叉搜索树的后序遍历的根节点一定在序列末端。并且存在一个连续序列比根节点小，剩下的连续序列比根节点大。如果不满足条件就返回false，如果满足就分成两个序列递归，一直到序列数量等于1。

代码

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()==0) return false;
        return VerifyCore(sequence, 0, sequence.size()-1);
    }
    bool VerifyCore(vector<int> sequence, int low, int high){
        if(low>=high) return true;
        int root=high, left=low, right=high-1;
        --high;
        while(left<=high && sequence[left]<sequence[root]) ++left;
        while(right>=low && sequence[right]>sequence[root]) --right;
        if(left!=right+1) return false;
        return VerifyCore(sequence, low, right) && VerifyCore(sequence, left, high);
    }
};

24. 二叉树中和为某一值的路径

题目描述

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

解题思路

用前序遍历，每次将期望值减去根节点，如果在叶子节点上期望值为0则证明成功找到一条路径。

代码

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > result;
        vector<int> path;
        FindPathCore(root, expectNumber, result, path);
        return result;
    }
    void FindPathCore(TreeNode* root, int expectNumber, vector<vector<int> > &result, vector<int> &path){
        if(root==NULL) return;
        path.push_back(root->val);
        expectNumber -= root->val;
        if(root->left==NULL && root->right==NULL &&expectNumber==0) result.push_back(path);
        FindPathCore(root->left, expectNumber, result, path);
        FindPathCore(root->right, expectNumber, result, path);
        path.pop_back();
    }
};

25. 复杂链表的复制

题目描述

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

解题思路

将复制分为三步，第一步将每个节点复制后插入在原节点后面，方便索引。第二步，将新节点的random指向前一个节点的random的next，不过要记得异常检测。第三步，将新节点和旧节点分割。

代码

/*
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(pHead==NULL) return NULL;
        // First
        RandomListNode* tmpOld=pHead, *tmpNew;
        while(tmpOld!=NULL){
            tmpNew=new RandomListNode(tmpOld->label);
            tmpNew->next=tmpOld->next;
            tmpOld->next=tmpNew;
            tmpOld=tmpNew->next;
        }
        // Second
        tmpOld = pHead;
        while(tmpOld!=NULL){
            tmpNew = tmpOld->next;
            if(tmpOld->random!=NULL) tmpNew->random=tmpOld->random->next;
            tmpOld=tmpNew->next;
        }
        // Third
        RandomListNode *newHead=pHead->next;
        tmpOld = pHead, tmpNew = pHead->next;
        while(tmpNew->next!=NULL){
            tmpOld->next = tmpOld->next->next;
            tmpNew->next = tmpNew->next->next;
            tmpNew = tmpNew->next;
            tmpOld = tmpOld->next;
        }
        tmpOld->next=NULL;
        return newHead;
    }
};

26. 二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

解题思路

要求不能创建新节点，所以用一个指针指链表头，一个指链表尾，中序遍历二叉树，遇到一个节点就插入到链表尾部。

代码

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode *pList=NULL, *pListHead=NULL;
        ConvertCore(pRootOfTree, pList, pListHead);
        return pListHead;
    }
    void ConvertCore(TreeNode* root, TreeNode *&pList, TreeNode *&pListHead){
        if(root==NULL) return ;
        ConvertCore(root->left, pList, pListHead);
        if(pList==NULL){
            pList=root;
            pListHead=root;
        }else{
            pList->right=root;
            root->left=pList;
            pList = root;
        }
        ConvertCore(root->right, pList, pListHead);
    }
};

27. 字符串的排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

解题思路

全排列经典算法，每次都从将子串的第一个数和接下来的每个位置交换。

代码

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> result;
        if(str.size()==0) return result;
        PermutationCore(str, 0, str.size(), result);
        sort(result.begin(), result.end());
        return result;
    }
    void PermutationCore(string str, int k, int length, vector<string> &result){
        if(k==length) result.push_back(str);
        for(int i=k; i<length; ++i){
            if(i!=k&&str[i]==str[k]) continue;
            swap(str[i], str[k]);
            PermutationCore(str, k+1, length, result);
            swap(str[i], str[k]);
        }
    }
};

28. 数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解题思路

存储一个计数和记录一个数，不断比较两个数，如果两个数一样就计数加一，如果不一样就减一。如果计数等于0则记录新的数。注意有可能不存在，所以最后还要检测一遍。

代码

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size()==0) return 0; 
        int recordNum = numbers[0];
        int count=1;
        for(int i=1; i<numbers.size(); ++i){
            if(numbers[i]==recordNum) ++count;
            else --count;
            if(count==0) {
                recordNum=numbers[i];
                count=1;
            }
        }
        // if this is the result.
        count = 0;
        for(int i=0; i<numbers.size(); ++i)
            if(numbers[i]==recordNum) count++;
        return count>(numbers.size()/2)?recordNum:0;
    }
};

29. 最小的K个数

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

解题思路

可以用O(n)的时间复杂度做，用快排的思想。
也可以用堆来做，针对大数据的情况下，O(nlogk)的时间复杂度。

代码

快排：

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(input.size()==0||k==0||input.size()<k) return {};
        int i=0, j=input.size()-1, mid;
        while(i<j){
            mid = partition(input, i, j);
            if(mid+1==k) return vector<int> (input.begin(), input.begin()+k);
            else if(mid+1<k) i=mid;
            else j=mid-1;
        }
        return vector<int> (input.begin(), input.begin()+k);
    }
    int partition(vector<int> &input, int low, int high){
        int pivot = input[high];
        while(low<high){
            while(low<high && input[low]<=pivot) ++low;
            swap(input[low], input[high]);
            while(low<high && input[high]>pivot) --high;
            swap(input[low], input[high]);
        }
        input[low] = pivot;
        return low;
    }
};

堆排序：

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(input.size()==0 || k==0 || input.size()<k) return {};
        priority_queue<int> heap;
        for(int i=0; i<k; ++i) heap.push(input[i]);
        for(int i=k; i<input.size(); ++i){
            if(input[i]<heap.top()){
                heap.pop();
                heap.push(input[i]);
            }
        }
        vector<int> result;
        while(!heap.empty()){
            result.push_back(heap.top());
            heap.pop();
        }
        return result;
    }
};

30. 连续子数组的最大和

题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)

解题思路

用一个变量存储全局最大，用另一个变量存储当前和，如果当前和比当前数还要小，那就抛弃之前的和。如果当前和比最大和要大，则替换最大和。

代码

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size()==0) return 0;
        int curSum=array[0], curMax=array[0];
        for(int i=1; i<array.size(); ++i){
            curSum += array[i];
            if(curSum<array[i]) curSum=array[i];
            if(curSum>curMax) curMax=curSum;
        }
        return curMax;
    }
};

31. 整数中1出现的次数（从1到n整数中1出现的次数）

题目描述

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

解题思路

跳过

32. 把数组排成最小的数

题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解题思路

可以看作是一种排序，而且排序的比较方法是看两个数两种合并方法的大小。

代码

class Solution {
public:
    static bool compaire(int a, int b){
        string strA = to_string(a), strB = to_string(b);
        return stoi(strA+strB)<=stoi(strB+strA);
    }
    string PrintMinNumber(vector<int> numbers) {
        sort(numbers.begin(), numbers.end(), compaire);
        string result;
        for(int i=0; i<numbers.size(); ++i){
            result += to_string(numbers[i]);
        }
        return result;
    }
};

33. 丑数

题目描述

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解题思路

将index前的每一个丑数存起来，用三个指针分别存储乘以2、3、5刚好比最后一个丑数要大的那个位置，每次从最后一个丑数乘以2、3、5中三个数的最小值作为最新的丑数，循环到index个。

代码

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<7) return index;
        vector<int> uglyResult(index, 1);
        int ugly2=0, ugly3=0, ugly5=0;
        for(int i=1; i<index; ++i){
            uglyResult[i] = min(uglyResult[ugly2]*2, min(uglyResult[ugly3]*3, uglyResult[ugly5]*5));
            while(uglyResult[ugly2]*2<=uglyResult[i]) ++ugly2;
            while(uglyResult[ugly3]*3<=uglyResult[i]) ++ugly3;
            while(uglyResult[ugly5]*5<=uglyResult[i]) ++ugly5;
        }
        return uglyResult[index-1];
    }
};

34. 第一个只出现一次的字符

题目描述

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置

解题思路

用数组hash表存储即可，遍历字符串，找到第一个值为1的字符。

代码

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int hash[256];
        memset(hash, 0, sizeof(hash));
        for(auto c:str) ++hash[c];
        for(int i=0; i<str.size(); ++i) if(hash[str[i]]==1) return i;
        return -1;
    }
};

35. 数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：

对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5

示例1

输入
1,2,3,4,5,6,7,0
输出
7

解题思路

用归并排序，但是在merge的时候要统计逆序数，从后往前merge，如果第一part的数比第二part要大，则第二part前面的所有数都是逆序对。

代码

class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()<2) return 0;
        vector<int> cache(data.size(), 0);
        return InversePairsCore(data, 0, data.size()-1, cache)%1000000007;
    }
    long long InversePairsCore(vector<int> &data, int low , int high, vector<int> &cache){
        if(low>=high) {
            return 0 ;
        }
        int mid = low + (high-low)/2;
        long long leftCount = InversePairsCore(data, low, mid, cache);
        long long rightCount = InversePairsCore(data, mid+1, high, cache);
        long long curCount = 0;
        int stop1=mid, stop2=high, begin1=low, begin2=mid+1;
        int cacheIdx = high;
        while(begin1<=stop1&&begin2<=stop2){
            if(data[stop1]<data[stop2]){
                cache[cacheIdx--] = data[stop2--];
            }else {
                curCount += (stop2-begin2+1);
                cache[cacheIdx--] = data[stop1--];
            }
        }
        while(begin1<=stop1) cache[cacheIdx--]=data[stop1--];
        while(begin2<=stop2) cache[cacheIdx--]=data[stop2--];
        for(int i=low; i<=high; ++i)
            data[i] = cache[i];
        return leftCount+rightCount+curCount;
    }
};

36. 两个链表的第一个公共结点

题目描述

输入两个链表，找出它们的第一个公共结点。

解题思路

两个指针一起跑，跑到有一个停止，就马上停止，然后另一个没跑完的再带着那个链表的头指针继续跑完，最后短链表和长链表一起跑，跑到一样的就输出。

代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==NULL || pHead2==NULL) return NULL;
        ListNode *tmp1=pHead1, *tmp2=pHead2;
        while(tmp1&&tmp2){
            tmp1 = tmp1->next;
            tmp2 = tmp2->next;
        }
        ListNode *longHead, *shortHead;
        if(tmp1==NULL){
            longHead=pHead2;
            shortHead=pHead1;
            while(tmp2){
                longHead=longHead->next;
                tmp2=tmp2->next;
            }
        }else {
            longHead=pHead1;
            shortHead=pHead2;
            while(tmp1){
                longHead=longHead->next;
                tmp1=tmp1->next;
            }
        }
        while(longHead!=shortHead){
            longHead=longHead->next;
            shortHead=shortHead->next;
        }
        return longHead;
    }
};

37. 数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数。

解题思路

定义两个函数，一个找左起点，一个找右节点，用二分查找。

代码

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.size()==0) return 0;
        return getRightIdx(data, k)-getLeftIdx(data, k)+1;
    }
    int getLeftIdx(vector<int> data, int k){
        int mid, i=0, j=data.size()-1;
        while(i<=j){
            mid = (i+j)/2;
            if(data[mid]>k){
                j=mid-1;
            }else if(data[mid]<k){
                i=mid+1;
            }else{
                if(mid==0||data[mid-1]!=k) return mid;
                j=mid-1;
            }
        }
        return -1;
    }
    int getRightIdx(vector<int> data, int k){
        int mid, i=0, j=data.size()-1;
        while(i<=j){
            mid = (i+j)/2;
            if(data[mid]>k){
                j=mid-1;
            }else if(data[mid]<k){
                i=mid+1;
            }else{
                if(mid==data.size()-1||data[mid+1]!=k) return mid;
                i=mid+1;
            }
        }
        return -2;
    }
};

38. 二叉树的深度

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

解题思路

后序遍历，返回左右子树的最大深度+1。

代码

struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x):
        val(x), left(NULL), right(NULL);
}
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot==NULL) return 0;
        return max(TreeDepth(pRoot->left), TreeDepth(pRoot->right))+1;
    }
};

39. 平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

解题思路

判断左右子树是否是平衡二叉树，并且根据左右子树的高的来判断根节点是否是一颗平衡二叉树。

代码

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int height;
        return IsBalancedCore(pRoot, height);
    }
    bool IsBalancedCore(TreeNode* pRoot, int &height){
        if(pRoot==NULL){
            height=0;
            return true;
        }
        int leftHeight, rightHeight;
        bool isBalanced = IsBalancedCore(pRoot->left, leftHeight) && IsBalancedCore(pRoot->right, rightHeight);
        height = max(leftHeight, rightHeight) + 1;
        return isBalanced && abs(leftHeight-rightHeight)<=1;
    }
};

40. 数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

解题思路

用异或做，并且将异或结果分组，得到两组，分别做抑异或。

代码

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int xorSum = 0;
        for(int a:data) xorSum ^= a;
        int splitBit = 0;
        while(((xorSum>>splitBit)&1)==0){
            ++splitBit;
        }
        *num1=0, *num2=0;
        for(int a:data){
            if((a>>splitBit)&1){
                *num1 ^=a;
            }else {
                *num2 ^=a;
            }
        }
    }
};

41. 和为S的连续正数序列

题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

解题思路

用两个指针表示一个连续序列，sum=(begin+end)*(end-begin+1)/2， begin代表开始的数，end代表结束的数，每次得到的sum与目标一样就加入结果，不一样就调整指针。

代码

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        int curSum=0, length=(sum+1)/2;
        int begin=1, end=2;
        vector<vector<int> > result;
        while(end<=length){
            curSum = (begin+end)*(end-begin+1)/2;
            if(curSum==sum){
                vector<int> seq;
                for(int j=begin; j<=end; ++j){
                    seq.push_back(j);
                }
                result.push_back(seq);
                ++begin;
            }else if(curSum<sum){
                ++end;
            }else {
                ++begin;
            }
        }
        return result;
    }
};

42. 和为S的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。

解题思路

因为排序了，所以直接用左右指针往中间靠拢就可以了。sum比目标大就减右指针，比目标小就加左指针。

代码

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        if(array.size()<=1) return {};
        int low=0, high=array.size()-1;
        while(low<high){
            int curSum = array[low]+array[high];
            if(curSum==sum){
                return {array[low], array[high]};
            }else if(curSum<sum){
                ++low;
            }else{
                --high;
            }
        }
        return {};
    }
};

43. 左旋转字符串

题目描述

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

解题思路

先将旋转部分和剩下部分各自翻转，最后整个字符串翻转。

代码

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if(str.size()==0 || n==0) return str;
        rotate(str, 0, n-1);
        rotate(str, n, str.size()-1);
        rotate(str, 0, str.size()-1);
        return str;
    }
    void rotate(string &str, int left, int right){
        while(left<right){
            swap(str[left++], str[right--]);
        }
    }
};

44. 翻转单词顺序列

题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

解题思路

单词各自翻转，最后整个字符串翻转。

代码

class Solution {
public:
    string ReverseSentence(string str) {
        if(str.size()<=1) return str;
        for(int i=0, j=0; i<str.size(); ++i){
            if(str[i]==' ') {
                rotate(str, j, i-1);
                j=i+1;
            }else if(i==str.size()-1){
                rotate(str, j, i);
            }
        }
        rotate(str, 0, str.size()-1);
        return str;
    }
    void rotate(string &str, int low, int high){
        while(low<high)
            swap(str[low++], str[high--]);
    }
};

45. 扑克牌顺子

题目描述

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。

解题思路

先排序，算出有几个大小王，然后计算相邻数的总间隙不超过大小王个数，如果有两个点数相同的不能算顺子。

代码

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if(numbers.size()==0) return false;
        sort(numbers.begin(), numbers.end());
        int i=0, count=0;
        for(;numbers[i]==0; ++i, ++count);
        for(++i;i<numbers.size(); ++i){
            if(numbers[i]==numbers[i-1]) return false;
            count -= numbers[i]-numbers[i-1]-1;
            if(count<0) return false;
        }
        return true;
    }
};

46. 孩子们的游戏(圆圈中最后剩下的数)

题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

解题思路

每次都少了第m-1个人，假设原来的序号为0到n-1，下次就从m开始。将其重新编号。

m       0
m+1     1
.       .
.       .
n-1   n-m-1
0      n-m
.       .
m-2    n-2

所以假设下一次编号为x，这次为f(x)，则f(x)= (x+m)%n。当剩下一个人的时候，编号为0，所以从0递推起。

代码

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<=1) return n-1;
        int x=0;
        for(int i=2; i<=n; ++i){
            x= (x+m)%i;
        }
        return x;
    }
};

47. 求1+2+3+...+n

题目描述

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

解题思路

用递归，利用短路特性。

class Solution {
public:
    int Sum_Solution(int n) {
        int result=1;
        n-1==0 || (result=Sum_Solution(n-1)+n);
        return result;
    }
};

48. 不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

解题思路

用与和异或，异或相当于位相加，不进位。与再往左移一位相当于进位。

代码

class Solution {
public:
    int Add(int num1, int num2)
    {
        while(num1){
            int tmp = num1^num2;
            num1 = (num1&num2)<<1;
            num2 = tmp;
        }
        return num2;
    }
};

49. 把字符串转换成整数

题目描述

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0
输入描述:
输入一个字符串,包括数字字母符号,可以为空
输出描述:
如果是合法的数值表达则返回该数字，否则返回0
示例1
输入

+2147483647
    1a33

输出

2147483647
    0

解题思路

异常检测非常重要，有左右两边有空格，还有正负号。

代码

class Solution {
public:
    int StrToInt(string str) {
        if(str.size()==0) return 0;
        int i=0, j=str.size()-1;
        while(i<=j&&str[i]==' ') ++i;
        while(str[i]==' ') --j;
        if(i>j) return 0;
        bool isNeg=false;
        if(str[i]=='-') isNeg=true, ++i;
        else if(str[i]=='+') ++i;
        int result=0;
        while(i<=j){
            if(str[i]<'0'||str[i]>'9') return 0;
            result = 10*result + (str[i++]-'0');
        }
        return isNeg?-result:result;
    }
};

50.数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

解题思路

关键点在于0到n-1。所以可以将数字作为索引，索引到某个位置上，将这个位置的数做一些操作，可以标志这个作为索引的那个数字是否重复，并且这个操作是可以恢复的。

代码

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        for(int i=0; i<length; ++i){
            int num = (numbers[i]+length)%length;
            if(numbers[num]<0){
                *duplication=num;
                return true;
            }else
                numbers[num] -= length;
        }
        return false;
    }
};

51. 构建乘积数组

题目描述

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...*A[i-1]A[i+1]...*A[n-1]。不能使用除法。

解题思路

将乘积分成左右两部分，用两个循环来乘，最后再乘起来。

代码

class Solution{
public:
    vector<int> multiply(const vector<int>& A) {
        if(A.size()==0) return A;
        vector<int> B(A.size());
        B[0]=1;
        for(int i=1; i<A.size(); ++i){
            B[i] = B[i-1]*A[i-1];
        }
        vector<int> C(A.size());
        C[A.size()-1]=1;
        for(int i=A.size()-2; i>=0; --i){
            C[i] = C[i+1]*A[i+1];
        }
        for(int i=0; i<A.size(); ++i){
            B[i] *= C[i];
        }
        return B;
    }
};

52. 正则表达式匹配

题目描述

请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

解题思路

关键是分析情况，对于*这种情况做好分析。
有三种情况：
1. 假设模式当前字母是'\0'，而字符串不是，则返回false，否则返回true。
2. 假设模式第二个字符不是'*'
* 直接匹配当前字母，如果一样就字符串和模式都往后移一位。
* 如果不匹配则直接返回false。
3. 假设模式第二个字符是'*'
* 如果当前字符不匹配，则模式往后调两个。
* 如果当前字符匹配了
* 字符串不变，模式往后调两个
* 或者字符串后移一位，模式后移两位
* 或者字符串后移一位，模式不变。

代码

class Solution {
public:
    bool match(char* str, char* pattern)
    {
        if(str==NULL || pattern==NULL) return false;
         return matchCore(str, pattern);
    }
    bool matchCore(char* str, char* pattern){
        if(*pattern=='\0') return *str=='\0';
        if(*(pattern+1)!='*'){
            if(*pattern== *str ||(*pattern=='.'&&*str!='\0'))
                return matchCore(str+1, pattern+1);
            else 
                return false;
        }else {
            if(*pattern== *str ||(*pattern=='.'&&*str!='\0')){
                return matchCore(str, pattern+2) || matchCore(str+1, pattern+2) || matchCore(str+1, pattern);
            }else {
                return matchCore(str, pattern+2);
            }
        }
    }
};

53. 表示数值的字符串

题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

54. 字符流中第一个不重复的字符

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
输出描述:
如果当前字符流没有存在出现一次的字符，返回#字符。

解题思路

用一个hash表存好每个字符出现的位置，如果出现两次置为特殊值。输出的时候遍历hash表，找到最小的位置。

代码

class Solution
{
public:
    int hash[256];
    int index;
    Solution():index(0)
    {
        memset(hash, -1, sizeof(hash));
    }
  //Insert one char from stringstream
    void Insert(char ch)
    {
        if(hash[ch]==-1)
            hash[ch]=index;
        else if(hash[ch]>=0)
            hash[ch]=-2;
        ++index;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        char result='#';
        int minIdx = INT_MAX;
        for(int i=0; i<256; ++i){
            if(hash[i]>=0&&hash[i]<minIdx){
                minIdx=hash[i];
                result = i;
            }
        }
        return result;
    }
};

55. 链表中环的入口结点

题目描述

一个链表中包含环，请找出该链表的环的入口结点。

解题思路

先用快慢指针跑，如果没环快指针就会遇到NULL，如果有环，快慢指针一定会相遇。然后快指针指向头节点，与慢支针一起走，指导相遇。

代码

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

56. 删除链表中重复的结点

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

解题思路

用一个辅助Node指向头节点，用一个指针指向当前节点，判断当前节点的next是否相等，如果相等则往前移动。注意处理当前节点的next为空的情况。

代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        ListNode* helperNode = new ListNode(0), *curNode=pHead;
        helperNode->next = pHead;
        ListNode* preNode = helperNode;
        while(curNode){
            if(curNode->next!=NULL&&curNode->val==curNode->next->val){
                while(curNode->next!=NULL&&curNode->val==curNode->next->val){
                    curNode=curNode->next;
                }
                curNode = curNode->next;
                preNode->next=curNode;
            }else {
                curNode = curNode->next;
                preNode = preNode->next;
            }
        }
        return helperNode->next;
    }
};

57. 二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解题思路

分两种情况：
1. 如果右孩子存在，则输出右子树的最左节点。
2. 如果右孩子不存在，则从根节点里找，直到是根节点的左子树或者无根节点的时候停止。

代码

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if(pNode->right){
            pNode = pNode->right;
            while(pNode->left) pNode=pNode->left;
            return pNode;
        }else {
            while(pNode->next&&pNode->next->right==pNode) pNode = pNode->next;
            return pNode->next;
        }
    }
};

58. 对称的二叉树

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

解题思路

将左右子树前序遍历，左子树使用中->左->右的顺序，右子树使用中->右->左的顺序。

代码

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot==NULL) return true;
        return isSymmetricalCore(pRoot->left, pRoot->right);
    }
    bool isSymmetricalCore(TreeNode* root1, TreeNode* root2){
        if(root1==NULL) return root2==NULL;
        if(root2==NULL) return root1==NULL;
        if(root1->val!=root2->val) return false;
        return isSymmetricalCore(root1->left, root2->right) && isSymmetricalCore(root1->right, root2->left);
    }
};

59. 按之字形顺序打印二叉树

60. 把二叉树打印成多行

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

解题思路

用一个指针一直指着队列中的末尾，遇到换行就切换。

代码

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int> > result;
            if(pRoot==NULL) return result;
            vector<int> oneLine;
            queue<TreeNode*> helper;
            helper.push(pRoot);
            TreeNode* rightNode = pRoot;
            while(!helper.empty()){
                TreeNode* node = helper.front();
                helper.pop();
                oneLine.push_back(node->val);
                if(node->left) helper.push(node->left);
                if(node->right) helper.push(node->right);
                if(node==rightNode){
                    rightNode = helper.back();
                    result.push_back(oneLine);
                    oneLine.clear();
                }
            }
            return result;
        }
};

61. 序列化二叉树

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

解题思路

62. 二叉搜索树的第k个结点

题目描述

给定一颗二叉搜索树，请找出其中的第k小的结点。例如，

中，按结点数值大小顺序第三个结点的值为4。

解题思路

中序遍历，按左->中->右的顺序，找到k=0则停止。

代码

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(k<=0) return NULL;
        TreeNode* result=NULL;
        KthNodeCore(pRoot, k, result);
        return result;
    }
    void KthNodeCore(TreeNode* pRoot, int& k, TreeNode* &result)
    {
        if(pRoot==NULL) return;
        KthNodeCore(pRoot->left, k, result);
        if(k==1){
            if(result==NULL)
                result=pRoot;
            return;
        }
        --k;
        KthNodeCore(pRoot->right, k, result);
    }
};

63.数据流中的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

解题思路

用两个堆，一个放左边的最大值，一个放右边的最小值。

代码

class Solution {
private:
    priority_queue<int> leftHeap;
    priority_queue<int, vector<int>, greater<int> > rightHeap;
public:
    void Insert(int num)
    {
        if(leftHeap.empty()) leftHeap.push(num);
        else if(num>leftHeap.top()){
            rightHeap.push(num);
            if(rightHeap.size()>leftHeap.size()){
                leftHeap.push(rightHeap.top());
                rightHeap.pop();
            }
        } 
        else {
            leftHeap.push(num);
            if(leftHeap.size()-1>rightHeap.size()){
                rightHeap.push(leftHeap.top());
                leftHeap.pop();
            }
        }
    }
    double GetMedian()
    { 
        if(leftHeap.size()==0)
            return 0;
        if(leftHeap.size()==rightHeap.size())
            return (leftHeap.top()+rightHeap.top())/2.0;
        return leftHeap.top();
    }
};

64. 滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

65. 矩阵中的路径

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如
a b c e
s f c s
a d e e
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。