2024.10/14

在算法设计与分析上发现了一个有意思的题：

这题我一时间没思路说真的，相当于字符串遍历一次，这过程只能额外借用 1 个空间的大小。我后面想到了一种方法，但是不是分治。

个人思路：

就是使用循环的方法去解决这个问题:

1.    字符串是自循环移动的，假如 n = 4，k = 2，我们从 1 出发，则到 3，再到 0 结束。从 2 出发到 4 ，在到 2 结束，意思就是说，循环移动最后形成的是一个循环，直观的样例

2.    因此可以因为 n，k 分裂成多个循环，每个循环进行两两交换即可，并且这些循环时连续的，非常方便，下面看一下代码。（但实际上到这里不完全正确

3.    但是我们看下面特殊的样例。这个样例就不能用上面的代码了。因为你会发现，在第一次循环时，它提前走过后面要走过的 [0, k) 之间的数字，就这样重复了，这样交换就明显的存在问题。之前每个循环的交换都是互不影响的。那这个想法就错了么？实际不然，往下看。

4.    仔细观察上面的数字，我们排序一下。这一看，好像是以 7 为循环的。那么这个数字，是怎么来的？其实能很明显的发现，其还是循环的，如果以 7 循环，那么，每个循环就不会重复，而这个 7 其实是 217 和 77 的 gcd，这是符合数学上的原理的。因此这题就解出来了！

正确源代码：

总结：循环 + gcd，算是个有意思的思路，感觉以后可能在别的题目可以用到！