首页 > 试题广场 >

制造回文

[编程题]制造回文

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

牛牛有一些字母卡片,每张卡片上都有一个小写字母,所有卡片组成一个字符串s。牛牛一直认为回文这种性质十分优雅,于是牛牛希望用这些卡片拼凑出一些回文串,但是有以下要求:
1、每张卡片只能使用一次
2、要求构成的回文串的数量最少
牛牛想知道用这些字母卡片,最少能拼凑出多少个回文串。
例如: s = "abbaa",输出1,因为最少可以拼凑出"ababa"这一个回文串
s = "abc", 输出3,因为最少只能拼凑出"a","b","c"这三个回文串

输入描述:

输入包括一行,一个字符串s,字符串s长度length(1 ≤ length ≤ 1000).
s中每个字符都是小写字母

输出描述:

输出一个整数,即最少的回文串个数。

示例1

输入

abc

输出

算法知识视频讲解

Java

CoderMore

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

编辑于 2017-07-26 17:46:01 回复(12)

元气の悟空

#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组奇数后  绝对带不上第二组奇数
 //综上所述  奇数决定一切.....

发表于 2017-08-02 19:14:19 回复(2)

Python

智．之水叶神

#解答思路：统计出现次数为奇数的字母个数

# -*- encoding:utf -*-
import sys

if __name__ == "__main__":

	s = str(sys.stdin.readline().strip())
	a={};res=0

	for i in s:
		if i in a:
			a[i]+=1
		else:
			a[i]=1
	for i in a.values():
		i=i%2
		res+=i
	print res

编辑于 2017-08-01 09:20:24 回复(2)

阿呆的呆

错误的原因是对最少的理解有误

这里的最少是所有的卡片都要用到，并且只能用一次，看最少能构成多少个回文数，比如bbbbbaa，可以构成abbbbba或者babbbab或者bbababb，因为所有卡片只能用一次，且必须都用到，所以最少能构成的回文数只能是这三个中的一个，最多的话就有7个 a b b b b b a ,单独一个字母也是回文数

发表于 2019-06-25 10:59:22 回复(0)

牛客125471号

while(s=readline()){

sum=plalindromeNum(s);

print(sum);

}

function plalindromeNum(s){

var num=new Array(26);

for (var i = 0; i < num.length; i++) {

num[i]=0;

}

var sum=0;

s=s.split("");

if (s.length>=1&&s.length<=1000) {

for (var i = 0; i < s.length; i++) {

if(s[i]<='z'&&s[i]>='a'){

num[parseInt(s[i], 16)-10]++;

}

for (var j = 0; j <26; j++) {

if(num[j]%2==1){

sum++;

}

if (sum==0) {

sum=1;

}

return sum;

}

发表于 2017-07-28 21:59:20 回复(0)

WillCarter

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

编辑于 2017-07-28 11:19:53 回复(0)

633_重庆森林

博客地址http://www.jianshu.com/p/3ac3c622a6dc

我们知道回文串的话，就是前后相等，那么一个字符至少出现两次，除了一种情况，就是可以有一个字符只出现一次，就是这个字符在中间。

所以，我们的思路就是统计出现奇数次字符的个数，假设只出现一个奇数次字符，那么其他都是偶数次的，那么直接奇数次的放中间就行了，所以至少是一种，如果没出现更好，也是一种，如果出现两个奇数次字符，那么一个拿去放中间，另一个只能单独领出来作为一个回文串，所以至少要两种，如果出现三个奇数次字符，那么就至少要三种。所以问题就变成统计奇数次字符出现的个数

代码

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

发表于 2017-07-27 18:25:38 回复(0)

SaltyFish

具体思路为：

1.统计26个字符各自出现的次数

2.回文串的个数取决于奇数次数字符的个数，如aba，b只有一次，可以放在中间组成回文串，但abca，出现了两个奇数次的字符，又由于每个字符只能使用一次，那么只能有：aba，c，于是就是两种，依此类推。

3.如果都是偶数次数的话必然可以组成一个最长的回文串，长度为1。

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

发表于 2017-07-26 15:13:28 回复(0)

Python

牛客J

```
# -*- coding:utf-8 -*-
import sys
S=sys.stdin.readline().strip('\n')
setS=set(S)
result=0
for i in setS:
    if S.count(i) & 1: #判断S中的某个字符个数是否为奇数
        result +=1
result=1 if result==0 else result
print(result)

编辑于 2017-07-27 14:48:42 回复(1)

Java

pomay

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

编辑于 2017-08-09 19:40:13 回复(2)

哼哼一直在

前端铁头娃的JS实现。

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

思路嘛，其实一个字符串可以构成的回文数量，是取决于这个字符串中总数为奇数的字符的个数。

额，这句话有点绕口。举个栗子，"abc" 可以构成的回文是 3 ，因为字符串中总数为奇数的字符的个数是3， a ， b， c。

所以解题方法就是统计字符串中字符总数为奇数的那些字符的数量。。

发表于 2017-07-26 09:45:36 回复(3)

笑忘书生

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

发表于 2017-07-26 08:47:20 回复(5)

折枝销落

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

发表于 2017-07-25 22:43:02 回复(0)

梦箱

表示没理解 “要求构成的回文串的数量最少”这一句话，对于第一个输入abbaa；可构成的回文串ababa和baaab，所以最少可以构成两种？有没有大神帮我解释下这题是什么意思？？？？

发表于 2017-07-25 22:37:34 回复(5)

Java

jalr4ever

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

发表于 2019-06-20 10:14:17 回复(0)

AlexReadyZ

#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");
}

编辑于 2018-05-14 18:55:41 回复(0)

Sunward

  思路：把输入字符串的字符存放到一个Map中，键是字符串的每一个字符，值是该字符在字符串中出现的次数。 
          1.所有的字符都加入到Map当中后，对Map的值进行遍历，如果是奇数，count值+1
 
          2.如果是偶数，不做改变
 
  
 
  importjava.util.Scanner; 
  importjava.util.Map; 
  importjava.util.HashMap; 
  publicclassMain{ 
      publicstaticintminHuiwen(String str){ 
          intcount = 0; 
          //Map存放每个字母的个数 
          Map<String,Integer> map = newHashMap<String,Integer>(); 
          intlength = str.length(); 
          for(inti=0;i < 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 size = map.size(); 
          if(size == length){ 
              count = size; 
          }else{ 
              for(Integer temp: map.values()){ 
                  //如果该字母是奇数 
                  if(temp%2!=0){ 
                      count++; 
                  } 
              } 
          } 
          return count; 
            
      } 
      publicstaticvoidmain(String[] args){ 
            Scanner scanner = newScanner(System.in); 
            String str = scanner.nextLine(); 
            System.out.println(minHuiwen(str)); 
        }  
        
  } 

发表于 2018-03-16 09:47:46 回复(0)

志浩

s = list(input())
s_set = set(s)
k = 0
num = 0
for i in s_set:
for j in s:
if i == j:
k += 1
if k % 2 == 0:
num = num
else:
num += 1
k = 0
if num == 0:
num = 1
print(num)

发表于 2017-11-24 17:01:17 回复(0)

YuKai

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

发表于 2017-10-08 21:07:19 回复(0)

perhaps789

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

发表于 2017-09-10 21:16:16 回复(0)