1.最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
思路：动态规划
图片说明 

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();//字符串数组
        vector<vector<int>> dp(n, vector<int>(n));
        string ans;
        for (int l = 0; l < n; ++l) {
            for (int i = 0; i + l < n; ++i) {
                int j = i + l;
                if (l == 0) {
                    dp[i][j] = 1;//一个字符的情况
                }
                else if (l == 1) {
                    dp[i][j] = (s[i] == s[j]);//两个字符的情况
                }
                else {
                    dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);//状态转移方程
                }
                if (dp[i][j] && l + 1 > ans.size()) {
                    ans = s.substr(i, l + 1);//更新最大长度
                }
            }
        }
        return ans;
    }
};

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

/*
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||k==0) return nullptr;
        return KthNodeCore(pRoot,k);
    }
    TreeNode* KthNodeCore(TreeNode* pRoot,int &k)
    {
        TreeNode* target=nullptr;
        //中序遍历
        if(pRoot->left)
        {
            target=KthNodeCore(pRoot->left,k);//先遍历左子树
        }
        if(target==nullptr)//左子树中没找到
        {
            if(k==1)
                target=pRoot;//遍历完左子树，k=1，就返回根节点
            k--;//否则K--，开始遍历右子树
        }
        if(target==nullptr&&pRoot->right!=nullptr)//再遍历右子树
        {
            target=KthNodeCore(pRoot->right,k);
        }
        return target;
    }   
};

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

class Solution {
public:
    vector<int> res;
    void Insert(int num)
    {
        res.push_back(num);
    }

    double GetMedian()
    { 
        sort(res.begin(),res.end());
        int len=res.size();
        if(len%2==1)
            return (double)res[len/2];
        else
            return (double)((res[len/2]+res[len/2-1])/2.0);    
    }
};

4.滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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> maxInWindows;
        if(num.size()>=size&&size>=1)
        {
            deque<int> index;
            for(unsigned int i=0;i<size;i++)//放入一个滑动窗口，令队头是窗口的最大值
            {
                while(!index.empty()&&num[i]>=num[index.back()])
                {
                    index.pop_back();//要放入的数大于队尾，就把队尾弹出
                }
                index.push_back(i);//放入新数字
            }
            for(unsigned int i=size;i<num.size();i++)
            {
                maxInWindows.push_back(num[index.front()]);//存一个最大值
                while(!index.empty()&&num[i]>=num[index.back()])
                    index.pop_back();//要放入的数大于队尾，就把队尾弹出
                if(!index.empty()&&index.front()<=(int)(i-size))
                    index.pop_front();//队头大于滑动窗口范围，就弹出
                index.push_back(i);//放入新数字
            }
            maxInWindows.push_back(num[index.front()]);
        }
        return maxInWindows;
    }
};