企业官网建设流程全解析

Day 39

神奇的字母（二）

解题思路：

• 模拟收集

代码实现：

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);int[]hash=newint[26];intmax=0;charret='a';while(in.hasNext()){char[]c=in.next().toCharArray();for(charch:c){hash[ch-'a']++;if(hash[ch-'a']>max){ret=ch;max=hash[ch-'a'];}}}System.out.println(ret);}}

字符编码

解题思路：

• 注意，有多组输入，同时注意所有字符都要编码；
• 参考题目

代码实现：

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);while(in.hasNext()){Stringstr=in.next();int[]hash=newint[128];for(charch:str.toCharArray()){hash[ch]++;}PriorityQueue<Integer>queue=newPriorityQueue<>();for(intnum:hash){if(num>0)queue.add(num);}longret=0;while(queue.size()>1){ints1=queue.poll();ints2=queue.poll();ret+=(long)(s1+s2);queue.add(s1+s2);}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 = 5：

5 = 1 + 1 + 1 + 1 + 1 5 = 1 + 4

最优答案是2。

这里内层循环j从小到大，表示同一个完全平方数可以重复使用，例如1 + 1 + 1。因此这是一个完全背包问题。

复杂度：

• 时间复杂度：O(n√n)
• 空间复杂度：O(n)

代码实现：

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt();int[]dp=newint[n+1];for(inti=0;i<=n;i++){dp[i]=0x3f3f3f3f;}dp[0]=0;for(inti=1;i*i<=n;i++){for(intj=i*i;j<=n;j++){dp[j]=Math.min(dp[j],dp[j-i*i]+1);}}System.out.println(dp[n]);}}