首页 > 试题广场 >

字符串价值

[编程题]字符串价值
  • 热度指数：131 时间限制：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

输出

2
算法知识视频讲解
添加回答
C/C++
张子寒头像 张子寒
C语言和Python ：
#include <stdio.h>
#include <stdlib.h>
//用于系统快排的比较函数
int cmp(const void*a,const void*b){
    return *(int*)b-*(int*)a;
}

int main(void){
    char str[256] = {0};
    char c;
    int len = 0;
    do{
        scanf("%c", &c);
        if( str[c] == 0 )
            len ++;
        str[c] ++;
    }while( c != '\n');
    str['\n'] = 0;
    len --;
    //存放字符出现次数
    int *cnum = NULL;
    cnum = (int*)malloc(len*sizeof(int));
    int i, j;
    for(i = 0, j = 0; j < len; i ++){
        if(str[i]!= 0){
            cnum[j] = str[i];
            j ++;
        }
    }
    //标准库自带快排
    qsort(cnum,len,sizeof(int),cmp);
    
    int N;
    scanf("%d", &N);
    
    //逐个砍去最多的字符
    while(N > 0){
        for(i = 0; i < len; i ++){
            cnum[i] --;
            N --;
            if( N == 0 || i == len - 1 || cnum[i] >= cnum[i + 1])
                break;
        }
    }
    //计算结果
    int ret = 0;
    for(i = 0; i < len; i ++){
        ret += cnum[i]*cnum[i];
    }
    printf("%d", ret);
    
    free(cnum);
    return 0;
} 
str, N = input(), int(input())
dic = {}
for c in str:
    if dic.__contains__(c) :
        dic[c] += 1
    else :
        dic[c] = 1
vs = list(dic.values())    #values
vs.sort(reverse = True)
while N > 0 :    #防止N大于字符串长度
    for i in range(len(vs)) :
        vs[i] -= 1
        N -= 1
        if N == 0 or i == len(vs)-1 or vs[i] >= vs[i+1] :
            break
ret = 0
for i in vs :
    ret += i*i
print (ret)

发表于 2018-11-30 01:04:07 回复(0)
fuppl头像 fuppl
简单说一下思路，就是比较每个字母出现的次数，然后每次都从剩下的字母里选出一个重复次数最多的减一，这样就能保证最后的结果最小 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int n = in.nextInt();

        // 存储字母和重复次数的map
        Map<String , Integer> map = new HashMap<>();
        // 将str的每个字母都放进map
        for (int i = 1; i <= str.length(); i ++) {
            changeMap(map, str.substring(i - 1, i));
        }

        // map按值从大到小排序
        map = sortDesc(map);

        int count;
        // 每次拿出一个值最大的entry，然后减一，重复n次
        for(int i = 0; i < n; i ++) {
            count = 0;
             for (String s : map.keySet()) {
                 count ++;
                 changeMap2(map, s);
                 // 这是为了保证每次只拿出一个字母，肯定又更好的写法，但是目前没想到
                 if (count > 0) {
                     break;
                 }
             }
             map = sortDesc(map);
        }

        // 计算结果
        int result = 0;
        for (Integer integer : map.values()) {
            result += integer * integer;
        }

        System.out.println(result);
    }

    /**
     * 修改map，以str为key的value值 + 1
     * @param map
     * @param str key
     */
    public static void changeMap(Map<String, Integer> map, String str) {
        if (map.containsKey(str)) {
            map.put(str, map.get(str) + 1);
        } else {
            map.put(str, 1);
        }
    }

    /**
     * 修改map，以str为key的值 -1
     * @param map
     * @param str key
     */
    public static void changeMap2(Map<String , Integer> map, String str) {
        map.put(str , map.get(str) - 1);
    }

    /**
     * 将map按值从大到小排序，核心代码
     * @param map map
     * @return
     */
    public static Map<String, Integer> sortDesc(Map<String, Integer> map) {
        List<Map.Entry<String, Integer>> list = new LinkedList<>(map.entrySet());

        Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return - ((o1.getValue()).compareTo(o2.getValue()));
            }
        });

        Map<String, Integer> returnMap = new LinkedHashMap<>();
        for (Map.Entry<String, Integer> e : list) {
            returnMap.put(e.getKey(), e.getValue());
        }

        return returnMap;
    }
}



发表于 2021-03-13 15:21:47 回复(0)
C/C++
大海€头像 大海€
void SelectSort(int *arr,int len)//排序函数
{
   for(int i = 0;i < len;i++)
   {
     for(int j = i+1;j < len;j++)
    {
        if(arr[j] < arr[i])
        {
            int tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = tmp;
        }
    }
  }
}
int MinValue(char *str,int n)//n为允许移除的字符个数。
{
    assert(str!=NULL );
    if(strlen(str)<=0 || strlen(str)>50)
    {
    
        return 0 ;
    }
    int hash[123]={0};//只存放小写字母，97-123；
    int len=sizeof hash/sizeof hash[0];
    int count=0;
    int i=0;
    for(i=0;str[i]!='\0';i++)
    {
        hash[str[i]]++; //hash 的下标是字母的ASCII码值，内容是字母的次数    1.求字母出现次数
    }
    SelectSort(hash ,len);//2,排序
    for(int k=0;k<len-n;k++)//3.去除n个最大数字，求平方和
    {
        count+=hash[k]*hash[k];
    }
    return count;
}
int main()
{
char *str="aba";
printf("%d\n",MinValue(str,1))
return 0;

}

发表于 2018-11-28 22:30:09 回复(0)
提交观点

问题信息

贪心 字符串 爱奇艺 测试工程师 2018 数学
来自：爱奇艺2018秋季校招...
上传者：小小
难度：
3条回答 2646浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号