简介 栈的特点是后入先出,根据这个特点可以临时保存一些数据,之后用到依次再弹出来,常用于 DFS 深度搜索
队列一般常用于 BFS 广度搜索,类似一层一层的搜索
栈 设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。
辅助栈 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class MinStack {public : stack<int > minStack; stack<int > dataStack; MinStack () { minStack.push (INT_MAX); } void push (int x) { dataStack.push (x); minStack.push (min (minStack.top (),x)); } void pop () { minStack.pop (); dataStack.pop (); } int top () { return dataStack.top (); } int getMin () { return minStack.top (); } };
根据 逆波兰表示法 ,求表达式的值。
有效的运算符包括 +
, -
, *
, /
。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
思路:通过栈保存原来的元素,遇到表达式弹出运算,再推入结果,重复这个过程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution {public : int evalRPN (vector<string>& tokens) { if (tokens.empty ()) return 0 ; stack<int > st; for (int i=0 ;i<tokens.size ();i++) { if (tokens[i]=="+" ||tokens[i]=="-" ||tokens[i]=="*" ||tokens[i]=="/" ) { if (st.size ()<2 ) return -1 ; auto b=st.top (); st.pop (); auto a=st.top (); st.pop (); int res; switch (tokens[i][0 ]) { case '+' : res=a+b; break ; case '-' : res=a-b; break ; case '*' : res=a*b; break ; case '/' : res=a/b; break ; } st.push (res); } else { st.push (atoi (tokens[i].c_str ())); } } return st.top (); } };
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 class Solution {public : string decodeString (string s) { stack<int > nums; stack<string> strs; string res="" ; int num=0 ; for (int i=0 ;i<s.size ();i++) { char ch=s[i]; if (ch>='0' &&ch<='9' ) { num=num*10 +ch-'0' ; }else if ((ch >= 'a' && ch <= 'z' ) ||(ch >= 'A' && ch <= 'Z' )) { res+=ch; } else if (ch=='[' ) { nums.push (num); num=0 ; strs.push (res); res="" ; } else { int j=nums.top (); nums.pop (); while (j--) { strs.top ()+=res; } res=strs.top (); strs.pop (); } } return res; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution {public : vector<int > inorderTraversal (TreeNode* root) { vector<int >ans; if (root==NULL ) return ans; stack<TreeNode*> st; auto cur=root; while (cur!=NULL ||!st.empty ()) { while (cur!=NULL ) { st.push (cur); cur=cur->left; } cur=st.top (); st.pop (); ans.push_back (cur->val); cur=cur->right; } return ans; } };
给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝 (克隆)。
图中的每个节点都包含它的值 val
(int
) 和其邻居的列表(list[Node]
)。
class Node { public int val; public List<Node> neighbors; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution {public : unordered_map<Node*,Node*> mp; Node* cloneGraph (Node* node) { if (node==NULL ) return node; if (mp.count (node)) return mp[node]; const auto newnode=new Node (node->val); mp[node]=newnode; for (auto n:node->neighbors) { mp[node]->neighbors.push_back (cloneGraph (n)); } return mp[node]; } };
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : int numIslands (vector<vector<char >>& grid) { int count = 0 ; for (int i = 0 ; i < grid.size (); i++){ for (int j = 0 ; j < grid[0 ].size (); j++){ if (grid[i][j] == '1' ){ dfs (grid, i, j); count++; } } } return count; } void dfs (vector<vector<char >>& grid, int i, int j) { if (i < 0 || i >= grid.size () || j < 0 || j >= grid[0 ].size () || grid[i][j] != '1' ){ return ; } grid[i][j] = '2' ; dfs (grid, i + 1 , j); dfs (grid, i - 1 , j); dfs (grid, i, j + 1 ); dfs (grid, i, j - 1 ); } };
队列 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 class MyQueue {public : stack<int > s1,s2; int front; MyQueue () { } void push (int x) { if (s1.empty ()) front=x; s1.push (x); } int pop () { if (s2.empty ()) { while (!s1.empty ()) { s2.push (s1.top ()); s1.pop (); } } int ret =s2.top (); s2.pop (); return ret; } int peek () { if (!s2.empty ()) { return s2.top (); } return front; } bool empty () { if (s1.empty ()&&s2.empty ()) { return true ; } else { return false ; } } };
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution {public : vector<vector<int >> levelOrder (TreeNode* root) { vector<vector<int >> res; if (root==NULL ) return res; queue<TreeNode *> q; q.push (root); while (!q.empty ()) { int currentLevelSize=q.size (); vector<int > level; for (int i=0 ;i<currentLevelSize;i++) { auto cur=q.front (); level.push_back (cur->val); q.pop (); if (cur->left) q.push (cur->left); if (cur->right) q.push (cur->right); } res.push_back (level); } return res; } };