Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.
Topic describes
This is 564 on LeetCode. Find the most recent palindrome, difficulty is difficult.
I don’t want to Tag you.
Given a string NNN representing an integer, return its nearest palindrome integer (excluding itself). If there is more than one, return the smaller one.
“Nearest” is defined as the smallest absolute value of the difference between two integers.
Example 1:
Input: n = "123" Output: "121"Copy the codeExample 2:
Input: n = "1" Output: "0" Explanation: 0 and 2 are the nearest palindromes, but we return the smallest, which is 0.Copy the codeTip:
- NNN consists only of numbers
- NNN does not contain the leading 000
- NNN represents an integer in the range [1,1018 −1][1, 10^{18} -1][1,1018 −1]
Upper and lower bound analysis + boundary treatment
For any string value SSS (given length NNN), consider how to find palindrome string values (upper and lower bound) that are “first greater” and “first smaller”.
Since you’re looking for the “nearest” value, a natural thought would be to change the low digit first, but due to the symmetrical nature of the palindrome string, the side effect of each “low” modification is to change the corresponding “high” at the same time, so the only real position to change is the (relative) middle position.
For example, 🌰, for an odd palindrome string of length abcdeabcdeabcde, the change of dedede causes the change of ababab synchronously, so the last low value that can be changed is CCC; For even palindrome string values abcdabCDabCD, where DDD changes cause AAA to change synchronously, so the last position that can be changed is BCBCBC.
When the target position is modified, the values of other positions can be uniquely determined by the property of palindrome string, so it is only necessary to find the adjacent values of the position that can be modified.
For example, for abcdeabcdeabcDE, the first three digits of the most recent palindrome value may be one of abcabcabc, ABC + 1ABC + 1ABC +1, or ABC − 1ABC-1ABC −1. Other values are uniquely determined with the first three digits.
The above analysis holds for the general case, and the boundary case is where ABC + 1ABC + 1ABC +1 and ABC − 1ABC-1ABC −1 cause the overall length to change, That is, ABC = 999ABC = 999ABC =999 and ABC =100abc=100abc=100. In this case, the values obtained by directly applying the above method are 100000110000011000001 and 999999999 respectively. But the actual most recent values are 100001100001100001 and 999999999999.
In a nutshell: For ABC =999abc =999abc =999 (corresponding to the string 999xx999xx999XX), the above logic produces 100010001000, After palindrome supplement, 100000110000011000001 is obtained (actually 100001100001100001 is better); For ABC =100abc =100abc =100 (the original string is 100xx100XX100XX), the above logic is 999999, and the palindrome supplement is 999999999 (actually 999999999999 is better).
Therefore, for a value with length of NNN, the three cases of enumerating the first half (the first half remains unchanged, the first half plus or minus one) may be considered as an optimal solution. We need to take into account the boundary values related to length. That is, “the maximum palindrome string of length N − 1n-1N −1 (99…9999…9999…99)” and “the minimum palindrome string of length N +1n +1n +1 (10…0110…0110…01)” are also taken into account. The corresponding 10n−1−110^{n-1} -110n −1−1 and 10n+110^n + 110n+1 are also considered. Then choose the one with the smallest absolute difference from the above 555 values.
Some details: After enumerating the first half, we need to decide how to generate the second half based on the parity of the original string length to ensure that the constructed palindrome string length is still equal to the original string length.
That is, for abcdeabcdeabcde whose original string length NNN is odd, after processing abcabcabc, only bababa is generated according to the first two digits of ababab, without processing the middle character CCC. For abcdabcdabcd whose string length NNN is even, after processing ababab, another general value needs to generate bababa based on the whole ababab. No intermediate characters need to be skipped.
Code:
class Solution {
public String nearestPalindromic(String s) {
int n = s.length();
long cur = Long.parseLong(s);
Set<Long> set = new HashSet<>();
set.add((long) Math.pow(10, n - 1) - 1);
set.add((long) Math.pow(10, n) + 1);
long t = Long.parseLong(s.substring(0, (n + 1) / 2));
for (long i = t - 1; i <= t + 1; i++) {
long temp = -1;
if (n % 2= =0) temp = getNum(i, true);
else temp = getNum(i, false);
if(temp ! = cur) set.add(temp); }long ans = -1;
for (long i : set) {
if (ans == -1) ans = i;
else if (Math.abs(i - cur) < Math.abs(ans - cur)) ans = i;
else if (Math.abs(i - cur) == Math.abs(ans - cur) && i < ans) ans = i;
}
return String.valueOf(ans);
}
long getNum(long k, boolean isEven) {
StringBuilder sb = new StringBuilder();
sb.append(k);
int idx = isEven ? sb.length() - 1 : sb.length() - 2;
while (idx >= 0) sb.append(sb.charAt(idx--));
returnLong.parseLong(sb.toString()); }}Copy the code- Time complexity: O(logn)O(\log{n})O(logn)
- Space complexity: O(1)O(1)O(1)
The last
This is the No.564 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks, we will first finish all the topics without locks.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.