Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.
It is not because we see hope, but because we see hope. ‘
Day 53 2021.03.02
Find the nearest palindrome number
- Leetcode: leetcode-cn.com/problems/fi…
- Difficulty: difficulty
- Methods: Simulation
Topic describes
- Given a string representing an integer
n, returns the 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.
The sample
- Example 1
Input: n = "123" Output: "121"Copy the code- Example 2
Input: n = "1" Output: "0" Explanation: 0 and 2 are the nearest palindromes, but we return the smallest, which is 0.Copy the codeThought analysis
- This problem is not difficult, the main inspection is: careful, some boundary problems are easy to make mistakes
- A total of
waFive times. I had some problems. When we started, the idea was to take the first half of the data and flip it over and put it in the back.
Error sample analysis
"10"When encountering a situation that causes the palindrome integer number to become smaller, for example, the correct output is:"9"We went from two digits to one digit."100"Again, it’s the same problem of decreasing the number of digits. To modify the code at this point, you need to anticipate the decrease and increase of the lower bits"10"= >"9"Digits reduce"99"= >"101"Double-digit increases
"1283""1837722381"There are two sumsnIf the difference between the two values is the same, then you need to take the smaller one. Why this is wrong: When comparing, the order is default, so even if the first number is smaller than the last one, it does not count. Fix: Adjust the comparison order so that the smallest value is first and the largest value is last for comparison."1805170081"Same as above error cause.
ACcode
/ * * *@param {string} n
* @return {string}* /
var nearestPalindromic = function(n) {
let len = n.length;
If the length is less than 1, the palindrome number is -1
if(len == 1) return n - 1 + ' ';
// Discuss the case of length greater than 1
let ans = ' ';
// Preprocessing: the number of bits decreased or increased by 1
/ / the minimum
let multi = Math.pow(10, len - 1);
if(Number(n) <= multi + 1){
ans += multi - 1;
return ans;
}
/ / Max
let max = Math.pow(10, len);
if(Number(n) + 1 == max){
ans += max + 1;
return ans;
}
// Encapsulate the minimum difference function
function minCha (oneStr, twoStr, threeStr) {
// flag is used for the flag, which has the smallest difference
let flag = 0;
if(Math.abs(n - oneStr) <= Math.abs(n - twoStr)){
flag = 1;
}else {
flag = 2;
}
if(flag == 1) {if(Math.abs(n - oneStr) <= Math.abs(n - threeStr)){
flag = 1;
}else {
flag = 3; }}else if(flag == 2) {
if(Math.abs(n - twoStr) <= Math.abs(n - threeStr)){
flag = 2;
}else {
flag = 3; }}if(flag == 1) {return oneStr;
}else if(flag == 2) {return twoStr;
}else {
returnthreeStr; }}// Let's have a discussion
let mid = len / 2;
/ / even
if(len % 2= =0) {// Cut from the beginning to the middle position
let preStr = n.substr(0,mid);
// Cut from the middle position to the end
let lastStr = n.substring(mid);
let contra = lastStr.split(' ').reverse().join(' ');
// 1. Case: itself is palindrome number
if(preStr == contra){
let one = Number(preStr) - 1 + ' ';
let two = one.split(' ').reverse().join(' ');
ans += one + two;
}else {
// 2. It is not a palindrome itself (originally wrong idea: XXXX tries to change the following number, keep the preceding number unchanged XXXX)
// Which side is smaller - 1/0 / +1
/ / 0
let num = Number(preStr);
// -1
let one = num - 1 + ' ';
/ / + 1
let three = num + 1 + ' ';
let oneStr = one + one.split(' ').reverse().join(' ');
let twoStr = num + (num + ' ').split(' ').reverse().join(' ');
let threeStr = three + three.split(' ').reverse().join(' ');
// Encapsulate the functionans = minCha(oneStr, twoStr, threeStr); }}else {
// Cut from the beginning to the middle position
let preStr = n.substr(0,mid);
// Cut from the middle position to the end
let midStr = n.charAt(mid);
let lastStr = n.substring(mid + 1);
let contra = lastStr.split(' ').reverse().join(' ');
// 1. Case: itself is palindrome number
// 12121, the middle number is -1, if 0 then +1
if(preStr == contra){
let num = Number(midStr);
if(num == 0){
num++;
}else {
num--;
}
ans += preStr;
ans += num;
ans += preStr.split(' ').reverse().join(' ');
}else {
// Not palindrome number
let newPre = n.substr(0, mid + 1);
let num = Number(newPre);
let one = num - 1 + ' ';
let three = num + 1 + ' ';
let oneStr = preStr + one.split(' ').reverse().join(' ');
let twoStr = preStr + (num + ' ').split(' ').reverse().join(' ');
let threeStr = preStr + three.split(' ').reverse().join(' '); ans = minCha(oneStr, twoStr, threeStr); }}return ans;
};
Copy the codeconclusion
- The next time you encounter a situation where the current number +1/-1/0, be sure to arrange the order in advance, that is, -1/0/+1, to achieve the same difference and take the minimum value of the situation.
- To do it, you need to think about the problem, and be able to solve the sample in the way you think about it, and have a rough idea of how to solve the problem before you start. Otherwise, it’s just a little bit of a pinch and a little bit of a bump.
- When encountering some difficult problems (for myself), for example, the three numbers in this question are compared with each other, and I subconsciously feel difficult to choose one. I don’t want to write it, and I want to check the solution of the problem. In the future, if you encounter such a situation, you should write it out by hand, don’t be afraid of trouble, and then look at the solution written by others to optimize your own code.
Ask for advice
- I feel that I wrote the code after finishing, or very long, you guys, if there are optimization suggestions, you can leave a message directly, thank you very much, common progress!