和你一起轻松愉快的刷题

剑指 Offer 06. 从尾到头打印链表

递归思想打印元素

        使用数组保存链表中从前到后的元素，reverse数组或者直接返回一个逆序的数组。

        reverse(arr.begin(), arr.end()); // 反转数组中的元素

        arr.rbegin() <==> arr.end()

        arr.rend() <==> arr.begin()

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {    
public:vector reversePrint(ListNode* head) {if(!head){return vector();}vector result;while(head){result.push_back(head->val);head = head->next;}reverse(result.begin(), result.end());return result;// return vector(result.rbegin(), result.rend());}
};

剑指 Offer 07. 重建二叉树

前序遍历 + 中序遍历 => 后序遍历

        前序遍历的形式总是:
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
        中序遍历的形式总是:
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

        利用递归的方法建立二叉树，利用前序遍历和中序遍历的形式特点来确定当前子树的根节点。另外用哈希表预处理中序遍历的结果加速优化，可以更快速查找数字的位置。

/*** 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 {unordered_map index;
public:TreeNode* buildTree(vector& preorder, vector& inorder) {int n = preorder.size();// 构造哈希映射，快速定位根节点在中序遍历的位置for(int i=0; i& preorder, const vector& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {// 不存在子树，返回空if(preorder_left > preorder_right){return NULL;}// 根节点在前序遍历中的位置int preorder_root = preorder_left;// 根节点在中序遍历中的位置int inorder_root = index[preorder[preorder_root]];// 建立根节点TreeNode* root = new TreeNode(preorder[preorder_root]);// 左子树的节点数量int size_left_subtree = inorder_root - inorder_left;// 递归构造左子树// 先序遍历：[左边界+1，左边界+左子树节点数目]// 中序遍历：[左边界，根节点定位-1的元素]root->left = buildTreeHelper(preorder, inorder, preorder_left+1, preorder_left+size_left_subtree, inorder_left, inorder_root-1);// 递归构造右子树// 先序遍历：[左边界+1+左子树节点数目，右边界]// 中序遍历：[左边界，根节点定位-1]root->right = buildTreeHelper(preorder, inorder, preorder_left+size_left_subtree+1, preorder_right, inorder_root+1, inorder_right);return root;}
};

剑指 Offer 09. 用两个栈实现队列

栈实现队列

        队列先进先出，栈先进后出，所以还需要另外一个栈来反转数组中的元素，实现先进先出。这个翻转过程既可以在插入时完成，也可以在取值时完成。

class CQueue {stack in, out;
public:CQueue() {}void appendTail(int value) {in.push(value);}int deleteHead() {in2out();if(!out.empty()){int x = out.top();out.pop();return x;}return -1;}void in2out(){if(out.empty()){while(!in.empty()){int x = in.top();in.pop();out.push(x);}}}
};/*** Your CQueue object will be instantiated and called as such:* CQueue* obj = new CQueue();* obj->appendTail(value);* int param_2 = obj->deleteHead();*/

剑指 Offer 10- I. 斐波那契数列

斐波那契问题

        动态规划思想，三个变量保存值。

class Solution {
public:int fib(int n) {if(n == 0)  return 0;if(n == 1)  return 1;int ans = 0;int first = 0, second = 1;for(int i=2; i<=n; ++i){ans = (first + second) % 1000000007;first = second;second = ans;}return ans;}
};

剑指 Offer 10- II. 青蛙跳台阶问题

斐波那契问题

        青蛙一次可以跳上1级台阶或2级台阶，F(n) = F(n-1) + F(n-2)。   

        动态规划思想，三个变量保存值。

class Solution {
public:int numWays(int n) {if(n == 0)  return 1;if(n == 1)  return 1;int ans = 0;int first = 1, second = 1;for(int i=2; i<=n; ++i){ans = (first + second) % 1000000007;first = second;second = ans;}return ans;}
};

剑指 Offer 11. 旋转数组的最小数字

旋转数组

        二分法，即使数组被旋转过，仍然可以利用这个数组的递增性，使用二分查找。

        左排序数组任一元素 >= 右排序数组任一元素，旋转点就是右排序数组的第1个元素。

        当 nums[mid] > nums[r] 时： mid 一定在 左排序数组 中，即旋转点 x 一定在 [mid + 1, r] 闭区间内，因此执行 l = mid + 1；
        当 nums[mid] < nums[r] 时： mid 一定在 右排序数组 中，即旋转点 x 一定在[l, mid] 闭区间内，因此执行 r = mid；
        当 nums[mid] = nums[r] 时： 无法判断 mid 在哪个排序数组中，即无法判断旋转点 x 在 [l,mid] 还是 [mid + 1, r] 区间中。解决方案：--r，缩小判断范围，继续二分。

---

        为什么不用 nums[mid]和 nums[l] 作比较？

        二分目的是判断 mid 在哪个排序数组中，从而缩小区间。而在 nums[mid] > nums[l] 情况下，无法判断 mid 在哪个排序数组中。本质上是由于 r 初始值肯定在右排序数组中； l 初始值无法确定在哪个排序数组中。

        示例，当 l = 0, r = 4, mid = 2 时，有 nums[mid] > nums[l] ，而结果不同。
        [1, 2, 3, 4 ,5] 旋转点 x = 0 ： mid 在右排序数组；
        [3, 4, 5, 1 ,2] 旋转点 x = 3 ： mid 在左排序数组。

class Solution {
public:int minArray(vector& numbers) {int l = 0, r = numbers.size() - 1;while(l < r){int mid = l + (r - l)/2;if(numbers[mid] == numbers[r]){// 无法判断--r;}else if(numbers[mid] < numbers[r]){// 向左部分二分r = mid;}else{// 向右部分二分l = mid + 1;}}return numbers[l];}
};

剑指 Offer 12. 矩阵中的路径

矩阵搜索问题

        DFS + 回溯 + 剪枝

class Solution {
public:bool exist(vector>& board, string word) {int m = board.size(), n = board[0].size();for(int i=0; i>& board, string word, int x, int y, int k){int m = board.size(), n = board[0].size();if(x < 0 || x >= m || y < 0 || y >= n || board[x][y] != word[k]){return false;}if(k == word.size() - 1){return true;}board[x][y] = '.'; // 标记该位置已走过bool res = false;for(int i=0; i<4; ++i){int nx = x + dx[i];int ny = y + dy[i];if(dfs(board, word, nx, ny, k+1)){return true;}}board[x][y] = word[k]; // 回溯return false;}
};

剑指 Offer 14- I. 剪绳子

整数拆分

        1、数学推导

• 4 ： 2*2
• 5 ： 2*3
• 6 ： 3*3
• 7 ： 2*2*3 或 4*3
• 8 ： 2*3*3
• 9 ： 3*3*3
• 10：2*2*3*3 或 4*3*3
• 11：2*3*3*3
• 12：3*3*3*3
• 13：2*2*3*3*3 或 4*3*3*3

        k[0] 到 k[m] 只可能是 2 或者 3，当然也可能有 4，但是 4 = 2*2，也可以不考虑。5 < 2*3，6 < 3*3，比 6 更大的数字我们就更不用考虑了，肯定要继续拆分。

        2 的数量肯定小于 3 的数量，因为 2*2*2 < 3*3。

        由于题目规定 m > 1，所以 2 只能是 1，3 只能是2，这两个特殊情况直接返回就行了。

        2、动态规划

        dp[n] = max(dp[n], dp[i] * dp[n-i]);     

        j <= i/2 是因为 f(5) = f(1)*f(4)，f(5) = f(2)*f(3)，f(5) = f(3)*f(2)，f(5) = f(4)*f(1) ，故遍历一半即可，必须是小于等于。

// 数论
class Solution {
public:int cuttingRope(int n) {if(n == 2 || n == 3){return n - 1;}int mmax = 1;while(n > 4){mmax *= 3;n -= 3;}mmax *= n;return mmax;}
};

// 动态规划
class Solution {
public:int cuttingRope(int n) {if(n == 2 || n == 3){return n - 1;}vector dp(n + 1, 0);dp[1] = 1;dp[2] = 2;dp[3] = 3;// 2、3不能再拆分了，拆了会更小for(int i=4; i<=n; ++i){for(int j=1; j<=(i/2); ++j){dp[i] = max(dp[i], dp[j] * dp[i-j]);}}return dp[n];}
};

剑指 Offer 14- II. 剪绳子 II

整数拆分

        和 I 相比，II 增大了整数 n 的范围，涉及了 “大数越界情况下的求余问题” 。

        本题只能用数学推导，不能用动态规划了，动态规划的取余之后 max 函数就不能用来比大小了，比如取余后 2000000014（0） 会小于 1000000020（13）。

        可以将保存结果的变量设置为 long 或 long long 类型，防止溢出，也可以采用快速幂。

class Solution {
public:int cuttingRope(int n) {if(n == 2 || n == 3){return n - 1;}long mmax = 1;int mod = 1000000007;while(n > 4){mmax *= 3;mmax %= mod;n -= 3;}mmax *= n;mmax %= mod;return (int)mmax;}
};

剑指 Offer 15. 二进制中1的个数

二进制处理

        1、bitset 类库

        bitset<位数> foo; // 无参构造，默认每一位为0

        bitset<位数> foo(二进制数); // 构造函数，前面用0补充

        foo.count(); //返回1的个数 

        foo.size(); //返回位数 

        2、取余，%

        利用 % 来判断最后一位是不是2，也就是二进制中的1。

        3、位运算，&1

        每次 &1，如果最后一位是1，则计数+1，n 右移1位。

        4、位运算，n & (n - 1)

        把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0，那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

class Solution {
public:int hammingWeight(uint32_t n) {return bitset<32>(n).count();}
};

class Solution {
public:int hammingWeight(uint32_t n) {int cnt = 0;while(n != 0){cnt += n % 2;n /= 2;}return cnt;}
};

class Solution {
public:int hammingWeight(uint32_t n) {int cnt = 0;while(n != 0){if(n&1 != 0){++cnt;       }n >>= 1;}return cnt;}
};

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

剑指 Offer 16. 数值的整数次方

快速幂算法

        1、分治法

        2、倍增法（基于位运算）：标准的快速幂算法

class Solution {
public:double myPow(double x, long long  n) {return n > 0? myPowHelper(x, n): 1.0 / myPowHelper(x, -n);}double myPowHelper(double x, long long n){if(n == 0)  return 1;if(n == 1)  return x;double tmp = myPowHelper(x, n/2);if(n%2 == 0){return tmp * tmp;}else{return tmp * tmp * x;}}
};

class Solution {
public:double myPow(double x, long long n) {return n > 0? fastPow(x, n): 1.0 / fastPow(x, -n);}double fastPow(double x, long long n){double ans = 1.0;while(n){if(n & 1)ans *= x;x *= x;n >>= 1;}return ans;}
};

剑指 Offer 17. 打印从1到最大的n位数

最大 n 位数

        最大的 n 位数（记为 end ）和位数 n 的关系：

        如果 n 的数据很大的情况下，end 会溢出，无法正常存储，需要考虑大数越界问题。

class Solution {
public:vector printNumbers(int n) {vector ans;int end = pow(10, n) - 1;for(int i=1; i<=end; ++i){ans.push_back(i);}return ans;}
};

剑指 Offer 18. 删除链表的节点

链表删除节点

        1、单指针：找到要删除节点的前一个节点，注意头节点就是要删除的节点的情况。

        2、双指针：找到要删除节点和要删除节点的前一个节点和，注意头节点就是要删除的节点的情况。

        3、单指针/双指针 + 虚拟头节点：这样就不用考虑头节点就是要删除的节点的情况了。

        4、递归：找到删除的节点时返回该节点的下一个，否则返回当前节点。

        5、栈或数组等数据结构：遍历链表，将值不等于 val 的节点依次压入栈中；再将链表的节点重新连接。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {if(head->val == val){return head->next;}ListNode *pre = head;while((pre->next != NULL) && (pre->next->val != val)){pre = pre->next;}if(pre->next != NULL){pre->next = pre->next->next;}return head;}
};

class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {if(head->val == val){return head->next;}ListNode *pre = head;ListNode *cur = head;while((cur != NULL) && (cur->val != val)){pre = cur;cur = cur->next;}if(cur != NULL){pre->next = cur->next;}return head;}
};

class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {ListNode *dummy = new ListNode(0, head);ListNode *pre = dummy;while((pre->next != NULL) && (pre->next->val != val)){pre = pre->next;}if(pre->next != NULL){pre->next = pre->next->next;}return dummy->next;}
};

class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {if(head == NULL){return head;}head->next = deleteNode(head->next, val);return head->val == val? head->next: head; }
};

剑指 Offer 19. 正则表达式匹配

字符串编辑

        动态规划

        二维数组 dp[i][j] 表示：s[0] ~ s[i - 1] 和 p[0] ~ p [j - 1]是否匹配。根据字符、星号，点号，分情况讨论来更新 dp 数组。

class Solution {
public:bool isMatch(string s, string p) {int m = s.size(), n = p.size();vector> dp(m + 1, vector(n + 1, false));// 初始化 空串情况dp[0][0] = true;// 初始化第一行，如果有*，考虑匹配结果for(int j=1; j

class Solution {
public:bool isNumber(string s) {if(s.size() == 0){return false;}int index = 0;// 空格遍历下一个while(s[index] == ' '){++index;}bool numeric = scanInteger(s, index);// 判断小数部分：.123 或 123. 或 123.456if(s[index] == '.'){++index;numeric = scanUnsignedInteger(s, index) || numeric;// 注意不能是 numeric = numeric || scanUnsignedInteger(s, index);// 因为如果 numeric == true，就不会扫描.后面的部分，也就不会改变index的值了}// 判断指数部分：1e5 或 1e+5if(s[index] == 'e' || s[index] == 'E'){++index;numeric = scanInteger(s, index) && numeric;}// 空格遍历下一个while(s[index] == ' '){++index;}return numeric && index == s.size();}// 判断是否是整数：[+|-]Abool scanInteger(const string s, int& index){   if(s[index] == '+' || s[index] == '-'){++index;}return scanUnsignedInteger(s, index);}// 判断是否是无符号整数：Abool scanUnsignedInteger(const string s, int& index){int temp = index;while(index != s.size() && s[index] >= '0' && s[index] <= '9'){++index;}return index > temp;}
};

class Solution {
public:vector exchange(vector& nums) {vector ans;for(auto num: nums){if(num % 2 != 0){ans.push_back(num);}}for(auto num: nums){if(num % 2 == 0){ans.push_back(num);}}return ans;}
};

class Solution {
public:vector exchange(vector& nums) {int n = nums.size();vector ans(n, 0);int i = 0, j = n - 1;for(auto num: nums){if(num % 2 != 0){ans[i++] = num;}else{ans[j--] = num;}}return ans;}
};

class Solution {
public:vector exchange(vector& nums) {int n = nums.size();int i = 0, j = n - 1;while(i < j){while(i < j && nums[i]%2 == 1){++i;}while(i < j && nums[j]%2 == 0){--j;}if(i < j){swap(nums[i], nums[j]);}}return nums;}
};

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* getKthFromEnd(ListNode* head, int k) {int cnt = 0;ListNode *node = head;while(node != NULL){++cnt;node = node->next;}cnt = cnt - k;while(cnt--){head = head->next;}return head;}
};

class Solution {
public:ListNode* getKthFromEnd(ListNode* head, int k) {ListNode *fast = head;ListNode *slow = head;while(fast != NULL && k > 0){fast = fast->next;--k;}while(fast != NULL){fast = fast->next;slow = slow->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* reverseList(ListNode* head) {ListNode *prev = NULL, *next = NULL;while(head != NULL){next = head->next;head->next = prev;prev = head;head = next;}return prev;}
};

class Solution {
public:ListNode* reverseList(ListNode* head, ListNode* prev = nullptr) {if(!head){return prev;}ListNode* next = head->next;head->next = prev;return reverseList(next, head);}   
};

/*** 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* dummy = new ListNode(0);ListNode* node = dummy;while(l1 && l2){if(l1->val > l2->val){node->next = l2;l2 = l2->next;}else{node->next = l1;l1 = l1->next;}node = node->next;}node->next = l1? l1: l2;return dummy->next;}
};

/*** 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:bool isSubStructure(TreeNode* A, TreeNode* B) {if(A == NULL || B == NULL){return false;}// 当前节点开始比较 或 左子树 或 右子树return isSubStructureHelper(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);}bool isSubStructureHelper(TreeNode* A, TreeNode* B) {if(B == NULL)   return true;if(A == NULL)   return false;// 当前节点相同继续比较左子树和右子树if(A->val == B->val){return isSubStructureHelper(A->left, B->left) && isSubStructureHelper(A->right, B->right);}else{return false;}}
};

/*** 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:TreeNode* mirrorTree(TreeNode* root) {if(root == NULL){return NULL;}swap(root->left, root->right);mirrorTree(root->left);mirrorTree(root->right);return root;}
};

class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {if(root == NULL){return NULL;}queue q;q.push(root);while(!q.empty()){TreeNode* node = q.front();q.pop();if(node){q.push(node->left);q.push(node->right);swap(node->left, node->right);}}return root;}
};

class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {if(root == NULL){return NULL;}stack s;s.push(root);while(!s.empty()){TreeNode* node = s.top();s.pop();if(node){s.push(node->left);s.push(node->right);swap(node->left, node->right);}}return root;}
};

/*** 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:bool isSymmetric(TreeNode* root) {if(root == NULL){return true;}return isSymmetricHelper(root->left, root->right);}bool isSymmetricHelper(TreeNode* l, TreeNode* r) {if(l == NULL && r == NULL){return true;}if(l == NULL || r == NULL || l->val != r->val){return false;}return isSymmetricHelper(l->left, r->right) && isSymmetricHelper(l->right, r->left);}
};

class Solution {
public:bool isSymmetric(TreeNode* root) {if(root == NULL){return true;}return isSymmetricHelper(root->left, root->right);}bool isSymmetricHelper(TreeNode* l, TreeNode* r) {queue q;q.push(l); q.push(r);while(!q.empty()){TreeNode* node1 = q.front(); q.pop();TreeNode* node2 = q.front(); q.pop();if(node1 == NULL && node2 == NULL){continue;}if(node1 == NULL || node2 == NULL){return false;}if(node1->val != node2->val){return false;}q.push(node1->left);  q.push(node2->right);q.push(node1->right); q.push(node2->left);}return true;}
};

class Solution {
public:vector spiralOrder(vector>& matrix) {if(matrix.size() == 0){return vector();}int m = matrix.size(), n = matrix[0].size();vector ans;int left = 0, right = n - 1;int top = 0, bottom = m - 1;while(left <= right && top <= bottom){// 向右for(int j=left; j<=right; ++j){ans.push_back(matrix[top][j]);}if(++top > bottom)  break;// 向下for(int i=top; i<=bottom; ++i){ans.push_back(matrix[i][right]);}// 向左if(--right < left)  break;for(int j=right; j>=left; --j){ans.push_back(matrix[bottom][j]);}// 向上if(--bottom < top)  break;for(int i=bottom; i>=top; --i){ans.push_back(matrix[i][left]);}if(++left > right)  break;}return ans;}
};

class MinStack {
public:/** initialize your data structure here. */stack s, min_s;MinStack() {//min_s.push(INT_MAX);}void push(int x) {s.push(x);if(min_s.empty() || min_s.top() >= x){min_s.push(x);}}void pop() {if(!min_s.empty() && min_s.top() == s.top()){min_s.pop();}s.pop();}int top() {return s.top();}int min() {return min_s.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 MinStack {
public:/** initialize your data structure here. */stack s;int minNum = INT_MAX;MinStack() {}void push(int x) {minNum = std::min(minNum, x);s.push(minNum);s.push(x);}void pop() {s.pop();s.pop();if(!s.empty()){int tmp = s.top();s.pop();minNum = s.top();s.push(tmp);}else{ // 注意要恢复初始值minNum = INT_MAX;}}int top() {return s.top();}int min() {return minNum;}
};

class Solution {
public:bool validateStackSequences(vector& pushed, vector& popped) {if(pushed.size() != popped.size()){return false;}if(pushed.size() == 0 && popped.size() == 0){return true;}int len = pushed.size();stack s;int popIndex = 0;for(int i=0; i

/*** 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 levelOrder(TreeNode* root) {if(root == NULL){return vector();}vector ans;queue q;q.push(root);while(!q.empty()){root = q.front();q.pop();ans.push_back(root->val);if(root->left){q.push(root->left);}if(root->right){q.push(root->right);}}return ans;}
};

/*** 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> levelOrder(TreeNode* root) {if(root == NULL){return vector>();}vector> ans;queue q;q.push(root);while(!q.empty()){int cnt = q.size();ans.push_back(vector());for(int i=0; ival);if(node->left){q.push(node->left);}if(node->right){q.push(node->right);}}}return ans;}
};

/*** 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> levelOrder(TreeNode* root) {if(root == NULL){return vector>();}vector> ans;queue q;q.push(root);bool isOrderLeft = true;while(!q.empty()){int cnt = q.size();deque levelList;for(int i=0; ival);}else{levelList.push_front(node->val);}if(node->left){q.push(node->left);}if(node->right){q.push(node->right);}}ans.emplace_back(levelList.begin(), levelList.end());isOrderLeft = !isOrderLeft;}return ans;}
};

class Solution {
public:bool verifyPostorder(vector& postorder) {if(postorder.empty() || postorder.size() == 1){return true;}return verifyPostorderHelper(postorder, 0, postorder.size()-1);}bool verifyPostorderHelper(vector& postorder, int low, int high) {if(low >= high){return true;}int start = low;while(start < high && postorder[start] < postorder[high]){++start;}for(int i=start; i

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector> res;vector path;vector> pathSum(TreeNode* root, int target) {pathSumHelper(root, target);return res;}void pathSumHelper(TreeNode* root, int tar) {if(root == nullptr){return;}path.push_back(root->val);tar -= root->val;if(tar == 0 && root->left == nullptr && root->right == nullptr){res.push_back(path);}pathSumHelper(root->left, tar);pathSumHelper(root->right, tar);path.pop_back(); // 回溯：说明当前节点不满足要求，pop掉，返回其父亲节点}
};

class Solution {
public:unordered_map cachedNode;Node* copyRandomList(Node* head) {if(head == NULL){return NULL;}if(!cachedNode.count(head)){ // 当前节点未拷贝Node* newNode = new Node(head->val);cachedNode[head] = newNode;newNode->next = copyRandomList(head->next);newNode->random = copyRandomList(head->random);}return cachedNode[head];}
};

class Solution {
public:Node* copyRandomList(Node* head) {if(head == NULL){return NULL;}// 将拷贝节点放到原节点后面，例如1->2->3变成了1->1'->2->2'->3->3'for(Node* node = head; node != NULL; node = node->next->next){Node* newNode = new Node(node->val);newNode->next = node->next;node->next = newNode;}// 处理拷贝节点的random指针for(Node* node = head; node != NULL; node = node->next->next){Node* newNode = node->next;if(node->random == NULL){newNode->random = NULL;}else{// 注意是指向拷贝节点，不是源节点的node->random，否则拆分时会出现问题newNode->random = node->random->next;}}// 拆分拷贝节点和原节点，变成1->2->3和1'->2'->3'两个链表Node* newHead = head->next;for(Node* node = head; node != NULL; node = node->next){Node* newNode = node->next;node->next = node->next->next;if(newNode->next == NULL){newNode->next = NULL;}else{newNode->next = newNode->next->next;}}return newHead;}
};

/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node() {}Node(int _val) {val = _val;left = NULL;right = NULL;}Node(int _val, Node* _left, Node* _right) {val = _val;left = _left;right = _right;}
};
*/
class Solution {
public:Node *head = NULL;Node *pre = NULL;Node* treeToDoublyList(Node* root) {if(root == NULL)    return NULL;dfs(root);// 首位连接head->left = pre;pre->right = head;return head;}void dfs(Node* cur){if(cur == NULL) return;// 左 根 右dfs(cur->left);if(pre == NULL){ // 当前节点是第一个节点head = cur;pre = cur;}else{cur->left = pre;pre->right = cur;pre = cur;}dfs(cur->right);}
};

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Codec {
public:// Encodes a tree to a single string.string serialize(TreeNode* root) {if(root == NULL){return "";}string data;queue q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();// null用#表示，元素间用空格分隔if (node) {data += to_string(node->val) + ' ';q.push(node->left);q.push(node->right);} else {data += "# ";}}// 删除最后一个空格if (!data.empty()){data.pop_back();}return data;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {if(data.empty()){return NULL;}vector nodes; // 保存节点for(int i=0; ileft = nodes[pos++];nodes[i]->right = nodes[pos++];}}return nodes[0];}
};// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

class Codec {
public:// Encodes a tree to a single string.string serialize(TreeNode* root) {if(root == NULL){return "#";}return to_string(root->val) + " " + serialize(root->left) + " " + serialize(root->right);}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {istringstream temp(data);return des(temp);}TreeNode *des(istringstream& ss){string sub;ss >> sub;if(sub == "#"){return NULL;}TreeNode* node = new TreeNode(stoi(sub));node->left = des(ss);node->right = des(ss);return node;}
};

class Solution {
public:vector permutation(string s) {vector res;sort(s.begin(), s.end());do{res.push_back(s);}while(next_permutation(s.begin(), s.end()));return res;}
};

class Solution {
public:vector res;vector permutation(string s) {dfs(s, 0, s.size()-1);return res;}set st; // set去重void dfs(string& str, int s, int t){ // 从第s个数开始到第t个结束的全排列if(s == t){ // 递归结束，产生一个全排列if(st.find(str) == st.end()){st.insert(str);res.push_back(str);}return;}for(int i=s; i<=t; ++i){swap(str[s], str[i]); // 把当前第1个数与后面所有数交换位置dfs(str, s+1, t);swap(str[s], str[i]); // 恢复，用于下一次交换}}
};

class Solution {
public:vector res;vector permutation(string s) {if(s.size() == 0){return vector();}dfs(s, 0, s.size()-1);sort(res.begin(), res.end());return res;}void dfs(string& str, int s, int t){if(s == t){res.push_back(str);return;}unordered_map vis;// set st;for(int i=s; i<=t; ++i){if(vis[str[i]] == true){continue;}// if(st.find(str[i]) != st.end()){//     continue;// }vis[str[i]] = true;// st.insert(str[i]);swap(str[s], str[i]);dfs(str, s+1, t);swap(str[s], str[i]);            }}
};

class Solution {
public:int majorityElement(vector& nums) {sort(nums.begin(), nums.end());return nums[nums.size() / 2];}
};

class Solution {
public:int majorityElement(vector& nums) {unordered_map hash;for(int i=0; i nums.size()/2){return nums[i];}}return 0;}
};

class Solution {
public:int majorityElement(vector& nums) {int votes = 0, x = 0;for(int num: nums){if(votes == 0){x = num;}votes += num == x? 1: -1;}// 验证x是否为众数int cnt = 0;for(int num: nums){if(num == x){cnt++;}}return cnt > nums.size()/2? x: 0;}
};