剑指Offer 第25天 栈的压入、弹出序列 && 打印从1到最大的n位数
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
剑指 Offer 31. 栈的压入、弹出序列
输入两个整数序列第一个序列表示栈的压入顺序请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 {1,2,3,4,5} 是某栈的压栈序列序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1
输入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示例 2
输入pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出false
解释1 不能在 2 之前弹出。初始化 辅助栈 stackstack 弹出序列的索引 ii
遍历压栈序列 各元素记为 numnum元素 numnum 入栈
循环出栈若 stackstack 的栈顶元素 == 弹出序列元素 popped[i]popped[i] 则执行出栈与 i++i++返回值 若 stackstack 为空则此弹出序列合法。
class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int> s; int inx_push = 0; int inx_pop = 0; int s1 = pushed.size(); int s2 = popped.size(); while(inx_push < s1) { s.push(pushed[inx_push]); while(inx_pop < s2 && !s.empty() && s.top()==popped[inx_pop]) { s.pop(); inx_pop++; } inx_push++; } if(s.empty()) return true; return false; } }
剑指 Offer 17. 打印从1到最大的n位数
输入数字 n按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]class Solution { public: vector<int> printNumbers(int n) { vector<int> res; int l = pow(10, n)-1; for(int i = 1; i <= l; i++) res.push_back(i); return res; } };