首页 > 试题广场 >

制造回文

[编程题]制造回文

热度指数：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

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)

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)

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)

Java

被遗忘的左手

/*
 * 具体思路：统计字符串中字符出现次数为奇数的字符个数
 */
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 s = sc.nextLine(); 
        int count = 0;
        Map<Character, Integer> result = getCharMaps(s);
        for (Integer value : result.values()) {  
            if(value % 2 == 1) {
        	count++;
            }
        }  
        System.out.println(count);
        sc.close();
        
   } 
    public static Map<Character, Integer> getCharMaps(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            Integer count = map.get(c);
            map.put(c, count == null ? 1 : count + 1);
        }
        return map;
    }
}

编辑于 2017-07-25 21:24:27 回复(0)