class MedianFinder {
public:

    // Adds a number into the data structure.
    void addNum(int num) {
        small.push(num);
        big.push(-small.top());
        small.pop();
        if(small.size()<big.size())
        {
            small.push(-big.top());
            big.pop();
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        if(big.size()==small.size())
            return small.top()-(big.top()+small.top())/2.0;
        else
            return small.top();
    }

private:
    priority_queue<int> small, big;
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();

class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.length()<2)
            return 0;
        int ret=0;
        vector<int> dp(s.length(),0);
        for(int i=1;i<s.length();++i)
        {
            if(s[i]=='(')
                continue;
            else
            {
                if(s[i-1]=='(')
                {
                    dp[i]=i>1?(dp[i-2]+2):2;
                }
                else{
                    if(i-dp[i-1]-1>=0 && s[i-dp[i-1]-1]=='(')
                    {
                        dp[i]=dp[i-1]+2+((i-dp[i-1]-2)>=0?dp[i-dp[i-1]-2]:0);
                    }
                }
            }
            ret=max(ret, dp[i]);
        }
        return ret;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || !head->next)
            return;
        auto p1=head;
        auto p2=head->next;
        while(p2 && p2->next)
        {
            p1=p1->next;
            p2=p2->next->next;
        }

        auto h2=p1->next;
        p1->next = NULL;

        p1=h2->next;
        h2->next=NULL;
        while(p1)
        {
            p2=p1;
            p1=p1->next;
            p2->next=h2;
            h2=p2;
        }

        p1=head;
        while(h2)
        {
            p2=h2->next;
            h2->next=p1->next;
            p1->next=h2;
            p1=h2->next;
            h2=p2;
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(k==0 || !head)
            return head;
        int count=0;
        ListNode *root = new ListNode(0);
        root->next=head;
        auto p=root->next, q=root;
        while(p)
        {
            p=p->next;
            ++count;
        }
        p=root;
        k=k%count;
        for(int i=0;i<k && p ; ++i, p=p->next);
        while(p && p->next)
        {
            p=p->next;
            q=q->next;
        }
        p->next=root->next;
        root->next=q->next;
        q->next=NULL;
        return root->next;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int *ret = new int(INT_MIN);
        foo(root, ret);
        return *ret;
    }

    int foo(TreeNode* root, int *ret)
    {
        if(root==NULL)
            return 0;
        int left=max(foo(root->left, ret), 0);
        int right=max(foo(root->right, ret), 0);
        *ret = max(left+right+root->val, *ret);
        return max(left, right)+root->val;
    }
};

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for(auto i: prerequisites)
        {
            graph[i.second].push_back(i.first);
        }
        vector<bool> visit(numCourses, false);
        for(int i=0;i<numCourses; ++i)
            if(!dfs(graph, i, visit))
                return false;
        return true;
    }

    bool dfs(vector<vector<int>> &graph, int cur,  vector<bool> &visit)
    {
        if(visit[cur])
            return false;
        visit[cur]=true;
        for(auto i: graph[cur])
        {
            if(!dfs(graph, i, visit))
                return false;
        }
        visit[cur]=false;
        return true;
    }

};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> ret;
        sort(intervals.begin(), intervals.end(), [](Interval &lhs, Interval &rhs){
            return lhs.start<rhs.start;
        });
        for(auto &i: intervals)
        {
            if(ret.empty() ||
                ret.back().end < i.start)
                ret.push_back(i);
            else
                ret.back().end = ret.back().end>i.end ? ret.back().end : i.end;
        }
        return ret;
    }
};

class Solution {
public:
    int numSquares(int n) {
        if(n<0)
            return 0;
        vector<int> vec(n+1, INT_MAX);
        vec[0]=0;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j*j<=i;++j)
            {
                vec[i]=min(vec[i], vec[i-j*j]+1);
            }
        }
        return vec.back();
    }
};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> mmap;
        for(auto i: strs)
        {
            auto str = i;
            sort(str.begin(),str.end());
            mmap[str].push_back(i);
        }
        vector<vector<string>> ret;
        for(auto i: mmap)
        {
            sort(i.second.begin(),i.second.end());
            ret.push_back(i.second);
        }
        return ret;
    }
};

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> vec;
        foo(s, 0, s.size(), res, vec);
        return res;
    }

    void foo(string s, int beg, int end, vector<vector<string>> &res, vector<string> &vec)
    {
        if(beg>=end)
        {
            res.push_back(vec);
            return;
        }

        for(int i=beg; i<end; ++i)
        {
            if(bar(s, beg, i))
            {
                vec.push_back(s.substr(beg, i-beg+1));
                foo(s, i+1, end, res, vec);
                vec.pop_back();
            }
        }
    }

    bool bar(string s, int beg, int end)
    {
        while(beg<=end)
        {
            if(s[beg]==s[end])
            {
                ++beg;
                --end;
            }
            else
                return false;
        }
        return true;
    }
};