// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = s.size() - 1; // 饼干数组的下标
        int result = 0;
        for (int i = g.size() - 1; i >= 0; i--) {
            if (index >= 0 && s[index] >= g[i]) {
                result++;
                index--;
            }
        }
        return result;
    }
};

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five=0,ten=0,twenty=0;
        for(int bill:bills){
            //收到5
            if(bill==5){
                five++;
            }
            //收到10
            else if(bill==10){
                if(five<=0){
                    return false;
                }
                else{
                    ten++;
                    five--;
                }
                
            }
            //收到20
            else if(bill==20){
                if(five>=1&&ten>=1){//优先用10来找零
                    five--;
                    ten--;
                    twenty++;//可以不记录20块钱的个数，不用20找零
                }
                else if(five>=3){
                    five-=3;
                    twenty++;//可以不记录20块钱的个数，不用20找零
                }
                else{
                    return false;
                }
            }
        }
        return true;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;
        for(int i=0;i<nums.size();i++){
            count+=nums[i];
            if(result<count){
                result=count;
            } 
            if(count<=0){
                count=0;
            }
        }
        return result;
    }
};

class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b){
        return a[0]<b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        /*输入一个二维数组，输出一个整数*/
        if(points.size()==1){
            return 1;
        }
        // 先将二维数组排序
        sort(points.begin(),points.end(),cmp);
        int result=1;// 需要几只箭
        for(int i=1;i<points.size();i++){
            // 会发生重叠
            if(points[i-1][1]>=points[i][0]){
                points[i][1]=min(points[i][1],points[i-1][1]);// 更新当前气球的右边界
            }
            // 没有重叠
            else{
                result++;
            }
            
        }
        return result;
    }
};

 static bool cmp(vector<int>& a,vector<int>& b){
         
    return a[0]<b[0];
}

class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b){
        
        if(a[0]==b[0]){
            return a[1]<b[1];
        }
        return a[0]<b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        /*输入一个二维数组，输出一个整数*/
        if(points.size()==1){
            return 1;
        }
        // 先将二维数组排序
        sort(points.begin(),points.end(),cmp);
        int result=1;// 需要几只箭
        for(int i=1;i<points.size();i++){
            // 会发生重叠
            if(points[i-1][1]>=points[i][0]){
                points[i][1]=min(points[i][1],points[i-1][1]);// 更新当前气球的右边界
            }
            // 没有重叠
            else{
                result++;
            }
            
        }
        return result;
    }
};

static bool cmp(vector<int> &a,vector<int> &b){
        return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        /*输入一个二维数组，输出一个二维数组*/
        if(intervals.size()==1){
            return intervals;
        }
        //对数组进行排序
        sort(intervals.begin(),intervals.end(),cmp);
        //
        vector<vector<int>> result;
        bool flag = false;// 标记最后一个区间有没有合并
        for(int i=1;i<intervals.size();i++){
            // 当相邻区间重叠时，合并，当前区间i就是合并后的区间
            int start=intervals[i-1][0];
            int end = intervals[i-1][1];
            
            while(i<intervals.size()&&end>=intervals[i][0]){
                end = max(intervals[i][1],end);
                if (i == intervals.size() - 1) flag = true;
                i++;
            }
            result.push_back({start,end});
        }
        // 如果最后一个区间没有和前一个区间重叠，将需单独加入result
        if (flag == false) {
            result.push_back({intervals[intervals.size() - 1][0], intervals[intervals.size() - 1][1]});
        }
        return result;
    }

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if (nums.size() == 1) return true; // 只有一个元素，就是能达到
        for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
        }
        return false;
    }
};

class Solution{
public:
    vector<int> partitionLabels(string s){
        // 记录每个字符出现的最远下标
        int hash[27]={0};
        for(int i=0;i<s.size();i++){
            hash[s[i]-'a']=i;
        }
        vector<int> res;
        for(int i=0;i<s.size();i++){
            right=max(right,hash[s[i]-'a']);
            if(i==right){
                res.push_back(right-left+1);
                left=i+1;
            }
        }
        return res;
        
    }

};

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        // 从前向后
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
        }
        // 从后向前
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] ) {
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        // 统计结果
        int result = 0;
        for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
        return result;
    }
};

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int treeSize = tree.size(), maxRes = 0;
        int left = 0, right = 0, fruitOne, fruitTwo;//窗口的左、右边界，以及窗口中的两种水果
        while (right < treeSize){
            int tempRes = 1;//窗口的大小
            fruitOne = tree[left++];//第一种水果
            //寻找到第二种水果的第一次出现的位置（并且更新下一次的窗口的left）
            while (left < treeSize && tree[left] == fruitOne){
                ++left;
                tempRes += 1;
            }
            right = left;
            if (right < treeSize){//第二种水果
                fruitTwo = tree[right];
            }
            //当窗口tree[left, right)中的水果种数不多于2时，扩大右边界
            while (right < treeSize){
                if (tree[right] == fruitOne || tree[right] == fruitTwo){
                    ++right;
                    tempRes += 1;
                }
                else {
                    break;
                }
            }
            maxRes = max(maxRes, tempRes);//更新最大的水果数
        }
        return maxRes;
    }

};

class MyQueue {
public:
    stack<int>sck1;
    stack<int>sck2;
    MyQueue() {

    }
    
    void push(int x) {
        sck1.push(x);
        return ;
    }
    
    int pop() {
        // 把输入栈sck1中的元素放到输出栈sck2，清空sck1
        // 这样stk2的出栈顺序和输入的元素入stk1的顺序是一样的了
        while(!sck1.empty()){
            int num=sck1.top();// 获取栈顶元素，但不删除
            sck1.pop();// 删除栈顶元素，但不返回
            sck2.push(num); // 将元素压入栈顶
        }

        int val=sck2.top();// 返回栈顶元素
        sck2.pop();// 删除栈顶元素
        // 清空输出栈sck2
        while(!sck2.empty()){
            sck1.push(sck2.top());
            sck2.pop();
        }
        return val;
    }
    // 返回队列开头的元素
    int peek() {
        // 清空sck1，元素放入到sck2
        while(!sck1.empty()){
            sck2.push(sck1.top());
            sck1.pop();
        }
        //得到“队列”开头的元素
        int val=sck2.top();
        // 清空sck2，元素放入到sck1
        while(!sck2.empty()){
            sck1.push(sck2.top());
            sck2.pop();
        }
        return val;
    }
    
    bool empty() {
        if(sck1.empty()){
            return true;
        }
        return false;
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        for(int i=0;i<s.size();i++){
            // 左括号入栈，保存对应的右括号，这样右括号来的时候，直接对比是否相等就行
            if(s[i]=='('){
                st.push(')');
            }
            else if(s[i]=='{'){
                st.push('}');
            }
            else if(s[i]=='['){
                st.push(']');
            }
            // 右括号出现
            // 右括号多余s.empty()
            // 左右不匹配
            else if(st.empty()||s[i]!=st.top()){
                return false;
            }
            else{
                st.pop();//左右括号匹配，
            }
        }
        // 左括号多余，则s.empty()==false;
        //都匹配，就是true
        return st.empty();
    }
};

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0, len = s.size();
        // 统计空格数量
        for (char c : s) {
            if (c == ' ') count++;
        }
        // 修改 s 长度
        s.resize(len + 2 * count);//多加两个空格数，因为字符串本身有一个，再加两个（才能放下%20）
        // 倒序遍历修改
        for(int i = len - 1, j = s.size() - 1; i < j; i--, j--) {
            if (s[i] != ' ')
                s[j] = s[i];
            else {
                s[j - 2] = '%';
                s[j - 1] = '2';
                s[j] = '0';
                j -= 2;
            }
        }
        return s;
    }
};

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string str1;
        str1 =s.substr(0,n);
        s.erase(0,n);//即从给定起始位置0处开始删除, 要删除字符的长度为n, 返回值修改后的string对象引用
        return s+str1;
    }
};

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string str="";
        for(int i=n;i<s.size();i++){
            str+=s[i];
        }
        for(int i=0;i<n;i++){
            str+=s[i];
        }
        return str;
    }
};

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0, len = s.size();
        // 统计空格数量
        for (char c : s) {
            if (c == ' ') count++;
        }
        // 修改 s 长度
        s.resize(len + 2 * count);//多加两个空格数，因为字符串本身有一个，再加两个（才能放下%20）
        // 倒序遍历修改
        for(int i = len - 1, j = s.size() - 1; i < j; i--, j--) {
            if (s[i] != ' ')
                s[j] = s[i];
            else {
                s[j - 2] = '%';
                s[j - 1] = '2';
                s[j] = '0';
                j -= 2;
            }
        }
        return s;
    }
};

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string str1;
        str1 =s.substr(0,n);
        s.erase(0,n);//即从给定起始位置0处开始删除, 要删除字符的长度为n, 返回值修改后的string对象引用
        return s+str1;
    }
};

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string str="";
        for(int i=n;i<s.size();i++){
            str+=s[i];
        }
        for(int i=0;i<n;i++){
            str+=s[i];
        }
        return str;
    }
};

class Solution {
public:
    // 反转字符串
    void reverse(string &s,int start,int end){
        int i=start;
        int j=end;
        for(;i<j;i++,j--){
            swap(s[i],s[j]);
        }
    }
    // 移除冗余空格
    // 考虑字符串s前中后空格的位置和fast的大小是否符合循环要求
    void removeExtraStr(string &s){
        int fast=0,slow=0;
        //移除字符串前面多余的空格
        while(s[fast]==' '//表示字符串前有空格
        &&s.size()>0//字符串s不为空
        &&fast<s.size())//fast不能指到s外
        {
            fast++;//结束循环后，fast指向第一个不是空格的字符
        }
        //移除字符串中间多余的空格
        for(;fast<s.size();fast++){
            if(fast-1>0&&
            s[fast]==' '&&
            s[fast-1]==' '){//连续两个空格不做操作
                continue;
            }
            else{//直到fast指向一个字符，前一个是空格，把fast指向的字符赋值给slow指向的位置
                s[slow]=s[fast];
                slow++;
            }
        }
        //移除字符串后面多余的空格
        if(s[slow-1]==' '){//fast指向空格，fast-1指向字符，这时候也执行了s[slow]=s[fast];所以多加了一个空格，如果指向反转字符串的操作，该空格在最前面
            s.resize(slow-1);
        }
        else{
            s.resize(slow);
        }
    }
    string reverseWords(string s) {
        // 移除多余空格
        removeExtraStr(s);
        // 反转字符串
        reverse(s,0,s.size()-1);
        //反转单个单词
        int start=0;
        for(int i=0;i<s.size();i++){
            if(s[i]==' '&&s[i-1]!=' '){
                reverse(s,start,i-1);
                start=i+1;
            }
            // 最后一个单词后没有空格的情况
            if((i == (s.size() - 1) )&& s[i] != ' '){
                reverse(s,start,i);

            }
            
        }
        return s;
        
    }
};

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // 定义结果数组
        vector <int> ans;
        if(matrix.empty()) return ans; //若数组为空，直接返回答案
        //赋值上下左右边界
        int u = 0; 
        int d = matrix.size() - 1;// 行的数目-1
        int l = 0;
        int r = matrix[0].size() - 1;// 列的数目-1
        // 右下左上 。。
        while(true)
        {
            for(int i = l; i <= r; ++i) ans.push_back(matrix[u][i]); //向右移动直到最右
            if(++ u > d) break; //重新设定上边界，若上边界大于下边界，则遍历遍历完成，下同
            for(int i = u; i <= d; ++i) ans.push_back(matrix[i][r]); //向下
            if(-- r < l) break; //重新设定有边界
            for(int i = r; i >= l; --i) ans.push_back(matrix[d][i]); //向左
            if(-- d < u) break; //重新设定下边界
            for(int i = d; i >= u; --i) ans.push_back(matrix[i][l]); //向上
            if(++ l > r) break; //重新设定左边界
        }
        return ans;
    }
};

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n,0));// 定义一个二位数组
        
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop=n/2;//每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid=n/2;// 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 每一圈循环，需要控制每一条边遍历的长度
        int i,j;

        while(loop--){
            i= startx;
            j= starty;
            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < starty + n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < startx + n - offset; i++) {
                res[i][j] = count++;
            }
             // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }
            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;
            // offset 控制每一圈里每一条边遍历的长度
            offset += 2;
        }
        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        //,n为偶数不用
        if(n%2){
            res[mid][mid]=count;

        }
        return res;

    }
};

class MyLinkedList {
public:
    /** 初始化数据结构 */
    MyLinkedList():head(new node()),tail(head),size(0) {}
    
    /** 得到链表中第index个结点的值，index小于0或大于链表长度（链表的index从0开始），返回-1 */
    int get(int index) {
        if(index>=size||index<0)
            return -1;
        else if(index==size-1)
            return tail->val;
        
        node *cur=head->next;
        while(index--)
            cur=cur->next;
        return cur->val;
    }
    
    /** 添加新的头节点 */
    void addAtHead(int val) {
        ++size;
        node *tmp=new node(val);
        tmp->next=head->next;
        head->next=tmp;
        //注意更新尾节点
        if(size==1)
            tail=tmp;
    }
    
    /** 在链表最后添加一个结点. */
    void addAtTail(int val) {
        ++size;
        node *tmp=new node(val);
        tail->next=tmp;
        tail=tmp;
    }
    
    /** 在链表第index个结点前添加结点，
    如果index等于链表长度，则将结点添加到链表末尾。
    如果index大于链表长度，则不会插入结点
    如果index小于0，则在头部插入结点。
     */
    void addAtIndex(int index, int val) {
        if(index<=0)
            addAtHead(val);
        else if(index==size)
            addAtTail(val);
        else if(index<size){
            node *cur=head;
            while(index--)
                cur=cur->next;
            // node *nxt=cur->next;
            // node *tmp=new node(val);
            // cur->next=tmp;
            // tmp->next=nxt;
            node *tmp=new node(val);
            // cur指向第index个结点的前一个
            tmp->next=cur->next;
            cur->next=tmp;
            ++size;
        }
    }
    
    /** 索引有效，则删除链表的第index个结点*/
    void deleteAtIndex(int index) {
        if(index>=size||index<0)
            return ;
        node *cur=head;
        while(index--)
            cur=cur->next;
        node *tmp=cur->next;
        cur->next=tmp->next;
        //tmp指向最后一个结点时，注意更新尾节点，
        if(!tmp->next)
            tail=cur;// cur指向第index个的前一个结点
        delete(tmp);
        --size;
    }
private:
    struct node{
        int val;
        node *next;
        node():val(0),next(nullptr){}
        node(int v):val(v),next(nullptr){}
    };
    node *head=nullptr;
    node *tail=nullptr;
    int size=0;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

/**
 * 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) {
        ListNode *curA=headA;
        ListNode *curB=headB;
        int lenA=0;
        int lenB=0;
        //计算A长度
        while(curA){
            lenA++;
            curA=curA->next;
        }
        //计算B长度
        while(curB){
            lenB++;
            curB=curB->next;
        }
        curA=headA;
        curB=headB;
        // 让curA指向长的链表,lenA为其长度。
        if(lenB>lenA){
            swap(lenA,lenB);
            swap(curA,curB);
        }
        // 计算两个链表的长度差；
        int gap=lenA-lenB;
        // curA指向链表的一个结点，使两个链表的末尾对齐
        while(gap--){
            curA=curA->next;
        }
        // 同时遍历，相等则返回结点
        while(curA){
            if(curA==curB){
                return curA;
            }
            curA=curA->next;
            curB=curB->next;
        }
        //不等，返回空。
        return NULL;
    }
};

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // 定义一个虚拟头结点， 方便处理
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        // 初始化指针
        ListNode g = dummyHead;
        ListNode p = dummyHead.next;

        // 将指针移到相应的位置
        for(int step = 0; step < m - 1; step++) {
            g = g.next; p = p.next;
        }

        // 头插法插入节点
        for (int i = 0; i < n - m; i++) {
            ListNode removed = p.next;
            p.next = p.next.next;

            removed.next = g.next;
            g.next = removed;
        }

        return dummyHead.next;
    }
}