/* 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);}};竟然不支持带图打卡？？？？？？？？？