/*struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}};*/class Solution {public:    bool HasSubtree(TreeNode* A, TreeNode* B)    {        if(!A || !B) return false;        if(isPart(A,B)) return true;        return (HasSubtree(A->left,B) || HasSubtree(A->right,B));    }        bool isPart(TreeNode *A1,TreeNode *B1)    {        if(!B1) return true;        if(!A1 || A1->val != B1->val) return false;                return (isPart(A1->left,B1->left) && isPart(A1->right,B1->right));    }};

D16

// 旋转数组 最小值

//树的镜像 将树的所有结点左右儿子全部交换/*struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}};*/class Solution {public:    void Mirror(TreeNode *pRoot) {        if(!pRoot) return;        Mirror(pRoot->left);        Mirror(pRoot->right);        swap(pRoot->left,pRoot->right);    }};

//栈的压入 弹出序列class Solution {public:    bool IsPopOrder(vector<int> pushV,vector<int> popV) {        if(pushV.size() != popV.size()) return false;                int i = 0;        stack<int> stk;        for(auto x:pushV)        {            stk.push(x);            while( stk.size() && stk.top()==popV[i])            {                stk.pop();                i++;            }        }                return stk.empty();    }};

//翻转倒数第k个结点/*struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}};*/class Solution {public:    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {        int n = 0;        for (auto p = pListHead; p; p = p->next) n ++ ;        if (n < k) return nullptr;        auto p = pListHead;        for (int i = 0; i < n - k; i ++ ) p = p->next;        return p;    }};

//反转链表 -- 迭代/*只需要完成逆置链表函数struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}};*/class Solution {public:    ListNode* ReverseList(ListNode* pHead) {        ListNode *prev = nullptr;        ListNode *cur = pHead;        while (cur)        {            ListNode *next = cur->next;            cur->next = prev;            prev = cur, cur = next;        }        return prev;    }};

//翻转单词顺序class Solution {public:    string ReverseSentence(string s) {        int k = 0;        for (int i = 0; i < s.size();)        {            int j = i;            while (j < s.size() && s[j] ==  ) j ++ ;            if (j == s.size()) break;            i = j;            while (j < s.size() && s[j] !=  ) j ++ ;            reverse(s.begin() + i, s.begin() + j);            if (k) s[k ++ ] =  ;            while (i < j) s[k ++ ] = s[i ++ ];        }        //s.erase(s.begin() + k, s.end());        reverse(s.begin(), s.end());        return s;    }};

//水题 用这个方法，解决三道题目了class Solution {public:    int rectCover(int number) {        int fio[40]={0,1,2};        for(int i=3;i<40;i++)            fio[i]=fio[i-1]+fio[i-2];        return fio[number];    }};

//连续子数组的最大值class Solution {public:    int FindGreatestSumOfSubArray(vector<int> array) {        int res = INT_MIN,s=0;        int n = array.size();        for(int i=0;i<n;i++)        {            if(s < 0) s = 0;            s += array[i];            res = max(res,s);        }                return res;    }};

//两个栈实现队列class Solution{public:    void push(int node) {        stack1.push(node);    }    //stack.pop() 移除栈顶元素    //stack.push()     //stack.top() 访问栈顶元素    int pop() {        if(stack2.empty())        {            if(stack1.empty()) return  -1;            else             {                while(!stack1.empty())//只要栈1 不为空一直将栈1中最上面的数压入栈2                {                    stack2.push(stack1.top());                    stack1.pop();                }            }        }        int node = stack2.top();        stack2.pop();        return node;    }    private:    stack<int> stack1;    stack<int> stack2;};

//利用栈来实现 /***  struct ListNode {*        int val;*        struct ListNode *next;*        ListNode(int x) :*              val(x), next(NULL) {*        }*  };*/class Solution {public:    vector<int> printListFromTailToHead(ListNode* head) {        vector<int> res;        while(head)        {            res.push_back(head->val);            head = head->next;        }        return vector<int>(res.rbegin(),res.rend());    }};

//替换空格class Solution {public:void replaceSpace(char str[],int length) {        if(length == 0 || str == nullptr) return;                int original = 0,number_blank = 0,k = 0;        while(str[k] != )        {            original ++; //            if( str[k] ==  ) number_blank ++;            k ++;        }        int new_length = original + number_blank * 2;        int i = original,j = new_length;        while(i >= 0 && j > i)        {            if(str[i] ==  )            {                str[ j -- ] = 0;                str[j --] = 2;                str[j --] = %;            }            else str[j--] = str[i];            i --;        }}};

//我又来水了 hhh,画个图很容易就找到了规律，本来想如果库函数过不了的话准备写的快速幂，但是~~~class Solution {public:    int jumpFloorII(int number) {        return pow(2,number-1);    }};竟然不支持带图打卡？？？？？？？？？