Problem
实现 FreqStack
,模拟类似栈的数据结构的操作的一个类。
FreqStack
有两个函数:
-
push(int x)
,将整数x
推入栈中。 -
pop()
,它移除并返回栈中出现最频繁的元素。- 如果最频繁的元素不只一个,则移除并返回最接近栈顶的元素。
示例:
输入:
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出:[null,null,null,null,null,null,null,5,7,5,4]
解释:
执行六次 .push 操作后,栈自底向上为 [5,7,5,7,4,5]。然后:
pop() -> 返回 5,因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。
pop() -> 返回 7,因为 5 和 7 都是频率最高的,但 7 最接近栈顶。
栈变成 [5,7,5,4]。
pop() -> 返回 5 。
栈变成 [5,7,4]。
pop() -> 返回 4 。
栈变成 [5,7]。
Solution
这道题目我使用了两个哈希表:
Freq
用来统计数字出现的次数: integer
->unsigned
FreqStack
用来统计出现次数所对应的栈:unsigned
->stack<int>
主要的解法是为每次出现第几次的元素建一个栈,比如
1,3,4,5,1,1,
那么1,3,4,5
就会在FreqStack[1]
上因为他们的出现次数为1
而第二次出现的1
就会压入FreqStack[2]
,第三次出现的1
会出现在FreqStack[3]
,以此类推。
在Freq
哈希表的辅助下,判断出现次数会相当容易。AC代码如下
class FreqStack {
public:
void push(int x) {
Freq[x]++;
maxfreq = max(Freq[x], maxfreq);
FreqStack[Freq[x]].push(x);
}
int pop() {
int x = FreqStack[maxfreq].top();
FreqStack[maxfreq].pop();
if(FreqStack[Freq[x]].empty())
maxfreq--;
Freq[x]--;
return x;
}
private:
unordered_map<int, unsigned> Freq;
unordered_map<unsigned, stack<int>> FreqStack;
unsigned maxfreq = 0;
};
[Leetcode]895.最大频率栈的更多相关文章
-
[LeetCode] 895. Maximum Frequency Stack 最大频率栈
Implement FreqStack, a class which simulates the operation of a stack-like data structure. FreqStack ...
-
leetcode Maximal Rectangle 单调栈
作者:jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4052721.html 题目链接:leetcode Maximal Rectangle 单调栈 ...
-
LeetCode 155:最小栈 Min Stack
LeetCode 155:最小栈 Min Stack 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈. push(x) -- 将元素 x 推入栈中. pop() -- ...
-
[LeetCode] Min Stack 最小栈
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. pu ...
-
[LeetCode] Max Stack 最大栈
Design a max stack that supports push, pop, top, peekMax and popMax. push(x) -- Push element x onto ...
-
[Swift]LeetCode895. 最大频率栈 | Maximum Frequency Stack
Implement FreqStack, a class which simulates the operation of a stack-like data structure. FreqStack ...
-
最大频率栈 Maximum Frequency Stack
2018-10-06 22:01:11 问题描述: 问题求解: 为每个频率创建一个栈即可. class FreqStack { Map<Integer, Integer> map; Lis ...
-
LeetCode刷题总结-栈、链表、堆和队列篇
本文介绍LeetCode上有关栈.链表.堆和队列相关的算法题的考点,推荐刷题20道.具体考点分类如下图: 一.栈 1.数学问题 题号:85. 最大矩形,难度困难 题号:224. 基本计算器,难度困难 ...
-
LeetCode 895. Maximum Frequency Stack
题目链接:https://leetcode.com/problems/maximum-frequency-stack/ 题意:实现一种数据结构FreqStack,FreqStack需要实现两个功能: ...
随机推荐
-
placehoder不兼容ie9以下和opero12以下
颜色设置 解决方案一: ::-webkit-input-placeholder { /* WebKit browsers */ color:#999; } :-moz-placeholder { /* ...
-
【读书笔记】iOS网络-使用Game Kit实现设备间通信
Apple的Game Kit框架可以实现没有网络状况下的设备与设备之间的通信,这包括没有蜂窝服务,无法访问Wi-Fi基础设施以及无法访问局域网或Internet等情况.比如在丛林深处,高速公路上或是建 ...
-
【翻译自nikic大神】PHP中原生类型的方法
引言 第一次,翻译别人的文章,用四级英语的水平来翻译~~囧,可能有很多不太恰当的地方,尽管拍砖(有些地方实在想不到恰当的翻译,我同时贴出了原文和自己很low的翻译). 翻译这篇文章用了我3个晚上一个中 ...
-
redis 优化
系统优化echo "vm.overcommit_memory=1" > /etc/sysctl.conf 0, 表示内核将检查是否有足够的可用内存供应用进程使用:如果有足够的 ...
-
Mac中安装maven3.2.1
Mac中安装maven3.2.1 原文链接:http://blog.csdn.net/f_zongjian/article/details/24144803 本机OS X:10.9,未安装XCode, ...
-
无法更新 EntitySet“GuigeInfo”,因为它有一个 DefiningQuery,而 <;ModificationFunctionMapping>; 元素中没有支持当前操作的 <;InsertFunction>; 元素。
1:实体中必须有主键 2:删除创建的模型重新创建
-
Linux 操作命令列表记录
Linux 操作命令列表记录 SSH登录 登录 ## 范式 ssh [username]@[host] ## 例 ssh -p 1222 root@10.0.0.1 使用非默认端口(ssh默认端口22 ...
-
intellij-项目目录隐藏无用的文件和文件夹
File-->Editor-->File Types
-
微信硬件平台(八) 3 ESP8266向微信服务器请求设备绑定的用户
https://api.weixin.qq.com/device/get_openid?access_token=自己申请微信token&device_type=gh_e93c1b3098b9 ...
-
mongodb 配置文件
本文档是在mongodb为3.4下编写的,仅作为参考,详细内容请参考:https://docs.mongodb.com/manual/reference/configuration-options/# ...