Algorithms to Determine a Palindrome Number

  • 时间：2020-09-12 10:06:27
  • 分类：网络文摘
  • 阅读：157 次

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

推荐阅读：
What Should You Blog About During the Pandemic and Beyond?　 6 Tips For Starting a Business During a Pandemic　 Will Your Blog be affected by the Current Facebook Ad Boycott?　 Unobvious Life Hacks for Ads Optimization in Google　 Essential Traits That Will Help Bloggers Work From Home Successf　 Examining the Physical and Mental Health of Writers and Bloggers　 How will Blogging Change after the Pandemic?　 Digital Relationships: 5 Tips For Building A Better Veterinary B　 The 2020 Pandemic Further Boosts Earnings and Influence of Blogg　 What to Do When Your Blog Gets Too Big for You Alone　
评论列表
添加评论