Bảng màu gần nhất lớn hơn số đã cho trong python

Cho một số nguyên k, hãy viết chương trình tìm số nguyên gần nhất [không bao gồm chính nó], là một số đối xứng

Lưu ý vấn đề

• Một số nguyên được gọi là đối xứng nếu nó giữ nguyên khi các chữ số của nó được đặt trước
• 'Gần nhất' có nghĩa là chênh lệch tuyệt đối giữa hai số nguyên phải nhỏ nhất
• num là một số nguyên dương được biểu thị bằng một chuỗi, có độ dài không vượt quá 15 chữ số
• Nếu hai số nguyên palindrome gần nhất với num và có một ràng buộc giữa chúng, thì trả về số nhỏ hơn làm đầu ra

ví dụ 1

Input: "99"
Output: "101"
Explanation: "88" and "101" are two nearest integers which are palindrome. But "101" is the answer because the absolute difference is minimum between "99" and "101".

Các giải pháp

Chúng tôi sẽ thảo luận về hai cách tiếp cận cho vấn đề trên

1. Cách tiếp cận ngây thơ

Như chúng ta có thể thấy rằng đối xứng gần nhất với một số có thể nhỏ hơn hoặc lớn hơn số đó. Đối với palindrome lớn hơn, giới hạn dưới là số + 1 trong khi đối với palindrome dưới, giới hạn trên là số - 1. Vì vậy, chúng tôi di chuyển xa hơn từ số một và kiểm tra xem nó có phải là màu nhạt hay không. Bằng cách này, chúng tôi nhận được hai số đối xứng - một thấp hơn số và một lớn hơn số. Kiểm tra cái nào trong số chúng gần nhất [chênh lệch tuyệt đối tối thiểu] và trả lại dưới dạng câu trả lời

Mã giả

int closestPalindrome[int n]
{
    low = n-1
    
    // will decrease the low till low is a palindrome
    while[!checkPalindrome[low]]
        low -= 1
    
    high = n + 1
    
    // will increase the high till high is a palindrome
    while[!checkPalindrome[high]]
        high += 1
    
    // checking difference between both
    if [ n - low < high - n]
        return low
    else
        return high
}

phức tạp

Thời gian phức tạp. O[√N]

Độ phức tạp không gian. Ô[1]

2. Phương pháp tiếp cận hiệu quả

Thuộc tính của palindrom là phía bên trái của palindrome là hình ảnh phản chiếu của phía bên phải. Vì vậy, có một suy nghĩ rằng nếu chúng ta làm cho bất kỳ bên nào giống bên kia, chúng ta có thể đạt được mục tiêu của mình

Ví dụ: Trong trường hợp “12345”, chúng tôi phản chiếu “12” sang phải để biến nó thành “12321”. Tương tự, đối với 123456, chúng tôi sao chép “123” sang bên phải

Bây giờ, câu hỏi xuất hiện trong đầu chúng ta là chúng ta nên thay đổi bên nào để biến nó thành một đối xứng. [ Nghĩ. ]

Chúng ta có thể sao chép phần bên trái của số sang bên phải để có bảng màu gần nhất. [ Tại sao?]

Hãy tìm hiểu sâu hơn về lý do tại sao chúng ta sao chép từ trái sang phải mà không phải ngược lại. Giả sử số là "abcxy"

cách đầu tiên. Sao chép nửa sau sang nửa đầu, bảng màu mới thu được sẽ là "yxcxy" có hiệu tuyệt đối là. 10000[a−y]+1000[b−x]. từ số ban đầu

cách thứ hai. Nếu chúng ta sao chép nửa đầu sang nửa sau của chuỗi, chúng ta sẽ nhận được "abcba", có chênh lệch tuyệt đối là. 10[x−b]+[y−a]. Cố gắng thay đổi c bổ sung, trong cả hai trường hợp, sẽ phải chịu một giá trị bổ sung ít nhất là 100 trong chênh lệch tuyệt đối

Vì vậy, chúng tôi thấy rằng việc sao chép từ trái sang phải luôn tốt hơn trong những điều kiện như vậy

Có thể có trường hợp bạn cần kiểm tra nhiều bảng màu ứng cử viên bằng cách thay đổi các chữ số ở giữa. Ví dụ

1805170811 

Nửa đầu là 18051. Sau khi thay đổi các chữ số ở giữa, các ứng cử viên là 1805005081, 1805115081 và 1805225081. Sự khác biệt tuyệt đối là tối thiểu cho 1805225081. Vì vậy, nó là palindrome gần nhất

Làm thế nào để có được những palindromes ứng cử viên này? . ]

Chúng ta có thể giữ nguyên chữ số ở giữa, tăng và giảm chữ số ở giữa đi 1 và sau đó phản chiếu phần bên trái để nhận các số đối xứng ứng cử viên này

Vì vậy, bây giờ chúng ta biết quy trình để có được bảng màu gần nhất, nhưng chúng ta hãy xem xét một số trường hợp góc

Gourav Hammad

Theo dõi

27 Tháng ba, 2020

·

1 phút đọc

Làm cách nào để tìm bảng đối xứng tiếp theo có thể có cho một bảng màu đã cho?

Làm thế nào bạn có thể tìm thấy bảng màu đối với một giá trị số trong Python?

số palindrome lớn nhất là gì?

44 có phải là một số xuôi không?