#include <vector> class Solution { public: //使用单调栈，找到离自己最近的比他大的值，单调递减栈，保留局部最大值， //因为可以循环，若按照不能循环的情况，栈中最开始没有元素，所以先让开始的时候就有前面的单调递减值 vector<int> nextBigger(vector<int>& nums) { int n = nums.size(); vector<int> res(n); stack<int> stk; for(int i=n-2; i >= 0; --i){ //初...

class Solution { public: //对于数组中的一个数，看他的左边有多少大于他的数，右边有多少大于它的数，两个值相乘，即以本值为最小值的连续子树组的个数， //要找到最近的小于它的数，使用栈，递增栈，保留的是局部最小值，只用比较局部最小值即可；数组记录全局最小值； int sumSubarr(vector<int>& nums) { const int MOD = 1e9 + 7; int n = nums.size(); stack<int> stk; vector<int> left(n); vector<int> ...

class Solution { public: //模拟压栈出栈的顺序 bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { stack<int> stk; int i=0; int n = popV.size(); for(int a:pushV){ stk.push(a); while( !stk.empty() && i<= n && stk.top() == popV[i] ){ stk.pop(); ++i; } } return (...

#include <string> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param path string字符串 * @return string字符串 */ string simplifyPath(string path) { stack<string> stk; path.push_back('/'); // '/'是处理前面累积的字符串的标志，可能有最后没有/的情况，确保最后一个部分被处理； string temp = ""; fo...

#include <stack> #include <string> class Solution { public: string removeDuplicateLetters(string str) { int n = str.size(); stack<char> stk; vector<int> last_apper(26, 0); //记录字母是否已经保留了一个； vector<int> visited(26, 0); for(int i=0; i<n; ++i){ //记录每种字母最后一次出现的位置 last_app...

#include <climits> class Solution { public: //双指针检测，一个数比左边的数的最大数小则需要往前移，比右边的最小数小则需要往后移； int findUnsortedSubarray(vector<int>& nums) { int n = nums.size(); //双指针， int Max = nums[0], Min = nums[n-1], l = -1, r=-2; for(int i=1; i<n; i++){ Max = max(Max, nums[i]); Min = min(Min , nums...

class Solution { public: /** 这道题可以用递归的方式进行模拟，模拟选取根节点的过程，每层递归处理一个根节点的情况，分左右子树再递归，返回左右子树可能的乘积； 但是可以发现，成树的多样性和数字本身大小没有关系，只与数的个数有关，所以可以记录不同节点数的树的多样性，由小至大树，即动态规划； */ static const int mod = 1000000007; int numberOfTree(int n) { vector<long long> dp(n+1); //下标表示有多少节点 dp[0] = 1; dp[1] = 1; for(int i=2...

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ #include <stack> class Solution { public: bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { if(!pRoot1 || !pRoot2)return false; stack<TreeNode*> stk...

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ #include <stack> class Solution { public: bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { if(!pRoot1 || !pRoot2)return false; stack<TreeNode*> stk...

class Solution { public: //对需要检验的后序遍历序列进行排序，检验它是否可以是排序后的序列（中序）的出栈顺序；是则true bool VerifySquenceOfBST(vector<int> sequence) { if(sequence.size() == 0)return false; stack<int> stk; vector<int> vinorder(sequence); sort(vinorder.begin(), vinorder.end()); int j=0; for(int i=0; i<vinord...

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <unordered_map> class Solution { public: unordered_map<int, int> vin; //以节点值为键，在数组的下标为值； TreeNode* reConstructBinaryTree(vec...

#include <climits> class Solution { public: //对数组进行逆序检测，会按照根节点-》右子树-》左子树 的顺序，并且以此检测是按照，根-》右子树-》右子树根-》右子树，直到遇到小于前一个数的值，即最下层的左子树， //数大于后面的数，即它是前一个数的右子树且根节点，若数小于后数，则遇到了左子树，但不知道是谁的左子树，栈维护； bool VerifySquenceOfBST(vector<int> sequence) { if(sequence.empty()){ return false; } int root = INT_MA...

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: //采用广度优先搜索，并且是从每一层的右边进行检测，遇到有节点且再次遇到空节点说明有空缺即false； bool isCompleteTree(TreeNode* root) { queue<TreeNode*> q; q.pu...

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: //递归调用，保证进入的节点非空，是叶节点则计入答案； int ans=0; int sumNumbers(TreeNode* root) { if(!root)return 0; dfs(root, 0); return ans; } v...