剑指 Offer 29. 顺时针打印矩阵
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5]
1 vector<int> spiralOrder(vector<vector<int>>& matrix) {
2 //模拟整个过程
3 //top,上边界，botton下边界，left左边界，right右边界
4 vector<int>res;
5 int n=matrix.size();
6 if(n<=0)
7 return res;
8 int m=matrix[0].size();
9 int num=n*m;
10 int top=0;
11 int bottom=n-1;
12 int left=0;
13 int right=m-1;
14 while(num)
15 {
16 //从左到右
17 for(int i=left;i<=right&num>0;++i)
18 {
19 res.push_back(matrix[top][i]);
20 num--;
21 }
22 top+=1;
23
24 //从上到下
25 for(int i=top;i<=bottom&num>0;++i)
26 {
27 res.push_back(matrix[i][right]);
28 num--;
29 }
30 right-=1;
31
32 //从右到左
33 for(int i=right;i>=left&num>0;--i)
34 {
35 res.push_back(matrix[bottom][i]);
36 num--;
37 }
38 bottom-=1;
39
40 //从下到上
41 for(int i=bottom;i>=top&num>0;--i)
42 {
43 res.push_back(matrix[i][left]);
44 num--;
45 }
46 left+=1;
47 }
48 return res;
49}
剑指 Offer 30. 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.min(); --> 返回 -3.minStack.pop();minStack.top(); --> 返回 0.minStack.min(); --> 返回 -2.
1MinStack() {
2}
3stack<int>s1;
4stack<int>s2;
5
6void push(int x) {
7 s1.push(x);
8 //每次放入s2的都是当前最小的元素
9 if(s2.empty()||s2.top()>x)
10 {
11 s2.push(x);
12 }
13 else
14 s2.push(s2.top());
15}
16
17void pop() {
18 s1.pop();
19 s2.pop();
20
21}
22
23int top() {
24 return s1.top();
25}
26
27int min() {
28 return s2.top();
29
30
31
32}
剑指 Offer 31. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输出：true解释：我们可以按以下顺序执行：push(1), push(2), push(3), push(4), pop() -> 4,push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
1 bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
2 if(popped.size()==0&&pushed.size()==0)
3 return true;
4 if(pushed.size()<=0||popped.size()<=0||pushed.size()!=popped.size())
5 return false;
6
7 //用一个栈来模拟 如果栈顶和pop一样则弹出
8 //如果最后栈为空 则说明都可以按顺序弹出
9 stack<int>s;
10 int i=0,j=0;
11 while(i<pushed.size())
12 {
13 s.push(pushed[i]);
14 while(!s.empty()&&j<popped.size()&&s.top()==popped[j])
15 {
16 s.pop();
17 ++j;
18 }
19 ++i;
20 }
21 if(s.empty())
22 return true;
23 return false;
24
25
26}
剑指 Offer 32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:给定二叉树: [3,9,20,null,null,15,7],3\9 20\15 7返回：[3,9,20,15,7]
1vector<int> levelOrder(TreeNode* root) {
2 //层次遍历
3 //使用queue
4 vector<int>res;
5 if(root==NULL)
6 return res;
7 queue<TreeNode*>q;
8
9 q.push(root);
10 while(!q.empty())
11 {
12 root=q.front();q.pop();
13 res.push_back(root->val);
14 if(root->left)
15 q.push(root->left);
16 if(root->right)
17 q.push(root->right);
18 }
19 return res;
20
21}
剑指 Offer 32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:给定二叉树: [3,9,20,null,null,15,7],3\9 20\15 7返回其层次遍历结果：[[3],[9,20],[15,7]]
1 vector<vector<int>> levelOrder(TreeNode* root) {
2 //层次遍历 但是需要每一层 放在一个vector中
3 vector<vector<int>>res;
4 if(root==NULL)
5 return res;
6 //用当前队列的大小表示每一层元素个数即可
7 queue<TreeNode*>q;
8 q.push(root);
9 while(!q.empty())
10 {
11 int sz=q.size();
12 vector<int>ans;
13 while(sz--)
14 {
15 root=q.front();q.pop();
16 ans.push_back(root->val);
17 if(root->left)
18 q.push(root->left);
19 if(root->right)
20 q.push(root->right);
21 }
22 res.push_back(ans);
23 }
24 return res;
25}
剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:给定二叉树: [3,9,20,null,null,15,7],3\9 20\15 7返回其层次遍历结果：[[3],[20,9],[15,7]]
1vector<vector<int>> levelOrder(TreeNode* root) {
2 vector<vector<int>>res;
3 if(root==NULL)
4 return res;
5
6 //两个层
7 //奇数层，下一层为偶数层，其子节点从左到右入栈，可以实现从右到左输出
8 //偶数层，下一层为奇数层，其子节点从右到左入栈，可以实现从左到右输出
9
10 int cur=0;//奇数层 s[0]存储奇数层
11 int nex=1;//偶数层 s[1]存储偶数层
12 stack<TreeNode*>s[2];
13
14 //第一层为奇数层
15 s[cur].push(root);
16 vector<int>ans;
17 while(!s[cur].empty()||!s[nex].empty())
18 {
19 root=s[cur].top();s[cur].pop();
20 ans.push_back(root->val);
21 if(cur==0)//奇数层
22 {
23 if(root->left)
24 s[nex].push(root->left);
25 if(root->right)
26 s[nex].push(root->right);
27 }
28 else
29 {
30 if(root->right)
31 s[nex].push(root->right);
32 if(root->left)
33 s[nex].push(root->left);
34 }
35 if(s[cur].empty())//当前层为空了
36 {
37 cur=1-cur;
38 nex=1-nex;//交替
39 res.push_back(ans);
40 ans.clear();
41 }
42 }
43 return res;
44}
文章转载自写点代码，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
