有一种有趣的字符串价值计算方式:统计字符串中每种字符出现的次数,然后求所有字符次数的平方和作为字符串的价值
例如: 字符串"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),即允许移除的字符个数。
输出一个整数,表示得到的最小价值
aba 1
2
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); } }
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); } }
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); } }
我的只排了一次序,感觉应该最简单了吧... 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); }
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); } }
还是数组替代哈希表用着记录字符出现的次数用的舒服。。。
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; }
你们这些大佬真厉害,一下就能发现规律
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);
}
}
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; } }
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; } }