笔试强训之每日一题(七)

x33g5p2x  于2022-02-07 转载在 其他  
字(1.1k)|赞(0)|评价(0)|浏览(114)

笔试强训之每日一题(七)

判断是否互为字符重排

题目链接

题目描述

给定两个字符串 s1 和 s2,请编写一个程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。

示例 1

输入: s1 = “abc”, s2 = "bca"
输出: true

示例 2

输入: s1 = “abc”, s2 = "bad"
输出: false

题目思路

当两个字符串的字符一样时,利用哈希的思想,将s1中对应字符在哈希表中对应位置++,将将s1中对应字符在哈希表中对应位置–,如果最后哈希表中的数组都为0,则确定其中一个字符串的字符重新排列后,能变成另一个字符串。否则不能

题目代码

class Solution {
public:
    bool CheckPermutation(string s1, string s2) 
    {
        int arr1[128] = {0};
        if(s1.size()!=s2.size())
        {
            return false;
        }
        for(int i = 0;i<s1.size();i++)
        {
            arr1[s1[i]]++;
            arr1[s2[i]]--;
        }
        for(int i = 0;i < 128;i++)
        {
            if(arr1[i]!=0)
            {
                return false;
            }
        }
        return true;
    }
};

回文排列

题目链接

题目描述

给定一个字符串,编写一个函数判定其是否为某个回文串的排列之一。回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。回文串不一定是字典当中的单词。

示例1

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

题目思路

当字符串当中有两个或两个以上的奇数次字符时,则该字符串的重新排列不会是回文串,反之则该字符串的重新排列会是回文串,我们同样利用哈希的思想来解决,先统计字符的次数,然后看次数是奇数的有几个,如果有两个或两个以上,则不会是回文串,反之,则会是回文串。

题目代码

class Solution {
public:
    bool canPermutePalindrome(string s) {
        //哈希
        if(s.size() == 0)
        {
            return false;
        }
        int arr[128] = {0};
        for(int i = 0;i<s.size();i++)
        {
            arr[s[i]]++;//统计次数
        }
        int count = 0;
        for(int i = 0;i<128;i++)
        {
            if((arr[i]%2) == 1)//次数是奇数
            {
                count++;
            }
        }
        return count < 2;
    }
};

相关文章