首页 > 试题广场 >

制造回文

[编程题]制造回文
  • 热度指数：279 时间限制：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

输出

3
算法知识视频讲解
添加回答
牛客210938800号头像 牛客210938800号
输出奇数个的字母的个数就行了。 
#include <iostream>
#include <vector>

using namespace std;

int main() {
    string str;
    cin >> str;
    
    vector<int> v(26, 0);
    for (char c : str)
        v[c - 'a']++;
    
    int odd = 0;
    for (int n : v)
        if (n % 2 == 1)
            odd++;
    
    cout << odd << endl;
}


编辑于 2021-09-02 17:28:52 回复(1)
不要叫我老哥头像 不要叫我老哥
如果所有字母均出现偶数次，输出不应该是1吗
发表于 2022-06-30 15:36:52 回复(0)
C-H-Y头像 C-H-Y 
//偶数可以任意结合，奇数一个就是一个
let lie = readline()
let solve = {}
for(let i = 0;i<lie.length;i++){
    if(solve[lie.charAt(i)]){
        solve[lie.charAt(i)]++
    }else{
        solve[lie.charAt(i)]=1
    }
}
let cnt = 0
for(let key of Object.keys(solve)){
    if(solve[key]%2) cnt++
}
if(cnt==0) cnt=1
console.log(cnt)

发表于 2022-02-08 22:04:38 回复(0)
天启殇瑕头像 天启殇瑕
个人理解：本质上是看字符串中每个字符出现的个数是奇数次还是偶数次，如果是偶数次一定可以构成一组回文串，奇数次一定会剩下一个无法组成回文串落单，但需要注意的是，如果可构成一组由偶数次字符的回文串时其中间可以带一个奇数次字符，因此最后需要再-1，否则不需要-1。 
import java.util.Scanner;
import java.util.HashMap;
 
public class Main
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        String inputString = scanner.next();
        HashMap<Character, Integer> countMap = new HashMap<>();
        for (int i = 0; i < inputString.length(); i++)
        {
            char ch = inputString.charAt(i);
            if (!countMap.containsKey(ch))
            {
                countMap.put(ch, 0);
            }
            countMap.put(ch, countMap.get(ch) + 1);
        }
        int result = 0;
        boolean evenAdded = false;
        boolean oddAdded = false;
        for (Character key : countMap.keySet())
        {
            int value = countMap.get(key);
            if ((value & 1) == 0 && !evenAdded)
            {
                result += 1;
                evenAdded = true;
            }
             
            if ((value & 1) == 1)
            {
                result += 1;
                oddAdded = true;
            }
        }
        if (evenAdded && oddAdded) result -= 1;
        System.out.println(result);
    }
}


发表于 2021-09-02 14:54:27 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 数据库工程师 信息技术岗 区块链 测试开发工程师 2019 2020 大数据开发工程师 数据分析师 Java工程师 牛客
上传者：小小
难度：
4条回答 3207浏览

热门推荐

通过挑战的用户

相关试题

制造回文

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号