下个由相同数字构成的回文串
难度:
标签:
题目描述
代码结果
运行时间: 31 ms, 内存: 17.8 MB
/*
* 题目思路:
* 1. 使用Java Stream API的方式处理字符串。
* 2. 需要进行字符串的拆分和拼接来寻找下一个回文数。
* 3. 相比于普通Java方法,这种方法可能在性能上有所折损,但代码简洁。
*/
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class NextPalindromeStream {
public static String nextPalindrome(String num) {
int len = num.length();
int mid = len / 2;
boolean leftSmaller = IntStream.range(0, mid).anyMatch(i -> num.charAt(i) < num.charAt(len - 1 - i));
String leftHalf = num.substring(0, mid);
String mirrored = leftHalf + new StringBuilder(leftHalf).reverse().substring(len % 2 == 0 ? 0 : 1);
if (leftSmaller) {
String leftPart = leftHalf + (len % 2 == 0 ? "" : num.charAt(mid));
String incremented = String.valueOf(Long.parseLong(leftPart) + 1);
leftHalf = incremented.substring(0, mid);
mirrored = leftHalf + new StringBuilder(leftHalf).reverse().substring(len % 2 == 0 ? 0 : 1);
}
return mirrored;
}
}
解释
方法:
该题目的目的是找到由相同数字组成的下一个回文串。算法的主要思路是从中心向外寻找可以形成下一个较大的回文串的机会。具体步骤如下:
1. 使用一个栈来存储遍历过的字符和它们的索引,以便在找到一个更小的字符时可以进行替换。
2. 从字符串的中心位置向左遍历,寻找第一个可以交换的位置,这个位置的字符应该小于其对应的栈顶字符。
3. 一旦找到这样的位置,从栈中移除所有比当前字符大的元素,记录下可以交换的位置。
4. 如果没有找到合适的交换位置,则返回空字符串。
5. 根据找到的交换位置,构造新的回文串,确保新串比原串大。
6. 特别注意处理字符串长度为奇数的情况,中间的字符需要保持不变。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
算法中使用栈的目的是什么?它如何帮助找到可交换的字符位置?
▷🦆
为什么在找到一个比栈顶元素小的字符后,要移除所有比当前字符大的栈顶元素?这样做的目的是什么?
▷🦆
构造新的回文串时,如何确保新串比原串大?具体是哪些操作保证了这一点?
▷🦆
当字符串长度为奇数时,中间的字符应如何处理?为什么特别指出需要保持不变?
▷