面试题 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
【面试题】排列序列
【面试题】排列序列
35 1
算法面试真题详解:下一个排列
算法面试真题详解:下一个排列
算法面试真题详解:下一个排列
|
机器学习/深度学习 存储 算法
大厂面试真题详解:带重复元素的排列
大厂面试真题详解:带重复元素的排列
大厂面试真题详解:带重复元素的排列
|
3月前
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
|
10天前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
12天前
|
存储 缓存 Java
大厂面试必看!Java基本数据类型和包装类的那些坑
本文介绍了Java中的基本数据类型和包装类,包括整数类型、浮点数类型、字符类型和布尔类型。详细讲解了每种类型的特性和应用场景,并探讨了包装类的引入原因、装箱与拆箱机制以及缓存机制。最后总结了面试中常见的相关考点,帮助读者更好地理解和应对面试中的问题。
37 4
|
1月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
67 2