牛牛有一些字母卡片,每张卡片上都有一个小写字母,所有卡片组成一个字符串s。牛牛一直认为回文这种性质十分优雅,于是牛牛希望用这些卡片拼凑出一些回文串,但是有以下要求:
1、每张卡片只能使用一次
2、要求构成的回文串的数量最少
牛牛想知道用这些字母卡片,最少能拼凑出多少个回文串。
例如: s = "abbaa",输出1,因为最少可以拼凑出"ababa"这一个回文串
s = "abc", 输出3,因为最少只能拼凑出"a","b","c"这三个回文串
输入包括一行,一个字符串s,字符串s长度length(1 ≤ length ≤ 1000). s中每个字符都是小写字母
输出一个整数,即最少的回文串个数。
abc
3
import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ String str = sc.nextLine(); int[] ch = new int[26]; int length = str.length(); for(int i = 0; i < length; i++){ ch[str.charAt(i) - 'a']++; } int odd = 0; for(int i = 0; i < 26; i++){ if(ch[i] % 2 == 1) odd++; } System.out.println(odd == 0 ? 1 : odd); } } }
#include<stdio.h> #include<string> #include<iostream> #include<map> using namespace std; int main(){ string x; while(cin>>x){ map<char,int> book; for(int i=0;i<x.length();i++){ char tmp=x[i]; if(book.count(tmp)==0) book[tmp]=0; book[tmp]++; } map<char,int>::iterator it; int cnt=0; for(it=book.begin();it!=book.end();it++) if((it->second)%2==1) cnt++; printf("%d\n",cnt==0?1:cnt); } }//我们只要看看奇数个数的卡片有多少种就可以 //原因是因为 偶数个数的卡片一定可以组成长回文 不管有多少个 //偶数和奇数也可以组 不过多组偶数只能带1组奇数 //例子 2个a 4个b 3个c 5个d //那么我们把a和b合起来 bbaabb 之后带一组奇数 bbcacacbb 或者 bdbdadadbdb //我们可以发现 带上了1组奇数后 绝对带不上第二组奇数 //综上所述 奇数决定一切.....
#include<iostream> #include<string> using namespace std; int main() { string s; int num[26] = { 0 }; int sum_min = 0; cin >> s; for (int i = 0; i < s.length(); i++) { num[s[i] - 97] += 1; } for (int i = 0; i < 26; i++) { if (num[i] % 2 == 1) sum_min++; } if(sum_min == 0)//如果出现的字符全为偶数个,最少可只组成一个回文串 sum_min = 1; cout << sum_min; }
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = in.nextLine(); in.close(); System.out.println(helper(s)); } private static int helper(String s) { int[] count = new int[26]; int ans = 0; for(int i=0;i<s.length();i++) { int j = s.charAt(i) - 'a'; count[j]++; } for(int i=0;i<count.length;i++) { if(count[i] % 2 != 0) ans++; } return (ans == 0)?1:ans; } }
#include<iostream> #include<vector> #include<string> using namespace std; int main() { string str; while (getline(cin, str)) { int count = 0; vector<int> ivec(26, 0); for (int i = 0; i < str.size(); i++)//统计字符出现的次数 { int j = str[i] - 'a'; ivec[j]++; } for (int i = 0; i < 26; i++)//统计奇数次字符的个数 { if (ivec[i] % 2 != 0) count++; } cout << (count == 0 ? 1:count) << endl;//如果没有奇数次字符,那必然只有一个最长回文串 } return 0; }
import java.util.Scanner; public class Main { public static int BackString(String s) { int oddCount = 0; int evenCount = 0; int[] result = new int[256]; // 找出字符串中奇数个出现的字符 char[] c = s.toCharArray(); // 判断每个小写字母在字符串中出现的次数 for (int i = 0; i < c.length; i++) { if (c[i] != '\0') result[c[i]]++; } // 小写字母a-z对应ASCII码97-122 for (int i = 97; i <= 122; i++) { if (result[i] != 0 && result[i] % 2 != 0) oddCount++; if (result[i] != 0 && result[i] % 2 == 0)// 如果为偶数 evenCount++; } if (oddCount == 0 & evenCount != 0)// 如果都是成对出现,最少能拼出一个,如abba return 1; else return oddCount; } public static void main(String[] args) { // 输入包括一行,一个字符串s,字符串s长度length(1 ≤ length ≤ 1000). // s中每个字符都是小写字母 Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String s = sc.nextLine(); System.out.println(BackString(s)); } } }
var line = readline(); var count = 0; var hash = {}; for(var i=0, len=line.length; i<len; i++){ if(!hash[line[i]]){ hash[line[i]] = 1; } else{ hash[line[i]] += 1; } } for(var j in hash){ if(hash[j]%2 != 0) count += 1; } print (count);
#include <iostream> #include <string> using namespace std; //依次统计字符串中每个字符的个数,然后统计出现奇数次的字符个数,如果没有出现奇数次的字符,则回文串最少为1;否则,最少即为出现奇数次的字符个数 int main() { string str; cin >> str; int count[26]; for (int i = 0; i < 26; i++) count[i] = 0; for (auto x : str) count[x - 'a']++; int res = 0; for (int i = 0; i < 26; ++i) if (count[i] &1) res++; if (res == 0) res++; cout << res << endl; }
#include<iostream> #include<vector> #include<string> //#include <algorithm> using namespace std; int main() { string str; while (getline(cin,str)) { int count = 0; vector<int> ivec(26, 0); for (int i = 0; i < str.size(); i++) { for (int j = 0; j < 26; j++) { if (str[i] -'a'==j ) ivec[j]++; } } for (int i = 0; i < 26; i++) { if (ivec[i] % 2 != 0) count++; } cout << count; } return 0; }
Java 使用 HashMap 的代码示例
import java.util.HashMap; import java.util.Scanner; import java.util.Map.Entry; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); char[] a = s.toCharArray(); sc.close(); int cnt = 0; int remain = 0; HashMap<Character, Integer> frequencyCounter = new HashMap<>(); for (char var : a) { frequencyCounter.put(var, frequencyCounter.getOrDefault(var, 0) + 1); if (frequencyCounter.get(var) % 2 == 0) { frequencyCounter.put(var, 0); } } for (Entry<Character, Integer> entry : frequencyCounter.entrySet()) { int val = entry.getValue(); if (val != 0) { cnt++; } } System.out.println(cnt > 0 ? cnt : 1); //至少是 1 个 } }
#include<iostream> #include<string> #include<map> using namespace std; int main(void) { int count=0; string str; map<char,int> mp; bool even = true; while(cin>>str) { int size = str.size(); for(int i=0;i<size;i++) { mp[str[i]]++; } for(const auto &c :mp) { if(c.second%2) { count++; even =false; } } } count = even?1:count; cout<<count<<endl; return 0; system("pause"); }
#include<iostream> #include<string> #include<map> using namespace std; typedef map<char,int> _map; void work(){ string str; cin>>str; _map _map_; int number=0; for(auto &i:str){ ++_map_[i]; } auto beg=_map_.begin(); auto end=_map_.end(); while(beg!=end){ if((*beg).second%2!=0) ++number; ++beg; } cout<<number<<endl; } int main(){ work(); return 0; }
// javascript 版本
while(line = readline()) {
var obj = {};
var oddNum = 0;
// 记录每个字符的个数
for(var i = 0, len = line.length; i < len ; i++) {
if(obj[line[i]]) {
obj[line[i]]++;
} else {
obj[line[i]] = 1;
}
}
// 如果某个字符个数为奇数,则至少的回文串加一
for(var key in obj) {
if(obj[key] % 2 == 1) {
oddNum++;
}
}
if(oddNum == 0) {
oddNum = 1;
}
print(oddNum);
}