//这里填你的代码^^
class Solution {
public:
    int maxVowels(string s, int k) {
        unordered_set<char> S({'a','e','i','o','u'});
        int res=0;
        for(int i=0,cnt=0;i<s.size();i++){
            cnt+=S.count(s[i]);
            if(i>=k) cnt-=S.count(s[i-k]);
            if(i>=k-1) res=max(res,cnt);
        }
        return res;
    }
};
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        stringstream ssm(sentence);
        string word;
        for(int i=1;ssm>>word;i++){
            if(word.substr(0,searchWord.size())==searchWord)
                return i;
        }
        return -1;
    }
};
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
/**
 * 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:
    vector<vector<int>> ans;
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        vector<int> path;
        dfs(root,sum,path);
        return ans;
    }
    void dfs(TreeNode* root, int sum,vector<int>path){
        if(!root) return;
        path.push_back(root->val);
        sum-=root->val;
        if(!root->left&&!root->right&&!sum) ans.push_back(path);
        dfs(root->left,sum,path);
        dfs(root->right,sum,path);
        path.pop_back();
        sum+=root->val;
    }
};
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
class Solution {
public:
    vector<int> seq;
    bool verifySequenceOfBST(vector<int> sequence) {
        seq=sequence;
        if(seq.empty()) return true;
        return dfs(0,seq.size()-1);
    }
    bool dfs(int l,int r){
        int k,root;
        root=seq[r];
        while(k<r&&seq[k]<root) k++;
        for(int i=k;i<r;i++) if(seq[i]<root) return false;
        if(l>=r) return true;
        return dfs(l,k-1)&&dfs(k,r-1);
    }
};
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(!head||!head->next) return 0;
        ListNode *p=head,*q=head;
        while(p&&q)
        {
            p=p->next;
            q=q->next;
            if(q) q=q->next;
            else return 0;
            if(p==q)
            {
                p=head;
                while(p!=q){
                    p=p->next;
                    q=q->next;
                }
                return p;
            }
        }
        return 0;
    }
};
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stackValue;
    stack<int> stackMin;
    MinStack() {

    }

    void push(int x) {
        stackValue.push(x);
        if (stackMin.empty() || stackMin.top() >= x)
            stackMin.push(x);
    }

    void pop() {
        if (stackMin.top() == stackValue.top()) stackMin.pop();
        stackValue.pop();
    }

    int top() {
        return stackValue.top();
    }

    int getMin() {
        return stackMin.top();
    }
};

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
class Solution {
public:
    vector<int> printMatrix(vector<vector<int>>& matrix) {
        vector<int> res;
        if (matrix.empty()) return res;
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<bool>> st(n, vector<bool>(m, false));
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        int x = 0, y = 0, d = 1;
        for (int k = 0; k < n * m; k ++ )
        {
            res.push_back(matrix[x][y]);
            st[x][y] = true;

            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b])
            {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        return res;
    }
};

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return dfs(root->left,root->right);
    }
    bool dfs(TreeNode*p,TreeNode*q){
        if(!p||!q) return !p&&!q;
        if(p->val!=q->val) return false;
        return dfs(p->left,q->right)&&dfs(p->right,q->left);
    }
};
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
class Solution {
public:
    void mirror(TreeNode* root) {
        if(!root) return ;
        swap(root->left,root->right);
        mirror(root->left);
        mirror(root->right);
    }
};
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
class Solution {
public:
    bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot1||!pRoot2) return false;
        if(isPart(pRoot1,pRoot2)) return true;
        return hasSubtree(pRoot1->left,pRoot2)||hasSubtree(pRoot1->right,pRoot2);
    }
    bool isPart(TreeNode*p1,TreeNode*p2){
        if(!p2) return true;
        if(!p1||p1->val!=p2->val) return false;
        return isPart(p1->left,p2->left)&&isPart(p1->right,p2->right);
    }
};
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~