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: true

Example 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　
评论列表
添加评论