牛客算法：字符串价值

佚名 6年前 (2019-04-10) 随笔 1865人围观抢沙发百度已收录

首先附上自己比较蠢的方法，帮助理解。后面附上大神的代码。感受差距。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

import java.util.*;
public class Main{
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            String s = in.next();
            int k = in.nextInt();
            System.out.println(helper(s,k));
        }
    }
    public static int helper(String s, int k){
        char []str = s.toCharArray();
        Arrays.sort(str);
        //统计有多少种字符
        int n = 1;
        for(int i = 0; i < str.length-1;i++) {
            if(str[i]!=str[i+1]) n++;
        }
        int []cnt = new int[n]; //存放各个字符的价值，如题中的4,2,1
        int cntt = 1; //统计各个字符串的价值
        for(int i = 1, j = 0; i < str.length;i++){
            if(str[i-1] == str[i] && i!=str.length-1){
                cntt++;
            }else{
                cnt[j] = cntt;
                cntt = 1;
                j++;
            }
        }
        cnt[n - 1]++;  //最后一个字符漏算，在循环外加上
         
        //去除k字符的核心思想是，每次总取最大的数减一，故减一次拍一次序
        Arrays.sort(cnt);
        for(int i = 0;i < k ; i++){
            cnt[cnt.length - 1] -= 1;
            Arrays.sort(cnt);
        }
        int sov = 0;
        for(int i = 0; i < cnt.length ; i++){
            sov += cnt[i]*cnt[i];
        }
         
        return sov;
         
    }
}

大神成程晨代码：

链接：https://www.nowcoder.com/questionTerminal/9240357eefcf4d938b90bdd5eec3712b
来源：牛客网

import java.util.*;
public class Main{
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            System.out.println(helper(in.next(),in.nextInt()));
        }
    }
    public static int helper(String s,int k){
        char[] cs = s.toCharArray();
        int[] a = new int[26];
        for(char c:cs){
            a[c - 'a']++;
        }
        //不用自己造轮子系列
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->{
            return o2 - o1;
        });
        for(int num:a){
            if(num != 0) pq.add(num);
        }
        int i = 0;
        while(i < k){
            int num = pq.remove();
            pq.add(num - 1);
            i++;
        }
        int sum = 0;
        for(int num:pq){
            sum += num * num;
        }
        return sum;
    }
}