[algorithm] 숫자가 회문인지 어떻게 확인합니까?

Program / 글쓴이

숫자가 회문인지 어떻게 확인합니까?

모든 언어. 모든 알고리즘. (숫자를 문자열로 만든 다음 문자열을 되 돌리는 알고리즘 제외).

답변

이것은 프로젝트 오일러 문제 중 하나입니다 . Haskell에서 해결했을 때 정확히 제안한대로 숫자를 문자열로 변환하십시오. 문자열이 pallindrome인지 확인하는 것은 사소한 일입니다. 성능이 충분하다면 왜 더 복잡하게 만드는가? pallindrome이된다는 것은 수학적인 것이 아니라 어휘 적 속성입니다.

답변

주어진 숫자에 대해 :

n = num;
rev = 0;
while (num > 0)
{
    dig = num % 10;
    rev = rev * 10 + dig;
    num = num / 10;
}

만약 n == rev다음 num회문이다 :

cout << "Number " << (n == rev ? "IS" : "IS NOT") << " a palindrome" << endl;

답변

def ReverseNumber(n, partial=0):
    if n == 0:
        return partial
    return ReverseNumber(n // 10, partial * 10 + n % 10)

trial = 123454321
if ReverseNumber(trial) == trial:
    print("It's a Palindrome!")

정수에만 작동합니다. 부동 소수점 숫자 또는 선행 0을 고려해야하는지 여부는 문제 설명에서 명확하지 않습니다.

답변

사소한 문제가있는 대부분의 대답은 int 변수가 오버플로 될 수 있다는 것입니다.

http://articles.leetcode.com/palindrome-number/를 참조하십시오

boolean isPalindrome(int x) {
    if (x < 0)
        return false;
    int div = 1;
    while (x / div >= 10) {
        div *= 10;
    }
    while (x != 0) {
        int l = x / div;
        int r = x % 10;
        if (l != r)
            return false;
        x = (x % div) / 10;
        div /= 100;
    }
    return true;
}

답변

int is_palindrome(unsigned long orig)
{
    unsigned long reversed = 0, n = orig;

    while (n > 0)
    {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }

    return orig == reversed;
}

답변

각 개별 숫자를 스택으로 밀고 튀어 나옵니다. 앞뒤로 같은 경우 회문입니다.

답변

여분의 공간을 사용하지 않고이 문제를 해결 한 답변을 보지 못했습니다. 즉, 문자열이나 다른 정수를 사용하여 숫자를 바꾸거나 다른 데이터 구조를 사용하는 모든 솔루션을 보았습니다.

자바와 같은 언어는 정수 오버 플로우에 랩 어라운드 있지만,이 동작은 C. 같은 언어 (에 정의되지 자바 2147483647 (는 Integer.MAX_VALUE를) 반전 시도 )
해결 방법 문체, 꽤하지 않습니다, 긴 또는 무언가를 사용할 수 있지만, 할 수있다 그 접근법처럼.

회문 숫자의 개념은 숫자가 앞뒤로 동일하게 읽혀 져야한다는 것입니다. 큰. 이 정보를 사용하여 첫 번째 숫자와 마지막 숫자를 비교할 수 있습니다. 트릭은 첫 번째 숫자의 경우 순서가 필요합니다. 이것을 12321이라고 말하십시오. 이것을 10000으로 나누면 1을 얻을 수 있습니다. 후행 1은 10으로 mod를 가져 와서 검색 할 수 있습니다. 이제 이것을 232로 줄 (12321 % 10000)/10 = (2321)/10 = 232입니다. 이제 10000을 2 배로 줄여야합니다. 이제 Java 코드로 넘어갑니다.

private static boolean isPalindrome(int n) {
    if (n < 0)
        return false;

    int div = 1;
    // find the divisor
    while (n / div >= 10)
        div *= 10;

    // any number less than 10 is a palindrome
    while (n != 0) {
        int leading = n / div;
        int trailing = n % 10;
        if (leading != trailing)
            return false;

        // % with div gets rid of leading digit
        // dividing result by 10 gets rid of trailing digit
        n = (n % div) / 10;

        // got rid of 2 numbers, update div accordingly
        div /= 100;
    }
    return true;
}

숫자가 0 인 경우를 다루기 위해 Hardik 의 제안에 따라 편집했습니다 .