笔试——字符串价值

墨蓝 2022-06-07 07:38 162阅读 0赞

有一种有趣的字符串价值计算方式：统计字符串中每种字符出现的次数，然后求所有字符次数的平方和作为字符串的价值。

例如：字符串“abacaba”，里面包括4个‘a’，2个‘b’，1个‘c’，于是这个字符串的价值为：4\*4+2\*2+1\*1=21；

牛牛有一个字符串s，并且允许你从s中移除最多k个字符，你的目标是让得到的字符串的价值最小。

输入描述：

输入包括两行：第一行一个字符串s，长度length（1<=length<=50），只包含小写字母；

第二行包含一个整数k（0<=k<=length），即允许移除的字符个数。

样例输入：

aba

样例输出：

代码：

import java.util.Arrays;
    import java.util.HashMap;
    import java.util.Scanner;
    
    public class stringValue {
    	public static void main(String[] args) {
    		Scanner in = new Scanner(System.in);
    		String s = in.nextLine();
    		int k = in.nextInt();
    		HashMap<Character,Integer> map = new HashMap<>();
    		
    		//用map存放对应字符的个数
    		for(int i=0;i<s.length();i++){
    			char c = s.charAt(i);
    			if(!map.containsKey(c))
    				map.put(c, 1);
    			else
    				map.put(c, map.get(c)+1);
    		}
    		int[] num = new int[map.size()];
    		int i=0;
    		for(Character key : map.keySet()){
    			num[i++]=map.get(key);
    		}
    		
    		k_remove(num,k);//移除k个字母
    		
    		int sum=0;
    		for(int j=0;j<num.length&&num[j]!=0;j--){
    			if(num[j]==0)
    				break;
    			sum += num[j]*num[j];
    		}
    		System.out.println(sum);
    	}
    
    	private static void k_remove(int[] num, int k) {
    		//要移去k次，但是并不能只在一个数上减掉k，要将k平摊开，每次移去的是最大的个数的字母，才能使得其平方和最小，
    		for(int i=0;i<k;i++){
    			Arrays.sort(num);
    			if(num[num.length-1]>0)
    				num[num.length-1]--;
    			else
    				return;
    		}
    	}
    }