当前位置：网站首页>刷题《剑指Offer》day12
刷题《剑指Offer》day12
2022-08-08 10:57:00 【吃豆人编程】
题目来源：力扣《剑指Offer》第二版
完成时间：2022/08/07
文章目录
30. 包含min函数的栈
题目链接：剑指 Offer 30. 包含min函数的栈 - 力扣（LeetCode）
我的题解
我的题解和书上的一样，用一个辅助栈。出栈的时候，两个栈同时出栈。入栈的时候，判断一下，如果入栈元素小于等于辅助栈栈顶元素，则直接入栈，如果大于则辅助栈的栈顶元素再入栈一次。这样可以保持辅助栈栈顶的元素最小。
class MinStack {
public:
/** initialize your data structure here. */
stack<int> min_stack;
stack<int> data_stack;
MinStack() {
}
void push(int x) {
if(min_stack.empty() || x < min_stack.top()){
min_stack.push(x);
}else {
min_stack.push(min_stack.top());
}
data_stack.push(x);
}
void pop() {
if(!data_stack.empty()){
min_stack.pop();
data_stack.pop();
}
}
int top() {
return data_stack.top();
}
int min() {
return min_stack.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(); */
31. 栈的压入、弹出序列
题目链接：剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode）
我的题解1
这道题我一开始稀里糊涂的，没考虑清楚直接就写了，然后居然也过了。思路就是先匹配入栈序列，入栈序列完事后，如果出栈序列还没完事，再检查出栈序列。
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int index_push = 0, index_pop = 0;
stack<int> stack1;
while(index_push != pushed.size()){
if(stack1.empty()){
stack1.push(pushed[index_push]);
index_push++;
}
if(stack1.top() == popped[index_pop]){
stack1.pop();
index_pop++;
}else if(index_push != pushed.size()){
stack1.push(pushed[index_push]);
index_push++;
}else {
return false;
}
}
while(index_pop != popped.size()){
if(stack1.top() == popped[index_pop]){
stack1.pop();
index_pop++;
}else {
return false;
}
}
return true;
}
};
我的题解2
后来我发现如果在第一次循环中没有清空栈的话，必定是不符合要求的。精简了一下，代码如下：
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int index_push = 0, index_pop = 0;
stack<int> stack1;
while(true){
while(!stack1.empty() && stack1.top() == popped[index_pop]){
stack1.pop();
index_pop++;
}
if(index_push != pushed.size()){
stack1.push(pushed[index_push]);
index_push++;
}else {
break;
}
}
return stack1.empty();
}
};
我的题解3
好吧。。看了评论区大佬的题解，发现还可以进一步精简
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int index = 0;
stack<int> stack1;
for(int i = 0;i < pushed.size();i++) {
stack1.push(pushed[i]);
while(!stack1.empty() && stack1.top() == popped[index]){
stack1.pop();
index++;
}
}
return stack1.empty();
}
};
leetcode 这个提交是真的迷
32 - I. 从上到下打印二叉树
题目链接：剑指 Offer 32 - I. 从上到下打印二叉树 - 力扣（LeetCode）
我的题解
模板题，队列套就完事了
/** * 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<int> levelOrder(TreeNode* root) {
vector<int> result;
if(root == nullptr) return result;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
TreeNode* tmp = que.front();
que.pop();
if(tmp->left) que.push(tmp->left);
if(tmp->right) que.push(tmp->right);
result.push_back(tmp->val);
}
return result;
}
};
32 - II. 从上到下打印二叉树 II
题目链接：剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣（LeetCode）
我的题解
这题也非常简单，直接在上题的基础上改就行了，在每次while循环中加入对当前队列元素个数的判断，即可得出某一层的节点熟练，遍历一遍即可。
/** * 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<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if(root == nullptr) return result;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
int size = que.size();
vector<int> res;
for(int i = 0;i < size;i++) {
TreeNode* tmp = que.front();
que.pop();
if(tmp->left) que.push(tmp->left);
if(tmp->right) que.push(tmp->right);
res.push_back(tmp->val);
}
result.push_back(res);
}
return result;
}
};
32 - III. 从上到下打印二叉树 III
题目链接：剑指 Offer 32 - III. 从上到下打印二叉树 III - 力扣（LeetCode）
我的题解
这题也比较简单，上一题基础上加个count计数，如果是偶数，就把元素插入到vector的头部。
/** * 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<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if(root == nullptr) return result;
int count = 1;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
int size = que.size();
vector<int> res;
for(int i = 0;i < size;i++) {
TreeNode* tmp = que.front();
que.pop();
if(tmp->left) que.push(tmp->left);
if(tmp->right) que.push(tmp->right);
if(count % 2 == 1) {
//res.push_front(tmp->val);
res.push_back(tmp->val);
}else {
res.insert(res.begin(),tmp->val);
}
}
result.push_back(res);
count++;
}
return result;
}
};
//res.push_front(tmp->val);
res.push_back(tmp->val);
}else {
res.insert(res.begin(),tmp->val);
}
}
result.push_back(res);
count++;
}
return result;
}
};
边栏推荐
猜你喜欢
【访谈】Eotalk Vol.01：Eoapi，我们希望以开源的方式构建 API 生态系统
在SAP分析云里根据业务数据绘制词云(Word Cloud)
软件测试之测试代表用户
新款“廉价”SUV曝光，安全、舒适一个不落
【kali-权限提升】（4.2.4）社会工程学工具包：远控木马使用、设置、利用
ets声明式ui开发，怎么获取当前系统时间
模式识别 学习笔记：第六章 其他分类方法 (持续更新中。。。)
Jingkai Safety Supervision App technical service support
Loadrunner12.0.2 installation and Chinese language pack installation (Chinese)
上海控安SmartRocket系列产品推介（二）：SmartRocket Modeler可视化建模开发工具
随机推荐
About the Celery service report under win Process 'Worker' exited with 'exitcode 1' [duplicate]
轻量级接口自动化框架（jmeter+ant+jenkins）
LeetCode每日一题--有序队列(整理最小表示法)
Leetcode 700. 二叉搜索树中的搜索
一文读懂配置管理（CM）
Kubernetes资源编排系列之四: CRD+Operator篇
Machine learning model too slow?Look at Intel (R) extension to accelerate
关于mysql联合索引的最左前缀原则以及b+tree
二、线性结构
NoSQL数据库有哪些优势吗？又有哪些劣势呢？
JSON Schema模式用法
键值数据库中可以对值进行查询嘛？
PWA 应用 Service Worker 缓存的一些可选策略和使用场景
Flutter实现搜索的三种方式
EZVIZ and Xiaomi compete against smart cameras
目标检测中的Classificition Loss
图数据库一般用于什么时候呢？
卫星互联网真能替代 5G？
萤石、小米对垒智能摄像头
移动适配vw/vh方法—vw/vh实例—模拟B站手机端首页—获取样式教程视频