笔试强训 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，因此本次对总长度的贡献为两者出现次数之和。

用小根堆维护所有节点权重：

  1. 将所有字符出现次数放入小根堆。
  2. 每次取出最小的两个数x、y。
  3. 合并为新节点x + y，将其加入答案。
  4. 将x + y放回堆中。
  5. 重复直到堆中只剩一个节点。

最终累加值就是最短ß编码长度。

代码实现：

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

解题思路：

代码实现：

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);}}