当前位置：网站首页>刷题《剑指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;
}
};
边栏推荐
猜你喜欢
3 million tenders!Qingdao Medical Security Bureau host database middleware operation and maintenance service project
模式识别 学习笔记：第七章 特征选择
一起学习集合框架之 TreeSet
四、哈希表
ets声明式ui开发，怎么获取当前系统时间
微服务负载均衡器Ribbon实战
Apple developer account application process full version
以技术御风险，护航云原生 | 同创永益 X 博云举办产品联合发布会
(kali - elevated privileges 】 【 4.2.4) social engineering toolkit: remote control trojans use, set up and use
Dubins curve study notes and related thinking
随机推荐
3D激光SLAM：LIO-SAM整体介绍与安装编译
模式识别 学习笔记：第八章 特征提取
TCP通信
在.net core中，利用C＃实现fastdfs多文件批量上传
分布式系统设计策略
软件测试之测试代表用户
"Weekly Translate Go" This time we have something different!-- "How to Code in Go" series launched
一条SQL在MySQL中是如何执行的
部署spark2.2集群(standalone模式)
模式识别 学习笔记：第六章 其他分类方法 (持续更新中。。。)
学习笔记：CS520 Knowledge Graphs
使用文档数据库的目的是什么呢？
5S软件就是将软件应用全维度简单化的软件系统
列存储数据库是什么呢？
有哪些典型的列存储数据库呢？
Leetcode 105. 从前序与中序遍历序列构造二叉树
Optional common method analysis
模式识别 学习笔记：第七章 特征选择
Thoroughly understand the differences and application scenarios of session, cookie, sessionStorage, and localStorage (interview orientation)
七、图结构