目录
895最大频率栈
复杂度爆了
简述一下思路:
- 用栈来存入栈元素,用哈希表来存出现次数,用一个frequency来记录最大出现次数
- 遍历栈,将栈顶元素放到另一个临时栈中,如果栈顶元素的出现次数=frequency,那么说明是最大元素,我就把他出栈然后用临时栈还原stk
- 如果遍历了一遍没有相等的,复原栈,frequency--,再遍历栈
优化思路:
感觉可以直接用vector来存元素,省去了出入栈的开销
frequency也可以在遍历的时候记录一个最大的,
class FreqStack {
public:
FreqStack() {}
void push(int val) {
stk.push(val);
mymap[val]++;
if (mymap[val] > frequency) {
frequency++;
}
}
int pop() {
int ret = -1;
while (true) {
while (!stk.empty()) {
if (mymap[stk.top()] == frequency) {
ret = stk.top();
stk.pop();
break;
}
tempstk.push(stk.top());
stk.pop();
}
while(!tempstk.empty())
{
stk.push(tempstk.top());
tempstk.pop();
}
if(ret!=-1)
{
mymap[ret]--;
return ret;
}
else
{
frequency--;
}
}
while (!tempstk.empty()) {
stk.push(tempstk.top());
tempstk.pop();
}
}
private:
stack<int> stk;
stack<int> tempstk;
unordered_map<int, int> mymap;
int frequency = 0;
};
优化版本v1
还是有点爆
感觉主要是出在vector的erase上
继续优化:
class FreqStack {
public:
FreqStack() {}
void push(int val) {
stk.push_back(val);
mymap[val]++;
if (mymap[val] > frequency)
frequency++;
}
int pop() {
int nextfrequency = 0;
// int nextret=-1;
int ret = -1;
while (ret == -1) {
for (int i = stk.size() - 1; i >= 0; i--) {
if (mymap[stk[i]] == frequency) {
ret = stk[i];
mymap[ret]--;
stk.erase(stk.begin() + i);
break;
} else {
if (mymap[stk[i]] > nextfrequency) {
nextfrequency = mymap[stk[i]];
}
}
}
if(ret==-1)
frequency=nextfrequency;
}
return ret;
}
private:
unordered_map<int, int> mymap;
vector<int> stk;
int frequency = 0;
};
优化版本v2
这个版本将erase变成=-1,在数据中不去检测为-1的数据,但是没有什么用
还是一样的复杂度
看题解了
我靠还有这种解法
自己写一下
class FreqStack {
public:
FreqStack() {}
void push(int val) {
if (++mymap[val] > stkarr.size())
stkarr.push_back(stack<int>());
stkarr[mymap[val] - 1].push(val);
}
int pop() {
int ret=stkarr.back().top();
stkarr.back().pop();
mymap[ret]--;
if(stkarr.back().empty())
{
stkarr.pop_back();
}
return ret;
}
private:
vector<stack<int>> stkarr;
unordered_map<int, int> mymap;
};
884
哈希表的简单使用,非常简单,但是处理字符串比较繁琐
class Solution {
public:
vector<string> uncommonFromSentences(string s1, string s2) {
unordered_map<string,int> map1;
unordered_map<string,int> map2;
vector<string> ans;
int slowptr=0;
for(int i=0;i<s1.length();i++)
{
if(s1[i]==' ')
{
map1[s1.substr(slowptr, i-slowptr)]++;
slowptr=i+1;
}
}
map1[s1.substr(slowptr, s1.length()-slowptr)]++;
slowptr=0;
for(int i=0;i<s2.length();i++)
{
if(s2[i]==' ')
{
map2[s2.substr(slowptr, i-slowptr)]++;
slowptr=i+1;
}
}
map2[s2.substr(slowptr, s2.length()-slowptr)]++;
for(auto itr:map1)
{
if(itr.second==1&&map2.find(itr.first)==map2.end())
{
ans.push_back(itr.first);
}
}
for(auto itr:map2)
{
if(itr.second==1&&map1.find(itr.first)==map1.end())
{
ans.push_back(itr.first);
}
}
return ans;
}
};
846一手顺子
用map记录手中的牌,map中自带key值排序,再去遍历就可以了
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int groupSize) {
int n=hand.size();
if(n%groupSize!=0)
{
return false;
}
map<int,int> mymap;
for(int i=0;i<n;i++)
{
mymap[hand[i]]++;
}
int x=n/groupSize;
for(int i=0;i<x;i++)
{
int value=mymap.begin()->first;
for(int j=0;j<groupSize;j++)
{
if(mymap.find(value)==mymap.end())
{
return false;
}
mymap[value]--;
if(mymap[value]==0)
{
mymap.erase(value);
}
value++;
}
}
return true;
}
};
标签:val,int,ret,stk,frequency,哈希,mymap
From: https://www.cnblogs.com/liviayu/p/17984348