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

来源:牛客网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

分析

这道题需要一点思路。

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

代码

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python读书笔记

《python算法教程》Day3 - 递归递归简介代码示例

这是《python算法教程》的第3篇读书笔记。由于之前看书的效率太低了,所以拖了一个多星期才写第三篇读书笔记。这次主要简单总结一下递归(recursion)。 ...

3048
来自专栏趣谈编程

快速排序(基础版)

1643
来自专栏算法channel

详解连续子数组的最大累乘之动态规划解法

此题出自LeetCode:152. Maximum Product Subarray,大意求子数组的最大值,举例子1:

2200
来自专栏决胜机器学习

《编程之美》读书笔记(一)——中国象棋将帅有效位置

《编程之美》读书笔记(一) ——中国象棋将帅有效位置 (原创内容,转载请注明来源,谢谢) 一、问题 ? 如上述棋盘,假设将为点A,帅为点B。将只能在d10...

4156
来自专栏TensorFlow从0到N

讨厌算法的程序员 1 - 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生...

3424
来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继...

901
来自专栏Android机动车

数据结构学习笔记——总述

数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。

691
来自专栏大数据学习笔记

Java程序设计(Java9版):第3章 流程控制

第3章 流程控制 学习要点 掌握三种流程控制 掌握简单的输入输出 了解三种循环设计方法 掌握数组、字符串和枚举类型 3.1 面向过程介绍...

3687
来自专栏大数据风控

Python中如何进行数据分组

数据分组 根据数据分析对象的特征,按照一定的数值指标,把数据分析对象划分为不同的区间进行研究,以揭示其内在联系和规律性。 cut 函数: cut(series,...

3567
来自专栏专注数据中心高性能网络技术研发

[LeetCode]Array主题系列{35,39,40,48题}

1. 内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解...

3518

扫码关注云+社区

领取腾讯云代金券