C#LeetCode刷题之#9-回文数（Palindrome Number）

问题

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

输入: 121

输出: true

输入: -121

输出: false

解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

输入: 10

输出: false

解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:

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

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Input: 121

Output: true

Input: -121

Output: false

Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Input: 10

Output: false

Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

示例

public class Program {

    public static void Main(string[] args) {
        var x = 121;
        var res = IsPalindrome(x);
        Console.WriteLine(res);

        x = -567;
        res = IsPalindrome2(x);
        Console.WriteLine(res);

        x = 168861;
        res = IsPalindrome3(x);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static bool IsPalindrome(int x) {
        //计算反转值
        if(x < 0) return false;
        var res = 0L;
        var value = x;
        while(x != 0) {
            res = res * 10 + x % 10;
            x = x / 10;
        }
        return res == value;
    }

    private static bool IsPalindrome2(int x) {
        //反转字符串
        if(x < 0) return false;
        var arr = x.ToString().ToCharArray();
        Array.Reverse(arr);
        return x.ToString() == new string(arr);
    }

    private static bool IsPalindrome3(int x) {
        //栈
        if(x < 0) return false;
        var palindrome = x.ToString();
        var stack = new Stack<char>();
        for(var i = 0; i < palindrome.Length / 2; i++) {
            stack.Push(palindrome[i]);
        }
        //奇数时，往后移一位
        int pos = 0;
        if(palindrome.Length % 2 == 1) {
            pos = 1;
        }
        for(var i = palindrome.Length / 2 + pos; i < palindrome.Length; i++) {
            if(palindrome[i] != stack.Pop()) return false;
        }
        return true;
    }

}

以上给出3种算法实现，以下是这个案例的输出结果：

True
False
True

分析：

显而易见，以上3种算法的时间复杂度均为： 。