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) —

推荐阅读：
关于奢侈　 爱你在心口难开（24至25章） 吴志俨　 珍惜生活的机会　 美丽的青海作文　 庆六一游园活动有感作文　 我的一次旅行　 一次有意义的教师节　 莲花池作文　 关于比的应用题练习　 和自然数有关的数学题　
评论列表
添加评论