gpt4 book ai didi

LeetCode题集-9-回文数

转载 作者:撒哈拉 更新时间:2024-12-20 10:47:52 57 4
gpt4 key购买 nike

题目:给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false .

回文数 。

是指正序(从左向右)和倒序(从右向左)读都是一样的整数.

例如,121 是回文,而 123 不是.

01、反转字符串法

此题我第一反应就是直接把整数转为字符串,然后通过字符串Reverse方法,反转字符串,最后再比较整数字符串和反转后字符串是否相等即可得出结果。代码实现如下:

//反转字符串法
public static bool IsPalindrome1(int x)
{
    var strX = x.ToString();
    //反转字符串
    var reversedStr = new string(strX.Reverse().ToArray());
    //比较入参和反转后字符串是否相等
    return strX == reversedStr;
}

02、反转字符数组法

此方法和反转字符串一脉相通,只是实现选用了不同的方法,此法是把整数字符串转为字符数组,然后再深拷贝一份用于反转的字符数组,通过Array.Reverse方法进行反转,最后通过SequenceEqual比较两个字符数组值是否相等.

其中有以下两个点容易出错:

其一因为字符数组是引用类型必须使用深拷贝,而不能像字符串那样直接赋值,深拷贝有很多种办法ToArray是比较简洁的方式; 。

其二因为本题要求是比较两个字符数组的值是否相等,因此不能直接使用==比较; 。

具体实现代码如下:

//反转字符数组法
public static bool IsPalindrome2(int x)
{
    //x转为字符数组
    var strXChars = x.ToString().ToCharArray();
    //深拷贝一份字符数组用于反转
    var reversedChars = strXChars.ToArray();
    //反转字符数组
    Array.Reverse(reversedChars);
    //比较入参和反转后字符串是否相等
    return strXChars.SequenceEqual(reversedChars);
}

03、双指针法

前面两个方法本质上都是在使用转为字符串的方法处理,我们进阶一下尝试不用转字符串的方式来处理.

虽然不用转字符串的方式,但是我们可以借鉴其思想,比如前面题目处理回文子串思想。我们是否可以像字符串一样,从整数的两端由外向内逐一比较两端的数字,如果都相等则结果为回文数.

在不转成字符串的情况下,怎么拿到整数的首尾数字呢?尾数字可以通过取余的方式获取,那么首数字要怎么获取呢?

比如12345,如果我们想要取到首数字1,那么就可以通过12345/10000=1获取,那么10000要怎么获取呢?我们可以对整数进行循环取整,假设除数div=1,取1次整则div乘10,最终得到10000.

然后我们就可以通过x/div取整获取左边数字,通过x%10取余获取右边数字,然后比较左右是否相等,如果相等则把左右两边已比较过的数字去掉,对剩下的整数继续比较,直至所有数字完成比较.

具体实现代码如下:

//双指针
public static bool IsPalindrome3(int x)
{
    //负数肯定不是回文数
    if (x < 0)
    {
        return false;
    }
    //定义除数变量,用于从前截取数字
    var div = 1;
    //通过循环对x取整,然后在乘10
    //求得可以获取x第1位数字对应的除数
    //比如12345,则除数为10000
    while (x / div >= 10)
    {
        div *= 10;
    }
    while (x > 0)
    {
        //获取左边数字
        var left = x / div;
        //获取右边数字
        var right = x % 10;
        //比较左右数字是否相等
        if (left != right)
        {
            //不相等则直接返回
            return false;
        }
        //去掉左边数字
        x = x % div;
        //去掉右边数字
        x = x / 10;
        //因为去掉两个数字
        //所以除数需除100
        div /= 100;
    }
    //为回文数字
    return true;
}

04、反转全部数字法

双指针法可能逻辑上比较复杂些,那么我们是否可以像字符串一样把整个整数反转过来呢?

其实反转整个数字其实也很简单,可以借鉴上一个方法中,取整取余的方式,把整个整数反转过来,然后直接比较反转后的整数和原整数是否相等即可.

其中需要注意的是一个32位整数反转后可能会导致溢出,因此反转结果我们需要使用64位整数存储。具体实现代码如下:

//反转全部数字
public static bool IsPalindrome4(int x)
{
    //负数肯定不是回文数
    if (x < 0)
    {
        return false;
    }
    //把入参赋值给临时变量
    int temp = x;
    //反转结果
    long reversed = 0;
    //从后往前循环处理整数中的每一个数字
    while (x != 0)
    {
        //获取x的个位数字
        int digit = temp % 10;
        //移除x的个位数字
        temp = temp / 10;
        //把x的个位数字拼接到反转结果的个位上
        reversed = reversed * 10 + digit;
    }
    //直接比较入参和反转后的整数是否相等
    return x == reversed;
}

05、反转一半数字

其实并不需要反转完所有数字我们才能知道是否是回文数,只需要反转完一半我们即可以知道是否为回文数.

比如输入 1221,我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”,并将其与前半部分 “12” 进行比较,因为二者相同,我们得知数字 1221 是回文.

此方法关键点是判断何时结束,以及是回文数的条件是啥.

对于反转一半数字,我们必须考虑到整数的长度是奇数还是偶数,如下图:

由此可以得出当x > revertedNumber时可以结束比较,而满足回文数的条件分奇偶两种情况x == revertedNumber 或 x == revertedNumber / 10.

具体代码实现如下:

//反转一半数字
public static bool IsPalindrome5(int x)
{
    //特殊情况:
    //当 x < 0 时,x 不是回文数。
    //同样地,如果数字的最后一位是 0,为了使该数字为回文,
    //则其第一位数字也应该是 0,只有 0 满足这一属性
    if (x < 0 || (x % 10 == 0 && x != 0))
    {
        return false;
    }
    var revertedNumber = 0;
    while (x > revertedNumber)
    {
        //获取x的个位数字
        var digit = x % 10;
        //把x的个位数字拼接到反转结果的个位上
        revertedNumber = revertedNumber * 10 + digit;
        //移除x的个位数字
        x /= 10;
    }
    //当数字长度为奇数时,例如,当输入为 12321 时,
    //在 while 循环的末尾我们可以得到 x = 12,revertedNumber = 123,
    //因此可得 x == revertedNumber/10
    //而当数字长度为偶数时,则 x == revertedNumber。
    return x == revertedNumber || x == revertedNumber / 10;
}

注:测试方法代码以及示例源码都已经上传至代码库,有兴趣的可以看看。https://gitee.com/hugogoos/Planner 。

最后此篇关于LeetCode题集-9-回文数的文章就讲到这里了,如果你想了解更多关于LeetCode题集-9-回文数的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

57 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com