笔试强训 Day 36：提取不重复的整数、哈夫曼编码、abb
Day 36
提取不重复的整数
解题思路：模拟
代码实现：
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);int[]hash=newint[10];char[]c=in.next().toCharArray();intn=c.length;StringBuildersb=newStringBuilder();for(inti=n-1;i>=0;i--){if(hash[c[i]-'0']>=1)continue;hash[c[i]-'0']++;sb.append(c[i]);}System.out.println(sb.toString());}}哈夫曼编码
解题思路：
使用哈夫曼编码时，出现次数少的字符应放在树的更深处。每次选择当前出现次数最少的两个节点合并，它们的所有字符编码长度都会增加1，因此本次对总长度的贡献为两者出现次数之和。
用小根堆维护所有节点权重：
- 将所有字符出现次数放入小根堆。
- 每次取出最小的两个数
x、y。 - 合并为新节点
x + y，将其加入答案。 - 将
x + y放回堆中。 - 重复直到堆中只剩一个节点。
最终累加值就是最短ß编码长度。
- 时间复杂度：
O(n log n) - 空间复杂度：
O(n)
代码实现：
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt();// 小根堆：每次 poll() 取出最小值PriorityQueue<Long>pq=newPriorityQueue<>();for(inti=0;i<n;i++){pq.offer(in.nextLong());}longans=0;// 不断合并当前最小的两个节点// 只有一种字符时，不需要区分它和其他字符，可以用长度为 0 的空编码，因此编码总长度为 0。while(pq.size()>1){longx=pq.poll();// 最小longy=pq.poll();// 次小longsum=x+y;ans+=sum;// 新的父节点放回去，继续参与下一轮合并pq.offer(sum);}System.out.println(ans);}}abb
解题思路：
- 线性 dp，难在统计二元组数量的方式；
代码实现：
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt();char[]s=in.next().toCharArray();// 记录前面的每种字符的个数long[]cnt=newlong[26];// 记录前面出现的不同二元组的个数, 每个元素表示以其为末尾, 二元组的数量long[]pair=newlong[26];// 记录前面出现的字符个数longtotal=0;// 记录 abb 出现个数longret=0;for(inti=0;i<n;i++){intc=s[i]-'a';// 以 c 为末尾的 xcc 数量ret+=pair[c];// 更新二元组, 表示以当前字符为末尾的二元组数量// err: 累加, 以当前 c 为结尾, 前面与 c 不同, 新组成的二元组数量pair[c]+=total-cnt[c];total++;cnt[c]++;}System.out.println(ret);}}