牛客网剑指offer编程练习(C++)

2018-09-06 石头人m 更多博文 » 博客 » GitHub »

数据结构 编程练习

原文链接 http://www.stormstone.xin/2018/09/06/%E7%89%9B%E5%AE%A2%E7%BD%91%E5%89%91%E6%8C%87Offer%E7%BC%96%E7%A8%8B%E7%BB%83%E4%B9%A0(C++)/
注:以下为加速网络访问所做的原文缓存,经过重新格式化,可能存在格式方面的问题,或偶有遗漏信息,请以原文为准。


牛客网编程练习-剑指offer,语言:c++11(clang++ 3.9)。

1.【数组】二维数组中的查找

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

/*矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,
* 因此从左下角开始查找,当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时,上移
*/
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
         int rowCount = array.size();
        int colCount = array[0].size();
        int i,j;
        for(i=rowCount-1,j=0;i>=0&&j<colCount;)
        {
            if(target == array[i][j])
                return true;
            if(target < array[i][j])
            {
                i--;
                continue;
            }
            if(target > array[i][j])
            {
                j++;
                continue;
            }
        }
        return false;
    }
};

2.【字符串】替换空格

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

/*
1:从前往后插入,这样移动·的次数多不建议
2:从后往前插入
*/
class Solution {
public:
void replaceSpace(char *str,int length) {
    //遍历一边字符串找出空格的数量
    if(str==NULL||length<0)
        return ;
    int i=0;
    int oldnumber=0;//记录以前的长度
    int replacenumber=0;//记录空格的数量
    while(str[i]!='\0'){
        oldnumber++;
        if(str[i]==' ')
            replacenumber++;
        i++; 
    }
    int newlength=oldnumber+replacenumber*2;//插入后的长度
    if(newlength>length)//如果计算后的长度大于总长度就无法插入
        return ;
    int pOldlength=oldnumber; //注意不要减一因为隐藏个‘\0’也要算里
    int pNewlength=newlength;
    while(pOldlength>=0&&pNewlength>pOldlength)//放字符
    {
        if(str[pOldlength]==' ') //碰到空格就替换
        {
            str[pNewlength--]='0';
            str[pNewlength--]='2';
            str[pNewlength--]='%';
        }
        else //不是空格就把pOldlength指向的字符装入pNewlength指向的位置
            str[pNewlength--]=str[pOldlength];
        pOldlength--; //不管是if还是else都要把pOldlength前移
    }
}
};

3.【链表】从尾到头打印链表

输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> value;
        if(head != NULL)
        {
            value.insert(value.begin(),head->val);
            while(head->next != NULL)
            {
                value.insert(value.begin(),head->next->val);
                head = head->next;
            }         

        }
        return value;
    }
};

4.【树 】重建二叉树

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

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int inlen=vin.size();
        if(inlen==0)
            return NULL;
        vector<int> left_pre,right_pre,left_in,right_in;
        //创建根节点,根节点肯定是前序遍历的第一个数
        TreeNode* head=new TreeNode(pre[0]);
        //找到中序遍历根节点所在位置,存放于变量gen中
        int gen=0;
        for(int i=0;i<inlen;i++){
            if (vin[i]==pre[0]){
                gen=i;
                break;
            }
        }
        //对于中序遍历,根节点左边的节点位于二叉树的左边,根节点右边的节点位于二叉树的右边
        //利用上述这点,对二叉树节点进行归并
        for(int i=0;i<gen;i++){
            left_in.push_back(vin[i]);
            left_pre.push_back(pre[i+1]);//前序第一个为根节点
        }
        for(int i=gen+1;i<inlen;i++){
            right_in.push_back(vin[i]);
            right_pre.push_back(pre[i]);
        }
        //和shell排序的思想类似,取出前序和中序遍历根节点左边和右边的子树
        //递归,再对其进行上述所有步骤,即再区分子树的左、右子子数,直到叶节点
        head->left=reConstructBinaryTree(left_pre,left_in);
        head->right=reConstructBinaryTree(right_pre,right_in);
        return head;
    }
};

5.【栈和队列 】用两个栈实现队列

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

/*
1.用两个栈实现一个队列的功能:
入队:将元素进栈A
出队:判断栈B是否为空,如果为空,则将栈A中所有元素pop,并push进栈B,栈B出栈;
 如果不为空,栈B直接出栈。

2.用两个队列实现一个栈的功能:
入栈:将元素进队列A
出栈:判断队列A中元素的个数是否为1,如果等于1,则出队列,否则将队列A中的元素依次出队列并放入队列B,直到队列A中的元素留下一个,然后队列A出队列,再把队列B中的元素出队列依次放入队列A中。
*/
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

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

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) {
        if (rotateArray.empty()) return 0;
        int left = 0, right = rotateArray.size() - 1;
        while (left < right) {
            //确认子数组是否是类似1,1,2,4,5,..,7的非递减数组
            if (rotateArray[left] < rotateArray[right]) return rotateArray[left];

            int mid = left + (right - left) / 2;
            //如果左半数组为有序数组
            if (rotateArray[left] < rotateArray[mid])
                left = mid + 1;
            //如果右半数组为有序数组
            else if (rotateArray[mid] < rotateArray[right])
                right = mid;
            //否则,rotateArray[left] == rotateArray[mid] == rotateArray[right]
            else {
                ++left;
            }
        }
        return rotateArray[left];
    }
};

7.【递归和循环 】 斐波那契数列

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。n<=39

/*递归要炸:重复计算
Fibonacci(4) = Fibonacci(3) + Fibonacci(2);
             = Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
             = Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
*/
class Solution {
public:
    int Fibonacci(int n) {
        int f = 0, g = 1;
        while(n--) {
            g += f;
            f = g - f;
        }
        return f;
    }
};

8.【递归和循环 】跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

class Solution {
public:
    int jumpFloor(int n) {
        int f=1,g=2;
        n--;
        while(n--)
        {
            g+=f;
            f=g-f;
        }
        return f;
    }
};

9.【递归和循环 】变态跳台阶

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

/*
f(0) = 1
f(1) = 1
f(2) = f(2-1) + f(2-2)
f(3) = f(3-1) + f(3-2) + f(3-3) 
...
f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n)  ==>  f(0) + f(1) + f(2) + f(3) + ... + f(n-1)
推导:
f(n-1) = f(0)+f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出:f(n) = 2*f(n-1)
即:
       | 1       , n=0
f(n) = | 1       , n=1
       | 2*f(n-1), n>=2
*/
class Solution {
public:
    int jumpFloorII(int number) {
        if(number==0)
            return number;
        int total=1;
        for(int i=1;i<number;i++)
            total*=2;
        return total;
    }
};

10.【递归和循环 】矩形覆盖

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

class Solution {
public:
    int rectCover(int number) {
        if (number <= 0) {
            return number;
        }
        int f1 = 1;
        int f2 = 2;
        int f3;

        for (int i = 3; i <= number; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
};

11.【位运算 】二进制中1的个数

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

// 解法一:一位一位的比较。
class Solution {
public:
     int  NumberOf1(int n) {
         int count=0;
         unsigned int flag=1;
         while(flag){
             if (n & flag){
                 count++;
             }
          flag=flag<<1;
         }
         return count;
     }
};

// 解法二:
class Solution {
public:
     int  NumberOf1(int n) {
          int count = 0;
          while(n!= 0){
              count++;
              n = n & (n - 1);
           }
          return count;
     }
};
/*
如果一个整数不为0,那么这个整数至少有一位是1。如果我们把这个整数减1,那么原来处在整数最右边的1就会变为0,原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子:一个二进制数1100,从右边数起第三位是处于最右边的一个1。减去1后,第三位变成0,它后面的两位0变成了1,而前面的1保持不变,因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算,从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说,把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1,就可以进行多少次这样的操作。
*/

12.【 代码的鲁棒性 】数值的整数次方

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

/**
 * 区分指数的正负。
 * 指数的二进制表达,例如13表达为二进制1101。
 * 举例:10^1101 = 10^0001*10^0100*10^1000。
 * 通过&1和>>1来逐位读取1101,为1时将该位代表的乘数累乘到最终结果。
 */
class Solution {
public:
    double Power(double base, int exponent) {
        long long p = abs((long long)exponent);
        double r = 1.0;
        while(p){
            if(p & 1) 
                r *= base;
            base *= base;
            p >>= 1;
        }
        return exponent < 0 ? 1/ r : r;
    }
};

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

/*
类似冒泡排序
*/
class Solution {
public:
    void reOrderArray(vector<int> &array) {
        for (int i = 0; i < array.size();i++){
            for (int j = array.size() - 1; j>i;j--){
                 //前偶后奇交换
                if (array[j] % 2 == 1 && array[j - 1]%2 == 0){
                    swap(array[j], array[j-1]);
                }
            }
        }
    }
};

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

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

/*
p1指针先跑,并且记录节点数,当p指针跑了k-1个节点后,p2指针开始跑,
当p1指针跑到最后时,p2所指指针就是倒数第k个节点
*/
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* p, unsigned int k) {
        ListNode* p1=p;
        ListNode* p2=p;
        for(int i=0;i!=k;++i)
            if(!p1)
                return nullptr;
            else
                p1=p1->next;
        while(p1){
            p1=p1->next;
            p2=p2->next;
        }
        return p2;
    }
};

15.【 链表】反转链表

输入一个链表,反转链表后,输出新链表的表头。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (!pHead || !pHead->next)
            return pHead;
        ListNode* pre = nullptr;//必须赋值为nullptr或NULL。
        ListNode* tmp;
        while(pHead){
            tmp = pHead->next;
            pHead->next = pre;
            pre=pHead;
            pHead = tmp;
        }
        return pre;
    }
};

16.【 链表】 合并两个排序的链表

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

/*
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;
        else if(pHead2==NULL)
            return pHead1;
        ListNode* newhead=NULL;
        if(pHead1->val < pHead2->val){
            newhead=pHead1;
            newhead->next=Merge(pHead1->next,pHead2);
        }
        else{
            newhead=pHead2;
            newhead->next=Merge(pHead1,pHead2->next);
        }
        return newhead;
    }
};

17.【 二叉树】树的子结构

输入两棵二叉树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 {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(!pRoot1)
            return false;
        if(!pRoot2)
            return false;
        return (dfs(pRoot1,pRoot2)) || HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right,pRoot2);
    }
private:
    bool dfs(TreeNode* r1,TreeNode* r2){
        if(!r2)
            return true;//r2为空表示匹配完毕,返回true
        if(!r1)
            return false;
        if(r1->val != r2->val)
            return false;
        return dfs(r1->left,r2->left) && dfs(r1->right,r2->right);
    }
};

18.【 二叉树】 二叉树的镜像

操作给定的二叉树,将其变换为源二叉树的镜像。

/*
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* tmp = pRoot->right;
        pRoot->right = pRoot->left;
        pRoot->left = tmp;

        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
};

19.【二维数组】【 画图让抽象形象化 】 顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 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.

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        vector<int> res;
        if(row == 0 || col == 0)
            return res;
        int left = 0,right = col-1,top = 0,btn = row-1;
        while(left <= right && top <= btn){
            for(int i = left;i <= right;i++)
                res.push_back(matrix[top][i]);
            if(top < btn)
                for(int i = top+1;i<=btn;i++)
                    res.push_back(matrix[i][right]);
            if(left<right && top<btn)
                for(int i = right-1;i>=left;i--)
                    res.push_back(matrix[btn][i]);
            if(left<right && top+1<btn)
                for(int i = btn-1;i>=top+1;i--)
                    res.push_back(matrix[i][left]);
            left++,right--,top++,btn--;
        }
        return res;
    }
};

20.【栈】【 举例让抽象具体化 】包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

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

21.【栈】【 举例让抽象具体化 】栈的压入、弹出序列

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

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

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

23.【二叉树】【 举例让抽象具体化 】二叉搜索树的后序遍历序列

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

/*
设最后一个元素是x (也就是根),如果去掉最后一个元素的序列为T,那么T满足:T可以分成两段,前一段(左子树)小于x,后一段(右子树)大于x,且这两段(子树)都是合法的后序序列。完美的递归定义。
*/
class Solution {
    bool judge(vector<int>& a, int l, int r){
        if(l >= r) return true;
        int i = r;
        while(i > l && a[i - 1] > a[r]) --i;
        for(int j = i - 1; j >= l; --j) if(a[j] > a[r]) return false;
        return judge(a, l, i - 1) && (judge(a, i, r - 1));
    }
public:
    bool VerifySquenceOfBST(vector<int> a) {
        if(!a.size()) return false;
        return judge(a, 0, a.size() - 1);
    }
};

24.【二叉树】【 举例让抽象具体化 】 二叉树中和为某一值的路径

输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)

/*
这类问题可以用带记忆的DFS来解决。
*/
/*
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>> ret;//存放结果
        vector<int> trace;//中间结果
        if(root)
            dfs(root,expectNumber,ret,trace);
        return ret;
    }
    void dfs(TreeNode* root,int expectNum,vector<vector<int>> &ret,vector<int> &trace) {
        trace.push_back(root->val);
        if(!root->left&&!root->right) {//是叶子节点
            if(expectNum==root->val)//该路径和为期望的值,则满足条件,存入结果
                ret.push_back(trace);
        }
        if(root->left)
            dfs(root->left,expectNum-root->val,ret,trace);
        if(root->right)
            dfs(root->right,expectNum-root->val,ret,trace);
        trace.pop_back();//不满足条件,清空trace
    }
};

25.【链表】【分解让复杂问题简单 】复杂链表的复制

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

/*
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) return NULL;
        RandomListNode *currNode = pHead;
        while(currNode){
            RandomListNode *node = new RandomListNode(currNode->label);
            node->next = currNode->next;
            currNode->next = node;
            currNode = node->next;
        }
        currNode = pHead;
        while(currNode){
            RandomListNode *node = currNode->next;
            if(currNode->random){               
                node->random = currNode->random->next;
            }
            currNode = node->next;
        }
        //拆分
        RandomListNode *pCloneHead = pHead->next;
        RandomListNode *tmp;
        currNode = pHead;
        while(currNode->next){
            tmp = currNode->next;
            currNode->next =tmp->next;
            currNode = tmp;
        }
        return pCloneHead;
    }
};

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){
        if(pRootOfTree == nullptr) return nullptr;
        TreeNode* pre = nullptr;
        convertHelper(pRootOfTree, pre);
        TreeNode* res = pRootOfTree;
        while(res ->left)
            res = res ->left;
        return res;
    }
    void convertHelper(TreeNode* cur, TreeNode*& pre){
        if(cur == nullptr) return;
        convertHelper(cur ->left, pre);
        cur ->left = pre;
        if(pre) pre ->right = cur;
        pre = cur;
        convertHelper(cur ->right, pre);
    }
};

27.【字符串】【分解让复杂问题简单 】字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

class Solution {
public:
    vector<string> Permutation(string str) {       
        if(str!="") dfs(str, 0);
        return ret;
    }
private:
    vector<string> ret;
    void dfs(string str, int s){
        int sz = str.size();
        if(s==sz){
            ret.push_back(str);
            return;
        }
        for(int i = s; i < sz; ++i){
            if(i!=s && str[s]==str[i]) continue;
            swap(str[s], str[i]);
            dfs(str, s+1);
        }
    }  
};

28.【数组】【 时间效率 】数组中出现次数超过一半的数字

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

/*
如果有符合条件的数字,则它出现的次数比其他所有数字出现的次数和还要多。
在遍历数组时保存两个值:一是数组中一个数字,一是次数。遍历下一个数字时,若它与之前保存的数字相同,则次数加1,否则次数减1;若次数为0,则保存下一个数字,并将次数置为1。遍历结束后,所保存的数字即为所求。然后再判断它是否符合条件即可。
*/
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n = numbers.size();
        if (n == 0) return 0;

        int num = numbers[0], count = 1;
        for (int i = 1; i < n; i++) {
            if (numbers[i] == num) count++;
            else count--;
            if (count == 0) {
                num = numbers[i];
                count = 1;
            }
        }
        // Verifying
        count = 0;
        for (int i = 0; i < n; i++) {
            if (numbers[i] == num) count++;
        }
        if (count * 2 > n) return num;
        return 0;
    }
};

29.【数组】【 时间效率 】最小的K个数

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

/*最小堆*/
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> result ;
        if(k > input.size()) return result;
        for(int i = 0; i < k ; i ++){
            heapSort(input,i,input.size());
            result.push_back(input[i]);
        }
        return result;
    }
private:
     void heapSort(vector<int> &input, int root, int end){
        for(int j = end -1; j >= root; j --){
            int parent = (j + root -1)/2;
            if(input[parent] > input[j]){
                int temp = input[j];
                input[j] = input[parent];
                input[parent] = temp;
            }
        }  
     }
};

30.【数组】【 时间效率 】连续子数组的最大和

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

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int n = array.size();
        int sum = array[0];
        int maxSum = array[0];
        for(int i=1;i<n;i++){
            sum = (sum < 0) ? array[i] : sum+=array[i];
            if(maxSum < sum)
                maxSum = sum;
        }
        return maxSum;
    }
};

31.【 时间效率 】整数中1出现的次数(从1到n整数中1出现的次数)

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

/*暴力也能过?*/
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
       int count = 0;
       for(int i=1;i<=n;i++){
           int tmp = i;
           while(tmp){
               if(tmp % 10 == 1)
                   count++;
               tmp /= 10;
           }
       }
        return count;
    }
};

/*高效方法:
主要思路:设定整数点(如1、10、100等等)作为位置点i(对应n的各位、十位、百位等等),分别对每个数位上有多少包含1的点进行分析
根据设定的整数位置,对n进行分割,分为两部分,高位n/i,低位n%i
    1.当i表示百位,且百位对应的数>=2,如n=31456,i=100,则a=314,b=56,此时百位为1的次数有a/10+1=32(最高两位0~31),每一次都包含100个连续的点,即共有(a%10+1)*100个点的百位为1
    2.当i表示百位,且百位对应的数为1,如n=31156,i=100,则a=311,b=56,此时百位对应的就是1,则共有a%10(最高两位0-30)次是包含100个连续点,当最高两位为31(即a=311),本次只对应局部点00~56,共b+1次,所有点加起来共有(a%10*100)+(b+1),这些点百位对应为1
    3.当i表示百位,且百位对应的数为0,如n=31056,i=100,则a=310,b=56,此时百位为1的次数有a/10=31(最高两位0~30)
    综合以上三种情况,当百位对应0或>=2时,有(a+8)/10次包含所有100个点,还有当百位为1(a%10==1),需要增加局部点b+1
    之所以补8,是因为当百位为0,则a/10==(a+8)/10,当百位>=2,补8会产生进位位,效果等同于(a/10+1)
*/
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
       int count=0;
        long long i=1;
        for(i=1;i<=n;i*=10){
            int a = n/i,b = n%i;
            count=count+(a+8)/10*i+(a%10==1)*(b+1);
        }
        return count;
    }
};

32.【 时间效率 】把数组排成最小的数


33.【时间空间效率的平衡 】 丑数


34.【时间空间效率的平衡 】第一个只出现一次的字符位置


35.【时间空间效率的平衡 】数组中的逆序对


36.【时间空间效率的平衡 】 两个链表的第一个公共结点


37.【知识迁移能力 】 数字在排序数组中出现的次数


38.【知识迁移能力 】 二叉树的深度


39.【知识迁移能力 】平衡二叉树


40.【知识迁移能力 】数组中只出现一次的数字


41.【知识迁移能力 】和为S的连续正数序列


42.【知识迁移能力 】和为S的两个数字


43.【知识迁移能力 】左旋转字符串


44.【知识迁移能力 】翻转单词顺序列


45.【抽象建模能力 】扑克牌顺子


46.【抽象建模能力 】孩子们的游戏(圆圈中最后剩下的数)


47.【 发散思维能力 】求1+2+3+...+n


48.【 发散思维能力 】不用加减乘除做加法 不用加减乘除做加法


49.【综合 】 把字符串转换成整数


50.【数组 】数组中重复的数字


51.【数组 】构建乘积数组


52.【字符串 】正则表达式匹配


53.【字符串 】表示数值的字符串


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


55.【链表 】 链表中环的入口结点


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


57.【树 】 二叉树的下一个结点


58.【树 】 对称的二叉树


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


60.【树 】 把二叉树打印成多行


61.【树 】 序列化二叉树


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


63.【树 】数据流中的中位数


64.【栈和队列 】 滑动窗口的最大值


65.【 回溯法 】矩阵中的路径


66.【 回溯法 】机器人的运动范围