前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[编程题] 制造回文分析代码

[编程题] 制造回文分析代码

作者头像
desperate633
发布2018-08-22 16:18:09
3340
发布2018-08-22 16:18:09
举报
文章被收录于专栏:desperate633

来源:牛客网2017年校招全国统一模拟笔试(第五场)编程题集合

时间限制:1秒 空间限制:32768K

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

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

输入例子1: abc

输出例子1: 3

分析

这道题需要一点思路。

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

代码

代码语言:javascript
复制
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 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 分析
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档