小红书 秋招 笔试(三题)

算法：给定一个字符串s，允许执行至多一次操作。操作需要选择两个下标i和j，其中i必须小于j，同时选择一个正整数k作为移动步长。操作的具体内容是交换字符s[i]与s[i-k]的位置，同时交换字符s[j]与s[j+k]的位置。目标是通过最多一次这样的操作，使得得到的字符串字典序尽可能小。需要找出所有可能结果中字典序最小的字符串。

思路：由于只能操作一次，我们需要枚举所有可能的操作方案，即枚举不同的i、j和k值。但直接枚举所有参数会超时，因此需要优化。观察操作特点，发现操作实际上是将相距k的两个位置进行交换，且操作涉及四个位置。为了减小字典序，应尽可能将较小的字符移到前面。我们可以尝试固定k，然后寻找能使字符串变优的交换对。对于每个可能的k，预处理哪些位置可以进行交换，然后尝试交换i和j对应的位置，并检查结果。同时注意边界条件，确保i-k和j+k不越界。最后在所有可能的操作结果中选择字典序最小的字符串，包括不操作的原字符串。

#秋招笔面试记录##秋招笔试记录##秋招投递记录##秋招的破防瞬间#