《剑指offer》

1. 二维数组中的查找

题目描述

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

解法一: 每一行用一次二分

时间复杂度: $O(nlogn)$ (该复杂度无法通过牛客OJ)

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        for( int i = 0; i<array.size(); i++){
            int low = 0, high = array[i].size()-1;
            while(low < high){
                int mid = (low+high) / 2;
                if(target > array[i][mid]) low = mid;
                else if(target < array[i][mid]) high = mid;
                else return true;
            }
        }
        return false;
    }
};

每一行二分需要 logn 的时间, 总共有n行.

解法二: 从左下角开始

时间复杂度: $O(n+m)$, 最多走 $n+m$ 步, $n$ 和 $m$ 分别为矩阵的宽和高
空间复杂度: $O(1)$

从左下角开始, 向右为大数方向, 向上为小数方向, 每次至少移动一位, 总共需要移动n次

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int i = array.size()-1;
        int j = 0, len = array[0].size();
        while(i>=0 && j < len){
            if(target > array[i][j]) j++;  // target在大数方向
            else if(target < array[i][j]) i--;  // target在小数方向
            else return true;
        }
        return false;
    }
};

2. 替换空格

题目描述

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

解法: 从前向后记录空格，从后向前替换空格

时间复杂度: $O(n)$

需要注意, 如果替换的空间超过了length的申请空间, 则需要重新申请空间

class Solution {
public:
	void replaceSpace(char *str,int length) {
        int white_count = 0;
        int char_count = 0;
        char *s = str;
        while(*s!='\0'){
            if(*s == ' ') white_count++;
            else char_count++;
            s++;
        }
        char* res_str = str;
        if(char_count + white_count*3 >length)
            res_str = new char[char_count+white_count*3 + 1];
        int old_length = char_count+white_count+1;
        int new_length = char_count+white_count*3 + 1;
        while(old_length >=0 && new_length >= 0){
            if(str[old_length] != ' '){
                res_str[new_length--]=str[old_length--];
            }else{
                old_length--;
                res_str[new_length--]='0';
                res_str[new_length--]='2';
                res_str[new_length--]='%';
            }
        }
        str = res_str;
	}
};

3.从尾到头打印链表

题目描述

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

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/

解法一: reverse

时间复杂度: $O(n)$
空间复杂度: $O(n)$

顺序访问, 然后将vector里面的元素逆置. 这两部操作时间复杂度皆为 $O(n)$

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        while(head!=nullptr){
            res.push_back(head->val);
            head = head->next;
        }
        std::reverse(res.begin(), res.end());
        return res;
    }
};

解法二: swap (实际上依然是reverse)

时间复杂度: $O(n)$
空间复杂度: $O(n)$

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        if(head == nullptr) return res;
        while(head!=nullptr){
            res.push_back(head->val);
            head = head->next;
        }
        int mid = (res.size()-1)/2;
        int len = res.size()-1;
        for(int i =0 ;i<=mid;i++)
            std::swap(res[i], res[len-i]);
        return res;
    }
};

解法三: 栈

时间复杂度: $O(n)$
空间复杂度: $O(2n)$

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

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) {}
 * };
 */

首先需要注意一点的是: 这里前序和中序不能包含重复的元素, 否则无法确定前序和中序中节点的对应关系

解法一: 递归

时间复杂度: $O(
空间复杂度:

根据前序和中序的对应关系, 利用递归完成构建, 构建时, 先构建当前节点, 然后是左右子树.

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return helper(pre, 0, pre.size()-1, vin, 0, vin.size()-1);

    }

    TreeNode* helper(vector<int> &pre, int pre_i, int pre_j, vector<int> &vin, int vin_i, int vin_j){
        if(pre_i > pre_j || vin_i > vin_j) return nullptr;
        TreeNode* node = new TreeNode( pre[pre_i] ); // 当前节点
        int v = vin_i;
        while(pre[pre_i] != vin[v]) v++; //找到前序在中序中的对应节点, 这里可以用哈希表来改进查找的复杂度
        node->left = helper(pre, pre_i+1, pre_i+v-vin_i, vin, vin_i, v-1);
        node->right = helper(pre, pre_i+v-vin_i+1, pre_j, vin, v+1, vin_j);
        return node;
    }
};

解法二: 迭代

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        stack<TreeNode*> tree_stack;
        if(pre.size() == 0) return nullptr;
        TreeNode * root = new TreeNode(pre[0]);
        tree_stack.push(root);
        int index = 0;
        for(int i = 1; i<pre.size() ; i++){
            TreeNode * cur_node = tree_stack.top();
            if(cur_node->val != vin[index]){
                cur_node->left = new TreeNode(pre[i]);
                tree_stack.push(cur_node->left);
            }else{
                while( !tree_stack.empty() && tree_stack.top()->val == vin[index]){ // 注意, 这里不能用cur_node, 而必须用tree_stack.top()
                    cur_node = tree_stack.top(); tree_stack.pop(); index++;
                }
                cur_node->right = new TreeNode(pre[i]);
                tree_stack.push(cur_node->right);
            }
        }
        return root;
    }
};

5.用两个栈实现队列

6.旋转数组的最小数字

7.斐波那契数列

$$f(n) = \begin{cases} 0, & n=0 \\ 1, & n=1(或2) \\ f(n-1)+f(n-2), & n>2 \end{cases}$$

解法一: 递归(超时,超内存)

class Solution {
public:
    int jumpFloor(int number) {
        if(number==0) return 0;
        if(number==1 || number==2) return 1;
        return jumpFloor(number-1)+jumpFloor(number-2);
    }
};

解法二: 迭代

class Solution {
public:
    int Fibonacci(int n) {
        if(n ==0) return 0;
        if(n==1 || n==2) return 1;
        int n1=1, n2=1;
        for(int i=3; i<=n; i++){
            int temp = n2;
            n2 = n2+n1;
            n1 = temp;
        }
        return n2;
    }
};

解法二: 迭代

8.跳台阶

题目描述

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

解法一: 递归(超时, 超内存)

设n个台阶的跳法有 $f(n)$ 种, 当青蛙跳上一个台阶后, 剩下的走法就是只有n-1个台阶的走法, 因此就是 $f(n-1)$ , 同理, 如果当前跳了2个台阶, 那么剩下的就是f(n-2), 因此有以下公式:

$$f(n) = \begin{cases} 1, & n=1 \\ 2, & n=2 \\ f(n-1) + f(n-2) & n>1 \end{cases}$$

从上可以看出, 这道题就是斐波那契数列的变种, 不同之处在于初始值不同(因为台阶为2时, 有两种跳法), 因此解法同上.

解法二: 迭代

class Solution {
public:
    int jumpFloor(int number) {
        if(number==0) return 0;
        if(number==1) return 1;
        int n1 = 1;
        int n2 = 2;
        for(int i=3; i<=number; i++){
            int temp=n2;
            n2 = n2 + n1;
            n1 = temp;
        }
        return n2;
    }
};

9.变态跳台阶

题目描述

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

解法一: 递归

对于n个台阶, 可以跳1次, 2次, …., n次, 那么对应的剩下的台阶的跳法就有 $f(n-1), f(n-2), …, f(n-n)$ 种, 所以有下式:

$$f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)$$ $$f(n) = \begin{cases} 1, & n=0 \\ 1, & n=1 \\ 2*f(n-1), & n>=2 \end{cases}$$

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

10.矩形覆盖

对于 $n \times 2$ 大小的矩形, 可以竖着排列一个 $2\times 1$ 矩形, 或者横着排列上下两个 $2\times 1$ 的矩形, 那么对应的剩下的矩形面积就分别为 $(n-1) \times 2$ 和 $(n-2) \times 2$, 所以有下式:

$$f(n) = \begin{cases} 1, & n=1 \\ 2, & n=2 \\ f(n-1) + f(n-2) & n>1 \end{cases}$$

解法一: 递归(超时)

解法二: 迭代

class Solution {
public:
    int rectCover(int number) {
        if(number==0) return 0;
        if(number==1) return 1;
        int n1=1, n2=2;
        for(int i=3; i<=number; i++){
            int temp = n2;
            n2 = n2+n1;
            n1 = temp;
        }
        return n2;
    }
};

11.二进制中1的个数

题目描述

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

解法一: 按位与&

时间复杂度: $O(1)$, 因为最多比较32次(long为64次)
空间复杂度: $O(1)$

注意: (n&i) 一定要带括号, 因为它的优先级比==, != 等符号低.

class Solution {
public:
     int  NumberOf1(int n) {
         int i = 1;
         int count = 0;
         while( i!=0 ){
             if( (n&i) != 0) count++; // 注意, 这里的判断条件是 !=0, 并且 n&i 一定要带括号
             i = i << 1;
         }
         return count;
     }
};

解法二: n&(n-1)

一个整数 $n$, 将其与 $n-1$ 按位逻辑与, 得到的数刚好是将 $n$ 最右边的1置为0(其他位不变), 那么一个数有多少个1, 就可以进行多少次这样的操作.

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

12.数值的整数次方

题目描述

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

解法一: 递归

当n为偶数时: $x^n = x^{n/2} \times x^{n/2}$
当n为奇数时: $x^n = x\times x^{n/2} \times x^{n/2}$

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0) return 1.0;
         unsigned int un = abs(n);  //注意这里必须是 unsigned类型, 就算是long , 也必须带unsigned, 主要是因为abs(INT_MIN)仍为负数INT_MIN!
        if(n < 0)
            x = 1/x;
        return (un%2==0) ? myPow(x*x, un/2) : x*myPow(x*x, un/2);
    }
};

解法二: 非递归

n要么为偶数, 要么为奇数, 就算为奇数, 也可以拆分成 $x\times x^{n-1}$ 的形式, 对于偶数n, 可以写成 $x^{n/2} \times x{n/2}$ 的形式, 对于 $x^{n/2}$, 可以继续按奇数偶数进行拆分. 举例来说, 对于x=2, n=10 , 可以写成 $2^{10} = 2^{5} \times 2^{5}$ 对于 $2^5$ , 可以写成, $2 \times 2^2 \times 2^2$, 可以看出, x每次与自身相乘后, n的次数就会变成原来二分之一, 这样, 可以用循环实现幂乘的操作, 如下所示.

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0) return 1.0;
         unsigned int un = abs(n);  //注意这里必须是 unsigned类型, 就算是long , 也必须带unsigned, 主要是因为abs(INT_MIN)仍为负数INT_MIN!
        if(n < 0)
            x = 1/x;
        double res =1.0;
        while(un>0){
            if(un%2 == 1){
                res * = x;
            }
            x * =x;
            un /= 2;
        }
        return res;
    }
};

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

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

题目描述

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

解法一: 两个指针

时间复杂度: $O(n)$ 遍历一次
空间复杂度: $O(1)$

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

15.反转链表

题目描述

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

解法一: 两个指针pre和cur

时间复杂度: $O(n)$ 一次遍历
空间复杂度: $O(1)$

利用两个指针pre和cur维持当前节点和前一个节点, 然后执行反转操作

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* pre = nullptr;
        ListNode* cur = pHead;
        while(pHead != nullptr){
            cur = pHead;
            pHead = pHead->next;
            cur->next = pre;
            pre = cur;
        }
        return cur;
    }
};

16.合并两个排序的链表

题目描述

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

解法一: 原地合并

用辅助指针head申请一个指向头结点的指针, 并用cur维护当前节点, 通过比较大小进行插入合并

/*
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 == nullptr) return pHead2;
        if(pHead2 == nullptr) return pHead1;
        ListNode * head = new ListNode(0);
        ListNode * cur = head;
        while(pHead1!=nullptr && pHead2!=nullptr){
            if(pHead1->val < pHead2->val){
                cur->next = pHead1;
                cur = cur->next;
                pHead1 = pHead1->next;
            }else{
                cur->next = pHead2;
                cur = cur->next;
                pHead2 = pHead2->next;
            }
        }
        if(pHead1!=nullptr) cur->next = pHead1;
        if(pHead2!=nullptr) cur->next = pHead2;
        return head->next;
    }
};

解法二: 递归

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

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(pRoot2 == nullptr) return false;
        std::stack<TreeNode * > pre_root;
        while(!pre_root.empty() || pRoot1!=nullptr){
            while(pRoot1!=nullptr){
                if(pRoot1->val == pRoot2->val && is_subtree(pRoot1, pRoot2))
                    return true;
                pre_root.push(pRoot1);
                pRoot1 = pRoot1->left;
            }
            if(!pre_root.empty()){
                pRoot1 = pre_root.top(); pre_root.pop();
                pRoot1 = pRoot1->right;
            }
        }
        return false;

    }
    bool is_subtree(TreeNode * pRoot1, TreeNode * pRoot2){
        std::stack<TreeNode * > pre_root;
        while(!pre_root.empty() || pRoot2!=nullptr){
            while(pRoot2!=nullptr){
                if(pRoot1==nullptr || pRoot2->val != pRoot1->val)
                    return false;
                pre_root.push(pRoot1);
                pre_root.push(pRoot2);
                pRoot1 = pRoot1->left;
                pRoot2 = pRoot2->left;
            }
            if(!pre_root.empty()){
                pRoot2 = pre_root.top(); pre_root.pop(); // 注意入栈与出栈的顺序要刚好相反
                pRoot1 = pre_root.top(); pre_root.pop();
                pRoot1 = pRoot1->right;
                pRoot2 = pRoot2->right;
            }
        }
        return true;
    }
};

解法二: 递归

class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool result = false; //用result变量来记录是否已经是子树, 如果result一旦为true, 就直接返回, 不用再继续递归
        if(pRoot1 != nullptr && pRoot2 != nullptr){
            result = is_subtree(pRoot1,pRoot2);
            if(!result) result = HasSubtree(pRoot1->left, pRoot2);
            if(!result) result = HasSubtree(pRoot1->right, pRoot2);
        }
        return result;
    }
    bool is_subtree(TreeNode* pRoot1, TreeNode* pRoot2){
        if(pRoot2 == nullptr ) return true;
        if(pRoot1==nullptr || pRoot2->val != pRoot1->val) return false;
        return is_subtree(pRoot1->left, pRoot2->left) && is_subtree(pRoot1->right, pRoot2->right);
    }
};

18.二叉树的镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5

解法一: 递归

先根遍历

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

解法二: 非递归

先根遍历

class Solution {
public:
    void Mirror(TreeNode * pRoot) {
        std::stack<TreeNode * > pre_root;
        TreeNode * cur = pRoot;
        while(!pre_root.empty() || cur!=nullptr){
            while(cur!=nullptr){
                TreeNode * temp = cur->left;
                cur->left = cur->right;
                cur->right = temp;
                pre_root.push(cur);
                cur = cur->left;
            }
            if(!pre_root.empty()){
                cur = pre_root.top(); pre_root.pop();
                cur = cur->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.

解法一: 按层打印

时间复杂度: $O(n)$
空间复杂度: $O(n)$

按照层从外而内进行打印, 需要注意层的边界条件, 以及上下层和左右层之间不能重复.

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> res;
        if(matrix.size()==0 ||matrix[0].size()==0) return vector<int>{};
        int row = matrix.size(), col = matrix[0].size();
        int layers = (std::min(row,col) + 1)/2;
        for(int layer=0; layer<layers; layer++){

            for(int i=layer, j=layer; j< col-layer; j++ )
                res.push_back(matrix[i][j]);
            for(int i=layer+1, j=col-layer-1; i<row-layer-1; i++)
                res.push_back(matrix[i][j]);
            // 这里的 i > (row-1)/2 也可以写作 layer != row-1-layer, 避免上下重复
            for(int i=row-layer-1, j=col-layer-1; i > (row-1)/2 && j >=layer; j--)
                res.push_back(matrix[i][j]);
            // 这里的 j < col/2 也可以写作 layer != col-1-layer, 避免左右重复
            for(int i=row-layer-2, j=layer; j < col/2 &&  i>layer; i--)
                res.push_back(matrix[i][j]);
        }
        return res;
    }
};

20.包含min函数的栈

题目描述

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

解法: 利用辅助栈实现

应用一个辅助栈，压的时候，如果A栈的压入比B栈压入大，B栈不压，，，，小于等于，AB栈同时压入，出栈，如果，AB栈顶元素不等，A出，B不出。

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

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> s;
        if(pushV.size()==0) return false;
        s.push(pushV[0]);
        int i = 0, j=1;
        while(!s.empty()){
            if(s.top() != popV[i]){
                if(j<pushV.size())
                    s.push(pushV[j++]);
                else
                    return false;
            }else{
                s.pop();
                i++;
            }
        }
        return true;
    }
};

更简洁的写法:

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

22.从上往下打印二叉树

题目描述

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

解法: 层次遍历

用一个变量cur_len来维护当前层的节点数, 这样就无序额外存储层深等其他信息.

/*
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> res;
        if(root==nullptr) return res;
        std::queue<TreeNode*> q_tree;
        q_tree.push(root);
        while(!q_tree.empty()){
            int cur_len = q_tree.size(); // 获取当前层节点数目
            for(int i=0; i<cur_len; i++){ //直到遍历完当前层节点
                TreeNode* cur_node = q_tree.front(); q_tree.pop();
                res.push_back(cur_node->val);
                if(cur_node->left != nullptr) q_tree.push(cur_node->left);
                if(cur_node->right != nullptr) q_tree.push(cur_node->right);
            }
        }
        return res;
    }
};

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

题目描述

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

解法: 根据后序序列的特性设计递归判断规则

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()==0) return false;
        return helper(sequence, 0, sequence.size()-1);
    }

    bool helper(vector<int> &sequence, int start, int end){
        if(start>=end) return true;
        int cur_i = start;
        while(cur_i < end && sequence[cur_i] < sequence[end]) cur_i++;
        int mid = cur_i;
        while(cur_i < end){
            if(sequence[cur_i] <sequence[end]) return false;
            cur_i++;
        }
        bool b1 = helper(sequence, start, mid-1);
        bool b2 = helper(sequence, mid, end-1);
        return b1&&b2;
    }
};

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

题目描述

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

解法一: 递归解法

先根遍历

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector<int> v_list;
    vector<vector<int> > res;
    int cur_number = 0;
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        if(root==nullptr) return res;
        cur_number += root->val;
        v_list.push_back(root->val);
        if(cur_number == expectNumber && root->left==nullptr && root->right==nullptr)
            res.push_back(v_list);
        if(root->left != nullptr ) FindPath(root->left, expectNumber);
        if(root->right != nullptr) FindPath(root->right, expectNumber);
        cur_number -= root->val;
        v_list.pop_back();
        return res;
    }
};

另一种写法: 通过减法控制当前的和

class Solution {
public:
    vector<int> v_list;
    vector<vector<int> > res;
    //int cur_number = 0;
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        if(root==nullptr) return res;
        expectNumber -= root->val; // 注意这里是减法
        v_list.push_back(root->val);
        if(0 == expectNumber && root->left==nullptr && root->right==nullptr) //条件语句变为 0 == expectNumber
            res.push_back(v_list);
        if(root->left != nullptr ) FindPath(root->left, expectNumber);
        if(root->right != nullptr) FindPath(root->right, expectNumber);
        //cur_number -= root->val; //注意, 可以不加这条语句
        v_list.pop_back();
        return res;
    }
};

解法二: 非递归

/*
非递归法：后序遍历
1.进栈时候，把值同时压入路径的向量数组，修正路径的和
2.出栈时候，先判断和是否相等，且该节点是否是叶节点，
判断完成后保持和栈一致，抛出路径，修改路径的和
3.向量数组和栈的操作要保持一致
*/
class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
        stack<TreeNode*> s;
        vector<int> v;
        vector<vector<int> > res;
        while (root || !s.empty()){
            while (root){
                s.push(root); v.push_back(root->val); expectNumber -= root->val;
                //能左就左，否则向右
                root = root->left ? root->left : root->right;
            }
            root = s.top();
            if (expectNumber == 0 && root->left == NULL && root->right == NULL)
                res.push_back(v);
            s.pop(); v.pop_back(); expectNumber += root->val;
            //右子数没遍历就遍历，如果遍历就强迫出栈
            if (!s.empty() && s.top()->left == root)
                root = s.top()->right;
            else
                root = NULL;//强迫出栈
        }
        return res;
    }
};

25.复杂链表的复制

题目描述

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

注意

链表的复制不同于其他复制，在进行链表复制时，必须创建新的节点，同时，不能通过newnode->next = oldnode-next对新节点进行赋值，这是因为这样赋值会使新链表指向旧链表的节点，造成混乱。

正确解题思路：

• 先对原链表中的每一个节点进行复制，将复制的节点插入到原节点之后，比如原链表是A->B->C，则复制后应该变成A->A1->B->B1->C->C1。
• 再按照原始链表中随机指针的指向，对新节点的随机指针进行赋值。
• 将链表拆分

/*
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; //少考虑这种情况会发生段错误
        RandomListNode* curnode = pHead;
        //C++允许在声明结构变量时省略关键字struct，但是C不允许
        while(curnode!=NULL){
            RandomListNode* clonenode = new RandomListNode(curnode->label);
            clonenode->next = curnode->next;
            curnode->next = clonenode;
            curnode = clonenode->next;
        }
        curnode = pHead;
        while(curnode!=NULL){ // 因为random有可能指向前面的节点, 所以必须在拆分链表之前进行random指针的赋值, 而不能在拆分链表的同时进行赋值
            if(curnode->random!=NULL){  //少考虑这种情况会不满足个别用例
                curnode->next->random = curnode->random->next;
                curnode = curnode->next->next;
            }
            else{
                curnode->next->random = NULL;
                curnode = curnode->next->next;
            }
        }
        curnode = pHead;
        RandomListNode* newhead = pHead->next;
        RandomListNode* newcur = pHead->next;
        while(curnode!=NULL){
            if(newcur->next == NULL){
                curnode->next = NULL;
                break;
            }
            curnode->next = newcur->next;
            newcur->next = newcur->next->next;
            curnode = curnode->next;
            newcur = newcur->next;
        }
        return newhead;
    }

};

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

题目描述

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

解法一：自己的思路

后序遍历，递归实现，首先将左子树全部变成有序的，然后将右子树全部变成有序的。由于在返回时，返回的是左右子树的根节点，因此，在将当前根节点与左右子树拼接时，需要移动到左子树的最后一个元素上（最大），与当前根节点的left拼接。对于右子树，要移动到右子树的第一个元素上（最小），与当前根节点的right拼接。

这里有一个需要注意的地方，以下两种声明方式，指针一定要初始化之后才能使用，会使代码结果表现不同，前者超时，后者通过

TreeNode* pre,* next;
TreeNode* pre=nullptr,* next=nullptr;

/*
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* node = recurve(pRootOfTree);
        while(node->left!=nullptr)
            node = node->left;
        return node;

    }

    TreeNode* recurve(TreeNode* pRootOfTree){
        TreeNode* pre=nullptr,* next=nullptr; // 这里，如果没有指定nullptr，则程序会超时！！！
        if(nullptr!=pRootOfTree->left)
            pre = recurve(pRootOfTree->left);
        if(nullptr!=pRootOfTree->right)
            next = recurve(pRootOfTree->right);
        if(pre!=nullptr){
            while(pre->right!=nullptr)
                pre=pre->right;
            pRootOfTree->left = pre;
            pre->right = pRootOfTree;
        }
        if(next!=nullptr){
            while(next->left!=nullptr)
                next = next->left;
            pRootOfTree->right = next;
            next->left = pRootOfTree;
        }
        return pRootOfTree;
    }
};

解法二：中序遍历，递归实现

由于对搜索二叉树来说，中序遍历的结果就是有序的，因此，只需要通过维护一个prenode指针来标记当前节点的上一个节点即可完成双向有序链表。

注意，这里有一个非常关键的点，那就是TreeNode*& prenode，如果少了&引用标识，则结果错误！具体原因看文章关于*&和*的联系和区别。

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==nullptr) return nullptr;
        TreeNode* prenode = nullptr;
        recurve(pRootOfTree,prenode);
        while(pRootOfTree->left!=nullptr)
            pRootOfTree = pRootOfTree->left;
        return pRootOfTree;

    }

    void recurve(TreeNode* root, TreeNode*& prenode){
        if(root->left!=nullptr)
            recurve(root->left,prenode);

        root->left = prenode;
        if(prenode!=nullptr) prenode->right = root;
        prenode = root;

        if(root->right!=nullptr)
            recurve(root->right,prenode);
    }
};

解法三：中序遍历，非递归实现

基于中序遍历的非递归方法，思路与解法二一致。

但是这里有个疑问，为什么使用下面的代码会发生段错误。

while(pRootOfTree->left!=nullptr)
    pRootOfTree = pRootOfTree->left;
return pRootOfTree;

发生段错误的原因主要是因为没有对pRootOfTree进行空指针检查,
就直接使用了该指针的成员变量, 访问了本不存在的内存, 从而造成
了段错误, 修改方法是在程序前加上空指针检查

以下代码额外设置了一个指针指向第一个节点，以避免使用上面代码带来的段错误。

class Solution {
public:
    stack<TreeNode*> S_node;
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==nullptr) return pRootOfTree;
        TreeNode* P = pRootOfTree;
        // TreeNode* node = pRootOfTree; 进行了空指针检查, 所以不用再使用这个指针了, 下面也是同理
        TreeNode* pre = nullptr;
        while(P!=nullptr||!S_node.empty()){
            while(P!=nullptr){
                S_node.push(P);
                P = P->left;
            }
            if(!S_node.empty()){
                P = S_node.top();
                P->left = pre;
                if(pre!=nullptr){
                    pre->right = P;
                }//else
                    //node = P;
                pre = P;
                S_node.pop();
                P = P->right;
            }
        }
        while(pRootOfTree->left!=nullptr)
            pRootOfTree = pRootOfTree->left;
        //return node;
        return pRootOfTree;
    }
};

另一种看起来逻辑性更好的写法:

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree == nullptr) return pRootOfTree;
        std::stack<TreeNode*> s_tree;
        TreeNode* cur_node = pRootOfTree;
        TreeNode* head = nullptr; //双向链表的头指针
        TreeNode* pre_node = nullptr; //双向链表的pre指针
        while(!s_tree.empty() || cur_node!=nullptr){
            while(cur_node!=nullptr){
                s_tree.push(cur_node);
                cur_node = cur_node->left;
            }
            if(!s_tree.empty()){
                cur_node = s_tree.top(); s_tree.pop();
                if(head==nullptr){
                    head = cur_node;
                    pre_node = head;
                }else{
                    pre_node->right = cur_node;
                    cur_node->left = pre_node;
                    pre_node = cur_node;
                }
                cur_node = cur_node->right;
            }
        }
        return head;
    }
};

27.字符串的排列

题目描述

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

解法一: 递归思路（没想到）：

将一个字符串看成两个部分，前一部分为首位字母，剩下的是后一部分。通过将首位字母与后一部分的所有字符交换（包括跟自己交换），可以得到第一个位置的所有可能情况。然后，再将剩下的部分看作是一个新的字符串，同样将剩余部分分成两部分，其中，第一部分是剩余部分的首位。如此，可以按照递归进行处理。

class Solution {
public:
    //bool my_sort(string s1, string s2){ return s1<s2;};
    vector<string> Permutation(string str) {
        vector<string> v_string;
        if(str=="") return v_string;
        PermutationHelp(v_string, 0, str);
        std::sort(v_string.begin(), v_string.end());
        return v_string;
    }

    void PermutationHelp(vector<string>& v_string, int pos, string str){
        /* if(pos == 0 ){
            v_string.push_back(str);
            PermutationHelp(v_string, pos+1, str);
        } \*/

        //这里i=pos而不是pos+1的原因是：如果用pos+1,会导致丟解，即自己与自己交换的那种情况没有继续向下递归
        for(int i=pos; i<str.length(); i++){
            std::swap(str.at(pos), str.at(i));
            if(std::count(v_string.begin(), v_string.end(), str) == 0) // 重复检查, 这里需要遍历, 会大大提高程序复杂度
                v_string.push_back(str);
            PermutationHelp(v_string, pos+1, str);
            //std::swap(str.at(pos), str.at(i));
            //能够注释本行的原因是因为上面已经利用count进行了重复检查. 但是实际上, 这是一种不太好的做法, 更好的写法在下面, 无需进行count重复检查
        }
    }
};

更简洁的写法:

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str == "") return res;
        permute_helper(res, 0, str);
        std::sort(res.begin(), res.end());
        return res;
    }

    void permute_helper(vector<string> &res, int pos , string &str){
        if(pos == str.size())
            res.push_back(str); // 注意, 这里是在pos==str.size()才将str放入res中, 这与上面的逻辑看起来好像有些矛盾
            // 实际上, 当pos==str.size()时, 包含了所有可能情况, 即一次交换也没有发生(只与自身交换), 或者交换了某些位置等情况
        else{
            for(int i = pos; i<str.size(); i++){
                if(str[pos] == str[i] && pos!=i) continue; //防止重复出现, 如"aa", 则只输出一个 [a,a]
                std::swap(str[pos], str[i]);
                permute_helper(res, pos+1, str);
                std::swap(str[pos], str[i]);
            }
        }
    }
};

解法二: 迭代

对于已经排列好的n-1个字符, 如果来了第n个字符, 则这个字符可以插入到n-1个字符的n个位置上, 注意控制字符是否重复, 即对于”aaaaa”来说, 如果新来的字符为’a’, 则这个’a’只有一种插法, 因此, 我们做判断: a与位置i(0~3)上的字符如果相等, 则不插入, 故而a只会插入到位置4上.(虽然位置4不存在, 但是插入时是能以超尾位置插入的)

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res(1,"");
        if(str=="") {res.pop_back(); return res;}
        for(int i=0; i<str.size(); i++){
            vector<string> res_tmp(std::move(res));
            for(int j=0; j<res_tmp.size(); j++){
                for(int k=0; k<=res_tmp[0].size(); k++){
                    if(k<res_tmp[0].size() && str[i] == res_tmp[j][k]) continue;
                    //跳过重复排列, 例如将a插入a的两端,只选择插一端即可(a插入1位置), 另一端跳过(a插入0位置)
                    string str_tmp = res_tmp[j];
                    str_tmp.insert(k, 1, str[i]);
                    res.push_back(str_tmp);
                }
            }
        }
        std::sort(res.begin(), res.end());
        return res;
    }
};

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

题目描述：

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

思路一：如果数组是有序的，那么，出现次数超过数组长度一半的数字一定位于数组的中间位置，如果中间位置的数字出现次数小于数组长度的一半，那么就不存在。该方法需要进行排序，所以算法时间复杂度为 $nlog(n)$ 。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        //bool mysort(int a, int b) {return a<b;}
            vector<int> counts;
            std::sort(numbers.begin(), numbers.end());
            int n = std::count(numbers.begin(), numbers.end(), numbers.at((int)numbers.size()/2));
            if (n > numbers.size()/2) return numbers.at((int)numbers.size()/2);
            else return 0;


	}
};

思路二：Patition

根据快排的思想，由于该数字一定在数组的中间位置，那么可以借助Partition来实现，随机选一个数字进行Partition，如果返回的mid索引最终停在N/2处，那么该索引对应的数字就有可能是答案，此时，只需统计该数字的出现次数即可。

该方法的时间复杂度是 $O(n)$ ，因为只会执行一边的Partition，并不会执行另一边.

Partition的时间复杂度为 $O(n)$, 找到mid == numbers.size()/2的复杂度为 $O(logn)$, 因此总的时间复杂度为 $O(nlogn)$.

需要注意，具体在代码中看

bool mysort(int a, int b) {return a<b;}
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int low = 0 ;
        int high = numbers.size()-1;
        int mid = Partition(numbers, low, high);
        while(mid != numbers.size()/2){
            if(mid < numbers.size()/2){
                low = mid + 1;
                mid = Partition(numbers, low, high);
            }else{
                high = mid - 1;
                mid = Partition(numbers,low, high);
            }
        }
        if(std::count(numbers.begin(), numbers.end(), numbers.at(mid)) > numbers.size()/2)
            return numbers.at(mid);
        else
            return 0;


	}

    int Partition(vector<int>& numbers, int low, int high){
        int p = numbers.at(low);
        int mid = low;
        while(low<high){
            while(low<high && p < numbers.at(high)) high--;
		//这里如果p用的是<,则需要下面的low++逻辑，否则，会陷入死循环，如果用的是<=，则在返回时，会返回首个元素的坐标
            numbers.at(low) = numbers.at(high);
            if(low!=high) low++;
            while(low<high && p > numbers.at(low)) low++;
            numbers.at(high) = numbers.at(low);
            if(low!=high) high--;
        }
        numbers.at(low) = p;
        if(low == high) return mid;
        else
            return low;
    }
};

思路三：同增异减

如果数组中存在这样一个数，那么这个数的出现次数一定大于其他所有数的出现次数总和，因此，设置两个变量，一个number用来存储数组中的第一个数，另一个num置为1,如果下一个数与number数相同，则num加一，否则减1,如果num被减为0,那么number转而存储下一个数，同时将num置为1。

这样，如果存在这个数，最终这个数一定为number，且num大于1。

// 这个解法是错误的, 不论怎么处理, 最后都要做count>half的检查, 这个方法能通过牛客的原因是因为牛客官方测例不够, 对于{2,2,3,3,5,5}的情况, 很明显应该输出0, 但是这个方法输出的是5
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int number = numbers.at(0);
        int num = 1;
        for(vector<int>::iterator iter = numbers.begin()+1; iter != numbers.end(); iter++){
            if(num == 0){ //这里与下面的区别之一是，一定要放在for训练内部的前面
                number = * (iter-1); //区别之二这里如果使用iter-1,则无须在最后做count检查
                num = 1;
            }
            if(number == * iter) num++;
            else num--;
        }
        if(num >= 1) return number; //这里，num只需要>=1 即可，仔细想一想这是为什么，为啥用了iter-1,就不用检查count。
        else return 0;
    }
};

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int number = numbers.at(0);
        int num = 1;
        for(int i = 1; i<numbers.size(); i++){
            if(num==0){
                number = numbers[i-1];
                num=1;
            }
            if(number == numbers[i]) num++;
            else num--;
        }
        if(count(numbers.begin(), numbers.end(), number) > numbers.size()/2) return number;
        //由于上面用的是iter，所以最终的num为1的数，只是有可能是我们要得数字，因此，需要进行检查。
        else return 0;

    }
};

29.最小的K个数

题目描述：

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

一定要考虑边界情况：

• 数组为空
• k大于数组size
• k小于0

思路一：最直接的想法，就是先对数组排序，然后输出前k个数。复杂度为 $nlog(n) + n$ 。 快排

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> k_input;
        if(k > input.size() || input.size()<=0) return k_input;
        int low = 0;
        int high = input.size()-1;
        quickSort(input, low, high);
        //vector<int> k_input(&input.at(0), &input.at(k-1));
        for(int i=0; i<k; i++) k_input.push_back(input.at(i));
        return k_input;
    }


    void quickSort(vector<int>& input, int low, int high){
        int mid = Partition(input, low, high);

        if(mid<high)    quickSort(input, mid+1, high);
        if(mid>low)    quickSort(input, low, mid-1);

    }

    int Partition(vector<int>& input, int low, int high){
        int p = input[low];
        while(low<high){
            while(low<high && p<=input[high]) high--;
            input[low] = input[high];
            while(low<high && p>=input[low]) low++;
            input[high] = input[low];
        }
        input[low] = p;
        return low;
    }
};

思路二：遍历整个数组，将当前元素与k_input数组进行比较，按照顺序插入，并且超出k的部分删除，最终直接返回k_input。时间复杂度 $O(nk)$ 。（该思想与冒泡排序思想类似）。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> k_input;
        if(k>input.size() || input.size()<=0) return k_input;
        k_input.push_back(input.at(0));
        for(auto iter = input.begin()+1; iter!=input.end(); iter++){
            for(int i =0 ;i<k; i++){
                if(i == k_input.size()){
                    k_input.push_back(*iter);
                    break;
                }else if(*iter < k_input.at(i)){
                    k_input.insert(k_input.begin()+i, *iter);
                    break;
                }
            }
            if(k_input.size() > k) k_input.pop_back();
        }

        return k_input;
    }
};

解法三: 大顶堆

遍历数组, 维护一个大顶堆, 每遇到一个比堆顶小的数, 就将其插入大顶堆 (如果是找最大的k个数, 就用小顶堆)

时间复杂度: $O(nlogk)$
空间复杂度: $O(k)$

借助priority_queue数据结构

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int> q;
        vector<int> res;
        if(k<=0 || k>input.size()) return res; // 边界条件检查, 是否会出现段错误或输出结果错误
        for(int i=0; i<input.size(); i++){
            if(i<k) q.push(input[i]);
            else if(input[i] < q.top()){
                q.pop(); q.push(input[i]);
            }
        }
        while(!q.empty()){
            res.push_back(q.top());
            q.pop();
        }
        return res;
    }
};

利用数组实现堆

class Solution {
public:
    void heapify(vector<int> &vec_heap, int index, int heap_size){
        int max=index;
        int left=index*2+1;
        int right = index*2+2;
        if(left<heap_size && vec_heap[max] < vec_heap[left]){
            //int temp = max; // 无需交换max和left, 只需记录max的值即可, 下面的right同理
            max = left;
            //left = temp;
        }
        if(right<heap_size && vec_heap[max] < vec_heap[right]){
            //int temp = max;
            max = right;
            //right = temp;
        }
        if(index != max){
            std::swap(vec_heap[index], vec_heap[max]);
            heapify(vec_heap, max, heap_size);
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(k<=0 || k > input.size()) return res;
        for(int i = 0; i<k;i++){
            res.push_back(input[i]);
        }
        for(int i=k-1; i>=0;i--){ //初始化堆
            heapify(res, i, k);
        }
        for(int i = k; i < input.size(); i++){ //i要从k开始, 因为k之前的已经是堆了
            if(input[i] < res[0]){
                res[0] = input[i];
                heapify(res, 0, k);
            }
        }
        for(int i = res.size()-1; i>0; i--){
            std::swap(res[0], res[i]);
            heapify(res, 0, i);
        }
        return res;
    }
};

另一种写法:

class Solution {
public:
    void heapify(vector<int> &vec_heap, int index, int heap_size){
        int max = index;
        int left = index*2 + 1;
        int right = index*2 + 2;
        if(left < heap_size && vec_heap[left] > vec_heap[max])
            max=left;
        if(right < heap_size && vec_heap[right] > vec_heap[max])
            max=right;
        if(max!=index){
            std::swap(vec_heap[max], vec_heap[index]);
            heapify(vec_heap, max, heap_size);
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(k<=0 || k>input.size()) return res;
        for(int i=k-1; i>=0; i--)
            heapify(input, i,k);
        for(int i=k; i<input.size(); i++){
            if(input[i] < input[0]){
                //std::swap(input[i], input[0]);
                input[0] = input[i];
                heapify(input, 0, k);
            }
        }
        for(int i=k-1; i>=0; i--){
            res.push_back(input[0]);
            std::swap(input[0], input[i]);
            heapify(input, 0, i); // i变小, 所以从k-1开始
        }
        return res;
    }
};

解法四: 快速选择算法

时间复杂度: 平均为 $O(n)$

复杂度分析: 每次都会扔掉一半, 所以每次进行检查的元素个数为之前的一半, 所有时间复杂度大致为:

$$T(n) = n + n/2 + n/8 + ... + (n/2)^k = n*(1-2^{-k})/(1-2^{-1}) = 2n$$

也就是说, 只要枢纽元素的选择使得两边的元素数量尽可能均衡, 就可以得到 $O(n)$ 的时间复杂度

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(k<=0 || k>input.size()) return res;
        quick_select(input, 0, input.size()-1, k);
        //运行完 quick_select 以后, k之前的元素都比k位置上的元素小
        for(int i = 0; i<k; i++)
            res.push_back(input[i]);
        return res;
    }

    void quick_select(vector<int> &vec, int low, int high, int k){
        int P = vec[low]
        while(low < high){
            while(low<high && P<=vec[high]) high--;
            vec[low] = vec[high];
            while(low<high && P>=vec[low]) low++;
            vec[high] = vec[low];
        }
        vec[low] = P; //此时, low所处位置为枢纽元P, low之前的都小于P, low之后的都大于P
        if(low == k-1) return; //如果low所处位刚好为k-1, 则从这之前的k个元素一定是最小的(包括vec[low]自身)
        else if( k < low) quick_select(vec, 0, low, k);
        else quick_select(vec, low+1, high, k);

    }
};

问题扩展 1

输入是两个整数数组, 他们任意两个数的和有可以组成一个数组, 求这个和中的前k个数

分析:

1. 假设两个整数数组为A和B, 各有N个元素, 任意两个数的和组成的数组C就有 $N^2$ 个, 那么可以把这些和看成N个有序数列, 由此, 问题就转变成了在这 $N^2$ 个有序数列里, 找到前k个最小的元素.
   • A[1]+B[1] <= A[1]+B[2] <= A[1]+B[3] <= …
   • A[2]+B[1] <= A[2]+B[2] <= A[2]+B[3] <= …
   • …
   • A[N]+B[1] <= A[N]+B[2] <= A[N]+B[3] <= …

问题扩展 2

有两个序列A和B都按照升序排列, 对于 1<=i,j<=k, 求k个最小的(ai+bj), 要求算法尽量高效.

30.连续子数组的最大和

题目描述

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

解法一：穷举

穷举遍历，时间复杂度 $O(n^2)$ 。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int max=array.at(0);
        for(auto iter=array.begin(); iter!=array.end(); iter++){
            //if(*iter > 0){
                int temp = 0;
                for(auto it = iter; it!=array.end(); it++){
                    temp += *it;
                    if(temp > max)
                        max = temp;
                //}
            }
        }
        return max;
    }
};

另一种写法(感觉更好理解些)

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size() == 0) return INT_MIN;
        int max_sum = array[0];
        int cur_sum = 0;
        for(auto x : array){
            cur_sum += x;
            if(cur_sum > max_sum) // 更新max_sum
                max_sum = cur_sum;
            if(cur_sum < 0) // 如果当前和为负, 则重置cur_sum
                cur_sum = 0;
        }
        return max_sum;
    }
};

解法二：最优-两个变量记录sum

$O(n)$ 的方法，根据数组性质，设置两个变量，一个记录当前的最大值，一个记录当前的子序列之和。首先，如果当前子序列之和为负，那么就是说，从当前位置开始的子序列，比从之前位置开始的子序列大，那么就可以不考虑从之前位置开始的子序列，之前累计的和也被抛弃。

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

解法三：dp

动态规划。与解法二的思路异曲同工，核心思想可有下述公式表示。 $f(i)代表以第i个数字结尾的子数组的连续最大和$

$$f(x)= \begin{cases} pData[i]& {i=0 或者f(i-1)\le 0} \\ f(i-1)+pData[i]& {i\ne 0 并且 f(i-1) > 0} \end{cases}$$

上面的形式是递归的，通常情况下都用递归的方式来分析动态规划问题，但最终都会基于循环去编码。 上述公式对应的非递归形式就是思路二的代码。

递归写法：

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int max = array.at(0);
        f(array, array.size()-1, max);
        return max;
    }

    int f(vector<int>& array, int i, int& max){
        if(i==0) return array.at(0);
        int f1  = f(array, i-1, max);
        if(f1<0)
            f1 = array.at(i);
        else{
            f1 = f1+ array.at(i);
        }
        if(f1> max) max =f1;
        return f1;
    }
};

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出现的次数）。

解法一：

时间复杂度: $O(nm)$, m为数字的长度

直接借助C++函数，先将int转换成string，然后count计算string里面‘1’的个数。（这种方法可能面试不会满意，可以提一下，不过肯定有其他方法）

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int count_1 = 0 ;
        for(int i = 1; i<=n; i++){
            string str = std::to_string(i);
            count_1 += std::count(str.begin(), str.end(), '1');
        }
        return count_1;
    }

};

解法二：

对每个数字进行除和求余的运算，得到每个数字中1的个数，然后将个数相加。 该方法的复杂度为 $O(nlogn)$ ，该种思想过于直接，时间复杂度较高，属于次等方案。（注意：这里的log底数按理说是10 ，但说大O记法是不考虑常数的，所以直接表示成log就可以）

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int count =0 ;
        for(int i =1 ;i<=n;i++){
            int i1 = has1(i);
            if(i1)
                count+=i1;
        }
        return count;
    }

    int has1(int num){
        int count=0;
        while(num){
            if(num%10 == 1)
                count++;
            num /= 10;
        }
        return count;
    }

};

解法三：

时间复杂度: $O(logn)$

设定整数点（如1、10、100等等）作为位置点i（对应n的各位、十位、百位等等），分别对每个数位上为1的情况有多少种进行分析

根据设定的整数位置，对n进行分割，分为两部分，高位n/i，低位n%i

当i表示百位，且百位对应的数>=2时,如n=31456,i=100，则a=314,b=56，此时百位为1的情况有a/10+1=32（最高两位0~31，百位为1,共32种），每一种都包含100个连续的点，即共有(a%10+1) * 100种情况百位为1

当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

当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 或者 1 时，则a/10==(a+8)/10，当百位>=2，补8会产生进位位，效果等同于(a/10+1)

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int count = 0;
        for(int i =1; i<=n; i*=10){
            int a = n/i;
            int b = n%i;
            count+=(a+8)/10*i+(int)(a%10==1)*(b+1);
        }
        return count;
    }
};

这种方法是一种通用解法, 可以用来求解整数0~n中x的出现次数, 其中, x 代表1~9中(0的情况貌似也差不多?)的任意一个数, 通用写法如下

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int count = 0;
        for(int i = 1; i<=n ;i = i*10){
            int a = n/i;
            int b = n%i;
            count += (a+(10-x-1))/10 * i + (int)(a%10==x) * (b+1); //在这里根据x的值, 可以求得不同情况下的解, 例如, 若要求8的出现次数, 则为:count += (a+1)/10 * i + (int)(a%10==8) * (b+1);
        }
        return count;
    }
};

解法四：

剑指offer的递归方法，没看懂，感觉好像有错误？

32.把数组排成最小的数

题目描述：

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

难点：

1. 找出一个新的排序规则，同时要证明这个排序规则是有效的
2. 看到将两个int整数拼接在一起，就应该想到大数问题

解法一：

主要考虑如何制定一个合理的判断规则：

比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较s1+s2,和s2+s1那个大，如果s1+s2大，那说明s2应该放前面，所以按这个规则，s2就应该排在s1前面。

基于上面的规则，首先将vector<int>转换成对应的vector<string>，然后直接利用快排进行排序，最后将排好序的字符串向量拼接输出。

时间复杂度为主要在排序，因此为 $O(nlogn)$ 。

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        if(numbers.size() == 0) return "";
        vector<string> str_numbers;
        for(auto it=numbers.begin(); it!=numbers.end(); it++){
            str_numbers.push_back(std::to_string(*it));
        }
        int low =0;
        int high = numbers.size()-1;
        quickSort(str_numbers, low, high);
        string s="";
        for(auto it = str_numbers.begin(); it != str_numbers.end(); it++){
            s+=*it;
        }
        return s;
    }

    void quickSort(vector<string>& str_numbers, int low , int high){
        int mid = Partition(str_numbers, low, high);
        if(mid<high) quickSort(str_numbers,mid+1, high);
        if(mid>low) quickSort(str_numbers, low, mid-1);
    }

    int Partition(vector<string>& str_numbers, int low, int high){
        string p = str_numbers.at(low);
        while(low<high){
            string s1= p + str_numbers.at(high);
            string s2= str_numbers.at(high) + p;
            while(low<high && s1.compare(s2) <=0){
                high--;
                s1 = p + str_numbers.at(high);
                s2 = str_numbers.at(high) + p;
            }
            str_numbers.at(low) = str_numbers.at(high);

            s1 = p + str_numbers.at(low);
            s2 = str_numbers.at(low) + p;
            while(low<high && s1.compare(s2) >=0){
                low++;
                s1 = p + str_numbers.at(low);
                s2 = str_numbers.at(low) + p;
            }
            str_numbers.at(high) = str_numbers.at(low);
        }
        str_numbers.at(low) = p;
        return low;
    }
};

更整洁的写法:

class Solution {
public:
    bool cmp(int a, int b){
        string sa = std::to_string(a);
        string sb = std::to_string(b);
        return sa+sb <= sb+sa;
    }
    string PrintMinNumber(vector<int> numbers) {
        if(numbers.size()==0) return ""; //!!!!少了这句话会产生段错误
        quick_sort(numbers, 0, numbers.size()-1);
        string res;
        for(auto num : numbers)
            res += std::to_string(num);
        return res;
    }
    int partition(vector<int> &numbers, int low, int high){
        int P = numbers[low];
        while(low<high){
            while(low<high && cmp(P, numbers[high])) high--;
            numbers[low] = numbers[high];
            while(low<high && cmp(numbers[low], P)) low++;
            numbers[high] = numbers[low];
        }
        numbers[low] = P;
        return low;
    }
    void quick_sort(vector<int> &numbers, int low , int high){
        int mid = partition(numbers, low, high);
        if(low<mid) quick_sort(numbers, low, mid-1);
        if(mid<high) quick_sort(numbers, mid+1, high);
    }
};

用C++的内置排序函数:

class Solution {
public:
    struct{
        bool operator()(int a, int b) const{
            string sa = std::to_string(a);
            string sb = std::to_string(b);
            return sa+sb < sb+sa;
        }
    }cmp;
    string PrintMinNumber(vector<int> numbers) {
        std::sort(numbers.begin(), numbers.end(), cmp);
        string res;
        for(auto num : numbers)
            res += std::to_string(num);
        return res;
    }
};

33.丑数

题目描述：

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

解法一：穷举判断

最简单的方法，就是对所有整数进行判断，该方法很容易超时

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<=0) return 0;
        int i = 0;
        int num = 1;
        int ugly=0;
        while(i<index){
            if(IsUgly(num)){
                i++;
                ugly = num;
            }
            num++;
        }
        num--;
        return num;


    }

    bool IsUgly(int num){
        while(num%2==0)
            num /=2 ;
        while(num%3==0)
            num /= 3;
        while(num%5==0)
            num /= 5;
        if(num == 1) return true;
        else return false;
    }



};

解法二：根据丑数性质构造丑数

时间复杂度: $O(n^2)$
空间复杂度: $O(n)$

用空间换时间，用一个数组将之前的丑数都存起来，然后，在判断下一个丑数时，不用对逐个整数判断，而只是与丑数和2,3,5的乘积进行判断

// 使用指针时，一定要千万注意，指针会改变指向地址的值，使得其他指向该地址的指针，其指向的值也跟着变！

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<=0) return 0;
        int* UglyArray = new int[index];
        UglyArray[0] = 1;

        for(int i = 1 ;i < index; i++){

            int *Ugly2 = UglyArray;
            int *Ugly3 = UglyArray;
            int *Ugly5 = UglyArray;
            while(*Ugly2 * 2 <= UglyArray[i-1])
                Ugly2++;
            while(*Ugly3 * 3 <= UglyArray[i-1])
                Ugly3++;
            while(*Ugly5 * 5<= UglyArray[i-1])
                Ugly5++;
            UglyArray[i] = Min(*Ugly2 *2, *Ugly3 *3, *Ugly5 *5);
        }
        int num = UglyArray[index-1];
        delete[] UglyArray;
        return num;

    }

    int Min(const int& a, const int& b,const int& c){
        int x = a<b? a:b;
        return x<c? x:c;
    }
};
//*

解法三: 最优

解法二的思路是正确的, 但是代码的实习上有重复计算, 例如, 最开始丑数集合为 {1}, 经过三次循环后, 丑数集合为 {1, 2, 3, 5}, 此时, 当进行第四次循环时, 会重复计算 1×2, 1×3, 1×5. 根据丑数的定义, 从 1 开始, 可以得到 2,3,5 这三个丑数, 然后从 2,3,5 开始(此时不用管1了), 可以得到 4,6,10,6,9,15,10,15,25 九个丑数, 根据这个思路, 我们可以指定三个变量来指示当前应该与2,3,5相乘的丑数, 而不是从第一个丑数开始遍历.

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index <=1) return 0;
        vector<int> ugly_numbers(index);
        ugly_numbers[0] = 1;
        int t2=0, t3=0, t5=0;
        for(int i=1; i<index; i++){
            int ugly_num = std::min( ugly_numbers[t2]*2, std::min(ugly_numbers[t3]*3, ugly_numbers[t5]*5));
            if(ugly_num == ugly_numbers[t2]*2) t2++;
            // 因为新增的最小丑数为 t2指示的丑数与2相乘, 所以t2之前的数都不可能再与2相乘组成新的丑数, 所以无需检查t2之前的数
            if(ugly_num == ugly_numbers[t3]*3) t3++;
            // 注意, 这里没有用else if 的原因是, 可能会出现重复的情况, 对于这种情况, 重复的指示器都要++, 避免将重复的丑数添加到数组中
            if(ugly_num == ugly_numbers[t5]*5) t5++;
            ugly_numbers[i] = ugly_num;
        }
        return ugly_numbers[index-1];
    }
};

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

题目描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）

解法一（自想）

每遇到一个字符，判断其是否是第一次出现，如果是则将它存在一个vector once里面，如果不是，则判断该字符是否在另一个vector more里面，如果没在，则该once中的该字符转移到mul里面，接着判断下一个字符。最终，输出once里面的首个元素。

该方法时间复杂度为 $O(n^2)$，并不令人满意。

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        vector<int> once_char;
        vector<char> mul_char;
        for(int i = 0; i< str.length();i++){
            bool isfirst = true;
            for(auto it = once_char.begin(); it!=once_char.end(); it++){
                if(str[*it] == str[i]){
                    isfirst = false;
                    once_char.erase(it);
                    mul_char.push_back(str[i]);
                    break;
                }

            }
            if(isfirst){
                auto mul_it = find(mul_char.begin(), mul_char.end(), str[i]);
                if(mul_it != mul_char.end())
                    isfirst = false;
            }
            if(isfirst){
                once_char.push_back(i);
            }
        }
        if(once_char.empty()) return -1;
        return once_char.front();
    }
};

解法二：牛客

借助哈希表，时间复杂度为 $O(n)$。哈希表的构造可以用256大小的数组实现，字符对应的int值可作为哈希表的索引，表内的内容存储了该字符出现的次数。总共需要遍历两次字符串，第一次更新数组内字符出现的次数，第二次找到首个出现次数为1的字符。空间复杂度为 $O(1)$ （256是常数）

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int hash_map[256];
        for(int i =0;i<256;i++)
            hash_map[i] = 0; //若少了初始化数组，则通不过，经过验证，数组默认内部不是0,而是随机数？
       //有一种更标准初始化为0的方法，无需显式while循环：int hash_map[256]= {0};
        for(int i = 0; i<str.length(); i++){
            hash_map[int(str[i])]++;
        }

        for(int i = 0; i<str.length(); i++){
            if(hash_map[int(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

注意：

仔细思考，这道题的P的数量会非常大，对于长度为n的数组，其P值最大可为 $\frac{n(n-1)}{2}$ 个。根据体重给出的数据，n最大可为 $2\times 10^5$ ，因此，P最大为 $\frac{2\times 10^5\times(2\times10^5 -1)}{2} \approx 2\times 10^{10}$,因此，使用int类型的数据时，有可能超过限制。所以，要使用long！( int类型数据范围为-21 4748 3648 到 21 4748 3647, 数量级在 $10^9$ 左右)

解法一（自）

暴力求解，时间复杂度 $O(n^2)$ ，这样做肯定不行

解法二（剑指）: 归并排序, 递归实现

将数组中的元素进行归并排序, 排序的时候, 如果前面子数组的元素大于后面的元素, 那么可以组成的逆序对的数量就是后面元素剩余的元素数量(两个子数组各自都已经排好序).

这里需要注意的几点：

1. 初始化是，将data数据复制到temp中，然后在递归时，将data和temp数组交换传递，可以不用在数组融合时，将temp中的数据复制到data中， 减少计算次数
2. 数组融合时使用的while循环，条件均为 $<=$ 或 $>=$。
3. 每次得到P的一部分时，都进行取余数，可保证P的值不会过大。（但还是要用long型整数）

class Solution {
public:
  int InversePairs(vector<int> data) {
      if (data.size() == 0) return 0;
      vector<int> temp= data;
      //int P=0;
      long P = mergeSort(data,temp, 0, data.size()-1);

      return P%1000000007;

  }

  long mergeSort(vector<int>& data,vector<int>& temp, int first, int last){
      int mid = (last + first)/2;
      long inv1=0,inv2=0,inv=0;
      if(first< last){
        //这里，首先temp和data相同，因此对于mergeSort来说，可以顺序颠倒
        //此时相当于把temp当前真实数组，而data当作了缓存空间
        //经过mergeSort后，data里面数据就是分别排好序的
        //所以传向mergeArray时，要把data放前面，把temp放后面
          inv1 = mergeSort(temp, data, first, mid);  //必须temp在前, 因为temp是已经将子数组排序过的
          inv2 = mergeSort(temp, data, mid+1, last);
          inv = mergeArray(data, temp, first, mid, mid+1, last); //此处data在前的原因是经过mergeSort以后, data变成了排序号的.

          //上面这种写法的可读性不好, 如果在mergArray函数里面, 使data = temp , 就能写出下面这种可读性较好的形式(但是由于多了赋值操作, 在牛客上会超时). 但是使用for循环只复制需要复制的部分, 就不会超时
          /*
          inv1 = mergeSort(data, temp, first, mid);
          inv2 = mergeSort(data, temp, mid+1, last);
          inv = mergeArray(data, temp, first, mid, mid+1, last);
          */
      }
      return (inv1+inv2+inv)%1000000007;
  }

  long mergeArray(vector<int>& data, vector<int>& temp, int first1,int last1,int first2,int last2){
      long int inv = 0;
      int t = last2;
      int i = last1;
      int j = last2;
      while(i>=first1 && j>=first2){
          if(data.at(i) > data.at(j)){
              temp.at(t) = data.at(i);
              inv += j-first2+1;;
              i--;
              t--;
          }else{
              temp.at(t) = data.at(j);
              j--;
              t--;
          }
      }
      while(i>=first1){
          temp.at(t) = data.at(i);
          t--;
          i--;
      }
      while(j>=first2){
          temp.at(t) = data.at(j);
          j--;
          t--;
      }
      // data=temp;  //这个赋值操作会使得代码整体的可读性较好, 但是可能会超时
      /*for(int i=first1; i<=last2; i++)
            data[i] = temp[i]; //这种复制每次只会复制一部分, 故而没有超时
      */  
      return inv%1000000007;
  }
};

解法三（剑指）: 归并排序, 迭代实现

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

题目描述

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

解法一：栈

时间复杂度: $O(m+n)$, 遍历两个链表
空间复杂度: $O(m+n)$, 两个栈

分析公共子节点的特点，首先，是单向链表，因此，从第一个公共子节点开始，后面的都是一样的，所以最好是能从链表的最后一项还是比较。但由于是单向链表，因此只能从头访问，从能访问最后的节点。 就像是先进先出一样 因此，考虑用两个辅助栈来帮助实现～

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        stack<ListNode*> s1;
        stack<ListNode*> s2;
        for(ListNode* cur = pHead1; cur!=nullptr; cur = cur->next){
            s1.push(cur);
        }
        for(ListNode* cur = pHead2; cur!=nullptr; cur = cur->next){
            s2.push(cur);
        }
        ListNode* firstCN = nullptr;
        while(!s1.empty() && !s2.empty()){
            if(s1.top() == s2.top()){
                firstCN = s1.top();
                s1.pop();
                s2.pop();
            }else
                break;
        }

        return firstCN;
    }
};

解法二: 常数空间复杂度

时间复杂度: $O(m+n)$, 遍历两次
空间复杂度: $O(1)$, 不使用额外空间

首先遍历得到两个链表的长度, 然后先让长链表前进长度差个节点, 接着两个链表共同向前遍历, 当相遇时即为第一个公共节点.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==nullptr || headB==nullptr) return nullptr;
        int lenA = 0;
        ListNode *curA = headA;
        while(curA !=nullptr){
            lenA++;
            curA = curA->next;
        }
        int lenB = 0;
        ListNode *curB = headB;
        while(curB != nullptr){
            lenB++;
            curB = curB->next;
        }
        if(lenA > lenB){
            int len = lenA-lenB;
            curA = headA;
            while(len--){
                curA = curA->next;
            }
            curB = headB;
            while(curA!=nullptr && curB!=nullptr){
                if(curA == curB) return curA;
                curA = curA->next;
                curB = curB->next;
            }
            return nullptr;
        }else{
            int len = lenB-lenA;
            curB = headB;
            while(len--){
                curB = curB->next;
            }
            curA = headA;
            while(curA!=nullptr && curB!=nullptr){
                if(curA == curB) return curA;
                curA = curA->next;
                curB = curB->next;
            }
            return nullptr;
        }
    }
};

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

题目描述

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

解法一（自想）

先利用二分查找找到该数字的下标，然后统计该数字左右两边的相等数的个数，虽然二分查找的时间复杂度为$O(logn)$，但是在对该数左右两边查看相等数个数时，时间复杂度为 $O(n)$，因此，最终的时间复杂度应为 $O(n)$ 。 （这样的复杂度不会让面试官满意）

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int count = 0;
        if(data.size() == 0) return count;
        int index = binarySearch(data, k, 0, data.size()-1);
        if(index == -1)
            return count;
        else{
            int i = index-1;
            while(index<data.size() && data.at(index) == k){
                index++;
                count++;
            }
            while(i>=0 && data.at(i) == k){
                i--;
                count++;
            }
        }
        return count;
    }

    int binarySearch(vector<int>& data, int num, int first, int last){
        if(first == last){
            if(data.at(first) == num) return first;
            else return -1;
        }
        int mid = (first+last)/2;
        if(data.at(mid) == num) return mid;
        else if(data.at(mid) > num) return binarySearch(data, num ,first, mid);
        else return binarySearch(data, num, mid+1, last);
    }
};

解法二：牛客

分析上面的方法，时间复杂度高的主要原因来自于最后的顺序检索。设想一下，如果知道目标数字出现的第一个位置和最后一个位置，是否就不用再进行顺序检索了？ 于是，可以将二分查找算法改成分别查找目标数字的首次出现位置和末次出现位置。也就是说，如果mid上的数字等于num，同时mid-1（mid>0）上的数字不等于num，则mid为首次出现位置，否则，首次出现位置就应该还在前半段，同理，末次出现位置也是相似的道理。

结合以上讨论，将二分查找分成两个函数，分别找首次和末次位置，这样时间复杂度就是 $O(logn)$，无需进行顺序查找。

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int count = 0;
        if(data.size() == 0) return count;
        int index1 = binarySearchFirst(data, k, 0, data.size()-1);
        int index2 = binarySearchLast(data, k, 0, data.size()-1);
        if(index1 == -1 || index2 == -1) return 0;
        else return index2-index1+1;
    }

    int binarySearchFirst(vector<int>& data, int num, int first, int last){
        if(first > last) return -1;
        int mid = (first+last)/2;
        if(data.at(mid) == num){
            if(mid == 0 || data.at(mid-1) != num)
                return mid;
            else
                return binarySearchFirst(data, num ,first, mid-1);
        }
        else if(data.at(mid) > num) return binarySearchFirst(data, num ,first, mid-1);
        else return binarySearchFirst(data, num, mid+1, last);
    }
    int binarySearchLast(vector<int>& data, int num, int first, int last){
        if(first > last) return -1;
        int mid = (first+last)/2;
        if(data.at(mid) == num){
            if(mid==last || data.at(mid+1)!=num)
                return mid;
            else
                return binarySearchLast(data, num, mid+1, last);
        }
        else if(data.at(mid) > num) return binarySearchLast(data, num ,first, mid-1);
        else return binarySearchLast(data, num, mid+1, last);
    }
};

解法三: 解法二的非递归实现(更简洁易懂)

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int low = 0, high = data.size()-1;
        int first_k = -1, last_k = -1;
        if(data.size() == 0) return 0;
        while(low < high){
            int mid = (low+high)/2;
            if(data[mid] < k) low = mid+1;
            else high = mid; //在data[mid] == k时并不退出, 而是继续判断, 知道low==high时, 才会退出, 此时 low 和 high 都应指向最左侧的k值
        }
        if(data[low] != k) return 0;
        else first_k = low;
        high = data.size()-1;
        while(low < high){
            int mid = (low+high+1)/2; // 因为只有 high 会移动到mid的下一位, 而low是等于mid的, 所以必须让mid更偏向右侧, 上面的逻辑也是同理, 希望让mid更偏向左侧
            if(k < data[mid]) high = mid-1;
            else low = mid;
        }
        last_k = low;
        return last_k - first_k + 1;
    }
};

解法四: 寻找插入位置

因为data中都是整数，所以可以稍微变一下，不是搜索k的两个位置，而是搜索 k-0.5 和 k+0.5 这两个数应该插入的位置，然后相减即可。因为数组中不存在 k-0.5 和 k+0.5 这两个数, 因此, 我们只需不断二分查找, 直到 low > high 为止即可.

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        return binary(data, k+0.5) - binary(data, k-0.5);
    }
    int binary(vector<int> &data, double k){
        int low =0 , high = data.size()-1;
        while(low <= high){ // 这里的等于号是必不可少的
            int mid = (low+high)/2;
            if(data[mid] < k) low = mid+1;
            else high = mid - 1;
        }
        return low;
    }
};

38.二叉树的深度

题目描述

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

解法一: 非递归

利用BFS广度优先遍历（错了，树没有广度遍历，这个应该叫层次遍历），结合一个专门存储当前节点所处深度的队列实现 利用一个layer_count变量来记录当前层总共的节点数, 每次当pop了当前节点数个节点后, depth都会增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 == nullptr) return 0;
        queue<TreeNode*> tree_q;
        tree_q.push(pRoot);
        int depth = 0;
        while(!tree_q.empty()){
            int layer_count = tree_q.size(); //记录当前层共有多少节点
            for(int i =0 ; i<layer_count; i++){ // 根据当前层节点进行pop
                TreeNode* cur_node = tree_q.front(); tree_q.pop();
                if(cur_node->left != nullptr) tree_q.push(cur_node->left);
                if(cur_node->right != nullptr) tree_q.push(cur_node->right);
            }
            depth++;
        }
        return depth;

    }
};

解法二：牛客

二叉树中的某个节点的深度，就是其左子树深度和右子树深度较大者+1 ， 二叉树的深度就是根节点的深度，所以，利用递归的思想实现。（代码简洁，但是复杂复杂度好像和广度优先一样，都是n？ 是这样吗？）

class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot==nullptr) return 0 ;
        int depth1 = 1, depth2 = 1;
        if(pRoot->left!=nullptr) depth1 = TreeDepth(pRoot->left)+1;
        if(pRoot->right!=nullptr) depth2 = TreeDepth(pRoot->right)+1;
        return depth1>depth2 ? depth1 : depth2;

    }
};

更简洁的写法:

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

39.平衡二叉树

题目描述

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

解法一（自想）

时间复杂度: $O(n)$, 每个节点至多访问一次
空间复杂度: $O(n)$, 有可能需要进行 n 次递归

将题目看作是求左右子树的深度，如果深度差超过1,那么就不是二叉树，返回一个特殊的标识（-1），这种方法属于一边遍历，一边判断，只需要遍历每个节点一次，通过递归实现。时间复杂度为 $O(logn)$

有一种“不太好”的方法是每遇到一个节点，就单独求一次这个节点对应的树的深度，这种做法要遍历一个节点很多次，是一种典型的不令人满意的做法, 下面的做法采用了剪枝, 使得对每个节点至多访问一次, 是较好的做法

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int tdepth = treeDepth(pRoot);
        if(tdepth!=-1) return true;
        else return false;

    }
    int treeDepth(TreeNode* root){
        if(root == nullptr) return 0;
        int leftdepth = treeDepth(root->left);
        if(leftdepth == -1) return -1;
        int rightdepth = treeDepth(root->right);
        if(rightdepth == -1) return -1;
        if(abs(leftdepth-rightdepth) > 1) return -1;
        return max(leftdepth,rightdepth) + 1;
    }
};

更凝练的写法:

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return tree_depth(pRoot)==-1 ? false : true;
    }
    int tree_depth(TreeNode* pRoot){
        if(pRoot == nullptr) return 0;
        int left_depth = tree_depth(pRoot->left); //注意, 这里没有 +1,
        if(left_depth==-1) return -1; // 在这里直接断left_depth判断, 如果发现=-1,就一路返回, 无需再求右子树深度
        int right_depth = tree_depth(pRoot->right); //注意, 这里没有 +1
        if(right_depth==-1 || abs(left_depth-right_depth) > 1) return -1;
        return max(left_depth, right_depth) + 1; // 注意, 这有一定要有+1, 因为树深度就等于左右子树最大深度+1
    }
};

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

题目描述

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

（暴力解法就不提了，肯定不是最优。）

解法一：异或

注：异或运算符还可以实现无中间变量的两个数字互换：

int a=2;
int b=4;
a = a^b; // a = 2^4 = 6
b = a^b; // b = 6^4 = 2
a = a^b; // a = 6^2 = 4
//同理有
a = a + b; // a = 2+4 = 6
a = a - b; // b = 6-4 = 2
a = a - b; // a = 6-2 = 4

异或运算的性质：任何一个数字异或它自己都等于0 。与0异或则保留原值
也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。

（这里不限定是一次，只要是奇数次都可以）

本题数列中，有两个出现一次的数字，第一次先全部异或，得到的结果是两个一次数字的异或值，该异或值至少有一位的值为1 (即在这一位上, 两个数字一个为0, 一个为1), 因此，找到这一位，然后根据这一位这数组分成两拨，如此一来，每一拨都变成了上面的简单情况。

（同理，如果有N个一次数字，可以通过不断分拨的方法解决, 例如, 如果有3个一次数字, 则找了为1的那一位, 可以将其分成具有2个一次数字和具有一个一次数字的两拨数组）

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int * num1,int * num2) {
        if(data.size() < 2 ) return;
        int xor_res = 0;
        for(auto x : data)
            xor_res ^= x;
        int i = 1;
        while( (xor_res & i) == 0) // 按位异或的优先级小于 '==' 的优先级, 因此一定要用括号括起来
            i = i<<1;
        *num1=0, *num2=0; //return;
        for(auto x : data){
            if( (x & i) != 0)  // 按位与的优先级小于 '!=' , 所以必须用括号
                *num1 = *num1 ^ x;
            else
                *num2 = *num2 ^ x;
        }
    }
};

扩展: 数组中只有一个数出现一次，其他数都出现了2次，找出这个数字

int find1From2(vector<int> a){
     int len = a.size(), res = 0;
     for(int i = 0; i < len; i++){
         res = res ^ a[i];
     }
     return res;
 }

扩展: 数组中只有一个数出现一次，其他数字都出现了3次(奇数次)，找出这个数字

例如数组a[]={2,4,4,4,6,6,6};结果则返回2；思路则是利用位运算，因为其他数字都出现了三次，那么他们的二进制相同位上1的个数则是3的倍数，这样的话，最后统计完3的倍数的位清0，剩下的1则都是那个只出现一次的数的位。
(也可以先统计每一位上面1的个数, 最后模3取余)

int find1From3(vector<int> a){
    int *bits = new int[32]; //因为整数一般为4字节, 32位
    int len = a.size();
    for(int i = 0; i < len; i++){
        for(int j = 0; j < 32; j++){
            bits[j] = bits[j] + ( (a[i]>>j) & 1); # 注意这里的括号是必不可少的, 因为 & 的优先级比 + 低得多
        }
    }
    int res = 0;
    for(int i = 0; i < 32; i++){
        if(bits[i] % 3 !=0){
            res = res | (1 << i);
        }
    }
    delete[] bits;
    return res;
}

可以看出, 这是一种比较通用的解法, 可以求解某个数字出现一次, 而其他数字出现n次的情况(如果n为偶数, 建议用异或实现).

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

题目描述

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

解法一（自想）

设置两个变量记录当前序列的start位置和end位置，判断当前序列的和:

• 如果=sum，则存储当前序列，并将start+1,序列前进;
• 如果>sum,将应减去序列中的最小值，也就是start指向位置的值，然后start+1;
• 如果<sum，则应该再加上下一个值，也就是end指向的值。

然后再进行上面的循环，直到start指向的位置值为(sum+1)/2,此时就已经不可能出现和为sum的连续序列了。该方法时间复杂度为$O(n)$

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> results;
        int tmp = 0;
        int start = 1;
        for(int end =start; start <= sum/2 ;){
            if(tmp == sum){
                vector<int> numseq;
                for(int i = start ; i<end; i++){
                    numseq.push_back(i);
                }
                results.push_back(numseq);
                tmp -=start; // 需要注意这里的顺序, 一定要先减去了 start 以后, 才能执行 start++
                start++;
            }else if( tmp > sum){
                tmp -= start;
                start++;
            }else{

                tmp += end;
                end++;
            }
        }

        return results;
    }
};

解法二: 等差序列求和公式

42.和为S的两个数字

题目描述

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

解法一（自想）

设置两个变量，分别指向数组的第一个位置和最后一个位置，然后将这两个变量所指位置的值相加，分以下三种情况：

• =sum; 判断二者乘积是否比当前最小值小，如果是，则改变最小值的持有值。 不管是否小，都将num1++ 实际上, 根本无需判断是否比当前最小值小, 因为对于和相同的两组数, 数字差值较大的那一组的成绩一定小于数字差值较小的, 因此, 只要找到符合和为sum条件的两个数字, 即可直接返回, 无需进行任何额外判断.
• >sum; num2--;
• <sum; num1++;
  循环以上三步直到 num1>=num2。最后判断minnum1和minnum2的值，如果二者相等，说明数组里面不存在这样的数对儿，返回空vector，若不相等，则输出这两个值。

结论证明：
假设：找到两组满足条件的数组对 $（x，y）$、$（x+a,y-a）$，其中（ $x+y=S, 0<a<y-x$ ）

$$x*y-[(x+a)(y-a)]=x*y-x*y-(y-x)a+a2=a[a-(y-x)]$$

因为 $0<a<y-x$ ,所以 $a-(y-x)<0$ ,所以 $a[a-(y-x)]<0$
因此 $(x,y)$ 乘积一定比 $(x+a,y-a)$ 小

当第一次找到符合条件的两个数字时, 它们的乘积就一定是最小的, 所以可以直接退出.

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> res;
        if(array.size() < 2) return res;
        int low = 0, high = array.size()-1;
        //在使用容器的back()方法访问时，必须要确保容器不是空的，否则会出现段错误（访问越界）
        while(low < high){
            if(array[low] + array[high] == sum){ //首次找到就可返回
                res.push_back(array[low]);
                res.push_back(array[high]);
                return res; //首次找到就可返回
                low++;
            }else if(array[low] + array[high] < sum)
                low++;
            else
                high--;
        }
        return res;
    }
};

43.左旋转字符串

题目描述

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

解法一（自想）：利用str.substr(pos,n)

注意：

这道题看似简单，实则很容易考虑不全，主要需注意以下几点：

• n大于str.length()的情况
• str.length()=0的情况
• n为负数的情况（虽然这里牛客没考虑，我觉得题里没说正数，所以是有负数的可能的）

越是简单的题，越要注意各种情况的考虑，因为这种题的考察点就是考虑是否全面，而不是题怎么解

class Solution {
public:
    string LeftRotateString(string str, int n) {
        string res = "";
        if(str.length() == 0) return str;
        if (n>=str.length())  n = n % str.length();
        if(n<0) n = str.size() + n; 左移n位(负), 等于右移-n位, 等于左移size+n位
        res=str.substr(n);
        res += str.substr(0,n);
        return res;
    }
};

解法二（牛客）：反转

利用多次反转的方法，首先将字符串按照n的位置分成两部分，然后进行以下三步（abcdefg，2）：

• 反转前一部分：ba
• 反转后一部分：gfed
• 反转整个字符串：bagfed -> defgab

时间复杂度也为$O(n)$

class Solution {
public:
    void my_inverse(string &str, int start, int high){
        int mid = (start+high)/2;
        for(int i = start ; i<=mid; i++){
            std::swap(str[i], str[high-i+start]); // 这里注意交换时的下标, 因为i是从start开始的, 所以高位的下标应该为high-(i-start)
        }
    }
    string LeftRotateString(string str, int n) {
        if(n==0) return str;
        if(n<0) n = str.size() + n; //左移n位(负), 等于右移-n位, 等于左移size+n位
        if (n>=str.length())  n = n % str.length();
        my_inverse(str, 0, n-1);
        my_inverse(str, n, str.size()-1);
        //return str;
        my_inverse(str, 0, str.size()-1);
        return str;
    }
};

利用 std::reverse() 实现:

class Solution {
public:

    string LeftRotateString(string str, int n) {
        string res = "";
        if(str.length() == 0) return str;
        if (n>=str.length())  n = n % str.length();
        if(n<0) n = str.size() + n; //左移-n位, 等于右移n位, 等于左移size-n位
        std::reverse(str.begin(), str.begin()+n);
        std::reverse(str.begin()+n, str.end());
        std::reverse(str.begin(), str.end());
        return str;
    }
};

44.翻转单词顺序列

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

解法一: 土办法

设值两个标记i，j，都从字符串的最后一位开始，如果当前字符不是空格，那么i指向下一个，直到遇到空格为止，此时，将i到j范围内字符提取出来，然后把令j=i。重复以上过程，直到i=0为止。 该解法时间复杂度为 $O(n)$ 而且只需遍历一边字符串。

但是空间复杂度也为 $O(n)$

class Solution {
public:
    string ReverseSentence(string str) {
        if(str.length() == 0) return str;
        string res = "";
        for(int i = str.length()-1, j=str.length()-1; i>=0; ){
            if(str[i] == ' '){//这里注意不能用双引号,双引号代表字符串,在C++内部,""与''表示的是不同的东西
                res += str.substr(i+1,j-i);
                res += " ";
                i--;
                j = i;
            }else if(i == 0){
                res += str.substr(i,j-i+1);
                i--;
            }else{
                i--;
            }
        }
        return res;
    }
};

解法二（牛客）：利用reverse执行两次反转

首先反转整个字符串，然后以空格为间隔，反转每个单词。时间复杂度也是$O(n)$ (遍历两次).
空间复杂度为 $O(1)$

class Solution {
public:
    string ReverseSentence(string str) {
        std::reverse(str.begin(), str.end());
        int i = 0;
        for(int j = 0; j<=str.size(); j++){
            if(str[j] == ' ' || j == str.size()){
                std::reverse(str.begin()+i, str.begin()+j);
                i=j+1;
            }
        }
        return str;
    }
};

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的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

注意:

该题目需要注意：1123 这样的顺序返回的是false

解法一(自想):

分析能组成顺子的数字的特征，首先，最大的数字和最小的数字他们的差一定要比numbers的size小，否则，肯定连不了顺子。比如12345和2300等。其次，如果数组中出现非0的重复数字，那么也一定不是顺子。因此，代码可以这样写：

• 找出非0的最大值和最小值
• 在找最值的时候顺便利用最简单的hash表来存储每个数字出现的次数，hash表长度为14，key值为数字，value值为key值出现的次数，如果value出现>1的情况，则直接返回false
• 做判断，如果max-min< numbers.size()，则返回true，否则返回false。

以上程序时间复杂度为$O(n)$ ，并且只需要遍历一次numbers。

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if(numbers.size() == 0) return false;
        int i = 0;
        while(numbers[i] == 0) i++;
        int min=numbers.at(i);
        int max = numbers.at(i);
        int zeronum = 0;
        int count[14] = {0};
        for(auto it = numbers.begin(); it!=numbers.end(); it++){
            if(*it < min && *it!=0) min = *it;
            if(*it > max) max = *it;
            if(*it == 0) zeronum++;
            count[*it]++;
            if(*it != 0 && count[*it] > 1) return false;
        }
        if(max-min <= numbers.size() - 1)
            return true;
        else{
            return false;
        }
    }
};

上面对max和min赋值的时候, 有可能会出现需要遍历n次的情况, 用下面的方法稍微改进一下(复杂度不变), 要注意不论是max还是min, 都不能为0.(全0的情况时, 会返回true)

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if(numbers.size() == 0) return false;
        int poke_hash[14]={0};
        int max_poke = INT_MIN, min_poke = INT_MAX;
        for(auto item : numbers){
            poke_hash[item]++;
            if(item!=0 && poke_hash[item]>1) return false;
            if(item!=0 && item < min_poke) min_poke = item;
            else if(item!=0 && item > max_poke) max_poke = item;
            if(max_poke!=INT_MIN && min_poke!=INT_MAX && max_poke - min_poke >= numbers.size()) return false;
        }
        return true;
    }
};

另一种写法, 可以让判断条件不用写的那么复杂, 推荐使用这种写法:

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        int len = numbers.size();
        if(len==0) return false;
        int hash_map[13]{0};
        int min=INT_MAX, max=INT_MIN, zero=0;
        for(auto n : numbers){
            if(n==0) continue;
            else if(hash_map[n-1]>0) return false;
            else if(n<min) min = n;
            else if(n>max) max = n;
            if(min!=INT_MAX && max!=INT_MIN && max-min>=len) return false; //如果发现已经不可能出现顺子, 则提前退出
            hash_map[n-1]++;
        }
        if(min==INT_MAX || max==INT_MIN) return true;
        if(max - min <len) return true;
        return false;
    }
};

解法二（牛客）：排序

先排序，在统计0的个数，再用0填补空缺，时间复杂度为 $O(nlogn)$ 不如上面的方法好。

46.圆圈中最后剩下的数：约瑟夫（Josephuse）环问题

题目描述

0,1,…,n-1这n个数字排成一个圆圈，从数字0开始每次删除m-1处的数字，然后从这个数字的下一位继续从0开始，删除m-1处的数字，求出圆圈里剩下的最后一个数字

解法一（自想）：利用vector维护动态数组模拟约瑟夫环

利用一个vector维护一个动态数组，数组内的内容是每个孩子的编号，每次要删除的节点位置，都在index+m-1处，如果index+m-1超过了数组的大小，则对数组的size求余即可。该算法是最简单的一种思路，vector或list在删除时，由于要将后面的元素向前挪，所以erase的时间
复杂度为 $O(n)$ ，因此，总的时间复杂度为$O(n^2)$。

空间复杂度为 $O(n)$

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<=0 || m<=0) return -1;
        if(n == 1) return 0;
        vector<int> joseph_ring;
        for(int i = 0; i<n; i++)
            joseph_ring.push_back(i);
        int index = 0;
        while(joseph_ring.size() > 1){
            index = (index+m-1) % joseph_ring.size();
            joseph_ring.erase(joseph_ring.begin() + index);
        }
        return joseph_ring[0];
    }
};

解法二（牛客）：经典解法，用环形链表模拟圆圈

可以用std::list或者std::vector来模拟一个环形链表，由于它们本身不是循环的，因此需要记得手动实现循环逻辑（其实就是解法一）

如果要求不可以使用标准模板库里面的数据容器来模拟环形链表，那么可以自己设计结构体类型，实现一个循环链表。

这里由于链表随机在删除节点时的时间复杂度为 $O(1)$ , 但是无法进行随机访问，只能顺序访问，因此删除时需要先顺序移动到该节点上才行, 所以要时间复杂度仍然为$O(n^2)$

空间复杂度为$O(n)$。

解法三（牛客）：

分析每次删除时的数字规律，总结出以下公式，按照公式编写递归或非递归程序，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$ 。

$$f(n) = \begin{cases} 0 & n=1 \\ [f(n-1,m)+m]\%n & n>1 \end{cases}$$

思考过程：当把第m个数(下标为m-1)去掉以后, 就只剩下了n-1个数, 此时, 再从下标m开始, 继续进行大小为n-1的约瑟夫环问题. 这里假设我们已经知道了大小为n-1的约瑟夫环问题的解为下标 $x’$, 则 $x’$ 在大小为n的约瑟夫环问题里面的下标应该为: $x = (x’ + m) % n$ . 由此式即可得到上面的递归公式

//非递归写法
class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<=0 || m<=0) return -1;
        int cur_n=1, res=0;
        while(cur_n <= n){// 注意是<=, 因为此处的i代表的是size, 必须要一直计算到i==n为止
            res = (res+m) % cur_n; //注意是要除以cur_n, 而不是n
            cur_n++;
        }
        return res;
    }
};

递归写法
class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<=0 || m<=0) return -1;
        if(n==1) return 0;
        return (LastRemaining_Solution(n-1,m)+m)%n;
    }
};

47.非常规法求前n项和

题目描述

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

这道题本身没有实际意义，侧重考察发散性思维和对C++相关机制的理解程度。

解法一：构造函数

每声明一个对象，则构造函数都被调用一次，因此，可以借助静态变量来在构造函数内部实现累加操作。

class sum{
        public:
        static int i ;
        static int s;
        sum(){i++; s+=i;};
        ~sum(){};
        static void set(){
            i = 0;
            s = 0;
        };
    };
int sum::i =0;
int sum::s = 0;
class Solution {
public:
    int Sum_Solution(int n) {
        sum::set();
        sum a[n];
        return sum::s;
    }
};

解法二：虚函数

利用虚函数来模拟递归函数，可以在两个类中分别定义函数，其中一个函数充当递归函数的角色，另一个函数处理终止递归的情况，然后在两个函数里二选一。

这里用到了一个小trick，那就是对于整型变量n，执行!!n以后，可以将其转换成布尔值（0和1）。

class A{
    public:
    virtual int sum(int n){return 0;};
};
A* Array[2];  //这里必须为指针，否则不会进入B的sum 函数
class B : public A{
    public:
    virtual int sum(int n){return Array[!!n]->sum(n-1) + n;};
};

class Solution {
public:
    int Sum_Solution(int n) {
        class A a;
        class B b;
        Array[0] = &a;
        Array[1] = &b;
        return Array[1]->sum(n);
    }
};

上面用了虚函数，那么使用普通的函数可以吗？答案是否定的，因为使用普通函数时，无法同时调用两个类的函数，最终只会调用A类的sum函数。

解法三：函数指针

同样是上面的思想，不过改为使用函数指针来实现两个函数模拟递归

int A(int n){
    return 0;
}

int B(int n){
    static int (*fun[2])(int n) = {A,B};

    return fun[!!n](n-1) + n;
}

class Solution {
public:
    int Sum_Solution(int n) {
        return B(n);
    }
};

解法四：模板类

使用模板类完成递归，这种方法有一个很大的缺点就是整个过程是在编译阶段完成的，因此无法使用动态的n，而必须是在编译期间就能确定的常量，另外，编译器对递归编译代码的递归深度也是有限制的，所以n不能太大。

48.不用加减乘除做加法

49.把字符串转换成整数

题目描述

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
输入描述:

输入一个字符串,包括数字字母符号,可以为空

输出描述:

如果是合法的数值表达则返回该数字，否则返回0

解法一（自想）：

从头开始逐个字符遍历，每次遇到一个“数字”，就将之间的res×10，然后再加上这个数字。需要特别注意“-123”，“+123”等情况。 时间复杂度为 $O(n)$ 。

class Solution {
public:
    int StrToInt(string str) {
        int  res = 0;
        bool negative = false;
        int i = 0;
        if(str[i] == '-'){
            negative=true;
            i++;
        }else if(str[i] == '+')
            i++;
        for(; i < str.length() ;i++){
            if( str[i] >= '0' && str[i] <= '9'){
                res = res*10 + (int)(str[i] - '0');
            }else
                return 0;

        }
        if(negative) res = 0 - res;
        return res;
    }
};

注意

上面的代码虽然已经解决了牛客的题，但是有几点是需要特别注意的！

首先，题目很简单，所以这道题的考察点只在于是否将所有情况都考虑到了，以下是一些可能的情况，日后再遇到一定要想起来：

• 首先考虑如何返回错误，首先不能使用可以转换成数值类型（int，bool，char）的数据直接指明错误（比如返回0，无法得知到底是错误当时真的是0），由此，可以创建一个全局的错误变量，如果要返回错误，则返回0并且将该变量状态改变。
• 非数字类符号不全是错误输出，如：+123、-123
• 只输入+和-时，要返回错误
• string str==""时，也要返回错误
• 如果为char str*，则要判断指针是否为空
• 一定要考虑数值溢出情况（当转换的数字大于最大正数，小于最小负数时，会溢出）

50.数组中重复的数字

题目描述

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

解法一：暴力

对于每个数组中的数字，都到前面的数字中去寻找是否有重复的。

时间复杂度： $O(n^2)$ 空间复杂度： $O(1)$

解法二：哈希

建立长度为n的哈希表，每次遇到一个数字x，就在hash[x]增1，如果此时hash[x]变为2，那么就说明有重复。

时间复杂度： $O(n)$ 空间复杂度： $O(n)$

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) {
        vector<int> hash(length);

        for (int i = 0; i< length; i++){
            hash[numbers[i]]++;
            if(hash[numbers[i]] > 1){
                *duplication = numbers[i];
                return true;
            }
        }
        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]。不能使用除法。

解法一（自想）：

将乘积看成两段，前i-1项的乘积，和后n-i项的乘积，分开计算，最终合并。
时间复杂度： $O(n)$ 空间复杂度： $O(n)$

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> B;
        int tmp = 1;
        for(auto it = A.begin(); it!=A.end(); it++){
            if(it!=A.begin()) tmp *= *(it-1);
            B.push_back(tmp);
        }
        tmp = 1;
        for(int i = A.size()-1; i >= 0; i--){
            if(i!=A.size()-1) tmp *= A.at(i+1);
            B.at(i) *= tmp;
        }
        return B;
    }
};

52.正则表达式匹配

题目描述

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

解法一：（牛客）

主要分两种情况：

• 当前字符的下一个字符不是*
• 当前字符的字一个字符是*

对于第一种情况：直接判断是否相等（包含‘.’的情况）

对于第二种情况，需要分情况讨论：

• 当前字符与pattern当前字符不相等，则patter当前只能出现零次，调用match(str, pattern+2)
• 当前字符与pattern字符相等（包含‘.’的情况），则pattern的选择有两种，出现零次，或者出现一次以上，这两种情况都必须考虑，否则会丢解，如（aab和a.*ab），因此，需要调用match(str, pattern+2) || match(str+1, pattern)

class Solution {
public:
    bool match(char* str, char* pattern)
    {
        if( *str == '\0' && *pattern == '\0')
            return true;
        if( *str != '\0' && *pattern == '\0')
            return false;

        if( *(pattern+1) != '*'){
            if(*str!='\0' && (*str == *pattern || *pattern=='.'))  //  *str的条件不能丢
                return match(str+1, pattern+1);
            else
                return false;
        }else{
            if(*str!='\0' && (*str == *pattern || *pattern=='.'))  //这里的if else组合语句是必须的，否则会在不能出现多次时，函数仍然考虑出现多次的情况，造成误解
                return match(str, pattern+2) || match(str+1, pattern);
            else
                return match(str, pattern+2);
        }


    }
};

53.表示数值的字符串

题目描述

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

解法一（自想）：

没有难点，考察点主要在于各种情况的考虑（以下均为false）：

• +
• -
• +12.2.2
• 12e
• 12e-
• 12E+4.3

class Solution {
public:
    bool isNumeric(char* string)
    {
        if(*string == '\0') return false;
        if(*string == '+' || *string == '-')
            string++;
        if(*string == '\0')
            return false;
        int point_count = 0;
        while( (*string >= '0' && *string <= '9')
             || *string == '.'){
            if (*string == '.') point_count++;
            if (point_count > 1) return false;
            string++;
        }
        if(*string == '\0')
            return true;
        if(*string == 'e' || *string == 'E')
            string++;
        else
            return false;
        if(*string == '\0')
            return false;
        if(*string == '+' || *string == '-')
            string++;
        if(*string == '\0')
            return false;
        while( *string >= '0' && *string <= '9' )
            string++;
        if(*string != '\0')
            return false;
        return true;
    }

};

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

解法一（牛客）：哈希表

建立一个哈希表和一个char数组（均为256大小），哈希表存储每个字符出现的次数，key为char，value为次数，数组存储所有 曾经 出现过一次的字符。

时间复杂度 $O(n)$ 空间复杂度 $O(1)$

class Solution
{
public:
  //Insert one char from stringstream
    char hash_c[256] = {0};
    char first_c[256] = {0};
    int index =0;
    void Insert(char ch)
    {
        hash_c[ch]++;
        if(hash_c[ch] == 1){
            *(first_c+index) = ch;
            index++;
        }

    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        for(int i =0 ;i<index; i++)
            if (hash_c[*(first_c+i)] == 1) return *(first_c+i);

        return '#';

    }

};

55.链表中环的入口节点

解法一（牛客）: FLoyd 的乌龟和兔子

假设有环，并且环中的节点数为n，那么只要设值两个指针，一个slow指针指向头结点，另一个fast指针指向第n+1个节点，然后每次slow指针和fast指针都增1，那么肯定会在环的头部相遇（因为fast刚好比slow领先了一个环的长度）

因此，首先需要判断是否有环，思路是：从头结点开始，slow每次走一步，fast每次走两步，那么只要有环，slow和fast就一定会在环中的某个节点处相遇，如果无环，则fast一定先到达空指针

判断有环后，令fast从当前节点开始，继续往下走（每次走一步），并记录步数，最终遇到slow时的步数就是环的长度. 求得环长后, 先令 fast 走环长距离, 然后再令 slow 和 fast 共同前进, 最终, 相遇点即为开始点.

该方法时间复杂度为 $O(n)$ 空间复杂度为 $O(1)$

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode* slow = pHead;
        ListNode* fast = pHead;
        while(slow!=nullptr && fast != nullptr){
            if(slow->next == nullptr)
                return nullptr;
            else
                slow = slow->next;
            if(fast->next == nullptr || fast->next->next == nullptr)
                return nullptr;
            else
                fast = fast->next->next;
            if(slow == fast)
                break;
        }
        fast = fast->next;
        int step = 1;
        while(slow != fast){ // 求环长
            fast = fast->next;
            step++;
        }
        fast = pHead;
        while(step>0){// 先让 fast 走环长距离
            fast = fast->next;
            step--;
        }
        slow = pHead;
        while(slow!=fast){ // 相遇点即为开始点
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

解法二: 优化解法一

时间复杂度: $O(n)$
空间复杂度: $O(1)$

https://blog.csdn.net/dawn_after_dark/article/details/82564271

比解法一更简洁的写法:
上面在求环的开始节点时, 是先求环长, 再让 fast 走环长距离, 然后 slow 和 fast 同步前进, 最终相遇点即为开始点, 这么写比较容易理解, 但难免有些繁琐. 实际上, 我们只需要令 fast=slow, 然后再让 slow 从头开始, 即 slow=0, 接着令 fast 和 slow 同步前进, 那么相遇点就是开始节点. 该性质的证明如下:

假设链表首部到环入口点距离为 $x$, 环长为 $c$, 两者在环内相交的点距离环的入口为 $a$, slow 表示慢指针走的距离, fast 表示快指针走的距离, $n$, $m$ 分别表示快慢指针在相遇时已经走得多少环. $2\times slow = fast$ (因为快指针的速度是慢指针速度的2倍). 那么, 则有下面的公式关系:

$$slow = x + mc + a$$ $$fast = x + nc + a$$ $$2\times slow = 2(x+mc+a) = x+nc+a = fast$$ $$x = (n-2m)c - a = (n-2m-1)c + c - a$$

因此, 可以看出链表首部到环入口的距离实则为 $环长倍数+ c-a$, 而此时的环内相遇点 slow 要从当前位置再次回到环入口点所需要的步数也为 $环长倍数+ c-a$, 因此可以采用共同前进的方法, 并且相交点一定为环入口点, 代码如下所示.

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead==nullptr) return nullptr;
        ListNode *fast = pHead;
        ListNode *slow = pHead;
        do{
            slow = slow->next;
            fast = fast->next;
            if(fast==nullptr) return fast; // 不存在环
            fast = fast->next;
            if(fast==nullptr) return fast; // 不存在环
        }while(slow!=fast);

        fast = slow;
        slow = pHead;
        while(slow!=fast){
            slow = slow->next;
            fast = fast->next; // 共同前进
        }
        return slow;
    }
};

解法三（牛客）： 断链法

同理，先判断有环无环

然后记录两个指针，一个当前节点指针cur，一个相邻祖先指针pre，每经过一个节点时，都将pre指针的next置为nullptr，则当cur的next为空时，既为环的首个节点。

该方法的时间复杂度为O(n)，且只需遍历两次，且第二次遍历的时候正好遍历n个节点，但是缺点是会破坏链结构，补救办法是使用额外的标记来替代断链，但是这样会增加额外空间开销

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode* slow = pHead;
        ListNode* fast = pHead;
        if(slow == nullptr) return nullptr;
        while(slow!=nullptr && fast != nullptr){
            if(slow->next == nullptr)
                return nullptr;
            else
                slow = slow->next;
            if(fast->next == nullptr || fast->next->next == nullptr)
                return nullptr;
            else
                fast = fast->next->next;
            if(slow == fast)
                break;
        }
        if(pHead->next == pHead) return pHead;  //需要特别考虑只有一个节点并且自己组成环的情况
        slow = pHead;
        fast = pHead->next;
        while(fast->next!=nullptr){
            slow->next = nullptr;
            slow = fast;
            fast = fast->next;
        }
        return fast;

    }
};

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

题目描述

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

解法一（自想）：

这道题本身比较简单，只需要维护一个pre指针和cur指针，分别指向前一个结点和当前结点，如果当前结点和下一个结点的值相等，那么就删除当前结点，最后我pre指针的next值设置为指向未重复的结点

但是！本题恶心了我很久，一直报段错误，主要原因是有的结点没有做空判断，就访问了结点的val或者next成员，此时如果结点是空的，那么就会报段错误，主要有以下这么几个情况：

• 头结点本身就是重复的，这个需要删除头结点，另外判断是否重复时，还要检查头结点的下一个结点是否为空，如果为空，则不能访问其val值，否则，报段错误
• 在进行重复判断时，访问cur->next->val时，需要先判断cur->next是否为空，如果为空，则不能访问其val值

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead == nullptr || pHead->next == nullptr) return pHead;
        ListNode* newHead = new ListNode(0); //  建立一个新的结点，其next用于标识头结点，以便在头结点重复时，指向新的头结点
        newHead->next = pHead;
        ListNode* cur = pHead;
        ListNode* pre = newHead;

        while(cur != nullptr && cur->next !=nullptr){   // 注意   这里一定必须是 && ，如果是|| ，则下面有可能会访问到空结点的val，造成段错误

            if(cur->val == cur->next->val){
                ListNode* dup = cur->next;
                while(cur->val == dup->val && dup!=nullptr){  // 同理，让验证所有欲访问的结点不为空
                    dup = dup->next;
                }
                cur = dup;
                pre->next = cur;
            }else{
                cur = cur->next;
                pre = pre->next;
            }

        }
        return newHead->next;

    }
};

57.二叉树的下一个节点

58.对称的二叉树

　题目描述

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

解法一（牛客）：递归

要判断一个树是否对称，需要判断其树的左右子节点是否相等，同时还要判断左子树的右子树和右子树的左子树是否相等，以及左子树的左子树和右子树的右子树是否相等，然后如此递归解之：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot == nullptr ) return true;
        return isSymHelper(pRoot->left, pRoot->right);

    }

    bool isSymHelper(TreeNode* subRoot1, TreeNode* subRoot2){
        if(subRoot1 == nullptr) return subRoot2==nullptr;
        if(subRoot2 == nullptr) return false;
        if(subRoot1->val != subRoot2->val) return false;

        bool b1 = isSymHelper(subRoot1->right, subRoot2->left);
        bool b2 = isSymHelper(subRoot1->left, subRoot2->right);
        return b1&&b2;
    }

};

解法二（牛客）：非递归

关键还是知道怎么样才能判断一个
二叉树是否对称，只要采用前序、中序、后序、层次遍历等任何一种遍历方法，分为先左后右和先
右后左两种方法，只要两次结果相等就说明这棵树是一颗对称二叉树。

//以下为层次遍历
//与普通遍历不同的是，对于这道题，必须要把左右子树都存入到queue中，不论是否为空，因为只有这样才能将整个二叉树的结构存储起来，以便判断
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        if( nullptr==pRoot) return true;
        q1.push(pRoot);
        q2.push(pRoot);
        TreeNode* cur1;
        TreeNode* cur2;
        while(!q1.empty() && !q2.empty()){
            cur1 = q1.front(); q1.pop();
            cur2 = q2.front(); q2.pop();
            if(cur1 == cur2 && nullptr == cur1)
                continue;
            if(nullptr == cur1 || nullptr == cur2)
                return false;
            if(cur1->val != cur2->val)
                return false;
            q1.push(cur1->left); q1.push(cur1->right);
            q2.push(cur2->right); q2.push(cur2->left);
        }

        return true;

    }

};

解法三（牛客）：非递归

=非递归算法，利用DFS和BFS===========================

BFS使用Queue来保存成对的节点

1. 出队的时候也是成对成对的

          1.若都为空，继续；
           2.一个为空，返回false;
           3.不为空，比较当前值，值不等，返回false；
   

   1. 确定入队顺序，每次入队都是成对成对的，如left.left， right.right ;left.rigth,right.left

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot == nullptr) return true;
        queue<TreeNode*> q;
        q.push(pRoot->left); q.push(pRoot->right);
        TreeNode* lnode; TreeNode* rnode;
        while(!q.empty()){
            lnode = q.front(); q.pop();
            rnode = q.front(); q.pop();
            if(nullptr == lnode && nullptr == rnode) continue;
            if(nullptr == lnode || nullptr == rnode) return false;
            if(lnode->val != rnode->val) return false;

            q.push(lnode->left); q.push(rnode->right);
            q.push(lnode->right); q.push(rnode->left);
        }
        return true;

    }

};

DFS使用stack来保存成对的节点

1. 出栈的时候也是成对成对的 ，

            1.若都为空，继续；
            2.一个为空，返回false;
            3.不为空，比较当前值，值不等，返回false；
   

2. 确定入栈顺序，每次入栈都是成对成对的，如left.left， right.right ;left.rigth,right.left

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        stack<TreeNode*> s;
        if(pRoot == nullptr) return true;

        s.push(pRoot->left);
        s.push(pRoot->right);
        TreeNode* lnode; TreeNode* rnode;
        while(!s.empty()){
            rnode = s.top(); s.pop();
            lnode = s.top(); s.pop();
            if( nullptr==lnode && nullptr == rnode)
                continue;
            if( nullptr == lnode || nullptr == rnode)
                return false;
            if(lnode->val != rnode->val)
                return false;
            s.push(lnode->left); s.push(rnode->right);
            s.push(lnode->right); s.push(rnode->left);
        }
        return true;

    }

};

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

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

解法一（自想, 差评）：

利用两个queue，一个用于层次遍历树节点，另一个用于存储对应节点的depth，然后每次访问节点时，都判断当前节点的层数，如果为奇数层，则将该层直接push back到结果向量中，如果为偶数，则将该层数据进行reverse后再push back到结果向量中。

时间复杂度为 $O(n^2)$ 空间复杂度为 $O(n)$

需要注意的是最后一层的边界条件与其它层不同一样，需要专门判断以下，具体可以看下面的点注释。

/*
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> > res;
        if(pRoot==nullptr) return res;
        queue<TreeNode*> q_node;
        queue<int> q_depth;
        q_node.push(pRoot);
        q_depth.push(1);
        TreeNode* cur; int depth;
        int global_depth = 1;
        vector<int> cur_layer;
        while(!q_node.empty()){
            cur = q_node.front(); q_node.pop();
            depth = q_depth.front(); q_depth.pop();
            if(cur->left != nullptr){
                q_node.push(cur->left);
                q_depth.push(depth+1);
            }
            if(cur->right != nullptr){
                q_node.push(cur->right);
                q_depth.push(depth+1);
            }

            if(depth == global_depth){
                cur_layer.push_back(cur->val);
                if(q_node.empty()){
                  // 对应最后一层的情况，当到了最后一层时，depth不会再继续增1了，
                  //所以不能通过global depth或depth的大小来判断是否进行pushback，
                  //需要通过看是否达到了最后一个节点来判断
                    if(global_depth % 2 == 1){
                        res.push_back(cur_layer);
                    }else{
                        reverse(cur_layer.begin(), cur_layer.end());
                        res.push_back(cur_layer);
                    }
                }
            }else{
                if(global_depth % 2 == 1){
                    res.push_back(cur_layer);
                }else{
                    reverse(cur_layer.begin(), cur_layer.end());
                    res.push_back(cur_layer);
                }
                cur_layer.clear();
                cur_layer.push_back(cur->val);
                global_depth=depth;
                if(q_node.empty()) res.push_back(cur_layer);
                //这句话用于处理最后一层只有一个节点的情况，如果只有一个节点的话，
                //那么当前queue就为空，不会进入下一次循环，从而导致最后一层没有pushback进去
            }
        }
        return res;
    }

};

解法二：利用reverse

同样的思路，另一种写法，更加简洁，通过while里面内置for循环，来保证每次for循环都会将一整层的节点放进队列中，无需额外的数组来存储depth信息

链接：https://www.nowcoder.com/questionTerminal/91b69814117f4e8097390d107d2efbe0
来源：牛客网

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        if(pRoot == NULL)
            return res;
        queue<TreeNode*> que;
        que.push(pRoot);
        bool even = false;
        while(!que.empty()){
            vector<int> vec; //将vec声明在内部，省去每次的clear操作，clear操作需要对vector进行遍历，并将每个元素置为null？
            const int size = que.size(); //当前存的节点数目就是这一层所有的节点，之前层的到已经被取出, 并且这一层的子节点还没有开始入队列
            for(int i=0; i<size; ++i){ //将该层所有节点的子节点入队列，同时当到达该层最后一个节点时终止
                TreeNode* tmp = que.front();
                que.pop();
                vec.push_back(tmp->val);
                if(tmp->left != NULL)
                    que.push(tmp->left);
                if(tmp->right != NULL)
                    que.push(tmp->right);
            }
            if(even) //根据奇偶标识判断是否需要reverse
                std::reverse(vec.begin(), vec.end());
            res.push_back(vec);
            even = !even;
        }
        return res;
    }

};

解法三: 最优(不用reverse)

时间复杂度: $O(n)$
空间复杂度: $O(n)$

在解法二中, 复杂度高的原因是因每次遇到偶数层的时候都要进行 reverse, 实际上, 当我们知道了该层的节点个数以后, 我们可以直接开辟一个指定大小的 vector, 然后根据下标随机访问来填入该层的节点值, 这样一来就不用进行 reverse, 并且空间复杂度与解法二相同

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == nullptr) return res;
        std::queue<TreeNode*> q;
        q.push(root);
        bool is_odd = true;
        TreeNode* cur_node;
        while(!q.empty()){
            int layer_len = q.size();
            vector<int> cur_layer(layer_len);
            for(int i=0; i<layer_len; i++){
                cur_node = q.front(); q.pop();
                if(is_odd==true)
                    cur_layer[i] = cur_node->val;
                else
                    cur_layer[layer_len-1-i ] = cur_node->val;

                if(cur_node->left!=nullptr) q.push(cur_node->left);
                if(cur_node->right!=nullptr) q.push(cur_node->right);

            }
            res.push_back(cur_layer);
            is_odd = !is_odd;
        }
        return res;
    }
};

60.把二叉树打印成多行

题目描述

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

解法一（半自想）：

while循环加for循环，无需额外记录层数，具体看59题解法二分析

时间和空间复杂度为 $O(n)$

/*
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> > res;
            if(pRoot== nullptr) return res;
            queue<TreeNode*> q_node;
            q_node.push(pRoot);
            while(!q_node.empty()){
                vector<int> cur_layer;
                const int cur_size = q_node.size();
                for(int i = 0;i<cur_size; i++){
                    TreeNode* cur_node = q_node.front(); q_node.pop();
                    cur_layer.push_back(cur_node->val);
                    if(cur_node->left != nullptr) q_node.push(cur_node->left);
                    if(cur_node->right != nullptr) q_node.push(cur_node->right);
                }
                res.push_back(cur_layer);
            }
            return res;
        }

};

61.序列化二叉树

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

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

解法一（自想）：

中根遍历，遍历到第k个节点时将其输出，如果k大于节点数量，输出nullptr, 时间复杂度 $O(n)$

/*
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(pRoot == nullptr) return nullptr;
        stack<TreeNode*> s_node;
        TreeNode* P =  pRoot;
        //ctor<TreeNode*> vec_node;
        int cur_k = 0;
        while(P!=nullptr || !s_node.empty()){
            while(P!=nullptr){
                s_node.push(P);
                P = P->left;
            }

            if(!s_node.empty()){
                P = s_node.top(); s_node.pop();
                cur_k++;
                if(cur_k == k) break;
                P = P->right;
            }
        }
        if(cur_k == k) return P;
        return nullptr;
    }
};

63.数据流中的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

解法一(自想):

插入时用vector的insert方法,按顺序插入,空间为 $O(n)$ ,时间复杂度为$O(n)$ 返回中位数时直接利用下标,时间复杂度和空间复杂度都为 $O(1)$.

这里关于vector的insert方法,有两个需要注意的点:

• it = vec.insert(it,num); 如果后序还要继续插入的话, 就必须将insert的结果重新赋值给it, 否则如果没有重新赋值而直接继续使用it的话,会导致段错误, 这里因为已经不需要继续插入了,所以可以用break直接跳出,无需赋值
• 插入时,如果num比vec里面所有的数都大, 那么会导致插入失败, 此时 ,应使用push_back将num插入到最后

class Solution {
public:
    vector<int> vec;

    void Insert(int num)
    {
        if(vec.size() == 0){
            vec.insert(vec.begin(), num);
            return;
        }
        bool is_insert=false;
        for(auto it=vec.begin(); it!=vec.end(); it++){
            if(*it > num){
                vec.insert(it,num);
                is_insert=true;
                break;
            }
        }
        if(!is_insert) vec.push_back(num);
    }

    double GetMedian()
    {
        if(vec.size() == 0) return 0;
        int x1 = vec.size()/2;
        int x2 = (vec.size()-1)/2;
        return (vec[x1]+vec[x2])/2.0;

    }

};

解法二:

插入的时候不考虑排序,在查找中位数时可以使用基于Partition的方法,时间复杂度为 $O(n)$.

解法三:AVL树

插入时间复杂度为 $O(logn)$ 找中位数时间复杂度为 $O(1)$

解法四(牛客):用大顶堆和小顶堆

思路:

如果能够保证数据容器左边的数据都小于右边的数据，这样即使左、右两边内部的数据没有排序，也可以根据左边最大的数及右边最小的数得到中位数。如何快速从一个容器中找出最大数？用最大堆实现这个数据容器，因为位于堆顶的就是最大的数据。同样，也可以快速从最小堆中找出最小数。　　因此可以用如下思路来解决这个问题：用一个最大堆实现左边的数据容器，用最小堆实现右边的数据容器。往堆中插入一个数据的时间效率是 O(logn)。由于只需 O(1)时间就可以得到位于堆顶的数据，因此得到中位数的时间效率是 O(1)。

首先要保证数据平均分配到两个堆中，因此两个堆中数据的数目之差不能超过 1

还要保证最大堆中里的所有数据都要小于最小堆中的数据

当数据的总数目是偶数时，按照前面分配的规则会把新的数据插入到最小堆中。如果此时新的数据比最大堆中的一些数据要小，怎么办呢？

可以先把新的数据插入到最大堆中，接着把最大堆中的最大的数字拿出来插入到最小堆中。由于最终插入到最小堆的数字是原最大堆中最大的数字，这样就保证了最小堆中的所有数字都大于最大堆中的数字。 当需要把一个数据插入到最大堆中，但这个数据小于最小堆里的一些数据时，这个情形和前面类似。

class Solution {
public:
    priority_queue<int, vector<int>, std::less<int> > q_max;
    priority_queue<int, vector<int>, std::greater<int> > q_min;

    void Insert(int num)
    {
        if( q_max.size()> q_min.size() ){
            q_max.push(num);
            int tmp = q_max.top(); q_max.pop();
            q_min.push(tmp);
        }else{
            q_min.push(num);
            int tmp = q_min.top(); q_min.pop();
            q_max.push(tmp);
        }
    }

    double GetMedian()
    {
        double res;
        if(q_max.size() == q_min.size()){
            int x1 = q_max.top();
            int x2 = q_min.top();
            res = (x1+x2)/2.0;
        }else{
            res = q_max.top();
        }
        return res;

    }

};

插入时间复杂度为 $O(logn)$ 找中位数时间复杂度为 $O(1)$

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]}。

解法一(自想):

用最直接的办法, 每次求出滑动窗口内的最大值, 然后存到max_res向量里面, 该方法时间复杂度为 $O(nm)$ . 空间为 $O(n)$

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> max_res;
        if(size == 0) return max_res; //无符号整数, 要首先考虑size为0的情况, 否则会导致下面的程序数组越界
        for(int i = 0 ; i< num.size()-size+1 ; i++){
            int tmp_max;
            //if(i<num.size())  tmp_max = num[i]; //这里的if语句看起来是多余的, 实际上可以帮助进行数组越界检查, 有助于快速确定bug位置
            for(int j = i+1; j< i+size ; j++){
                if(num[j] > tmp_max) tmp_max = num[j]; // 这里同样可以进行越界检查, 有助于bug定位, bug修复后可去掉
            }
            max_res.push_back(tmp_max);
        }
        return max_res;
    }
};

解法二(讨论区):

使用双端队列deque, 从下标0开始, 一直到n-1, 每次进行如下步骤:

• 当前元素是否比队列中最后一个元素大, 如果大, 说明队列元素以后也不可能再成为较大值, 直接pop, 如此循环, 直到队列为空或者遇到比当前值大的元素
• 判断队列中队首的元素是否过期(若队空则直接下一步, 无需判断), 若过期, 则pop, 否则, 不管( 只看队首, 队内的元素是否过期不影响算法, 因为就算过期后面也会将其淘汰)
• 将当前元素的下标存到队尾
• 将新的队首元素存到结果向量max_res中

注意: 队列里面存的是下标, 而不是元素本身的值, 后面在提到队列的元素值时, 均是指队列中存储的下标对应的元素值.

时间复杂度分析: 不是 $O(n*szie)$ 而是 $O(n)$ ?

原因: 假设队列里面的正好包含size个元素(最多就为size个), 那么这三个元素对应的值一定是递减的, 因为如果不是递减中, 在进行第一个判断时, 就会将其移除, 此时, 如果新来了一个元素, 如果该元素值小于队列中所有的值, 那么就只可能进行一次判断, 而不是循环size次, 而如果均大于队列中的值, 那么队列中的元素个数就会变成1个, 这样, 在下次进行判断时, 只会与一个元素做判断, 如果是元素值位于中间, 那么下一次做判断的元素个数也会减少一部分, 综上, 内部while循环时, 相对于普通的循环嵌套, 该种循环可以认为是常数级(虽然还是与size的大小有关, 但是总体来说, 要做的判断次数比通常的循环小).

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> max_res;
        deque<int> dq_index;
        for(int i =0; i< num.size(); i++){
            while(!dq_index.empty() && num[i] > num[dq_index.back()] ){
                dq_index.pop_back();
            }
            if(!dq_index.empty() && i-dq_index.front()>= size)
                    dq_index.pop_front();
            dq_index.push_back(i);
            if(i>=size-1)
                max_res.push_back(num[dq_index.front()]);
        }
        return max_res;
    }
};

65.矩阵中的路径

题目描述

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

解法一:

这是一个可以用回朔法解决的典型题。首先，在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。
重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。
　　由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个
字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。
　　由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。 当矩阵中坐标为（row,col）的
格子和路径字符串中相应的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符
如果4个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前一个，然后重新定位。
　　一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置

本题一定要注意边界条件即特殊情况的判断:

• 当矩阵所有元素一样时(这种情况一定要注意先)
• 当矩阵只有一个元素时(这两种情况要注意, 先进入递归程序, 然后再对flag矩阵进行判断, 否则, 当子串和矩阵大小一样时, 就无法判断到下一个字符是否==’\0’了)
  -

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(str[0] == '\0') return true;

        int* flag_matrix = new int[rows*cols];
        for(int i = 0; i<rows; i++){
            for(int j =0 ;j<cols; j++){
                flag_matrix[i*cols+j] = 1;
            }
        }
        for(int i = 0; i< rows; i++){
            for(int j = 0;j< cols; j++){
                if(matrix[i*cols+j] == str[0]){
                    bool is_path = hasPath_helper(matrix,flag_matrix,i,j, rows, cols, str, 0);
                    if(is_path)
                        return true;
                }
            }
        }

        delete []flag_matrix;
        return false;
    }

    bool hasPath_helper(char* matrix,int* flag_matrix, int i, int j, int rows, int cols, char* str,int x){
        if(str[x] == '\0') return true;

        if(i<0 || i>=rows || j<0 || j>=cols) return false;
        if(flag_matrix[i*cols+j] == 0 || matrix[i*cols+j] != str[x]) return false;

        flag_matrix[i*cols+j] = 0;
        bool is_path = hasPath_helper(matrix, flag_matrix, i, j-1, rows, cols, str, x+1) ||
                       hasPath_helper(matrix, flag_matrix, i-1 , j, rows, cols, str, x+1) ||
                       hasPath_helper(matrix, flag_matrix, i, j+1, rows, cols, str, x+1) ||
                        hasPath_helper(matrix, flag_matrix, i+1, j, rows, cols, str, x+1);
        flag_matrix[i*cols+j] = 1;
        return is_path;
    }


};

66.机器人的运动范围

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

解法一:

回溯法, 如果当前节点的位数值满足要求, 那么从当前节点开始, 满足要求的格子数字应该等于” 1+左+右+上+下”, 其中方向代表这个方向上的满足要求的格子数.

注意每走过一次格子, 需要将flag矩阵中当前格子的标识设为”已走过(1)”, 并且, 由于此任务是统计符合条件的格子总数, 所以和一般的回溯法不同, 不能在递归结束后将该格子的标识重新复位(否则不同路径上回到同一个格子重复计数).

class Solution {
public:
    int mc_helper(int threshold,int cur_i, int cur_j, vector< vector<int> >& flag_matrix){
        int rows = flag_matrix.size();
        int cols = flag_matrix[0].size();
        int cur_val = cur_i/10 + cur_i%10 + cur_j/10 + cur_j%10;

        if(cur_val > threshold
           || cur_i<0 || cur_i >=rows || cur_j<0 || cur_j>=cols
           || flag_matrix[cur_i][cur_j]) return 0;

        flag_matrix[cur_i][cur_j] = 1;
        return 1 + mc_helper(threshold, cur_i, cur_j-1, flag_matrix)+
                   mc_helper(threshold, cur_i, cur_j+1, flag_matrix)+
                   mc_helper(threshold, cur_i-1, cur_j, flag_matrix)+
                   mc_helper(threshold, cur_i+1, cur_j, flag_matrix);
        //flag_matrix[cur_i][cur_j] = 0;
        //return cur_count;
    }

    int movingCount(int threshold, int rows, int cols)
    {

        if(rows<=0 || cols<=0) return 0;


        vector< vector<int> > flag_matrix(rows, vector<int>(cols));
        int count = mc_helper(threshold,0, 0, flag_matrix);
        return count;
    }


};