有一种有趣的字符串价值计算方式:统计字符串中每种字符出现的次数,然后求所有字符次数的平方和作为字符串的价值
例如: 字符串"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),即允许移除的字符个数。
输出一个整数,表示得到的最小价值
aba 1
2
思路:
先计算每个字母出现次数,然后每次减出现次数最高的那个,注意:没减一次最大值会变化。
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String inputString = scanner.nextLine(); int k = scanner.nextInt(); scanner.close(); // 记录每个元素出现次数 int[] numArray = new int[26]; for (int i = 0; i < inputString.length(); i++) { numArray[inputString.charAt(i) - 'a']++; } // 按照出现次数进行排序 Arrays.sort(numArray); for (int i = numArray.length - 1; i >= 1; i--) { // 该值必须大于后面的值,加上下面的排序保证每次都是减出现次数最多的那个位置值 while (numArray[i] > 0 && numArray[i] >= numArray[i - 1] && k > 0) { numArray[i]--; k--; // 每次减完排序,一直减最大的那个 Arrays.sort(numArray); } } long sum = 0; for (int i = 0; i < numArray.length; i++) { sum += numArray[i] * numArray[i]; } System.out.println(sum); } }
import java.util.*; public class Main{ public static void main(String []args){ Scanner sc = new Scanner(System.in); String str = sc.nextLine(); int k = sc.nextInt(); int[] array = new int[26]; //array[0]代表a出现的次数,后面依次类推 for(int i = 0; i < str.length(); i ++){ char temp = str.charAt(i); int num = temp - 'a'; array[num]++; } //每次array数组中最大的数减一,为了找到最大的数,通过Arrays.sort()进行排序 int count = 0; while(k != count){ Arrays.sort(array); if(array[array.length-1] != 0){ array[array.length-1]--; count ++; } } int sum = 0; //数组的平方和就是最后的结果 for(int j = 0; j < array.length; j ++){ sum += Math.pow(array[j], 2); } System.out.println(sum); return; } }