Massive Algorithms: LeetCode 564 - Find the Closest Palindrome

LeetCode 564 - Find the Closest Palindrome

https://leetcode.com/problems/find-the-closest-palindrome

Given an integer n, find the closest integer (not including itself), which is a palindrome.

The 'closest' is defined as absolute difference minimized between two integers.

Example 1:

Input: "123"
Output: "121"

Note:

The input n is a positive integer represented by string, whose length will not exceed 18.
If there is a tie, return the smaller one as answer.

X.
https://discuss.leetcode.com/topic/87287/java-solution-with-full-explaination

We first need to find the higher palindrome and lower palidrome respectively. and return the one who has the least different with the input number.

For the higher palindrome, the low limit is number + 1 while for the lower palindrome, the high limit is number - 1.

One global solution to find a palindrome is to copy first half part of the array to the last half part, we regards this as standard palindrome.
We need to detect this standard palindrome belongs to higher one or the lower one. And other solutions will be based on this standard one.

For the higher palindrome, if the standard one belongs to higher, we just simply return it. Or we need to change it.
For example, String n is 1343, and the standard palindrome is 1331. to get the higher one from the standard palidrome, we start from the
first 3, which is (n.length - 1) / 2. Add the number by 1, (---> 1431)if the added result is not higher than 9, the changing process is finished,
otherwise, continuously changing the number of previous index by i. After the changing process, we re-palidrome the string. (1431 -- > 1441)

For the lower palindrome, similar idea.But we need to notice that when we decrease a number, and if the first character of the string is '0',
we need to resize the array of n.length - 1, and fill in with '9'. (for example, n is '1000', the standard palidrome is '1001'(higher one) ,the lower one '0000'-->'999'.)

    public String nearestPalindromic(String n) {
        Long number = Long.parseLong(n);
        Long big = findHigherPalindrome(number + 1);
        Long small = findLowerPalindrome(number - 1);
        return Math.abs(number - small) > Math.abs(big - number) ? String.valueOf(big) : String.valueOf(small);
    }
    public Long findHigherPalindrome(Long limit) {
        String n = Long.toString(limit);
        char[] s = n.toCharArray(); // limit
        int m = s.length;
        char[] t = Arrays.copyOf(s, m); // target
        for (int i = 0; i < m / 2; i++) {
            t[m - 1 - i] = t[i];
        }
        for (int i = 0; i < m; i++) {
            if (s[i] < t[i]) {
                return Long.parseLong(String.valueOf(t)); 
            } else if (s[i] > t[i]) { 
                for (int j = (m - 1) / 2; j >= 0; j--) {
                    if (++t[j] > '9') {
                        t[j] = '0';
                    } else {
                        break;
                    }
                }
                // make it palindrome again
                for (int k = 0; k < m / 2; k++) {
                    t[m - 1 - k] = t[k];
                }
                return Long.parseLong(String.valueOf(t)); 
            }
        }
        return Long.parseLong(String.valueOf(t));    
    }
    public Long findLowerPalindrome(Long limit) {
        String n = Long.toString(limit);
        char[] s = n.toCharArray();
        int m = s.length;
        char[] t = Arrays.copyOf(s, m);
        for (int i = 0; i < m / 2; i++) {
            t[m - 1 - i] = t[i];
        }
        for (int i = 0; i < m; i++) {
            if (s[i] > t[i]) {
                return Long.parseLong(String.valueOf(t)); 
            } else if (s[i] < t[i]) {
                for (int j = (m - 1) / 2; j >= 0; j--) {
                    if (--t[j] < '0') {
                        t[j] = '9';
                    } else {
                        break;
                    }
                }
                if (t[0] == '0') {
                    char[] a = new char[m - 1];
                    Arrays.fill(a, '9');
                    return Long.parseLong(String.valueOf(a)); 
                }
                // make it palindrome again
                for (int k = 0; k < m / 2; k++) {
                    t[m - 1 - k] = t[k];
                }
                return Long.parseLong(String.valueOf(t)); 
            }
        }
         return Long.parseLong(String.valueOf(t));  
    }

X.
http://www.cnblogs.com/weedboy/p/6848662.html

题目只有5个candidate数字。将最中间的数字+1，+0，-1然后构造回文数字，因为要尽可能里原来的数字近，只要将左边依次赋值给右边就好了。

这里可以构造出三个candidate。但是中间数字为0时，-1的时候会出现特殊情况；中间数字为9，+1的时候会出现特殊情况；这两种情况就是下面讨论的。

2.还有两种可能比较特别。如1001这种，就是中间数字为零的情况，上面的方法-1的情况构造出来就是99。但是答案明明是999。所以我们构造一个比原来位数小一位最大的回文，999作为candidate。还有一种情况就是999的情况，答案应该是1001.上面的方法中+1的方法构造出来的是100001.显然不对。所以我们够一个比原来位数大一位最小的回文。这是另外两个candidates

其实思路只有一个，就是将中间数字+1，+0，-1的情况讨论，另外两个只是对数字越出极限的讨论整理。

注意：

1.题目中要求的回文是不能跟原来的数字一样的，也就是距离为零是不行的。

2.NOTE1中要求数字最长为18位，所以应该用long

3.距离一样取小的那个。

    string other(string p,int l){
        string other="";
        int len=p.length();
        for(int i=len-1-(l&1);i>=0;i--)
          other+=p[i];
        return other;
    }
    string nearestPalindromic(string n) {
        int l=n.length();
        set<long> cand;
        //构造比原来位数大一位的最小回文
        cand.insert(long(pow(10,l))+1);
        //构造比原来位数小一位的最大回文
        cand.insert(long(pow(10,l-1))-1);
        long mid=stol(n.substr(0,(l+1)/2));
         //-1，+0，+1三种情况
        for(int i=-1;i<=1;i++){
            string p=to_string(mid+i);
            string pp=p+other(p,l);
            cand.insert(stol(pp));
        }
        
        long num = stol(n), minDiff = LONG_MAX, diff, minVal;
        //除去原来的数字
        cand.erase(num);
        for ( long val : cand ) {
            diff = abs(val - num);
            if ( diff < minDiff ) {
                minDiff = diff;
                minVal = val;
            } else if ( diff == minDiff ) {
                minVal = min(minVal, val);
            }
        }
        return to_string(minVal);
    }

X. Math
https://leetcode.com/articles/find-the-closest-palindrome/

Time complexity :

O(l)

. Scanning, insertion, deletion,, mirroring takes

O(l)

, where

l

is the length of the string.

    public String mirroring(String s) {
        String x = s.substring(0, (s.length()) / 2);
        return x + (s.length() % 2 == 1 ? s.charAt(s.length() / 2) : "") + new StringBuilder(x).reverse().toString();
    }
    public String nearestPalindromic(String n) {
        if (n.equals("1"))
            return "0";

        String a = mirroring(n);
        long diff1 = Long.MAX_VALUE;
        diff1 = Math.abs(Long.parseLong(n) - Long.parseLong(a));
        if (diff1 == 0)
            diff1 = Long.MAX_VALUE;

        StringBuilder s = new StringBuilder(n);
        int i = (s.length() - 1) / 2;
        while (i >= 0 && s.charAt(i) == '0') {
            s.replace(i, i + 1, "9");
            i--;
        }
        if (i == 0 && s.charAt(i) == '1') {
            s.delete(0, 1);
            int mid = (s.length() - 1) / 2;
            s.replace(mid, mid + 1, "9");
        } else
            s.replace(i, i + 1, "" + (char)(s.charAt(i) - 1));
        String b = mirroring(s.toString());
        long diff2 = Math.abs(Long.parseLong(n) - Long.parseLong(b));


        s = new StringBuilder(n);
        i = (s.length() - 1) / 2;
        while (i >= 0 && s.charAt(i) == '9') {
            s.replace(i, i + 1, "0");
            i--;
        }
        if (i < 0) {
            s.insert(0, "1");
        } else
            s.replace(i, i + 1, "" + (char)(s.charAt(i) + 1));
        String c = mirroring(s.toString());
        long diff3 = Math.abs(Long.parseLong(n) - Long.parseLong(c));

        if (diff2 <= diff1 && diff2 <= diff3)
            return b;
        if (diff1 <= diff3 && diff1 <= diff2)
            return a;
        else
            return c;
    }

http://blog.csdn.net/marlonlyh/article/details/70799152

题目的大意是给出一个数字（字符串形式），输出距离该数字最近的回文数字（字符串形式）。比如，输入”123”，距离123最近的回文数字为121，则输出”121”。要距离近，那么数字的高位要尽量相同。仔细分析可知，距离一个数字最近的回文数字只有三种可能。以”123456789”为例：首先回文就是要左右对称，”123456789”的左边为”12345”，对应回文数为”123454321”(代码中为midnum)。当然”123454321”不一定是距离最近的，也有可能是”123444321”(代码中为minnum)或者”123464321”(代码中为maxnum)，其左边分别为”12344”（”12345-1”）和”12346”（”12345+1”）。另外还要考虑数字左半边”+1”或者”-1”出现位数不同的情况。比如”9999”，左边为”99”，99+1=100，这时距离最近的数不可能把”100001”考虑进去，而应该是”10001”，所以数字左半边”+1”或者”-1”有位数改变的情况应该特殊考虑。算法时间复杂度为O(1)。

https://discuss.leetcode.com/topic/87220/python-simple-with-explanation

Let's build a list of candidate answers for which the final answer must be one of those candidates. Afterwards, choosing from these candidates is straightforward.

If the final answer has the same number of digits as the input string S, then the answer must be the middle digits + (-1, 0, or 1) flipped into a palindrome. For example, 23456 had middle part 234, and 233, 234, 235 flipped into a palindrome yields 23332, 23432, 23532. Given that we know the number of digits, the prefix 235 (for example) uniquely determines the corresponding palindrome 23532, so all palindromes with larger prefix like 23732 are strictly farther away from S than 23532 >= S.

If the final answer has a different number of digits, it must be of the form 999....999 or 1000...0001, as any palindrome smaller than 99....99 or bigger than 100....001 will be farther away from S.

def nearestPalindromic(self, S):
    K = len(S)
    candidates = [str(10**k + d) for k in (K-1, K) for d in (-1, 1)]
    prefix = S[:(K+1)/2]
    P = int(prefix)
    for start in map(str, (P-1, P, P+1)):
        candidates.append(start + (start[:-1] if K%2 else start)[::-1])
    
    def delta(x):
        return abs(int(S) - int(x))
    
    ans = None
    for cand in candidates:
        if cand != S and not cand.startswith('00'):
            if (ans is None or delta(cand) < delta(ans) or
                    delta(cand) == delta(ans) and int(cand) < int(ans)):
                ans = cand
    return ans

http://bookshadow.com/weblog/2017/04/23/leetcode-find-the-closest-palindrome/

记n的前半部分为p，分别用p，p - 1，p + 1及其逆序串拼接成长度为奇数或者偶数的回文串。

假设n的长度为m， p的长度应分别取m / 2，m / 2 + 1。

另外需要考虑进位时的边界情况，比如测试用例：11, 1001, 999

def nearestPalindromic(self, n): """ :type n: str :rtype: str """ evenPal = lambda sp : int(sp + sp[::-1]) oddPal = lambda sp : int(sp + sp[::-1][1:]) sn, n = n, int(n) if len(sn) == 1: return str(n - 1) ans = -999999999999999999 mid = len(sn) / 2 for sp in sn[:mid], sn[:mid + 1], str(int(sn[:mid]) * 10): p = int(sp) for pal in evenPal, oddPal: for d in -1, 0, 1: val = pal(str(p + d)) if val == n: continue ans = min(ans, val, key = lambda x : (abs(x - n), x)) return str(ans)

https://discuss.leetcode.com/topic/87200/java-solution

    public String nearestPalindromic(String n) {
        if (n.length() >= 2 && allNine(n)) {
            String s = "1";
            for (int i = 0; i < n.length() - 1; i++) {
                s += "0";
            }
            s += "1";
            return s;
        }
        boolean isOdd = (n.length() % 2 != 0);
        String left = n.substring(0, (n.length() + 1) / 2);
        long[] increment = {-1, 0, +1};
        String ret = n;
        long minDiff = Long.MAX_VALUE;
        for (long i : increment) {
            String s = getPalindrom(Long.toString(Long.parseLong(left) + i), isOdd);
            if (n.length() >= 2 && (s.length() != n.length() || Long.parseLong(s) == 0)) {
                s = "";
                for (int j = 0; j < n.length() - 1; j++) {
                    s += "9";
                }
            }
            long diff = s.equals(n) ? Long.MAX_VALUE : Math.abs(Long.parseLong(s) - Long.parseLong(n));
            if (diff < minDiff) {
                minDiff = diff;
                ret = s;
            }
        }
        return ret;
    }
    private String getPalindrom(String s, boolean isOdd) {
        String right = new StringBuilder(s).reverse().toString();
        return isOdd ? s.substring(0, s.length() - 1) + right : s + right;
    }
    private boolean allNine(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '9') {
                return false;
            }
        }
        return true;
    }

X. https://leetcode.com/articles/find-the-closest-palindrome/
The simplest solution is to consider every possible number smaller than the given number

n

, starting by decrementing 1 from the given number and go on in descending order. Similarly, we can consider every possible number greater than

n

starting by incrementing 1 from the given number and going in ascending order. We can continue doing so in an alternate manner till we find a number which is a palindrome.
Time complexity :

O(\sqrt{n})

. Upto

2*\sqrt{n}

numbers could be generated in the worst case.

    public String nearestPalindromic(String n) {
        long num = Long.parseLong(n);
        for (long i = 1;; i++) {
            if (isPalindrome(num - i))
                return "" + (num - i);
            if (isPalindrome(num + i))
                return "" + (num + i);
        }
    }
    boolean isPalindrome(long x) {
        long t = x, rev = 0;
        while (t > 0) {
            rev = 10 * rev + t % 10;
            t /= 10;
        }
        return rev == x;
    }

http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/
https://discuss.leetcode.com/topic/88897/java-solution-with-detailed-proof

LeetCode 564 - Find the Closest Palindrome

Labels

Popular Posts