感觉有点不对劲，全组开会不叫我，连续三次了。。。
老鬼约 4 分钟最近看到一个网友的吐槽，真是让我忍不住笑出声：“感觉有点不对劲，全组开会不叫我，连续三次了…” 这是什么操作？
程序员的世界里，最怕的就是被忽视，特别是那种感觉自己仿佛透明的时刻。
你知道吗，这种心情就像是写代码的时候，突然出现bug，debug了半天才发现原来是自己没有定义变量——明明存在，却好像被遗忘。
我觉得，作为程序员，尤其是对我们这种每天跟屏幕打交道的，偶尔被“排除”这种事儿，心里多少会有点不舒服。
你想，毕竟每个人都有个小心眼，不是吗？不过这也提醒了我，做事要更“显眼”一点，毕竟你不在场，谁知道你有没有贡献呢？【备注:文末可领最新资料】。
算法题：得分最高的最小轮调
给定一个字符串，要求你进行“最小轮调”操作，以此得到得分最高的字符串。
“轮调”是指将字符串的某个前缀移动到字符串的后面。举个例子，对于字符串“abcde”，将“ab”移到后面就变成“cdeab”。最小轮调指的是找到所有可能的轮调中，字典序最小的那个。
这题看似简单，实际做起来就有点“想不到”的感觉。作为程序员，我想我们都喜欢这种看起来不复杂，实际上却有点挑战的题目。今天，我就带大家一块儿理理这道题的解决思路。
首先，来个简单的例子帮助大家理清题意。假设给定字符串是"abcde"。我们可以轮调得到以下这些字符串：
abcde
bcdea
cdeab
deabc
eabcd
显然，字典序最小的字符串是"abcde"本身。问题是：如果字符串更长，手动一个一个试就不现实了。所以我们要考虑如何高效地找到字典序最小的轮调。
问题的关键点就是：如何通过某种技巧快速得到最小的轮调？大部分人都会想到：排序。没错，你可以将所有可能的轮调都生成出来，然后排序，选出最小的那个。但是，效率太低，时间复杂度会达到O(n^2 log n)。那如果字符串长度是10^5，O(n^2 log n)直接挂了。我们得考虑一种更高效的方法。
经过一番思考后，我们发现可以借助一种叫做“最小表示法”的算法来解决这个问题。最小表示法是一个非常经典的字符串算法，用来高效地找到一个字符串的最小轮调。
具体地，最小表示法可以通过“最小循环排列”来求解，这也是著名的** Booth算法**的一个应用。它的时间复杂度是O(n)，比排序要高效得多。通过这种方式，我们不需要生成所有轮调，直接用算法得到最小轮调。
Booth算法的核心思想：
将字符串本身与它自己拼接成一个新的字符串 S + S。这样可以确保我们可以通过循环的方式，检查所有的轮调。然后通过滑动窗口的方式，找到该字符串的最小轮调。
Booth算法代码实现（Java版）
public class Main {
public static int[] minRotation(String s) {
String doubled = s + s; // 将字符串自己拼接
int n = s.length();
int[] f = new int[n * 2]; // 存储每次最小轮调的索引
int k = 0; // 最小轮调的开始位置 for (int j = 1; j < n * 2; j++) {
int i = f[j - k - 1];
while (i != 0 && doubled.charAt(k + i) != doubled.charAt(k + j)) {
if (doubled.charAt(k + i) > doubled.charAt(k + j)) {
k = j;
}
i = f[i - 1];
}
if (doubled.charAt(k + i) != doubled.charAt(k + j)) {
if (doubled.charAt(k + i) > doubled.charAt(k + j)) {
k = j;
}
f[j - k] = 0;
} else {
f[j - k] = i + 1;
}
}
return new int[] {k, k + n - 1};
}
public static void main(String[] args) {
String s = "bcdea";
int[] result = minRotation(s);
System.out.println("The lexicographically smallest rotation starts at index: " + result[0]);
}
}
代码解释
我们首先将输入字符串 S与它自己拼接成S + S，这样我们就可以模拟轮调了。然后我们用一个数组 f来记录每个字符的匹配信息，用来保存每次找到最小轮调的开始位置。核心的逻辑是通过比较当前字符和之前的字符，来决定是否更新最小轮调的起始位置。如果当前字符更小，就更新起始位置。
这段代码运行的时间复杂度是O(n)，大大提高了效率。
结果
对于字符串“bcdea”，该算法会返回最小轮调的起始位置是0，也就是说它本身就是字典序最小的轮调。你可以尝试将字符串改成其他值，验证算法的有效性。
我觉得这道题的核心就是理解最小表示法的思想。通过Booth算法，我们可以在O(n)的时间内高效地找到最小轮调，避免了暴力解法的低效。相信大家在面试或者算法学习时，遇到类似的字符串轮调题目时，可以把这个算法应用起来。虽然看起来很复杂，但理解了其中的逻辑，后面遇到这类问题就会变得相对容易了。
最后，我为大家打造了一份deepseek的入门到精通教程，完全免费：https://www.songshuhezi.com/deepseek
同时，也欢迎加入下方的交流群，一起研究deepseek的最新玩法