执行操作后字典序最小的字符串
难度:
标签:
题目描述
代码结果
运行时间: 79 ms, 内存: 0.0 MB
/*
* This solution is similar to the Java version but uses Java Streams for concise and functional-style operations.
*/
import java.util.*;
import java.util.stream.*;
public class SmallestStringStream {
private static String add(String s, int a) {
return IntStream.range(0, s.length())
.mapToObj(i -> (i % 2 == 1) ? (char) (((s.charAt(i) - '0' + a) % 10) + '0') : s.charAt(i))
.map(String::valueOf)
.collect(Collectors.joining());
}
private static String rotate(String s, int b) {
int n = s.length();
b = b % n;
return s.substring(n - b) + s.substring(0, n - b);
}
public static String findLexSmallestString(String s, int a, int b) {
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.offer(s);
visited.add(s);
String minString = s;
while (!queue.isEmpty()) {
String current = queue.poll();
String added = add(current, a);
if (visited.add(added)) {
queue.offer(added);
minString = Stream.of(minString, added).min(String::compareTo).orElse(minString);
}
String rotated = rotate(current, b);
if (visited.add(rotated)) {
queue.offer(rotated);
minString = Stream.of(minString, rotated).min(String::compareTo).orElse(minString);
}
}
return minString;
}
public static void main(String[] args) {
String s = "5525";
int a = 9;
int b = 2;
System.out.println(findLexSmallestString(s, a, b)); // Output: "2050"
}
}
解释
方法:
这个题解利用了循环串的概念和数字的周期性。首先,定义了一个辅助函数 generate(num, a) 来找出对于一个给定的数字 num,在累加操作下,如何通过最小的变化使其达到最小的可能值。接着在主函数中,通过旋转和累加操作,尝试生成所有可能的字符串变体。具体步骤包括:将字符串 s 转换为整数数组,然后对每个可能的旋转位移进行遍历,每次旋转后再对奇数位执行累加操作,如果 b 是奇数,也对偶数位执行累加操作,最后将所有可能的字符串收集起来,返回其中字典序最小的字符串。这种方法考虑了通过不同的旋转和累加操作来探索所有可能的字符串配置,并利用集合来避免重复处理相同的旋转配置。
时间复杂度:
O(n^2)
空间复杂度:
O(n^2)
代码细节讲解
🦆
在`generate`函数中,为什么选择循环10次来计算数字在累加`a`后的最小值?这是基于哪些数学原理或者假设?
▷🦆
题解中提到了通过集合`seen`来避免处理相同的旋转配置,但是如何判断什么时候一个旋转配置已经被处理过?具体是基于哪种属性来避免重复处理的?
▷🦆
关于字典序最小字符串的生成,题解中提到的`如果b是奇数,也对偶数位进行累加操作`,这一操作是基于什么样的考虑?为什么偶数位的处理与`b`的奇偶性有关?
▷