【Leetcode】面试题 01.02. 判定是否互为字符重排、面试题 01.04. 回文排列

逃离我推掉我的手 2024-03-29 16:09 62阅读 0赞

>  作者：一个喜欢猫咪的的程序员
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![7d63d497b5114103b3dd7633a1ba4731.jpeg][]
> 
> --------------------
> 
> **目录**
> 
> 面试题 01.02. 判定是否互为字符重排 
> 
> 面试题 01.04. 回文排列
> 
> --------------------

## 面试题 01.02. 判定是否互为字符重排 ##

[面试题 01.02. 判定是否互为字符重排![icon-default.png_t_MBR7][]https://leetcode.cn/problems/check-permutation-lcci/][01.02. _icon-default.png_t_MBR7_https_leetcode.cn_problems_check-permutation-lcci] 题目描述：

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

示例：

![3d2f8f98355847af8fe68779a7f11624.png][]

--------------------

思路：

**设定两个下标n1,n2来遍历两个字符串，设s2的长度为size，判断s1\[n1\]==s2\[n2\],如果有交换s2中n2下标指向的字符和字符串的最后一个字符，n1++， size--；**

**注意极端情况：**

**s1的长度不等于s2的长度，返回false。**

代码：

void swap(char* ch1, char* ch2)
    {
        char tmp = *ch1;
        *ch1 = *ch2;
        *ch2 = tmp;
    }
    bool CheckPermutation(char* s1, char* s2) {
        int n1 = 0;
        int size = strlen(s2);
        if(strlen(s1)!=strlen(s2))
        return false;
        while (n1 < strlen(s1))
        {
            int num = size;
            int n2 = 0;
            while (n2 < size)
            {
                if (s1[n1] == s2[n2])
                {
                    if (n2 != size - 1)
                    swap(&s2[n2],&s2[size-1]);
                    size--;
                    n1++;
                    break;
                }
                n2++;
            }
            if (size == num)
            {
                return false;
            }
        }
        return true;
    }

--------------------

## 面试题 01.04. 回文排列 ##

[面试题 01.04. 回文排列![icon-default.png_t_MBR7][]https://leetcode.cn/problems/palindrome-permutation-lcci/][01.04. _icon-default.png_t_MBR7_https_leetcode.cn_problems_palindrome-permutation-lcci]

题目描述：

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

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

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

示例：

![ec587017cff94fef8e622b575a7ba644.png][]

--------------------

思路：

**注意回文串的特点是奇数个字符的数量要么是1要么0.**

**剩余的思想跟上题差不多**

**代码：**

void swap(char* ch1, char* ch2)
    {
        char tmp = *ch1;
        *ch1 = *ch2;
        *ch2 = tmp;
    }
    bool canPermutePalindrome(char* s) {
        int num = 0;//奇数字符个数
        int cur = 0;
        int size = strlen(s);
        if (size == 1)
            return true;
        while (cur < size)
        {
            int m = 1;//个数
            int i = cur+1;
            while (i < size)
            {
                if (s[cur] == s[i])
                {
                    m++;
                    swap(&s[i], &s[size - 1]);
                    size--;
                }
                i++;
            }
            if (m % 2 == 1)
                num++;
            cur++;
        }
        if (num == 0 || num == 1)
            return true;
        else
            return false;
    }

--------------------

[7d63d497b5114103b3dd7633a1ba4731.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/2d9da8531b5e4e969886a0d3f9a183f6.png
[icon-default.png_t_MBR7]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/0f440cc11db84d5a8b0b3ca5b1ff3569.png
[01.02. _icon-default.png_t_MBR7_https_leetcode.cn_problems_check-permutation-lcci]: https://leetcode.cn/problems/check-permutation-lcci/
[3d2f8f98355847af8fe68779a7f11624.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/ab4d4c2c51dd42feb5a201e520d2fcfa.png
[01.04. _icon-default.png_t_MBR7_https_leetcode.cn_problems_palindrome-permutation-lcci]: https://leetcode.cn/problems/palindrome-permutation-lcci/
[ec587017cff94fef8e622b575a7ba644.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/0a1263a1cfbf47d6a12e3487d1229b6d.png