
问题
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
输入: 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种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3840。