java Map练习-字母卡片(牛客网)\贪心\排序\递归

题目描述

给你n张卡片，卡片上仅包含大写英文字母，现你可从这n张卡片中选出k张，要求得到尽可能高的分数。
关于分数的计算方式，在你所选择的k张卡片中，含有相同字母的卡片分数为卡片数乘以相同卡片个数。
就样例而言，选择九张D和其他任意一张，得到的结果为9*9+1 。

输入描述:
输入包含两行，第一行含两个整数n，k(0

第二行为每张卡片上的字母
输出描述:
输出仅包含一行，输出尽可能高的分数
示例1
输入

15 10 
DZFDFZDFDDDDDDF

输出

82

题目首先需要多组输入,题目中未提到,用console.hasNext()判断循环结束,输入后获取字符串,再转为字符数组,使用map统计每个个数,再将map中的value传入数组中,排序后从大到小遍历至总和为k

package set;
import java.util.*;
public class MapDemo02 {public static void main(String[] args){Scanner console = new Scanner(System.in);//循环直到控制台没有输入,实现多组输入while(console.hasNext()){//第一行输入,回车结束String str1 = console.nextLine();//将字符串分解为n 和 kString[] s = str1.split(" ");int n = Integer.parseInt(s[0]);int k = Integer.parseInt(s[1]);//第二行输入一串字母String str2 = console.nextLine();//将字母转化为字符数组char[] c = str2.toCharArray();Map<Character,Integer> maps = new HashMap<>();//利用Map统计每个字符的个数for(Character cs:c){//第一次获得,赋值0if(maps.get(cs) == null){maps.put(cs,0);}//每次获得,value+1maps.put(cs,maps.get(cs)+1);}//用values方法将value传入集合Collection<Integer> col = maps.values();int a[] = new int[col.size()];int x = a.length - 1;int m = 0;//再将集合中的数传入数组for(Integer i:col){a[m] = i;m++;}//调用获得分数的方法System.out.println(score(a,k,x));}}public static long score(int[] a,int k,int x){//对数组进行排序Arrays.sort(a);//若数组中最大的数比k大,意味着有k个相同字母,最大分数既为k*kif(a[x] >= k) return (long)k*k;k = k - a[x];//取字母最大个数a[x],剩下k个继续从剩下数组中取,递归return (long)a[x]*a[x] + score(a,k,x-1);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！