숫자가 회문인지 어떻게 확인합니까?
숫자가 회문인지 어떻게 확인합니까?
모든 언어. 모든 알고리즘. (숫자는 SDK를 사용하여 만든 다음 노드를 되 돌리는 알고리즘 제외).
이 프로젝트 오일러 문제 중 하나입니다 . Haskell에서 해결했을 때 제안한대로 숫자를 단순화하여 변환하십시오. 그것은 팔린 드롬인지 확인하는 것은 사소한 일입니다. 성능이 충분하다면 왜 더 복잡하게 만드는가? 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;
}
각 숫자 숫자를 스택으로 밀고 튀어 나옵니다. 앞뒤로 같은 경우 회문입니다.
문제를 해결 한 답변을 보지 않고 해결합니다. 즉, 숫자를 바꾸거나 다른 데이터 구조를 사용하는 모든 솔루션을 보았습니다.
Java와 같은 언어는 정수 오버플로를 감쌀 수 있고 C와 같은 언어에서는 동작이 정의되어 있습니다. ( Java에서 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 의 제안에 따라 편집했습니다 .
빠르고 빠른 반복적 인 방법이 있습니다.
def reverse(n):
newnum=0
while n>0:
newnum = newnum*10 + n % 10
n//=10
return newnum
def palindrome(n):
return n == reverse(n)
또한 재귀와 관련된 메모리 문제를 방지합니다 (예 : Java의 StackOverflow 오류)
재미로, 이것도 효과가 있습니다.
a = num;
b = 0;
if (a % 10 == 0)
return a == 0;
do {
b = 10 * b + a % 10;
if (a == b)
return true;
a = a / 10;
} while (a > b);
return a == b;
숫자를 사랑하는 것을 다음으로 만들었습니다.
왜 그 메시지를 수신합니까? 쉽게 구현하고 읽을 수 있습니다. 컴퓨터가 없어도 2**10-23십진 회문 인지 적이면 십진법으로 작성하여 테스트해야합니다.
'문자열 연산이 산술보다 느리다'라는 슬로건은 실제로입니다. Smink의 산술 알고리즘을 간단하게 반전과 비교했습니다 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)
초 결과 (더 낮을수록) :
중독 1.50960231881 산술 1.69729960569
내가 아는 가장 빠른 방법 :
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;
}
나는 매우 무자비한 방법으로 오일러 문제에 답했다. 당연히, 새로운 잠금 해제 관련 포럼에 도착했을 때 훨씬 더 똑똑한 알고리즘이 표시되었습니다. 즉, 핸들 Begoner를 방문한 멤버는 새로운 접근 방식을 사용하여 알고리즘을 사용하여 솔루션을 다시 구현하기로 결정했습니다. 그의 버전은 Python (중첩 루프 사용)이고 Clojure (단일 루프 / 반복 사용)로 다시 구현했습니다.
여기 당신의 즐거움을 위해 :
(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 (* i j)]
(if (and (> product mx) (palindrome? (str product)))
(recur product i j
(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)))
Common Lisp 대답도 있었지만 나에게 확고하지 않다.
다음은 모든베이스에 대해 작동하는 함수를 구성하는 Scheme 버전입니다. 추가 검사 기능이 있습니다. 숫자가 밑 수가 여러 개인 경우 신속하게 false를 반환합니다 (0으로 끝남).
그리고 전체 역수를 다시 만들지 않고 절반 만 만듭니다.
그게 우리가 필요한 전부입니다.
(define make-palindrome-tester
(lambda (base)
(lambda (n)
(cond
((= 0 (modulo n base)) #f)
(else
(letrec
((Q (lambda (h t)
(cond
((< h t) #f)
((= h t) #t)
(else
(let*
((h2 (quotient h base))
(m (- h (* h2 base))))
(cond
((= h2 t) #t)
(else
(Q h2 (+ (* base t) m))))))))))
(Q n 0)))))))
골랑 버전 :
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
}
숫자를 공유로 변환하지 않고 루비의 재귀 솔루션.
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 <typename bidirection_iter>
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
palindromic 인 경우 숫자는 palindromic입니다.
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 Code)
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
나는 설치하기 때문에 항상이 솔루션을 사용합니다.
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();
}
}
다음은 목록을 제공하는 스택으로 사용하는 솔루션입니다.
def isPalindromicNum(n):
"""
is 'n' a palindromic number?
"""
ns = list(str(n))
for n in ns:
if n != ns.pop():
return False
return True
스택을 팝하는 것은 비교를 위해 숫자의 가장 오른쪽 만 고려하고 검사를 줄이는 데 실패합니다.
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;
}
매우 추천하지 않은 재귀 적 방법은 옵션을 제공합니다.
(파이썬 코드)
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)
참고 URL : https://stackoverflow.com/questions/199184/how-do-i-check-if-a-number-is-a-palindrome
'IT' 카테고리의 다른 글
| jQuery에서 마우스 휠 이벤트를 보시겠습니까? (0) | 2020.07.12 |
|---|---|
| getMinutes () 0-9- 두 자리 숫자를 표시하는 방법? (0) | 2020.07.12 |
| IISExpress를 사용하여 SSL 연결 / 연결되어 (0) | 2020.07.12 |
| S3 버킷에있는 객체는 어떻게 알 수 있습니까? (0) | 2020.07.12 |
| VB.NET의 숨겨진 기능? (0) | 2020.07.12 |