编程题——字符串价值

迈不过友情╰ 2022-04-23 18:40 188阅读 0赞

【题目】  
有一种有趣的字符串价值计算方式:统计字符串中每种字符出现的次数,然后求所有字符次数的平方和作为字符串的价值。例如: 字符串"abacaba",里面包括4个’a’,2个’b’,1个’c’,于是这个字符串的价值为4 \* 4 + 2 \* 2 + 1 \* 1 = 21。牛牛有一个字符串s,并且允许你从s中移除最多k个字符,你的目标是让得到的字符串的价值最小。  
输入描述: 输入包括两行,第一行一个字符串s,字符串s的长度length(1 ≤ length ≤ 50),其中只包含小写字母(‘a’-‘z’)。 第二行包含一个整数k(0 ≤ k ≤ length),即允许移除的字符个数。  
输出描述: 输出一个整数,表示得到的最小价值  
示例1  
输入 aba  
1  
输出 2

【思路】  
不断将出现最多次的字符数量减1。  
最后将所有字符出现次数平方和加起来。

【实现】

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class Main {
    	public static void main(String[] args) throws IOException {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		String s = br.readLine();//读字符串s
    		int k = Integer.parseInt(br.readLine());//读输入k
    		int[] z = new int[26];//创建26个英文字母数组，用来保存遍历的字母的个数
    		for(int i = 0;i<s.length();i++){//遍历输入的字符串
    		
    		//这里是说在数列a中的第str[i].chatAt(j)-'a'这个元素增加，如果以'ads'为例子,第一次是 
    		//a['a'-'a']++(a[0]++),第二次是a['d'-'a']++(a[3]++),第三次是a['s'-'a'](a[18]++)
    		
    			z[s.charAt(i)-'a']++;//保存字符串的个数
    		}
    		for(int i = 0;i<k;i++){//删除k个字符
    			int maxId = 0;
    			for(int j = 0;j<26;j++){//遍历保存字母个数的是数组，从最大的数子开始减
    				if(z[j]>z[maxId]){
    					maxId = j;
    				}
    			}
    			z[maxId]--;
    			
    		}
    		int res = 0;//结果
    		for(int i = 0;i<26;i++){//遍历数组，求平方和
    			res += Math.pow(z[i], 2);
    		}
    		System.out.println(res);
    	}
    }