字母卡片

[编程题]字母卡片

热度指数：5781 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你n张卡片，卡片上仅包含大写英文字母，现你可从这n张卡片中选出k张，要求得到尽可能高的分数。

关于分数的计算方式，在你所选择的k张卡片中，含有相同字母的卡片分数为卡片数乘以相同卡片个数。

就样例而言，选择九张D和其他任意一张，得到的结果为9*9+1 。

输入描述:

输入包含两行，第一行含两个整数n，k(0<k<=n<=1,000,000）

第二行为每张卡片上的字母

输出描述:

输出仅包含一行，输出尽可能高的分数

示例1

输入

15 10 
DZFDFZDFDDDDDDF

输出

算法知识视频讲解

Java

孤天祭

JAVA思路：

首先遍历字符串，用HashMap存值，key是字符，value是次数。

因为本题不关注最后是什么字母，只需把values值摘出来，从大到小排序。

遍历排序后的数组或集合，直到达到k，返回一个long的结果

需要注意的点是结果是long时要对int强转

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {

		while (sc.hasNext()) {
			//获取输入数据
			String[] str0 = sc.nextLine().split(" ");
			int n = Integer.parseInt(str0[0]);
			int k = Integer.parseInt(str0[1]);
			String str = sc.nextLine();
			//处理输入数据->键值对
			int len = str.length();
			HashMap<Character, Integer> map = new HashMap<Character, Integer>();
			for (int i = 0; i < len ; i++) {
				char ch=str.charAt(i);
				if(map.containsKey(ch)) {
					map.put(ch, map.get(ch)+1);
				}else {
					map.put(ch, 1);
				}
			}
			//对值排序
			ArrayList<Integer> list = new ArrayList<Integer>(map.values());
			long grade = 0;
//			Collections.sort(list);
//			Collections.reverse(list);
			Collections.sort(list,new Comparator<Integer>() {

				@Override
				public int compare(Integer o1, Integer o2) {
					// TODO Auto-generated method stub
					return o2-o1;
				}
			});
			//计算结果
			for (int i : list) {
				if (i >= k) {
					grade += (long) k * k;
					System.out.println(grade);
					break;
				} else {
					grade += (long) i * i;
					k -= i;
				}
			}

		}
	}

}

编辑于 2020-07-28 15:58:24 回复(0)

Java

你瞅啥瞅

import java.util.*;
public class Main {
public void calcu(long k, int n, String s){
//使用HashMap
    Map<Character,Integer> map = new TreeMap<Character,Integer>();
    int len=0;
    for(int i=0;i<s.length();i++)
    {
    // 如果包含该键值对，值+1
        if(map.containsKey(s.charAt(i))){ 
        int num=map.get(s.charAt(i))+1;
        map.remove(s.charAt(i));
        map.put(s.charAt(i), num);
        }else{
            //如果不包含，创建新键值对
            map.put(s.charAt(i), 1);
            len++;
            }
      }
    int []b = new int [len];
    int t=0;   //用来下标滑动
    int ex=0;
    long max=0;
    //遍历HashMap,将值存进数组
    for(Character key : map.keySet()){
        int num =map.get(key);
        b[t]=num;
        ++;
    }
    //对数组排序,冒泡
    for(int i=0;i<len;i++){
        for(int j=0;j<len-i-1;j++){
            if(b[j]>b[j+1]){
                ex=b[j];
                b[j]=b[j+1];
                b[j+1]=ex;
                }
            }
       }
      //选值
     for(int i=len-1;i>=0;i--){
        if(b[i]>=k){
            max = max+k*k;
            System.out.println(max);
            break;
            }else{
                max = max+b[i]*b[i];
                k = k-b[i];
            }
        }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    Main m = new Main();
    while(sc.hasNext())
    {
    int n = sc.nextInt();
    long k = sc.nextLong();
    String s= sc.next();
    m.calcu(k, n, s);
    }
    }
}

编辑于 2019-08-16 15:14:46 回复(3)