正文
leetcode上的一些栈、队列问题
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
20-有效的括号
思路：主要考察栈的一些基本操作，像push()（将数据压入栈顶）、top()（取栈顶的数据但不删除）、pop()（直接删除栈顶的元素）、empty()（判断栈是否为空）。这题就是先把三种括号类型的左边先入栈，然后再判断后面紧接着进入的是否是同类型匹配。
class Solution {
public:
bool isValid(string s) {
stack<char> p;
for(int i=0;i<s.size();i++){
if(s[i]=='('||s[i]=='{'||s[i]=='[')
p.push(s[i]);
else{
if(p.empty()) return false;
if(s[i]==')'&&p.top() != '(') return false;
if(s[i]=='}'&&p.top() != '{') return false;
if(s[i]==']'&&p.top() != '[') return false;
p.pop();
}
}
return p.empty();
}
};
150-逆波兰表达式
思路：逆波兰，把运算符放在两个数后面进行运算的表达式。可以想到使用栈解决时能够把遇到的数字都压入栈中，遇到符号则拿出来计算，然后再把结果压入栈中。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
if(tokens.size()==1)
return stoi(tokens[0]);
stack<int> st;
for(int i=0;i<tokens.size();i++){
if(tokens[i]!="+"&&tokens[i]!="-"&&tokens[i]!="*"&&tokens[i]!="/"){
st.push(stoi(tokens[i]));
}else{
int num1=st.top();st.pop();
int num2=st.top();st.pop();
if(tokens[i]=="+") st.push(num2+num1);
if(tokens[i]=="-") st.push(num2-num1);
if(tokens[i]=="*") st.push(num2*num1);
if(tokens[i]=="/") st.push(num2/num1);
}
}
return st.top();
}
};
71-简化路径
思路：
- 是“..”时删掉它上面紧挨着的一个路径；
- 中间是"."时直接去掉；
- 如果是空，则直接返回“/”;
- 如果是多个“/”，只保留一个；
- 路径可以看做是一个或多个"/"分隔开众多子字符串
class Solution {
public:
string simplifyPath(string path) {
vector<string> v;
int i=0;
while(i<path.size()){
while(path[i]=='/'&&i<path.size()) i++;
if(i==path.size()) break;
int start=i;
while(path[i]!='/'&&i<path.size()) i++;
int end=i-1;
string s=path.substr(start,end-start+1);
if(s==".."){
if(!v.empty()) v.pop_back();
}else if(s!="."){
v.push_back(s);
}
}
if(v.empty()) return "/";
string res;
for(int i=0;i<v.size();i++){
res +='/'+v[i];
}
return res;
}
};
126-单词接龙
思路：有点难理解。。
347-前K个高频词汇
思路：统计出现数字的频次考虑用HashMap，建立数字和其出现次数的映射，然后按照次数排序，然后按照最大堆来从大到小排序。
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> m;
priority_queue<pair<int, int>> q;
vector<int> res;
for(auto a:nums)
m[a]++;
for(auto it:m)
q.push({it.second,it.first});
for(int i=0;i<k;i++){
res.push_back(q.top().second);
q.pop();
}
return res;
}
};
23-合并K个排序链表
思路：K个链表先划分为合并K/2个链表，再不停地往下划分，直到划分成只有一个或者两个链表的任务。k通过(n+1)/2的目的是可以确保取值为奇数时能从后半段开始，当然为偶数的时候不会存在影响。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.empty())
return NULL;
int n=lists.size();
while(n>1){
int k=(n+1)/2;
for(int i=0;i<n/2;i++){
lists[i]=mergeTwolists(lists[i],lists[i+k]);
}
n=k;
}
return lists[0];
} ListNode* mergeTwolists(ListNode* l1,ListNode* l2){
ListNode* p=new ListNode(-1),*cur=p;
while(l1&&l2){
if(l1->val<l2->val){
cur->next=l1;
l1=l1->next;
}else{
cur->next=l2;
l2=l2->next;
}
cur=cur->next;
}
if(l1) cur->next=l1;
if(l2) cur->next=l2;
return p->next;
}
};
