算法研究-回文数

这个系列是笔者练习LeetCode上的算法题的记录&分享

题目

回文数（Palindrome Number）

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:
输入: 121
输出: true

示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:你能不将整数转为字符串来解决这个问题吗？

题解

需要注意的点：
1. 传入的是一个数字，需要判断的是一个数字
2. 比较容易发现，负数都不是回文数，尾数是0的数字也都不是回文数
3. 对于长度是奇偶数的情况处理

第一种：使用转为字符串的方法判断
先判断特殊情况，再转为字符串然后头尾循环判断

public bool IsPalindrome(int x) {
    if(x<0 || (x % 10 == 0 && x != 0)) return false;
    string _x = x.ToString();
    int count = _x.Length - 1;
    if (count == 0) return true;
    for (int i = 0; i < _x.Length; i++)
    {
        if (_x[i] != _x[count - i])
        {
            return false;
        }
        else if(i >= count/2){
            return true;
        }
    }
    return false;
}

第二种，使用数学方法，不转为字符串的形式判断
首先也是特殊情况的处理（负数、尾数为0）
根据回文的特性，可以将数字对半拆开，将右边的数字反转
例如：
123321 => 123 | 321 => 123 | 321
然后判断，左右的数字是否相等，如果相等则为回文

此处对于长度为奇数的数字处理为，不管中间的数字，无论中间的数字是什么都不影响左右两边的数字判断

public bool IsPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    int leftNumber = x, rightNumber = 0;
    while (leftNumber > rightNumber)
    {
        rightNumber = (rightNumber * 10) + (leftNumber % 10);
        leftNumber /= 10;
    };
    return leftNumber == rightNumber || leftNumber  == rightNumber / 10;
}