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种算法的时间复杂度均为： $O(n)$ 。

巴特西

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

最新文章

热门文章