首页 > 试题广场 >

字符串价值

[编程题]字符串价值

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

有一种有趣的字符串价值计算方式:统计字符串中每种字符出现的次数,然后求所有字符次数的平方和作为字符串的价值
例如: 字符串"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

输出

算法知识视频讲解

Java

牛客834002708号

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int k = in.nextInt();
        int sum = 0;
        TreeMap<Character, Integer> map = new TreeMap();   // 统计每个字母的个数
        for(int i=0;i<s.length();i++){
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i),0)+1);
        }
        int a[] = new int[map.size()];    // 只存放每个字母的个数
        int i = 0, n = a.length;
        Set set = map.entrySet();
        for(Object obj : set){
            Map.Entry<Character, Integer> m = (Map.Entry)obj;
            a[i++] = m.getValue();
        }
        // ************************** 重点：移除字母
        // 每次移除剩余最多的字母，使其剩下的个数比倒数第二多的少1个，直到移除k次
        while(k > 0){
            Arrays.sort(a);           // 排序：找到每次剩余最多的字母的个数
            int t = a[n-1]-a[n-2]+1;  // 每次移除t个
            a[n-1] -= t<=k ? t:k;     // 需要移除的个数满足t<=k，则移除t个；否则只能移除k次
            k -= t;                   // 还可以继续操作k次
        }
        // *****************************************************
        for(i=0;i<n;i++){
            sum += a[i]*a[i];
        }
        System.out.println(sum);
    }
}

发表于 2021-08-22 00:49:37 回复(0)

Java

horsemuzi

Map和List：每一次减去当前字符串中出现次数最多的字符🤣🤣🤣

import java.util.*; import java.util.stream.*; public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); String str = sc.next(); int k = sc.nextInt(); Map<Character, Integer> map = new HashMap<>(16); for (int i = 0; i < str.length(); i++) { char key = str.charAt(i); if (!map.containsKey(key)) { map.put(key, 1); } else { map.put(key, map.get(key) + 1); } } List<Integer> list = new ArrayList<>(map.values()); for (int i = 0; i < k; i++) { list = list.stream().sorted().collect(Collectors.toList()); list.set(list.size() - 1, list.get(list.size() - 1) - 1); } int result = 0; for (Integer integer : list) { result += integer * integer; } System.out.println(result); } }

发表于 2020-08-27 14:59:33 回复(0)

Java

何止hz

维护一个大顶堆

package com.t2018.爱奇艺;

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-14 9:29
 * @Description: 字符串价值
 * @version: 1.0
 */
public class Main8 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int k = sc.nextInt();
        int hash[] = new int[26];
        for (int i = 0; i < s.length(); i++)
            hash[s.charAt(i) - 'a']++;
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2) -> o2 - o1);
        for (int i = 0; i < 26; i++)
            if (hash[i] != 0)
                pq.offer(hash[i]);
        while (k-- > 0)
            pq.offer(pq.poll() - 1);
        int ans = 0;
        while (!pq.isEmpty())
            ans += pq.peek() * pq.poll();
        System.out.println(ans);
    }
}

发表于 2020-05-14 09:39:50 回复(0)

Java

背负永恒疾风命运的皇子

我的只排了一次序,感觉应该最简单了吧...
public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        int k=sc.nextInt();
        int[] c=new int[26];
        for(int i=0;i<s.length();i++){
            c[s.charAt(i)-97]++;
        }
        Arrays.sort(c);
        int d=0;
        int e=0;
        for(int i=25;i>0;i--){
            d=c[i]-c[i-1];
            d=d*(26-i);
            if(d<k){
                for(int j=i;j<26;j++)c[j]=c[j-1];
                k-=d;
            }
            else{
                while(k>0){
                for(int j=i;j<26;j++){
                    if(k==0)break;
                    c[j]--;
                    k--;
                }
                }
            }
            if(k==0)break;
        }
        int sum=0;
        //System.out.println(Arrays.toString(c));
        for(int i=25;i>=0;i--){
            sum+=c[i]*c[i];
        }
        System.out.println(sum);
    }

发表于 2019-08-16 15:28:19 回复(1)

Java

Mono_Chrome

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int k = sc.nextInt();
        int sum = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            if (map.containsKey(str.charAt(i))) {
                map.put(str.charAt(i), map.get(str.charAt(i)) + 1);
            } else {
                map.put(str.charAt(i), 1);
            }
        }
        int[] arr = new int[map.size()];
        int i = 0;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            arr[i++] = entry.getValue();
        }
        Arrays.sort(arr);

        while (k-- > 0) {
            arr[arr.length - 1] -= 1;
            Arrays.sort(arr);
        }
        for (i = 0; i < arr.length; i++) {
            sum += arr[i] * arr[i];
        }
        System.out.println(sum);
    }
}

发表于 2019-06-14 22:03:49 回复(0)

Java

百度内推官_Flyer

还是数组替代哈希表用着记录字符出现的次数用的舒服。。。

private static int solution(String s, int k) {
    int[] arr = new int[26];
    for (char ch : s.toCharArray()) {
        arr[ch - 'a']++;
    }

    for (int i = 0; i < k; i++) {
        Arrays.sort(arr);
        arr[25]--;
    }

    int res = 0;
    for (int i = 0; i < 26; i++) {
        res += arr[i] * arr[i];
    }
    return res;
}

编辑于 2019-05-17 20:19:54 回复(0)

Java

公子晓白

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String str = sc.next();
            int k = sc.nextInt();
            int result = minimumValue(str,k);
            System.out.println(result);
        }
    }

    private static int minimumValue(String str, int k) {
        char[] c = str.toCharArray();
        Arrays.sort(c);
        int[] intc = new int[c.length];
        int j = 0;
        for(int i = 0; i < c.length; i++) {
            if(i == 0) {
                intc[j]++;
                continue;
            }
            if(c[i] != c[i - 1]) {
                j++;
                intc[j]++;
            }
            else {
                intc[j]++;
            }
        }
        Arrays.sort(intc);
        for(int i = 0; i < k; i++) {
            intc[c.length - 1]--;
            Arrays.sort(intc);
        }
        int sum = 0;
        for(int i = 0; i < intc.length; i++) {
            sum += intc[i] * intc[i];
        }
        return sum;
    }
}

发表于 2019-04-17 11:28:55 回复(0)

Java

很白的月色

你们这些大佬真厉害，一下就能发现规律


import java.util.*;

public class Main {
    public static  void main(String[] args){
        Scanner in=new Scanner(System.in);
        String str=in.next();
        int k=in.nextInt();
        int[] count=new int[26];
        int res=0;
        for(int i=0;i<str.length();i++){
            count[str.charAt(i)-'a']++;
        }
        for(int i=0;i<k;i++){
            Arrays.sort(count);
            count[25]--;//最大的减一
        }
        for(int i=0;i<26;i++){
            if(count[i]!=0){
                res+=Math.pow(count[i],2);
            }
        }
        System.out.println(res);
    }
}

发表于 2019-03-11 21:57:46 回复(0)

Java

成程晨

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;
    }
}

发表于 2019-01-15 22:26:49 回复(0)

Java

SP小夜

看来大家想的都一样

package myone;
import java.util.*;
public class kuohao {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        int n=sc.nextInt();
        int a=sus(s,n);
        System.out.println(a);
    }
    public static int sus(String s,int n){
        int sum=0,x=0;//sum保存结果，x记录数组a下标
        int[] a=new int[s.length()];//存放不同字符出现次数
        Map map=new HashMap();//用哈希表判断字符是否重复
        for(int i=0;i<s.length();i++){
           if(map.containsKey(s.charAt(i))){//当插入哈希表中的key值重复时，累加重复位置
               a[(int) map.get(s.charAt(i))+1]++;//获取存储的value值
               continue;
           }
           map.put(s.charAt(i),x);//将字符作为key,字符在数组a中的位置作为value
           x++;
           a[x]++;//不重复时计1
        }
        
        for(int i=0;i<n;i++){//每次循环减去出现次数最多的字符中的一个
             a=lete(a);
        }
        
        for(int i=0;i<a.length;i++){//计算平方和
            if(a[i]!=0){
                sum+=a[i]*a[i];
            }
        }
        return sum;
    }
    
    public static int[] lete(int[] a){//每一次找出最大重复数减一
        int x=0,h=0;
        for(int i=0;i<a.length;i++){
             if(a[i]>=x){
                 x=a[i];
                 h=i;//记录下标
             }
        }
        a[h]--;
        return a;
    }
}

发表于 2019-01-10 16:43:05 回复(0)