笔试强训 Day 36：提取不重复的整数、哈夫曼编码、abb

Day 36提取不重复的整数解题思路模拟代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);int[]hashnewint[10];char[]cin.next().toCharArray();intnc.length;StringBuildersbnewStringBuilder();for(intin-1;i0;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){ScannerinnewScanner(System.in);intnin.nextInt();// 小根堆每次 poll() 取出最小值PriorityQueueLongpqnewPriorityQueue();for(inti0;in;i){pq.offer(in.nextLong());}longans0;// 不断合并当前最小的两个节点// 只有一种字符时不需要区分它和其他字符可以用长度为 0 的空编码因此编码总长度为 0。while(pq.size()1){longxpq.poll();// 最小longypq.poll();// 次小longsumxy;anssum;// 新的父节点放回去继续参与下一轮合并pq.offer(sum);}System.out.println(ans);}}abb解题思路线性 dp难在统计二元组数量的方式代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();char[]sin.next().toCharArray();// 记录前面的每种字符的个数long[]cntnewlong[26];// 记录前面出现的不同二元组的个数, 每个元素表示以其为末尾, 二元组的数量long[]pairnewlong[26];// 记录前面出现的字符个数longtotal0;// 记录 abb 出现个数longret0;for(inti0;in;i){intcs[i]-a;// 以 c 为末尾的 xcc 数量retpair[c];// 更新二元组, 表示以当前字符为末尾的二元组数量// err: 累加, 以当前 c 为结尾, 前面与 c 不同, 新组成的二元组数量pair[c]total-cnt[c];total;cnt[c];}System.out.println(ret);}}