面试题 01.04:回文排列

简介: 面试题 01.04:回文排列

题目

题目链接

给定一个字符串,编写一个函数判定其是否为某个回文串的排列之一。

回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。

回文串不一定是字典当中的单词。

示例1:

输入:"tactcoa"
输出:true(排列有"tacocat"、"atcocta",等等)

解题

方法一:哈希表

由于要可以排序成回文串,那么最多只能有一个字符的数量为奇数(放在最中间),其他均要为偶数

假设有n个字符,以下两种情况是可行的

  1. n个偶数
  2. n-1个偶数,1个奇数

因此只要判断 字符数量为奇数出现超过1次的,就不能排列为回文串。

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char,int> map;
        for(char c:s) map[c]++;
        int oddNum=0;
        for(pair<char,int> kv:map){
            if(kv.second%2==1){
                oddNum++;
                if(oddNum>1) return false;
            }
        }
        return true;
    }
};
相关文章
|
程序员
【Leetcode】面试题 01.02. 判定是否互为字符重排、面试题 01.04. 回文排列
目录 面试题 01.02. 判定是否互为字符重排 面试题 01.04. 回文排列
58 0
|
3月前
|
存储 Python
【面试题】排列序列
【面试题】排列序列
32 1
算法面试真题详解:下一个排列
算法面试真题详解:下一个排列
算法面试真题详解:下一个排列
|
机器学习/深度学习 存储 算法
大厂面试真题详解:带重复元素的排列
大厂面试真题详解:带重复元素的排列
大厂面试真题详解:带重复元素的排列
|
3月前
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
|
23天前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
54 2
|
27天前
|
JSON 安全 前端开发
第二次面试总结 - 宏汉科技 - Java后端开发
本文是作者对宏汉科技Java后端开发岗位的第二次面试总结,面试结果不理想,主要原因是Java基础知识掌握不牢固,文章详细列出了面试中被问到的技术问题及答案,包括字符串相关函数、抽象类与接口的区别、Java创建线程池的方式、回调函数、函数式接口、反射以及Java中的集合等。
24 0
|
3月前
|
XML 存储 JSON
【IO面试题 六】、 除了Java自带的序列化之外,你还了解哪些序列化工具?
除了Java自带的序列化,常见的序列化工具还包括JSON(如jackson、gson、fastjson)、Protobuf、Thrift和Avro,各具特点,适用于不同的应用场景和性能需求。