题目链接
// 分析题目不难发现,这道题其实和字符具体长啥样没关系
// 只和字母的个数有关系,所以我们只需统计字母的个数
// 总体思路分两个情况
// 第一个情况,若有不存在的字母
// 例如abab,除ab以外的字母都不存在,可以将两个a转化为单个z,以此类推
// 当所有字母都被占用的时候,那么就进入到第二种情况
// 把所有多出来的字符全都转化成某一个字母,比如a
// 此时的情况一定是a有n个,其他字母全是1个,我们只需要消除多余的a即可
// 每次删掉两个a,再转化成一个a,这样操作一次就少一个a
// 总会变成所有字母都只剩下一个的情况,即达成题意不重复
#include<iostream>
#include<vector>
#include <string>
using namespace std;
int n;
string s;
void solve() {
while(n--) {
cin >> s;
vector<int> a(26, 0); //建立数组储存26个字母的出现次数
for(int i = 0; i < s.size(); ++i) { //储存数据
a[s[i] - 97]++;
}
int cnt = 0;
for(int i = 0; i < 26; ++i) {
if(a[i] > 1) { // 找出用第一种情况要操作的次数
int temp = a[i] / 2;
cnt += temp;
a[i] = a[i] - temp * 2; // 减去被删除的字母
}
}
int cnt0 = 0; // 统计此时未出现的字母个数
for(int i = 0; i < 26; ++i) {
if(a[i] == 0) {
cnt0++;
}
}
int ans;
if(cnt > cnt0) { // 如果此时未出现字母的个数不够
ans = cnt + (cnt - cnt0);
// 第一个cnt代表第一种情况的操作次数
// cnt - cnt0代表将所有未被消化的字母累加到a头上
// 因每次操作会消除掉一个多余的a
// 所以最终答案是 第一种情况的操作次数 + (第二种情况的操作次数)
}
else {
ans = cnt;// 第一种情况可以容纳,那么操作次数就是答案
}
cout << ans << endl;
}
}
int main() {
while(cin >> n) {
solve();
}
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
String str = scanner.next();
System.out.println(minOperations(str));
}
}
public static int minOperations (String str) {
int[] hashMap = new int[26];
// 初始化数组
for (int i = 0; i < str.length(); i++) { // 遍历字符串
int position = str.charAt(i) - 'a'; // 寻找字符对应数组中的位置 a -> 0,b -> 1,...,z -> 25
hashMap[position]++;
}
int charUseCount = 0; // 记录 26 个位置被使用的次数
int result = 0; // 需要操作的次数
// 遍历数组
for (int i = 0; i < hashMap.length; i++) {
if (hashMap[i] == 1) { // 字符只出现一次，不需要操作，占用掉一个位置
charUseCount++;
}
if (hashMap[i] % 2 == 0) { // 字符出现偶数次，需要操作 n/2 次，并且占用 n / 2 个位置
charUseCount += hashMap[i] / 2;
result += hashMap[i] / 2;
}
if (hashMap[i] != 1 && hashMap[i] % 2 == 1) { // 字符出现奇数次，需要操作 n/2 次，并且占用 n / 2 + 1 个位置
result += hashMap[i] / 2;
charUseCount += hashMap[i] / 2 + 1;
}
}
if (charUseCount > 26) { // 二十六个位置不够使用时
result += charUseCount - 26;
}
return result;
}
}class Sol():
def __init__(self, str1):
self.str1 = str1
def f(self):
l = len(self.str1)
nums = [0 for _ in range(26)]
cnt = 0
kinds = 0
for i in range(l):
cur = self.str1[i]
nums[ord(cur) - ord('a')] += 1
for i in range(26):
cnt += int(nums[i]/2)
kinds += nums[i] % 2
if cnt + kinds < 26:
return cnt
else:
return cnt + cnt + kinds - 26
n = int(input())
ans = []
for i in range(n):
s = input()
solution = Sol(s)
ansnow = solution.f()
ans.append(ansnow)
for item in ans:
print(item)package main
import (
"fmt"
)
func minOperations(s string) int {
res := 0
aa := 0 // 被使用的字母数量
charCount := make(map[rune]int)
// 计算每个字符的频率
for _, c := range s {
charCount[c]++
}
for _, count := range charCount {
if count == 1 {
aa++
}
if count%2 == 0 {
res += count / 2 // 消除n个字符，需要n/2次操作
aa += count / 2 // 消耗n/2个字母
}
if count > 1 && count%2 != 0 {
res += count / 2 // 消除n个字符，需要n/2次操作
aa += count/2 + 1 // 消耗n/2个字母加上余出的1个字母
}
}
// 超出26个字母的部分，需要额外的操作
if aa > 26 {
res += aa - 26
}
return res
}
func main() {
var N int
fmt.Scanf("%d\n", &N)
for i := 0; i < N; i++ {
var s string
fmt.Scanf("%s\n", &s)
fmt.Println(minOperations(s))
}
}#include <stdio.h>
#include <string.h>
int minOperations(char* s) {
int result = 0;
int nums[26] = {0};
int size = strlen(s);
for (int i = 0; i < size; i++) {
nums[s[i] - 'a']++;
}
int count0 = 0;
for (int i = 0; i < 26; i++) {
if (nums[i] == 0)
count0++;
}
for (int i = 0; i < 26; i++) {
if (nums[i] > 1 && count0 >= ((nums[i] - 1) / 2)) {
count0 -= (nums[i] - 1) / 2;
result += nums[i] / 2;
nums[i] = 1;
}
else if (nums[i] > 1 && count0 > 0 && count0 < ((nums[i] - 1) / 2)) {
result += count0;
nums[i] -= (2 * count0);
count0 = 0;
i--;
}
else if (nums[i] > 1 && count0 <= 0) {
result += (nums[i] - 1);
nums[i] = 1;
}
}
return result;
}
int main() {
int N;
scanf("%d", &N);
getchar();
while (N--) {
char s[1005];
fgets(s, sizeof(s), stdin);
s[strcspn(s, "\n")] = '\0';
printf("%d\n", minOperations(s));
}
return 0;
}