Day 39神奇的字母二解题思路模拟收集代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);int[]hashnewint[26];intmax0;charreta;while(in.hasNext()){char[]cin.next().toCharArray();for(charch:c){hash[ch-a];if(hash[ch-a]max){retch;maxhash[ch-a];}}}System.out.println(ret);}}字符编码解题思路注意有多组输入同时注意所有字符都要编码参考题目代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);while(in.hasNext()){Stringstrin.next();int[]hashnewint[128];for(charch:str.toCharArray()){hash[ch];}PriorityQueueIntegerqueuenewPriorityQueue();for(intnum:hash){if(num0)queue.add(num);}longret0;while(queue.size()1){ints1queue.poll();ints2queue.poll();ret(long)(s1s2);queue.add(s1s2);}System.out.println(ret);}}}最少的完全平方数解题思路完全背包问题dp[j]表示组成数字j所需要的最少完全平方数个数。完全平方数依次为1, 4, 9, 16, ...状态转移dp[j] Math.min(dp[j], dp[j - i * i] 1);含义是如果最后选择平方数i * i那么前面需要先组成j - i * i再加上当前这个平方数因此数量是dp[j - i²] 1初始化dp[0] 0;因为组成0不需要任何数字。其他位置先设为一个很大的数0x3f3f3f3f表示暂时无法组成。例如n 55 1 1 1 1 1 5 1 4最优答案是2。这里内层循环j从小到大表示同一个完全平方数可以重复使用例如1 1 1。因此这是一个完全背包问题。复杂度时间复杂度O(n√n)空间复杂度O(n)代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();int[]dpnewint[n1];for(inti0;in;i){dp[i]0x3f3f3f3f;}dp[0]0;for(inti1;i*in;i){for(intji*i;jn;j){dp[j]Math.min(dp[j],dp[j-i*i]1);}}System.out.println(dp[n]);}}
