Algorithms to Determine a Palindrome Number

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

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

推荐阅读：
How to Turn a Binary Search Tree into a Increasing Order Search 　 How to Free TCP/UDP Port on Windows Using netstat and taskkill?　 The Review of cozmo robot from Anki　 Scaling Digital Marketing Agencies Through White Label Solutions　 How to Solve the Lemonade Change Problem by Simulation Algorithm　 How to Sum within A Range in a Binary Search Tree?　 Magik Says Happy Valentines by Drawing a Heart to Console　 Cloud-Ready Infrastructure Optimization　 Freedom of Speech Isn’t So Free　 10 Things You Should Do When Starting an Online Store　
评论列表
添加评论