leetcode刷题笔记—剑指offer

class Solution {
public:string replaceSpace(string s) {int len = s.size();string g;for(int i = 0; i < len; i++){if(s[i] == ' '){g += "%20";continue;}g += s[i];}return g;}
};

class Solution {
public:void Reverse(string &a,int left,int right){while(left < right){char temp = a[left];a[left] = a[right];a[right] = temp;left++;right--;}}string reverseLeftWords(string s, int n) {int len = s.size();if(n >= len){n %= len;}Reverse(s,0,n-1);Reverse(s,n,len-1);Reverse(s,0,len-1);return s;}   
};

class Solution {
public:int strToInt(string str) {int len = str.size();int i = 0;int flag = 1;//标记正负long long num = 0;//返回转化后的数字while(str[i] == ' ')//去掉前导空格{i++;}if(str[i] == '+'||str[i] == '-'){if(str[i] =='-')flag = -flag;i++;}while(i < len && str[i] >= '0' && str[i] <= '9'){num = num*10+(str[i]-'0')*flag;i++;if(flag == -1 && num < INT_MIN ){return INT_MIN;}if(flag == 1 && num > INT_MAX  ){return INT_MAX;}}if(i != len)//没有遍历完就是错误，直接返回当前的值{return num;}return num;}
};

class Solution {
public:vector<int> reversePrint(ListNode* head) {vector<int>ret;while(head!=NULL){ret.insert(ret.begin(),head->val);head = head->next;}return ret;}
};

class Solution {
public:ListNode* reverseList(ListNode* head) {if(head == nullptr){return nullptr;}ListNode * n1 = nullptr;ListNode * n2 = head;ListNode * n3 = head->next;while(n2 != nullptr){n2->next = n1;n1 = n2;n2 = n3;if(n3 != nullptr){n3 = n3->next;}} return n1;}
};

class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/
class Solution {
public:Node* copyRandomList(Node* head) {Node * cur = head;while(cur){Node * ne = cur->next;Node * newNode = (Node*)malloc(sizeof(Node));newNode->val = cur->val;newNode->next = ne;cur->next = newNode;cur = ne;}cur = head;while(cur){Node * ne = cur->next;Node * nene = cur->next->next;if(cur->random == nullptr){cur->next->random = nullptr;}else{cur->next->random = cur->random->next;}cur = nene;}Node * newNode1 =nullptr;Node * tail = nullptr;cur = head;while(cur){Node * ne = cur->next;Node * nene = cur->next->next;if(newNode1 == nullptr){newNode1 = tail = ne;}else{tail->next = ne;tail = tail->next;}cur->next = nene;cur = nene;}return newNode1;}
};

/* * struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {ListNode * cur = head;ListNode * prev = nullptr;while(cur){ListNode * ne = cur->next;if(cur->val == val){if(head == cur)//头删{head = ne;cur = head;}else{prev->next = ne;cur = prev->next;}}else{prev = cur;cur = ne;}}return head;}
};

 /** struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* getKthFromEnd(ListNode* head, int k) {//快慢指针法ListNode * slow = head;ListNode * fast = head;while(k--){fast = fast->next;}while(fast){slow = slow->next;fast = fast->next;}return slow;}
};

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){ListNode * newHead = (ListNode*)malloc(sizeof(ListNode));newHead->next = nullptr;ListNode * tail = newHead;while(l1 != nullptr && l2 != nullptr){if(l1->val <= l2->val){tail->next = l1;tail = tail->next;l1 = l1->next;}else{tail->next = l2;tail = tail->next;l2 = l2->next;}}if(l1 != nullptr){tail->next = l1;}if(l2 != nullptr){tail->next = l2;}return newHead->next;}
};

/*** 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 countA = 0;int countB = 0;while(curA){curA = curA->next;countA++;}while(curB){curB = curB->next;countB++;}if(countA > countB){countA -= countB;while(countA--){headA = headA->next;}}else{countB -= countA;while(countB--){headB = headB->next;}}while(headA != nullptr && headB != nullptr){if(headA == headB){return headA;}headA = headA->next;headB = headB->next;}return nullptr;}
};

class Solution {
public:void exchange(vector<int>&nums,int len){int * ret = (int*)malloc(sizeof(int) * (len + 1));int j = 0;for(int i = 0; i < len; i++){if((nums[i] & 1) == 1){ret[j++] = nums[i];}}for(int i = 0; i < len; i++){if((nums[i] & 1 )== 0){ret[j++] = nums[i];}}for(int i = 0; i < len; i++){nums[i] = ret[i];}}vector<int> exchange(vector<int>& nums) {int len = nums.size();exchange(nums,len);return nums;}
};

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int len = nums.size();unordered_map<int,int>hash;vector<int>ret;for(int i = 0; i < len; i++){int num = target - nums[i];if(hash.count(num)){ret.push_back(num);ret.push_back(nums[i]);break;}hash.insert({nums[i],i});}return ret;}
};

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int len = nums.size();deque<int>q;vector<int>ret;for(int i = 0; i < nums.size(); i++){if(!q.empty() && i - k + 1 > q[0]) q.pop_front();//下标小于滑动窗口则头删//形成单调递增的队列while(!q.empty() && nums[q[q.size()-1]] <= nums[i]) q.pop_back();q.push_back(i);if(i >= k - 1){ret.push_back(nums[q[0]]);}}return ret;}
};

class Solution {
public:string reverseWords(string s) {string ret;int i = 0;int num = s.size();while(i < num)//处理前置空格{if(s[i] != ' '){break;}i++;}while(s.size() > 0)//处理后置空格{int num = s.size();if(s[num-1] != ' '){break;}s.pop_back();}int len = s.size();if(len == 0) return s;while(i < len){int cnt = 0;int begin = ret.size();while(i < len && s[i] != ' '){ret += s[i];i++;}int end = ret.size();reverse(ret.begin()+begin,ret.begin()+end);//部分反转while(i < len && s[i] == ' '){cnt++;if(cnt == 1){ret += s[i];}i++;}}int num1 = ret.size();reverse(ret.begin(),ret.end());return ret;}
};

class CQueue {
public:CQueue() {}void appendTail(int value) {p_push.push(value);}int deleteHead() {if(p_push.empty() && p_pop.empty()){return -1;}if(!p_pop.empty()){int top = p_pop.top();p_pop.pop();return top;}else{while(!p_push.empty()){p_pop.push(p_push.top());p_push.pop();}}int top = p_pop.top();p_pop.pop();return top;}
private:stack<int>p_push;stack<int>p_pop;
};/*** Your CQueue object will be instantiated and called as such:* CQueue* obj = new CQueue();* obj->appendTail(value);* int param_2 = obj->deleteHead();*/

class MinStack {stack<int>x_push;stack<int>min_push;
public:/** initialize your data structure here. */MinStack() {min_push.push(INT_MAX);}void push(int x) {x_push.push(x);min_push.push(std::min(min_push.top(),x));//每次插入插最小的值进去，和最小值的栈顶比较。}void pop() {x_push.pop();min_push.pop();}    int top() {return x_push.top();}    int min() {return min_push.top();}
};
/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(x);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->min();*/

class MaxQueue {
public:deque<int>val;deque<int>vmax;MaxQueue() {}int max_value() {if(vmax.empty()){return -1;}return vmax.front();}void push_back(int value) {while((!vmax.empty()) && (vmax.back() < value))//单调递减的队列{vmax.pop_back();}val.push_back(value);vmax.push_back(value);}int pop_front() {if(val.empty()){return -1;}int ans = vmax.front();if(ans == val.front())//只有和最大值相等才需要删除，跟滑动窗口差不多{vmax.pop_front();}int front = val.front();val.pop_front();return front;}
};/*** Your MaxQueue object will be instantiated and called as such:* MaxQueue* obj = new MaxQueue();* int param_1 = obj->max_value();* obj->push_back(value);* int param_3 = obj->pop_front();*/

class Solution {
private:bool flag[110][110]= {false};int d[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int>ret;if (matrix.size() == 0 || matrix[0].size() == 0) return ret;int rows = matrix.size(),cols = matrix[0].size();int sum = rows * cols;int tal = 0;int row = 0,col = 0;int dir = 0;for(int i = 0; i < sum; i++){ret.push_back( matrix[row][col]);flag[row][col] = true;int a = row + d[dir][0],b = col + d[dir][1];//如果越界或者，或者已经插入的数据那么就走向量的下一个if(a < 0 || a >= rows || b < 0 || b >= cols || flag[a][b]){dir = (dir + 1) % 4;}//一直往某个方向走，直至不合法才进入上面的判定row += d[dir][0];col += d[dir][1];}return ret;}
};

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int>st;int n = pushed.size();int j = 0;for(int i = 0; i < n; i++){st.push(pushed[i]);while(!st.empty() && st.top() == popped[j]){j++;st.pop();}}return st.empty();}
};

class Solution {
public:int findRepeatNumber(vector<int>& nums) {unordered_map<int,int>hash;int k = 0;for(int i = 0; i < nums.size(); i++){if(hash.count(nums[i]))//hash判断该数有没有出现过{k = i;return nums[k];}hash.insert({nums[i],i});}return nums[k];}
};

//遍历法
class Solution {
public:int search(vector<int>& nums, int target) {int count = 0;for(int i = 0; i < nums.size(); i++){if(nums[i] > target){break;}if(nums[i] == target){count++;}}return count;}
};//二分法
// class Solution {
// public:
//     int search(vector<int>& nums, int target) {
//         if(nums.size() == 0) return 0;
//         int a = 0,b = 0;
//         int left = 0,right = nums.size() - 1;
//         while(left < right)
//         {
//             int mid = left + right >> 1;
//             if(nums[mid] >= target) right = mid;
//             else left = mid + 1;
//         }
//         if(nums[left] != target) return 0;
//         a = left;
//         left = 0,right = nums.size() - 1;
//         while(left < right)
//         {
//             int mid = left + right + 1>> 1;
//             if(nums[mid] <= target) left = mid;
//             else right = mid - 1;
//         }
//         b = left;
//         return b - a + 1;
//     }
// };

class Solution {
public:int missingNumber(vector<int>& nums) {int n = nums.size();int sum = 0;for(int i = 1; i <= n; i++){sum += i;}for(int i = 0 ; i < n; i++){sum -= nums[i];}return sum;}
};

class Solution {
public:bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {if(matrix.size() == 0 || matrix[0].size() == 0) return false;   int n = 0,m = matrix[0].size() - 1;while(n < matrix.size() && m >=0){if(matrix[n][m] > target) m--;else if(matrix[n][m] < target) n++;else return true;}return false;}
};

class Solution {
public:int minArray(vector<int>& numbers) {//这是一个左旋数组int n = numbers.size();//二分查找法int left = 0,right = n - 1;while(left < right){int mid = left + right >> 1;if(numbers[mid] > numbers[right]) left = mid + 1;else if(numbers[mid] < numbers[right]) right = mid;//当出现nums[m] = nums[j] 时，一定有区间[i, m] 内所有元素相等 或 区间[m, j] 内所有元素相等（或两者皆满			 足）。对于寻找此类数组的最小值问题，可直接放弃二分查找，而使用线性查找替代。else right--;}return numbers[left];}
};

class Solution {
public:char firstUniqChar(string s) {if(s.size() == 0) return ' ';vector<int>h;int arr[26] = {0};for(int i = 0; i < s.size(); i++){arr[s[i] - 'a']++;}for(int i = 0; i < s.size(); i++){if(arr[s[i] - 'a'] == 1)//找到所有只出现一次的字符{return s[i];}}return ' ';}
};//哈希法
class Solution {
public:char firstUniqChar(string s) {unordered_map<int, int> frequency;for (char ch: s) {++frequency[ch];}for (int i = 0; i < s.size(); ++i) {if (frequency[s[i]] == 1) {return s[i];}}return ' ';}
};

class Solution {
public:vector<int> levelOrder(TreeNode* root) {if(root == nullptr){return {};}queue<TreeNode*>q;vector<int>ret;q.push(root);while(q.size()){TreeNode * front = q.front();ret.push_back(front->val);q.pop();if(front->left != nullptr){q.push(front->left);}if(front->right != nullptr){q.push(front->right);}}return ret;}
};

//自己写的
class Solution {
public:int RootSize(TreeNode * root){if(root == nullptr){return 0;}int leftmax = RootSize(root->left);int rightmax = RootSize(root->right);return leftmax > rightmax ? leftmax + 1 : rightmax + 1;}vector<vector<int>> levelOrder(TreeNode* root) {if(root == nullptr){return {};}int num = RootSize(root);//求深度typedef pair<TreeNode*,int>PII;const int N = 1010;PII q[N];int hh = 0, tt = 0;int i = 0;vector<vector<int>>ret(num);q[tt] = {root,i};while(hh <= tt){PII t = q[hh++];TreeNode * front = t.first;int k = t.second;ret[k].push_back(front->val);if(front->left != nullptr){q[++tt] = {front->left,k + 1};}if(front->right != nullptr){q[++tt] = {front->right,k + 1};}}return ret;}
};
//官方题解
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector <vector <int>> ret;if (!root) {return ret;}queue <TreeNode*> q;q.push(root);while (!q.empty()) {int currentLevelSize = q.size();ret.push_back(vector <int> ());for (int i = 1; i <= currentLevelSize; ++i) {auto node = q.front(); q.pop();ret.back().push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return ret;}
};

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if(root == nullptr) return {};queue<TreeNode*>q;vector<vector<int>>ret;q.push(root);while(!q.empty()){int num = q.size();ret.push_back(vector<int>());for(int i = 0; i < num; i++){auto node = q.front();q.pop();ret.back().push_back(node->val);//在尾部进行尾插，因为插入了二维空vectorif(node->left) q.push(node->left);if(node->right) q.push(node->right);}}int k = ret.size();for(int i = 0; i < k; i++){if(i % 2 != 0)//奇数反转{reverse(ret[i].begin(),ret[i].end());}}return ret;}
};

//我写的
class Solution {
public:bool IsSame(TreeNode * A,TreeNode * B){if(B == nullptr) return true;//如果子结构为空那就是真if(A == nullptr) return false;//子结构不空，主结构空就falseif(A->val == B->val){//只有子结构完全匹配才是truereturn IsSame(A->left, B->left) && IsSame(A->right, B->right);}return false;}void TraverseTree(TreeNode * A,TreeNode * B,bool &flag){if(A == nullptr) return;TraverseTree(A->left,B,flag);//递归到最底部if(flag) return;//如果flag变成了真就直接返回了，不需要继续递归TraverseTree(A->right,B,flag);if(A->val == B->val){flag = IsSame(A,B);}}bool isSubStructure(TreeNode* A, TreeNode* B) {if(A == nullptr || B == nullptr) return false;bool flag = false;//最初是falseTraverseTree(A,B,flag);return flag;}
};
//题解：
class Solution {
public:bool isSubStructure(TreeNode* A, TreeNode* B) {if (A == NULL || B == NULL) return false;if (A->val == B->val) {if (dfs_isEqual(A, B)) {return true;}}return isSubStructure(A->left, B) || isSubStructure(A->right, B);}bool dfs_isEqual(TreeNode* A, TreeNode* B) {if (B == NULL) return true;if (A == NULL) return false;if (A->val == B->val) { return dfs_isEqual(A->left, B->left) && dfs_isEqual(A->right, B->right);} else {return false;}}
};

class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {if(root == nullptr){return root;}mirrorTree(root->left);mirrorTree(root->right);if(root->left != nullptr || root->right != nullptr){TreeNode * tmp = root->left;root->left = root->right;root->right = tmp;}return root;}
};

//我写的
class Solution {
public:void mirrorTree(TreeNode * root){if(root == nullptr) return;mirrorTree(root->left);mirrorTree(root->right);if(root->left != nullptr || root->right != nullptr){TreeNode * tmp = root->left;root->left = root->right;root->right = tmp;}return;}bool IsEmpty(TreeNode * A,TreeNode * B){if(A == nullptr && B == nullptr) return true;if(A == nullptr || B == nullptr) return false;if(A->val == B->val){return IsEmpty(A->left,B->left) && IsEmpty(A->right,B->right);}return false;}bool isSymmetric(TreeNode* root) {if(root == nullptr) return true;mirrorTree(root->right);bool flag = IsEmpty(root->left,root->right);return flag;}
};
//官方题解
class Solution {
public:bool check(TreeNode *p, TreeNode *q) {if (!p && !q) return true;if (!p || !q) return false;return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);}bool isSymmetric(TreeNode* root) {return check(root, root);}
};

class Solution {
public://DFS算法bool IsEmpty(vector<vector<char>>& board, vector<vector<int>>&visited,int rows,int cols,string word,int k){int a = board.size(),b = board[0].size();if(board[rows][cols] != word[k]) return false;//如果字符不同为假else if(k == word.size()-1) return true;//匹配成功返回visited[rows][cols] = true;bool result = false;for(int i = 0; i < 4; i++){int x = rows + dx[i],y = cols + dy[i];if(x >= 0 && x < a && y >= 0 && y < b)//判断边界{if(!visited[x][y])//判断是否访问过{bool flag = IsEmpty(board, visited, x, y, word, k + 1);if(flag) return true;//如果成功直接返回}}}visited[rows][cols] = false;//跳出循环要取消标记return result;}bool exist(vector<vector<char>>& board, string word) {int row = board.size(),col = board[0].size();vector<vector<int>>visited(row,vector<int>(col));bool flag = false;for(int i = 0; i < row; i++)for(int j = 0; j < col; j++){flag = IsEmpty(board,visited,i,j,word,0);if(flag) return true;}return false;}
private:int dx[4] = {0,0,-1,1};int dy[4] = {1,-1,0,0};
};

//我写的dfs
class Solution {
public:int get(int x){int sum = 0;while(x > 0){sum += x % 10;x /= 10;}return sum;}void check(vector<vector<int>>&ans, int row, int col, int k, int &res, int sum, int o){if(sum > k) return;res++;int a = ans.size(),b = ans[0].size();ans[row][col] = true;//走过就不要走了for(int i = 0; i < 2; i++){int x = row + dx[i], y = col + dy[i];if(x >= 0 && x < a && y >= 0 && y < b && !ans[x][y]){int q = get(x), p = get(y);int sum1 = p + q;check(ans,x,y,k,res,sum1,o+1);}    }}int movingCount(int m, int n, int k) {if(k == 0) return 1;vector<vector<int>>ans(m,vector<int>(n));int res = 0;//表示走格子的最大值int o = 1;int sum = 0;//记录数位和check(ans,0,0,k,res,sum,o); return res;}
private:int dx[4] = {1,0};//优化成下和右int dy[4] = {0,1};
};
//官方题解bfs
class Solution {// 计算 x 的数位之和int get(int x) {int res=0;for (; x; x /= 10) {res += x % 10;}return res;}
public:int movingCount(int m, int n, int k) {if (!k) return 1;queue<pair<int,int> > Q;// 向右和向下的方向数组int dx[2] = {0, 1};int dy[2] = {1, 0};vector<vector<int> > vis(m, vector<int>(n, 0));Q.push(make_pair(0, 0));vis[0][0] = 1;int ans = 1;while (!Q.empty()) {auto [x, y] = Q.front();Q.pop();for (int i = 0; i < 2; ++i) {int tx = dx[i] + x;int ty = dy[i] + y;if (tx < 0 || tx >= m || ty < 0|| ty >= n || vis[tx][ty]||get(tx)+get(ty) > k) continue;Q.push(make_pair(tx, ty));vis[tx][ty] = 1;ans++;}}return ans;}
};

class Solution {
public:vector<vector<int>>ret;vector<int>path;void dfs(TreeNode * root,int target){if(root == nullptr) return;path.emplace_back(root->val);target -= root->val;//只有是叶子节点的路径并且目标值为0才插入路径if(root->left == nullptr && root->right == nullptr && target == 0){ret.emplace_back(path);}dfs(root->left,target);dfs(root->right,target);path.pop_back();//回退时删除该路径的值}vector<vector<int>> pathSum(TreeNode* root, int target) {if(root == nullptr) return {};dfs(root,target);return ret;}
};

//利用优先队列做法
class Solution {
public:priority_queue<int,vector<int>>q;void PreInorder(TreeNode * root){if(root == nullptr) return;q.push(root->val);PreInorder(root->left);PreInorder(root->right);}int kthLargest(TreeNode* root, int k) {PreInorder(root);int maxi = -1e9;while(k--) {maxi = q.top();q.pop();}return maxi;}
};

class Solution {char * str[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//绝对映射
public:void dfs(string digits,vector<string>&v,int di,string conbina){if(di == digits.size()) {v.push_back(conbina);return;}int num = digits[di] - '0';//取出数字string s = str[num];for(auto ch : s){dfs(digits,v,di + 1,conbina + ch);//conbina不用+=的好处时栈峥回退不用尾删}}vector<string> letterCombinations(string digits) {vector<string>v;if(digits.empty()) return v;int di = 0;string conbina;dfs(digits,v,di,conbina);return v;}
};

class Solution {
public://二叉搜索树是左小右大，所以进行中序遍历void dfs(Node * cur){if(cur == nullptr) return;dfs(cur->left);if(head == nullptr) {head = tail = cur;//无数据要先插入}else{//双链表的相互指向tail->right = cur;cur->left = tail;tail = cur;}dfs(cur->right);}Node* treeToDoublyList(Node* root) {if(root == nullptr) return nullptr;dfs(root);//设置为循环链表head->left = tail;tail->right = head;return head;}private:Node * head = nullptr;Node * tail = nullptr;
};

class Solution {
public:int maxDepth(TreeNode* root) {if(root == nullptr) return 0;int leftmax = maxDepth(root->left);int rightmax = maxDepth(root->right);return leftmax > rightmax ? leftmax + 1 : rightmax + 1;}
};

class Solution {
public:int maxDepth(TreeNode * root){if(root == nullptr) return 0;int leftmax = maxDepth(root->left);int rightmax = maxDepth(root->right);return leftmax > rightmax ? leftmax + 1 : rightmax + 1;}bool isBalanced(TreeNode* root){if(root==NULL){return true;}int leftmax = maxDepth(root->left);int rightmax = maxDepth(root->right);return abs(leftmax-rightmax)<2 && isBalanced(root->left) && isBalanced(root->right);}
}; 

class Solution {
public:int sumNums(int n) {n && (n += sumNums(n - 1));return n;}
};

class Solution {
public:vector<TreeNode*>GetPath(TreeNode * root,TreeNode *target){vector<TreeNode*>ret;while(root != target){ret.push_back(root);if(root->val > target->val){root = root->left;}   else{root = root->right;}}ret.push_back(root);return ret;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {vector<TreeNode*>path_p = GetPath(root,p);//保存路径vector<TreeNode*>path_q = GetPath(root,q); TreeNode * res = nullptr;for(int i = 0; i < path_p.size() && i < path_q.size(); i++){if(path_p[i] == path_q[i])//寻找最近的公共祖先{res = path_p[i];}else{break;}}return res;}
};

class Solution {
public:bool GetPath(vector<TreeNode*>&path,TreeNode*root,TreeNode * target){if(root == nullptr) return false; //没找到   if(root == target){path.push_back(root);//找到将找到的也要插进去return true;}path.push_back(root);bool left1 = GetPath(path,root->left,target);if(left1) return true;bool right1 = GetPath(path,root->right,target);if(right1) return true;path.pop_back();//没找到退出的时候要删除路径return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {vector<TreeNode*>path_p;vector<TreeNode*>path_q;bool p1 = GetPath(path_p,root,p);bool q1 = GetPath(path_q,root,q);TreeNode * res = nullptr;for(int i = 0; i < path_p.size() && i < path_q.size(); i++){if(path_p[i] == path_q[i])//寻找最近的公共祖先{res = path_p[i];}else{break;}}return res;}
};

class Codec {
public:void rserialize(TreeNode * root,string & ret){//前序遍历转为字符串if(root == nullptr) {ret += "#,";return;}ret += to_string(root->val);//字符转换函数ret += ",";rserialize(root->left,ret);rserialize(root->right,ret);}// Encodes a tree to a single string.string serialize(TreeNode* root) {string ret;rserialize(root,ret);return ret;}// Decodes your encoded data to tree.TreeNode* rdeserialize(list<string>&dateArray){if(dateArray.front() == "#"){dateArray.erase(dateArray.begin());return nullptr;}TreeNode * root = new TreeNode(stoi(dateArray.front()));//将字符串转为数字dateArray.erase(dateArray.begin());//插入后删除root->left = rdeserialize(dateArray);root->right = rdeserialize(dateArray);return root;}TreeNode* deserialize(string data) {list<string>dateArray;//用链表存字符串string str;for(auto& c : data){if(c == ','){dateArray.push_back(str);str.clear();}else{str.push_back(c);}}if(!str.empty()) //如果后面有节点就需要插入在清空{dateArray.push_back(str);str.clear();}return rdeserialize(dateArray);}
};// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

//我写的
class Solution {
public:unordered_map<string,int>hash;void dfs(string s,vector<string>& ret,int len,string str,vector<int>&flag){if(str.size() == len){if(!hash.count(str)){ret.push_back(str);hash.insert({str,1});}return;}for(int i = 0; i < s.size(); i++){if(!flag[i]){flag[i] = true;dfs(s,ret,len,str + s[i],flag);flag[i] = false;}}}vector<string> permutation(string s) {int len = s.size();vector<string>ret;      vector<int>flag;flag.resize(len);  string str;dfs(s,ret,len,str,flag);return ret;}
};
//官方题解
// class Solution {
// public:
//     vector<string> rec;
//     vector<int> vis;//     void backtrack(const string& s, int i, int n, string& perm) {
//         if (i == n) {
//             rec.push_back(perm);
//             return;
//         }
//         for (int j = 0; j < n; j++) {
//             if (vis[j] || (j > 0 && !vis[j - 1] && s[j - 1] == s[j])) {
//                 continue;
//             }
//             vis[j] = true;
//             perm.push_back(s[j]);
//             backtrack(s, i + 1, n, perm);
//             perm.pop_back();
//             vis[j] = false;
//         }
//     }//     vector<string> permutation(string s) {
//         int n = s.size();
//         vis.resize(n);
//         sort(s.begin(), s.end());
//         string perm;
//         backtrack(s, 0, n, perm);
//         return rec;
//     }
// };

class Solution {
public:vector<int> printNumbers(int n) {vector<int>ret;if(n == 0) return ret;int k = 1;while(n--){k *= 10;}for(int i = 1; i < k; i++){ret.push_back(i);}return ret;}
};

class Solution {
public:int merge(vector<int>&nums,int left,int right,vector<int>&tmp){if(left >= right) return 0;int mid = (left + right) >> 1;int res = merge(nums,left,mid,tmp) + merge(nums,mid+1,right,tmp);int k = 0,i = left,j = mid + 1;while(i <= mid && j <= right){if(nums[i] <= nums[j]){tmp[k++] = nums[i++];}else{tmp[k++] = nums[j++];//只有q[i]>q[j]时才是逆序对，若是它大于q[j]了，那么mid-i+1的数都会大于q[j]，都属于逆序对，这是进行扫尾res += mid - i + 1;}}while(i <= mid){tmp[k++] = nums[i++];}while(j <= right){tmp[k++] = nums[j++];}for(int i = left,j = 0; i <= right; i++, j++){nums[i] = tmp[j];}return res;}int reversePairs(vector<int>& nums) {if(nums.size() == 0) return 0;vector<int>tmp;int len = nums.size();tmp.resize(len+1);return merge(nums,0,len-1,tmp);}
};

class Solution {
private:unordered_map<int, int> hash;
public:TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& prei,int in_begin,int in_end) {if(in_begin > in_end) return nullptr;TreeNode* root = new TreeNode(preorder[prei++]);int root_size = hash[root->val];root->left = _buildTree(preorder,inorder,prei,in_begin,root_size-1);root->right = _buildTree(preorder,inorder,prei,root_size+1,in_end);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {for(int i = 0; i < inorder.size(); i++){hash.insert({inorder[i],i});}int i = 0;return _buildTree(preorder,inorder,i,0,inorder.size()-1);}
};

class Solution {
public:double Pow(double x,long long n){if(n == 0) return 1.0;double y = Pow(x,n / 2);//快速幂算法//如果n为偶数就是返回的结果的平方，否则就是返回的结果多乘xreturn n % 2 == 0? y * y : y * y * x;}double myPow(double x, int n) {if(n == 0) return 1.0;long long N = n;//防止越界return N >= 0 ? Pow(x,N) : 1 / Pow(x,-N);}
};

class Solution {
public:void quick_sort(vector<string>&str, int left, int right){if(left >= right) return;int i = left,j = right;while(i < j){//找小while(i < j && str[j] + str[left] >= str[left] + str[j]) j--;//必须先从右往左//找大while(i < j && str[i] + str[left] <= str[left] + str[i]) i++;if(i < j) swap(str[i],str[j]);}swap(str[left],str[j]);quick_sort(str,left,j - 1);quick_sort(str,j + 1,right);}string minNumber(vector<int>& nums) {vector<string>str;int len = nums.size();for(int i = 0; i < len; i++){str.push_back(to_string(nums[i]));}quick_sort(str,0,len-1);string ret;for(auto ch : str){ret += ch;}return ret;}
};

class Solution {
public:bool isStraight(vector<int>& nums) {//大小王相当于赖子，只要最大值和最小值的差小于5肯定是顺子int maxi = 0, mini = 14;unordered_map<int,int>hash;for(int i = 0; i < 5; i++){if(nums[i] == 0) continue;//遇到大小王跳过maxi = ::max(nums[i],maxi);mini = ::min(nums[i],mini);if(hash.count(nums[i]))//如果重复则不是顺子{return false;}hash.insert({nums[i],i});}if(maxi - mini < 5) return true;return false;}
};

class Solution {
public:vector<int> getLeastNumbers(vector<int>& arr, int k) {vector<int>ret;priority_queue<int,vector<int>,greater<int>>q;for(auto ch : arr){q.push(ch);}while(k--){int top = q.top();q.pop();ret.push_back(top);}return ret;}
};

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int>st;for(auto& ch : tokens){if(ch == "+" || ch == "-" || ch == "*" || ch == "/"){int right = st.top();st.pop();int left = st.top();st.pop();char str = ch[0];int num;switch(str){case '+':num = left + right;st.push(num);break;case '-':num = left - right;st.push(num);break;case '*':num = left * right;st.push(num);break;case '/':num = left / right;st.push(num);break;}}else{st.push(stoi(ch));}}return st.top();}
};

class Solution {
public:int fib(int n) {long long * dp = new long long [110];dp[0] = 0;dp[1] = 1;for(int i = 2; i <= n; i++){dp[i] = (dp[i - 1] + dp[i - 2])%(1000000007);}return(int)dp[n];}
};

class Solution {
public:int numWays(int n) {long long * dp = new long long [110];dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i++){dp[i] = (dp[i - 1] + dp[i - 2])%(1000000007);}return(int)dp[n];}
};

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();int mini = 0x3f3f3f3f;//买股票的最小值int maxi = 0;//卖股票的最大值for(auto price : prices){maxi = max(maxi,price - mini);mini = min(mini,price);}return maxi;}
};

class Solution {
public:int maxSubArray(vector<int>& nums) {vector<int>dp(nums.size(),0);dp[0] = nums[0];for(int i = 1; i < nums.size(); i++){dp[i] = max(dp[i - 1] + nums[i],nums[i]);}int maxi = -0x3f3f3f3f;for(int i = 0; i < nums.size(); i++){maxi = max(dp[i],maxi);}return maxi;}
};

class Solution {
public:int maxValue(vector<vector<int>>& grid) {//动态规划int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(m, vector<int>(n));for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(i > 0)//只有大于0，才有向上走的那一步{dp[i][j] = max(dp[i][j],dp[i-1][j]);}if(j > 0)//只有大于0，才有向左走的那一步{dp[i][j] = max(dp[i][j],dp[i][j -1]);}dp[i][j] += grid[i][j];//确定了当前位置的上一步后就可以加当前的价值了}}return dp[m - 1][n - 1];}
};

class Solution {
public:int translateNum(int num) {string str = to_string(num);int len = str.size();vector<int>dp(len+1,0);//类似青蛙跳台阶问题，青蛙可以一直跳一个台阶，跳两个台阶要分情况dp[0] = 1;dp[1] = 1;for(int i = 2; i <= len; i++){string sub = str.substr(i - 2,2);//从第几位开始取多少位字符串if(sub <= "25" && sub >= "10"){dp[i] = dp[i - 1] + dp[i - 2];}else{dp[i] = dp[i - 1];}}return dp[len];}
};

class Sum
{
public:Sum(){_sum += _i;_i++;}static int get(){return _sum;}void Destroy(){_sum = 0;_i = 1;}
private:static int _i;static int _sum;
};
int Sum::_sum = 0;
int Sum::_i = 1;
int func(int n)
{Sum *s = new Sum[n];int ret = s->get();s->Destroy();//因为leetcode是全部测试用例用完才销毁，要重置，并且不能用析构return ret;
}
class Solution {
public:int sumNums(int n) {return func(n);}
};

class Solution {
public:int lengthOfLongestSubstring(string s) {int len = s.size();if(len == 0) return 0;if(len == 1) return 1;vector<int>dp(len,0);dp[0] = 1;int maxlen = 0;int tmp = 0;for(int i = 1; i < len; i++){int j = i - 1;while(j >= 0 && s[i] != s[j]) j--;if(dp[i-1] < i - j) dp[i] = dp[i-1] + 1;//第j个字符不在dp[i-1]的区间之内else dp[i] = i - j;//第j个字符在dp[i-1]的区间之内if(dp[i] > maxlen) maxlen = dp[i];}return maxlen;}
};

class Solution {
public:int nthUglyNumber(int n) {priority_queue<double,vector<double>,greater<double>>q;double ans = 1;for(int i = 1; i < n; i++){q.push(ans*2);q.push(ans*3);q.push(ans*5);ans = q.top();q.pop();while(!q.empty() && q.top() == ans) q.pop();}return ans;}
};

class Solution {
public:int hammingWeight(uint32_t n) {int count = 0;while(n){n = n & (n - 1);count++;}return count;}
};

class Solution {
public:int add(int a, int b) {while (b != 0) {unsigned int carry = (unsigned int)(a & b) << 1;a = a ^ b;b = carry;}return a;}
};

class Solution {
public:vector<int> GetNum(vector<int>&nums, int sz){vector<int>ret;int k = 0;for(int i = 0; i < 31; i++){if((sz >> i) & 1 == 1) {k = i;break;}}int a = 0, b = 0;for(int i = 0; i < nums.size(); i++){if(((nums[i] >> k) & 1) == 0){a ^= nums[i];}else{b ^= nums[i];}}ret.push_back(a);ret.push_back(b);return ret;}vector<int> singleNumbers(vector<int>& nums) {vector<int>ret;int sz = 0;for(int i = 0; i < nums.size(); i++){sz ^= nums[i];}return GetNum(nums,sz);}
};