文档章节

[Leetcode]895.最大频率栈

o
 osc_y8yehimr
发布于 2019/03/20 18:06
字数 397
阅读 12
收藏 0

精选30+云产品,助力企业轻松上云!>>>

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;
};
下一篇: mysql mha
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
[LeetCode] 895. Maximum Frequency Stack 最大频率栈

<br>Implement , a class which simulates the operation of a stack-like data structure. has two functions: , which pushes an integer onto the stack. , which removes and returns th......

osc_qhb83isy
2019/06/07
2
0
leetcode难题

4 寻找两个有序数组的中位数 35.9% 困难 10 正则表达式匹配 24.6% 困难 23 合并K个排序链表 47.4% 困难 25 K 个一组翻转链表 54.1% 困难 30 串联所有单词的子串 27.7% 困难 32 最长有效括号 ...

osc_btnnkvs0
2019/09/01
4
0
LinkedIn TAG

1 [leetcode]243. Shortest Word Distance最短单词距离 Two Pointers 2 [leetcode]244. Shortest Word Distance II最短单词距离(允许连环call) HashMap+Merge Sort 3 [leetcode]245. Shortes......

osc_gwn06u61
2019/04/25
2
0
LeetCode 84. 柱状图中最大的矩形(单调递增栈)

文章目录 1. 题目 2. 解题 1. 题目 题目链接 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 以上是...

Michael阿明
05/31
0
0
LeetCode 84. 柱状图中最大的矩形

我的LeetCode:https://leetcode-cn.com/u/ituring/ 我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 84. 柱状图中最大的矩形 题目 给定 n 个非负整数,用......

图灵的图,图灵的灵。
04/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

图解ARP协议(二)ARP***原理与实践

一、ARP***概述 在上篇文章里,我给大家普及了ARP协议的基本原理,包括ARP请求应答、数据包结构以及协议分层标准,今天我们继续讨论大家最感兴趣的话题:ARP***原理是什么?通过ARP***可以做...

osc_91g5cdgs
20分钟前
0
0
shell进度条实现

#!/bin/bashb=''i=0while [ $i -le  100 ]do    printf "progress:[%-50s]%d%%\r" $b $i    sleep 0.1    i=`expr 2 + $i`            b=#$b......

osc_npw5uz1o
22分钟前
13
0
通过ssh实现登录服务器脚本

版本v1 #!/bin/bash########################author: Bovin########################show all host infos of serverList.txtif [[ -f $HOME/.serverList.txt ]]then  hos......

osc_lt2jwwhb
24分钟前
8
0
VMware Fusion下Centos联网

1.VMware Fusion设置选择“网络适配器” 2.“连接我的网络适配器”选择“与我的mac共享” 3.编辑centos的ip配置文件 [root@Centos ~]# more /etc/sysconfig/network-scripts/ifcfg-eth0D...

osc_pg5rp78i
25分钟前
6
0
Kickstart配置文件参数详解

kickstart是什么? KickStart是一种无人值守的安装方法。它的工作原理时在安装过程中记录典型的需要人工干预填写的各种参数,并生成一个名为ks.cfg的文件。如果在安装过程中(不只局限于生成K...

osc_r9yyhhqz
25分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部