LeetCode-895. 最大频率栈以及HashMap的存值取值操作
admin
2024-03-04 17:12:06
0次

LeetCode-895. 最大频率栈

  • 题目描述
  • 解题思路
  • 代码
  • 思考和普及

题目描述

设计一个类似堆栈的数据结构,将元素推入堆栈,并从堆栈中弹出出现频率最高的元素。
实现 FreqStack 类:
FreqStack() 构造一个空的堆栈。
void push(int val) 将一个整数val压入栈顶。
int pop() 删除并返回堆栈中出现频率最高的元素。
如果出现频率最高的元素不只一个,则移除并返回最接近栈顶的元素。

解题思路

实现使用一个变量maxFreq更新每次操作的最大频次

使用哈希表和栈,建立一个存储val和其对应出现频次的哈希表,在建立一个频次key和当前频次出现有哪些元素value使用栈对出现的频次的元素保存的哈希表

代码

class FreqStack {// key是val,value是val对应的频次private Map freq;// key 存储频次,value是val入队的队列private Map> group;private int maxFreq;public FreqStack() {freq = new HashMap();group = new HashMap>();maxFreq = 0;}public void push(int val) {// freq.get(val) 记录的是val的频率freq.put(val,freq.getOrDefault(val,0)+1);// group.get(频次) 记录的是 频次对应出现的元素,putIfAbsent是key为空就group.putIfAbsent(freq.get(val), new ArrayDeque());group.get(freq.get(val)).push(val);// maxFreq 标记每次最大的频次maxFreq = Math.max(maxFreq,freq.get(val));}public int pop() {int val = group.get(maxFreq).pop();freq.put(val,freq.get(val)-1);// 最大频次的队列不为空,最大频率就始终是keyif (group.get(maxFreq).isEmpty()) {maxFreq--;}return val;}
}

思考和普及

HashMap类是java.util包下,HashMap的类继承了抽象Map的抽象类,实现Map接口,可以克隆复制的接口,序列化接口

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

HashMap 的 putIfAbsent(),方法会先判断指定的键 key 是否存在,不存在则将键值对插入到 HashMap 中。如果所指定的 key 不在 HashMap 中存在,则返回 null

注意,如果指定 key 之前已经和一个 null 值相关联了 ,则该方法也返回 null,因为 HashMap 的key允许有且仅有一个为 null

    public V getOrDefault(Object key, V defaultValue) {Node e;return (e = this.getNode(hash(key), key)) == null ? defaultValue : e.value;}public V putIfAbsent(K key, V value) {return this.putVal(hash(key), key, value, true, true);}

HashMap的哈希函数的实现,

    static final int hash(Object key) {int h;return key == null ? 0 : (h = key.hashCode()) ^ h >>> 16;}

HashMap的put方法

首次扩容,判断数组是否为空,如果数组为空,则进行第一次扩容

在自定义数组容量公式是 容量大小 = 需要的空间 / 0.75 + 1

第二步,计算索引,通过上面的哈希函数,计算键值对在数组中的索引

第三步,插入元素,如果当前位置元素为null,直接插入;如果当前位置元素不为null,并且key已经存在,则直接覆盖掉value;如果当前位置元素不为null,并且key不存在,就将数据链接到链表的末尾;若链表的长度达到8,链表就转化为红黑树,并且将数据插入到树中

第四步,再次扩容,如果数组元素的个数大于threshold,就再次进行扩容

    private static final long serialVersionUID = 362498820763181265L;static final int DEFAULT_INITIAL_CAPACITY = 16;static final int MAXIMUM_CAPACITY = 1073741824;static final float DEFAULT_LOAD_FACTOR = 0.75F;static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;static final int MIN_TREEIFY_CAPACITY = 64;transient Node[] table;transient Set> entrySet;transient int size;transient int modCount;int threshold;final float loadFactor;

HashMap的put方法,调用了putVal方法

    public V put(K key, V value) {return this.putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node[] tab;int n;if ((tab = this.table) == null || (n = tab.length) == 0) {n = (tab = this.resize()).length;}Object p;int i;if ((p = tab[i = n - 1 & hash]) == null) {tab[i] = this.newNode(hash, key, value, (Node)null);} else {Object e;Object k;if (((Node)p).hash == hash && ((k = ((Node)p).key) == key || key != null && key.equals(k))) {e = p;} else if (p instanceof TreeNode) {e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);} else {int binCount = 0;while(true) {if ((e = ((Node)p).next) == null) {((Node)p).next = this.newNode(hash, key, value, (Node)null);if (binCount >= 7) {this.treeifyBin(tab, hash);}break;}if (((Node)e).hash == hash && ((k = ((Node)e).key) == key || key != null && key.equals(k))) {break;}p = e;++binCount;}}if (e != null) {V oldValue = ((Node)e).value;if (!onlyIfAbsent || oldValue == null) {((Node)e).value = value;}this.afterNodeAccess((Node)e);return oldValue;}}++this.modCount;if (++this.size > this.threshold) {this.resize();}this.afterNodeInsertion(evict);return null;}

HashMap的get操作,根据传入的key查询到哈希函数操作之后的节点,判断这个节点是否为null,为空返回null,不为空返回节点值

    public V get(Object key) {Node e;return (e = this.getNode(hash(key), key)) == null ? null : e.value;}final Node getNode(int hash, Object key) {Node[] tab;Node first;int n;if ((tab = this.table) != null && (n = tab.length) > 0 && (first = tab[n - 1 & hash]) != null) {Object k;if (first.hash == hash && ((k = first.key) == key || key != null && key.equals(k))) {return first;}Node e;if ((e = first.next) != null) {if (first instanceof TreeNode) {return ((TreeNode)first).getTreeNode(hash, key);}do {if (e.hash == hash && ((k = e.key) == key || key != null && key.equals(k))) {return e;}} while((e = e.next) != null);}}return null;}

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...