Algorithms to Determine a Palindrome Number
- 时间:2020-09-12 10:06:27
- 分类:网络文摘
- 阅读:93 次
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:
Input: 121
Output: trueExample 2:
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.Example 3:
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?Hints:
Beware of overflow when you reverse the integer.
Determine a Palindrome Number by Converting to String
Converting the number to string should be the fairly easiest approach. And there is no risks to overflow the integer when converting to a string. After converting to string, we can reverse the string and if the original number is a palindrome, the reversed version (string) should be exactly the same.
C++:
1 2 3 4 5 6 7 8 9 10 11 | class Solution { public: bool isPalindrome(int x) { string s = std::to_string(x); // we can also do the following // string r = s; // std::reverse(begin(r), end(r)); string r(rbegin(s), rend(s)); return r == s; } }; |
class Solution { public: bool isPalindrome(int x) { string s = std::to_string(x); // we can also do the following // string r = s; // std::reverse(begin(r), end(r)); string r(rbegin(s), rend(s)); return r == s; } };
Java – we can use the StringBuilder’s method reverse() to reverse the string buffer:
1 2 3 4 5 6 7 | class Solution { public boolean isPalindrome(int x) { String s = String.valueOf(x); String r = new StringBuilder(s).reverse().toString(); return s.equals(r); } } |
class Solution { public boolean isPalindrome(int x) { String s = String.valueOf(x); String r = new StringBuilder(s).reverse().toString(); return s.equals(r); } }
Javascript: we convert the number x to string using new String() then, we split into array, reverse it, and join as a reversed string.
1 2 3 4 5 6 7 8 | /** * @param {number} x * @return {boolean} */ var isPalindrome = function(x) { const r = (new String(x)).split("").reverse().join(""); return r == x; }; |
/** * @param {number} x * @return {boolean} */ var isPalindrome = function(x) { const r = (new String(x)).split("").reverse().join(""); return r == x; };
Python: We can reverse a string in a few ways: [::-1] is the Pythonic way.
1 2 3 4 5 | class Solution: def isPalindrome(self, x: int) -> bool: s = str(x) r = s[::-1] return s == r |
class Solution: def isPalindrome(self, x: int) -> bool: s = str(x) r = s[::-1] return s == r
Of course, we can compare the characters at both ends in a classic way.
C++:
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: bool isPalindrome(int x) { string s = std::to_string(x); for (int i = 0; i < s.size() / 2; ++ i) { if (s[i] != s[s.size() - 1 - i]) { return false; } } return true; } }; |
class Solution { public: bool isPalindrome(int x) { string s = std::to_string(x); for (int i = 0; i < s.size() / 2; ++ i) { if (s[i] != s[s.size() - 1 - i]) { return false; } } return true; } };
Java:
1 2 3 4 5 6 7 8 9 10 11 | class Solution { public boolean isPalindrome(int x) { String s = String.valueOf(x); for (int i = 0; i < s.length(); ++ i) { if (s.charAt(i) != s.charAt(s.length() - i - 1)) { return false; } } return true; } } |
class Solution { public boolean isPalindrome(int x) { String s = String.valueOf(x); for (int i = 0; i < s.length(); ++ i) { if (s.charAt(i) != s.charAt(s.length() - i - 1)) { return false; } } return true; } }
Javascript:
1 2 3 4 5 6 7 8 9 10 11 12 13 | /** * @param {number} x * @return {boolean} */ var isPalindrome = function(x) { const r = x + ""; for (let i = 0; i < r.length; ++ i) { if (r[i] != r[r.length - 1 - i]) { return false; } } return true; }; |
/** * @param {number} x * @return {boolean} */ var isPalindrome = function(x) { const r = x + ""; for (let i = 0; i < r.length; ++ i) { if (r[i] != r[r.length - 1 - i]) { return false; } } return true; };
Python:
1 2 3 4 5 6 7 | class Solution: def isPalindrome(self, x: int) -> bool: s = str(x) for i in range(len(s) // 2): if s[i] != s[len(s) - i - 1]: return False return True |
class Solution: def isPalindrome(self, x: int) -> bool: s = str(x) for i in range(len(s) // 2): if s[i] != s[len(s) - i - 1]: return False return True
Converting to strings require O(logN) space, and O(logN) time.
Determining the Palindrome Number by Extracting the Digits
We can repeatedly extract the right-most digit (least significant) and construct the reversed integer. However, we need to pay attention not to overflow the integer.
All negative numbers are not palindromes.
C++:
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: bool isPalindrome(int x) { if (x < 0) return false; int64_t s = x, r = 0; while (s > 0) { r = r * 10 + s % 10; s /= 10; } return x == r; } }; |
class Solution { public: bool isPalindrome(int x) { if (x < 0) return false; int64_t s = x, r = 0; while (s > 0) { r = r * 10 + s % 10; s /= 10; } return x == r; } };
Java:
1 2 3 4 5 6 7 8 9 10 11 | class Solution { public boolean isPalindrome(int x) { if (x < 0) return false; long s = x, r = 0; while (s > 0) { r = r * 10 + s % 10; s /= 10; } return x == r; } } |
class Solution { public boolean isPalindrome(int x) { if (x < 0) return false; long s = x, r = 0; while (s > 0) { r = r * 10 + s % 10; s /= 10; } return x == r; } }
Javascript: We need to use Math.floor to discard the fraction part for the integer division.
1 2 3 4 5 6 7 8 9 10 11 12 13 | /** * @param {number} x * @return {boolean} */ var isPalindrome = function(x) { if (x < 0) return false; let s = x, r = 0; while (s > 0) { r = r * 10 + s % 10; s = Math.floor(s / 10); } return x === r; }; |
/** * @param {number} x * @return {boolean} */ var isPalindrome = function(x) { if (x < 0) return false; let s = x, r = 0; while (s > 0) { r = r * 10 + s % 10; s = Math.floor(s / 10); } return x === r; };
Python: beware we need to use // to do the integer division.
1 2 3 4 5 6 7 8 9 10 | class Solution: def isPalindrome(self, x: int) -> bool: if x < 0: return False r = 0 s = x while s > 0: r = r * 10 + s % 10 s //= 10 return x == r |
class Solution: def isPalindrome(self, x: int) -> bool: if x < 0: return False r = 0 s = x while s > 0: r = r * 10 + s % 10 s //= 10 return x == r
Repeatedly extracting digits cost O(logN) time but the space usage is constant.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:Bruteforce Algorithm to Compute the Maxmium Powerful Digit Sum u 4 Frequently Discussed SEO Myths Exposed 3 Reasons Why Graphic Designers Need to Self-Promote through Ins How to Split a String in C++? The Best Instagram Feed WordPress Plugins to Use Trie Class Data Structure in Python How to Monitor the CPU Temperature of Raspberry PI using Python Listen to what an SEO expert has to say about its benefits Depth First Search Algorithm to Compute the Smallest String Star Algorithm to Check if All Points are On the Same Line
- 评论列表
-
- 添加评论