制造回文

题目来源：牛客网--制造回文

题目描述

牛牛有一些字母卡片,每张卡片上都有一个小写字母,所有卡片 组成一个字符串s。牛牛一直认为回文这种性质十分优雅,于 是牛牛希望用这些卡片拼凑出一些回文串,但是有以下要求:
1. 每张卡片只能使用一次
2. 要求构成的回文串的数量最少

牛牛想知道用这些字母卡片,最少能拼凑出多少个回文串。

例如: s = "abbaa",输出1,因为最少可以拼凑出"ababa"这一个回文串
s = "abc", 输出3,因为最少只能拼凑出"a","b","c"这三个回文串

输入描述

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

输出描述

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

输入示例

abc

输出示例

3

解题思路

把所有出现次数为偶数的字母拼凑成最大的回文串
如果存在最大的回文串，还可以在回文串中间放一个出现一次的字母
出去偶数个字母，剩下的都是单个出现的，（如果a出现了3次，两次算在大回文串里，一次算单个出现）
组成的最少回文串就等于 除去偶数个字母后的 单个字母的个数
最大回文串可以包裹一个单个出现的字母 但是本身算一个回文串 相当于不加不减

java代码

import java.util.Scanner;

public class HuiwenChuan {

    public static void main(String[] args) {
        int sum=0;
        Scanner in = new Scanner(System.in);
        //定义一个长度为26的数组
        int[] count = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        String s = in.next();
        in.close();
        char[] sc = s.toCharArray();
        //统计各字母出现的次数
        for(int i=0;i<sc.length;i++){
            int intc = sc[i]-'a';
            count[intc]++;
        }
        //如果字母出现的次数为偶数，肯定在最大的回文串里
        for(int i=0;i<count.length;i++){
            if(count[i]!=0 && count[i]%2 != 0){
                sum++;
            }
        }       
        System.out.println(sum);
    }
}

python代码

def huiwen():
    count = {}
    s = input()
    #使用字典统计
    for i in s:
        if i not in count:
            count[i] = 1
        else:
            count[i] += 1
    sum = 0
    for v in count.values():
        if(v%2 != 0):
            sum+=1
    print(sum)

huiwen()

#使用 list 统计
count = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    print(type(count))
    for i in s:
        index = ord(i) - 97
        count[index]+=1

python统计字母出现次数时，还用了上面这种方法，但是没有字典快。
原因：

python中list对象的存储结构采用的是线性表，因此其查询复杂度为O(n),dict类似对key进行了hash,然后再对hash生成一个红黑树进行查找，其查找复杂其实是O(logn),并不是所谓的O(1)。O(1)只是理想的实现。