Как проверить, является ли число палиндром?

Как проверить, является ли число палиндром?

Любой язык. Любой алгоритм. (за исключением алгоритма создания числа a и затем изменения строки).

30 Solutions collect form web for “Как проверить, является ли число палиндром?”

Это одна из проблем проекта Эйлера . Когда я решил это в Haskell, я сделал именно то, что вы предлагаете, преобразуйте число в String. Тогда тривиально проверить, что строка является паллиндром. Если он работает достаточно хорошо, то зачем беспокоиться о его усложнении? Быть паллиндром – это лексическое свойство, а не математическое.

Для любого заданного числа:

  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!") 

Работает только для целых чисел. Из описания проблемы неясно, следует ли учитывать числа с плавающей запятой или ведущие нули.

Выше большинства ответов, имеющих тривиальную проблему, является то, что переменная int может переполняться.

См. http://leetcode.com/2012/01/palindrome-number.html.

 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; } 

Нажимайте каждую отдельную цифру на стек, а затем выталкивайте их. Если это то же самое вперед и назад, это палиндром.

Я не заметил никаких ответов, которые решили эту проблему, не используя лишнее пространство, т. Е. Все решения, которые я видел, использовали либо строку, либо другое целое число, чтобы изменить число или некоторые другие структуры данных.

Хотя такие языки, как Java, обертываются при переполнении целочисленными значениями, это поведение не определено в таких языках, как C. [ Попробуйте перевернуть 2147483647 (Integer.MAX_VALUE) в Java ]. Обходным решением может быть использование длинного или что-то, но, стилистически, я не совсем как этот подход.

Теперь понятие палиндромного числа состоит в том, что число должно читаться одинаково вперед и назад. Отлично. Используя эту информацию, мы можем сравнить первую цифру и последнюю цифру. Trick для первой цифры нам нужен порядок числа. Скажем, 12321. Разделив это на 10000, мы получим ведущий 1. Конечный 1 можно получить, взяв mod с 10. Теперь, чтобы уменьшить это до 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; } 

Отредактировано в соответствии с предложением Хардика , чтобы охватить случаи, когда в номере есть нули.

кроме того, чтобы сделать число a строкой, а затем изменить строку.

Зачем отказываться от этого решения? Его легко реализовать и прочитать . Если вас попросили без компьютера под рукой, то ли 2**10-23 является десятичным палиндром, вы наверняка проверите его, написав его в десятичной форме.

По крайней мере, на Python лозунг «строковые операции медленнее, чем арифметика» на самом деле является ложным. Я сравнил арифметический алгоритм Сминка с простым перестановкой строк int(str(i)[::-1]) . Существенной разницы в скорости не было – произошло чередование строк немного быстрее.

На языках низкого уровня (C / C ++) лозунг может выполняться, но один из них рискует переполнением ошибок с большими числами.


 def reverse(n): rev = 0 while n > 0: rev = rev * 10 + n % 10 n = n // 10 return rev upper = 10**6 def strung(): for i in range(upper): int(str(i)[::-1]) def arithmetic(): for i in range(upper): reverse(i) import timeit print "strung", timeit.timeit("strung()", setup="from __main__ import strung", number=1) print "arithmetic", timeit.timeit("arithmetic()", setup="from __main__ import arithmetic", number=1) 

Результаты в секундах (лучше – ниже):

strung 1.50960231881
арифметика 1.69729960569

В Python существует быстрый, итеративный способ.

 def reverse(n): newnum=0 while n>0: newnum = newnum*10 + n % 10 n//=10 return newnum def palindrome(n): return n == reverse(n) 

Это также предотвращает проблемы памяти с рекурсией (например, ошибка StackOverflow в Java)

Я ответил на проблему Эйлера, используя очень грубый путь. Естественно, на дисплее появился гораздо более умный алгоритм, когда я попал в новый разблокированный связанный с ним форум. А именно, у члена, который проходил ручку Begoner, был такой новый подход, что я решил переопределить свое решение, используя его алгоритм. Его версия была в Python (с использованием вложенных циклов), и я повторно реализовал ее в Clojure (используя один цикл / recur).

Здесь для вашего развлечения:

 (defn palindrome? [n] (let [len (count n)] (and (= (first n) (last n)) (or (>= 1 (count n)) (palindrome? (. n (substring 1 (dec len)))))))) (defn begoners-palindrome [] (loop [mx 0 mxI 0 mxJ 0 i 999 j 990] (if (> i 100) (let [product (* ij)] (if (and (> product mx) (palindrome? (str product))) (recur product ij (if (> j 100) i (dec i)) (if (> j 100) (- j 11) 990)) (recur mx mxI mxJ (if (> j 100) i (dec i)) (if (> j 100) (- j 11) 990)))) mx))) (time (prn (begoners-palindrome))) 

Были и ответы Общего Лиспа, но они были непримиримыми для меня.

Просто для удовольствия, этот тоже работает.

 a = num; b = 0; while (a>=b) { if (a == b) return true; b = 10 * b + a % 10; if (a == b) return true; a = a / 10; } return false; 

Вот версия Scheme, которая строит функцию, которая будет работать против любой базы. Он имеет проверку избыточности: быстро возвращайте false, если число кратно базовому (заканчивается на 0). И он не восстанавливает все обратное число, только половину. Это все, что нам нужно.

 (define make-palindrome-tester (lambda (base) (lambda (n) (cond ((= 0 (modulo n base)) #f) (else (letrec ((Q (lambda (ht) (cond ((< ht) #f) ((= ht) #t) (else (let* ((h2 (quotient h base)) (m (- h (* h2 base)))) (cond ((= h2 t) #t) (else (Q h2 (+ (* base t) m)))))))))) (Q n 0))))))) 

Самый быстрый способ, который я знаю:

 bool is_pal(int n) { if (n % 10 == 0) return 0; int r = 0; while (r < n) { r = 10 * r + n % 10; n /= 10; } return n == r || n == r / 10; } 

Версия Голанга:

 package main import "fmt" func main() { n := 123454321 r := reverse(n) fmt.Println(r == n) } func reverse(n int) int { r := 0 for { if n > 0 { r = r*10 + n%10 n = n / 10 } else { break } } return r } 

Рекурсивное решение в rubyе без преобразования числа в строку

 def palindrome?(x, a=x, b=0) return x==b if a<1 palindrome?(x, a/10, b*10 + a%10) end palindrome?(55655) 

Выложите первую и последнюю цифры и сравните их, пока не закончите. Там может быть цифра слева или нет, но в любом случае, если все совпадающие цифры совпадают, это палиндром.

Вот еще одно решение в c ++ с использованием шаблонов. Это решение будет работать для сравнения строк с палитронами без учета регистра.

 template  bool palindrome(bidirection_iter first, bidirection_iter last) { while(first != last && first != --last) { if(::toupper(*first) != ::toupper(*last)) return false; else first++; } return true; } 

метод с небольшим лучшим постоянным фактором, чем метод @sminks:

 num=n lastDigit=0; rev=0; while (num>rev) { lastDigit=num%10; rev=rev*10+lastDigit; num /=2; } if (num==rev) print PALINDROME; exit(0); num=num*10+lastDigit; // This line is required as a number with odd number of bits will necessary end up being smaller even if it is a palindrome if (num==rev) print PALINDROME 

здесь af # версия:

 let reverseNumber n = let rec loop acc = function |0 -> acc |x -> loop (acc * 10 + x % 10) (x/10) loop 0 n let isPalindrome = function | x when x = reverseNumber x -> true | _ -> false 

Число является палиндромным, если его строковое представление является палиндромным:

 def is_palindrome(s): return all(s[i] == s[-(i + 1)] for i in range(len(s)//2)) def number_palindrome(n): return is_palindrome(str(n)) 
 def palindrome(n): d = [] while (n > 0): d.append(n % 10) n //= 10 for i in range(len(d)/2): if (d[i] != d[-(i+1)]): return "Fail." return "Pass." 

Для проверки заданного числа является Palindrome или нет (код Java)

 class CheckPalindrome{ public static void main(String str[]){ int a=242, n=a, b=a, rev=0; while(n>0){ a=n%10; n=n/10;rev=rev*10+a; System.out.println(a+" "+n+" "+rev); // to see the logic } if(rev==b) System.out.println("Palindrome"); else System.out.println("Not Palindrome"); } } в class CheckPalindrome{ public static void main(String str[]){ int a=242, n=a, b=a, rev=0; while(n>0){ a=n%10; n=n/10;rev=rev*10+a; System.out.println(a+" "+n+" "+rev); // to see the logic } if(rev==b) System.out.println("Palindrome"); else System.out.println("Not Palindrome"); } } 

Множество решений, размещенных здесь, меняет целое число и сохраняет его в переменной, которая использует дополнительное пространство, которое является O(n) , но вот решение с O(1) пространством.

 def isPalindrome(num): if num < 0: return False if num == 0: return True from math import log10 length = int(log10(num)) while length > 0: right = num % 10 left = num / 10**length if right != left: return False num %= 10**length num /= 10 length -= 2 return True 

Я всегда использую это решение python из-за его компактности.

 def isPalindrome(number): return int(str(number)[::-1])==number 

Попробуй это:

 reverse = 0; remainder = 0; count = 0; while (number > reverse) { remainder = number % 10; reverse = reverse * 10 + remainder; number = number / 10; count++; } Console.WriteLine(count); if (reverse == number) { Console.WriteLine("Your number is a palindrome"); } else { number = number * 10 + remainder; if (reverse == number) Console.WriteLine("your number is a palindrome"); else Console.WriteLine("your number is not a palindrome"); } Console.ReadLine(); } } 

Ниже перечислены списки приложений в виде стеков в python:

 def isPalindromicNum(n): """ is 'n' a palindromic number? """ ns = list(str(n)) for n in ns: if n != ns.pop(): return False return True 

popping the stack учитывает только самую правую часть номера для сравнения, и он не может быстро сократить проверки

  public class Numbers { public static void main(int givenNum) { int n= givenNum int rev=0; while(n>0) { //To extract the last digit int digit=n%10; //To store it in reverse rev=(rev*10)+digit; //To throw the last digit n=n/10; } //To check if a number is palindrome or not if(rev==givenNum) { System.out.println(givenNum+"is a palindrome "); } else { System.out.pritnln(givenNum+"is not a palindrome"); } } } в  public class Numbers { public static void main(int givenNum) { int n= givenNum int rev=0; while(n>0) { //To extract the last digit int digit=n%10; //To store it in reverse rev=(rev*10)+digit; //To throw the last digit n=n/10; } //To check if a number is palindrome or not if(rev==givenNum) { System.out.println(givenNum+"is a palindrome "); } else { System.out.pritnln(givenNum+"is not a palindrome"); } } } 
 let isPalindrome (n:int) = let l1 = n.ToString() |> List.ofSeq |> List.rev let rec isPalindromeInt l1 l2 = match (l1,l2) with | (h1::rest1,h2::rest2) -> if (h1 = h2) then isPalindromeInt rest1 rest2 else false | _ -> true isPalindromeInt l1 (n.ToString() |> List.ofSeq) 
 checkPalindrome(int number) { int lsd, msd,len; len = log10(number); while(number) { msd = (number/pow(10,len)); // "most significant digit" lsd = number%10; // "least significant digit" if(lsd==msd) { number/=10; // change of LSD number-=msd*pow(10,--len); // change of MSD, due to change of MSD len-=1; // due to change in LSD } else {return 1;} } return 0; } в checkPalindrome(int number) { int lsd, msd,len; len = log10(number); while(number) { msd = (number/pow(10,len)); // "most significant digit" lsd = number%10; // "least significant digit" if(lsd==msd) { number/=10; // change of LSD number-=msd*pow(10,--len); // change of MSD, due to change of MSD len-=1; // due to change in LSD } else {return 1;} } return 0; } 

Рекурсивный способ, не очень эффективный, просто предоставить вариант

(Код Python)

 def isPalindrome(num): size = len(str(num)) demoninator = 10**(size-1) return isPalindromeHelper(num, size, demoninator) def isPalindromeHelper(num, size, demoninator): """wrapper function, used in recursive""" if size < =1: return True else: if num/demoninator != num%10: return False # shrink the size, num and denominator num %= demoninator num /= 10 size -= 2 demoninator /=100 return isPalindromeHelper(num, size, demoninator) 
  • Генерация перетасованного диапазона с использованием PRNG, а не перетасовка
  • Алгоритм для выделения перекрывающихся прямоугольников?
  • Big O при добавлении разных подпрограмм
  • Почему DFS, а не BFS для поиска цикла в графах
  • Подсчет инверсий в массиве
  • Увеличьте прямоугольную область под гистограммой
  • Алгоритм: эффективный способ удаления повторяющихся целых чисел из массива
  • Равномерное распределение n точек на сфере
  • самый быстрый алгоритм ближайшего соседа
  • Каков самый быстрый алгоритм для вычисления минимального расстояния между двумя наборами точек?
  • Выбирая n чисел с фиксированной суммой
  • Давайте будем гением компьютера.