61.序列化二叉树???

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

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

• 思路：序列化法

class Solution {
public:
    char* Serialize(TreeNode *pRoot) {
        string s;
        if (!pRoot)
            return NULL;
        deque<TreeNode*> q;
        q.push_back(pRoot);
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                if (q.front()) {
                    q.push_back(q.front()->left);
                    q.push_back(q.front()->right);
                    s += to_string(q.front()->val) + ' ';
                } else {
                    s += "# ";
                }
                q.pop_front();
            }
        }
        char* chr = strdup(s.c_str());
        return  chr;
    }
    TreeNode* Deserialize(char *str) {
        if (!str)
            return nullptr;
        int k = 0;
        auto ret = nextNode(str, k);
        deque<TreeNode*> q;
        q.push_back(ret);
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; ++i) {               
                q.front()->left = nextNode(str, k);
                q.front()->right = nextNode(str, k);
                if (q.front()->left)
                    q.push_back(q.front()->left);
                if (q.front()->right)
                    q.push_back(q.front()->right);
                q.pop_front();
            }
        }
        return ret;
    }
    TreeNode* nextNode(char *str,int &i) {
        string s;
        while (str[i] != '\0'&&str[i] != ' ') {
            if (str[i] == '#') {
                i += 2;
                return nullptr;
            }
            s += str[i];
            i++;
        }
        if (str[i] == ' ')
            i++;
        if (!s.empty())
            return new TreeNode(stoi(s));
        return nullptr;
    }
};

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

• 题目：给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4
• 知识点：二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的[二叉树]： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为[二叉排序树]。
• 思路：叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。 所以，按照中序遍历顺序找到第k个结点就是结果。

class Solution {
    int count = 0;
public:
    TreeNode* KthNode(TreeNode* pRoot, unsigned int k)
    {
        if(pRoot){ 
                TreeNode *ret = KthNode(pRoot->left, k);
                if(ret) return ret;
                if(++count == k) return pRoot;
                ret = KthNode(pRoot->right,k);
                if(ret) return ret;
        }
        return nullptr;
    }
};

63.数据流中的中位数

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

核心思路：
1.维护一个大顶堆，一个小顶堆，且保证两点：
1）小顶堆里的全大于 大顶堆里的；
2）2个堆个数的差值小于等于1
2.当insert的数字个数为奇数时：使小顶堆个数比大顶堆多1；
当insert的数字个数为偶数时，使大顶堆个数跟小顶堆个数一样。
3.那么当总数字个数为奇数时，中位数就是小顶堆堆头；
当总数字个数为偶数时，中卫数就是 2个堆堆头平均数

class Solution {
private:
    vector<int> big_part;
    vector<int> small_part;
public:
    void Insert(int num)
    {
        if (small_part.empty()) {
            small_part.push_back(num);
        }
        else {
            if (small_part.size() == big_part.size()) {
                if (num <= big_part.front()) {
                    small_part.push_back(num);
                    push_heap(small_part.begin(), small_part.end());
                }
                else {
                    pop_heap(big_part.begin(), big_part.end(), greater<int>());
                    small_part.push_back(big_part.back());
                    big_part.back() = num;
                    push_heap(small_part.begin(), small_part.end());
                    push_heap(big_part.begin(), big_part.end(), greater<int>());
                }
            }
            else {
                if (num >= small_part.front()) {
                    big_part.push_back(num);
                    push_heap(big_part.begin(), big_part.end(), greater<int>());
                }
                else {
                    pop_heap(small_part.begin(), small_part.end());
                    big_part.push_back(small_part.back());
                    small_part.back() = num;
                    push_heap(small_part.begin(), small_part.end());
                    push_heap(big_part.begin(), big_part.end(), greater<int>());
                }
            }
        }
    }
 
    double GetMedian()
    { 
        if (small_part.size() == big_part.size()) {
            return static_cast<double>(small_part.front() + big_part.front()) / 2;
        }
        else {
            return small_part.front();
        }
    }
 
};

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]}。
• 思路：

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> res;
        deque<int> s;
        for(unsigned int i=0;i<num.size();++i){
            while(s.size() && num[s.back()]<=num[i])//从后面依次弹出队列中比当前num值小的元素，同时也能保证队列首元素为当前窗口最大值下标
                s.pop_back();
            while(s.size() && i-s.front()+1>size)//当当前窗口移出队首元素所在的位置，即队首元素坐标对应的num不在窗口中，需要弹出
                s.pop_front();
            s.push_back(i);//把每次滑动的num下标加入队列
            if(size&&i+1>=size)//当滑动窗口首地址i大于等于size时才开始写入窗口最大值
                res.push_back(num[s.front()]);
        }
        return res;
    }
};

65.矩阵中的路径

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

这个题目是回溯法的典型题目；其实回溯法也是全排列的一种方案，在本题中，也就是尝试了matrix矩阵中所有点作为起点的方法，然后依据这个点进行向四个方向的递归；在递归中，不满足题目的会自动出栈回到上一个状态；

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(matrix==NULL||rows<1||cols<1||str==NULL) return false;
       bool *flag=new bool[rows*cols];
       memset(flag,false,rows*cols);
       for(int i=0;i<rows;i++)
       {
           for(int j=0;j<cols;j++)
           {
               if(haha(matrix,rows,cols,i, j,str,0,flag))
               {
                   return true;
               }
           }
       }
        delete[] flag;
        return false;
    }
     /*参数说明*/
    bool haha(char* matrix,int rows,int cols,int i,int j,char* str,int k,bool* flag)
    {
        //因为是一维数组存放二维的值，index值就是相当于二维数组的（i，j）在一维数组的下标
       int index = i * cols + j;
        //flag[index]==true,说明被访问过了，那么也返回true;
       if(i<0 || i>=rows || j<0 || j>=cols || matrix[index]!=str[k] || flag[index]==true)
               return false;
        //字符串已经查找结束，说明找到该路径了
       if(str[k+1]=='\0') return true;
        //向四个方向进行递归查找,向左，向右，向上，向下查找
       flag[index] = true;//标记访问过
       if(  haha(matrix, rows, cols, i - 1, j,     str, k + 1, flag)
          ||haha(matrix, rows, cols, i + 1, j,     str, k + 1, flag)
          ||haha(matrix, rows, cols, i,     j - 1, str, k + 1, flag)
          ||haha(matrix, rows, cols, i,     j + 1, str, k + 1, flag))
        {
            return true;
        }
        flag[index] = false;
        return false;
    }
};

66.机器人的运动范围

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

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        vector<int> isVisit(rows*cols, 0);
        return helper(threshold, rows, cols, 0, 0, isVisit);
    }
private:
    int helper(int threshold, int rows, int cols, int row, int col, vector<int>& isVisit)
    {
        if (row < 0 || row >= rows || col < 0 || col >= cols ||digitnum(row) + digitnum(col) > threshold || isVisit[row*cols+col] == 1)
            return 0;
        isVisit[row*cols+col] = 1;
        return 1 + helper(threshold, rows,cols, row-1, col,isVisit) +
            helper(threshold, rows,cols, row+1, col,isVisit) +
            helper(threshold, rows,cols, row, col-1,isVisit) +
            helper(threshold, rows,cols, row, col+1,isVisit); 
    }
    int digitnum(int num)
    {
        int cnt = 0;
        while(num)
        {
            cnt += num % 10;
            num /= 10;
        }
        return cnt;
    }
};