企业官网建设流程全解析

有关毕业设计的网站,设计方案格式模板范文,好看的电商网站模板下载,网页升级中每天自动更新什么意思最大频率栈 问题描述 实现 FreqStack 类#xff0c;模拟一个最大频率栈#xff08;频率栈#xff09;。 FreqStack 有两个方法#xff1a; push(int val)#xff1a;将整数 val 推入栈中pop()#xff1a;移除并返回栈中频率最高的元素 如果有多个元素频率相同#xff0c…最大频率栈问题描述实现FreqStack类模拟一个最大频率栈频率栈。FreqStack有两个方法push(int val)将整数val推入栈中pop()移除并返回栈中频率最高的元素如果有多个元素频率相同返回最接近栈顶的元素示例FreqStackfreqStacknewFreqStack();freqStack.push(5);// 栈为 [5]freqStack.push(7);// 栈为 [5,7]freqStack.push(5);// 栈为 [5,7,5]freqStack.push(7);// 栈为 [5,7,5,7]freqStack.push(4);// 栈为 [5,7,5,7,4]freqStack.push(5);// 栈为 [5,7,5,7,4,5]freqStack.pop();// 返回 5因为 5 的频率最高freqStack.pop();// 返回 75 和 7 频率相同(2)7 更接近栈顶freqStack.pop();// 返回 5freqStack.pop();// 返回 4算法思路多层栈 频率映射核心数据结构freq哈希表记录每个元素的当前频率group哈希表group[f]存储所有频率为f的元素栈maxFreq记录当前最大频率push 操作更新元素频率freq[val]将元素推入对应频率的栈group[freq[val]].push(val)更新最大频率maxFreq max(maxFreq, freq[val])pop 操作从group[maxFreq]弹出栈顶元素减少该元素的频率freq[val]--如果group[maxFreq]为空maxFreq--代码实现方法一多层栈importjava.util.*;classFreqStack{/** * 最大频率栈的实现 * * 核心数据结构 * - freq: 元素 - 频率 * - group: 频率 - 元素栈存储该频率的所有元素 * - maxFreq: 当前最大频率 */privateMapInteger,Integerfreq;// 元素频率映射privateMapInteger,DequeIntegergroup;// 频率分组栈privateintmaxFreq;// 当前最大频率publicFreqStack(){freqnewHashMap();groupnewHashMap();maxFreq0;}/** * 推入元素到频率栈 * * 时间复杂度: O(1) * * param val 要推入的元素 */publicvoidpush(intval){// 更新元素频率intffreq.getOrDefault(val,0)1;freq.put(val,f);// 更新最大频率maxFreqMath.max(maxFreq,f);// 将元素推入对应频率的栈group.computeIfAbsent(f,k-newArrayDeque()).push(val);}/** * 弹出频率最高且最接近栈顶的元素 * * 时间复杂度: O(1) * * return 弹出的元素 */publicintpop(){// 从最大频率栈中弹出元素intvalgroup.get(maxFreq).pop();// 减少该元素的频率freq.put(val,freq.get(val)-1);// 如果当前最大频率的栈为空减少最大频率if(group.get(maxFreq).isEmpty()){maxFreq--;}returnval;}}算法分析时间复杂度O(1)哈希表操作O(1)栈操作O(1)频率更新O(1)空间复杂度O(N)N 是推入的元素总数freq映射O(不同元素数量)group映射O(N)因为每个推入的元素都在某个频率栈中正确性频率优先总是从最大频率栈中弹出栈顶优先同一频率的元素按推入顺序存储后推入的在栈顶频率维护pop 后正确更新元素频率和最大频率算法过程操作序列: push(5), push(7), push(5), push(7), push(4), push(5) 状态变化: push(5): - freq: {5:1} - group: {1: [5]} - maxFreq: 1 push(7): - freq: {5:1, 7:1} - group: {1: [7,5]} - maxFreq: 1 push(5): - freq: {5:2, 7:1} - group: {1: [7,5], 2: [5]} - maxFreq: 2 push(7): - freq: {5:2, 7:2} - group: {1: [7,5], 2: [7,5]} - maxFreq: 2 push(4): - freq: {5:2, 7:2, 4:1} - group: {1: [4,7,5], 2: [7,5]} - maxFreq: 2 push(5): - freq: {5:3, 7:2, 4:1} - group: {1: [4,7,5], 2: [7,5], 3: [5]} - maxFreq: 3 pop() → 5: - 从group[3]弹出5 - freq: {5:2, 7:2, 4:1} - group: {1: [4,7,5], 2: [7,5], 3: []} - maxFreq: 2 (因为group[3]为空) pop() → 7: - 从group[2]弹出7 - freq: {5:2, 7:1, 4:1} - group: {1: [4,7,5], 2: [5], 3: []} - maxFreq: 2 pop() → 5: - 从group[2]弹出5 - freq: {5:1, 7:1, 4:1} - group: {1: [4,7,5], 2: [], 3: []} - maxFreq: 1 (因为group[2]为空) pop() → 4: - 从group[1]弹出4 - freq: {5:1, 7:1, 4:0} - group: {1: [7,5], 2: [], 3: []} - maxFreq: 1测试用例importjava.util.*;publicclassTest{publicstaticvoidmain(String[]args){// 测试用例1标准示例FreqStackfreqStack1newFreqStack();freqStack1.push(5);freqStack1.push(7);freqStack1.push(5);freqStack1.push(7);freqStack1.push(4);freqStack1.push(5);System.out.println(Test 1:);System.out.println(pop1: freqStack1.pop());// 5System.out.println(pop2: freqStack1.pop());// 7System.out.println(pop3: freqStack1.pop());// 5System.out.println(pop4: freqStack1.pop());// 4// 测试用例2单个元素FreqStackfreqStack2newFreqStack();freqStack2.push(1);freqStack2.push(1);System.out.println(Test 2:);System.out.println(pop1: freqStack2.pop());// 1System.out.println(pop2: freqStack2.pop());// 1// 测试用例3不同元素FreqStackfreqStack3newFreqStack();freqStack3.push(1);freqStack3.push(2);freqStack3.push(3);System.out.println(Test 3:);System.out.println(pop1: freqStack3.pop());// 3System.out.println(pop2: freqStack3.pop());// 2System.out.println(pop3: freqStack3.pop());// 1// 测试用例4复杂频率变化FreqStackfreqStack4newFreqStack();freqStack4.push(1);freqStack4.push(2);freqStack4.push(1);freqStack4.push(3);freqStack4.push(2);freqStack4.push(1);System.out.println(Test 4:);System.out.println(pop1: freqStack4.pop());// 1 (freq3)System.out.println(pop2: freqStack4.pop());// 2 (freq2, more recent than 1)System.out.println(pop3: freqStack4.pop());// 1 (freq2)System.out.println(pop4: freqStack4.pop());// 3 (freq1)System.out.println(pop5: freqStack4.pop());// 2 (freq1)System.out.println(pop6: freqStack4.pop());// 1 (freq1)// 测试用例5大量操作FreqStackfreqStack5newFreqStack();for(inti0;i1000;i){freqStack5.push(i%10);}// 测试用例6边界值FreqStackfreqStack6newFreqStack();freqStack6.push(Integer.MAX_VALUE);freqStack6.push(Integer.MIN_VALUE);freqStack6.push(Integer.MAX_VALUE);System.out.println(Test 6:);System.out.println(pop1: freqStack6.pop());// MAX_VALUESystem.out.println(pop2: freqStack6.pop());// MIN_VALUESystem.out.println(pop3: freqStack6.pop());// MAX_VALUE}}关键点数据结构使用Deque或Stack作为频率分组的容器ArrayDeque比Stack更高效避免同步开销频率维护push 时增加频率并更新最大频率pop 时减少频率并在必要时减少最大频率栈顶优先同一频率的元素按推入顺序存储后推入的元素在栈顶pop 时优先返回空间效率每个推入的元素只存储一次频率映射只存储不同元素的频率常见问题为什么不用优先队列优先队列无法高效处理频率动态变化的情况需要 O(log n) 时间更新优先级多层栈提供 O(1) 时间复杂度