【牛客编程巅峰赛S1第9场】牛牛的字符反转

题目

牛牛有一个长度为 n 的字符串，他想进行循环右移 k 位的操作，求他最少对这个字符串进行几次区间反转操作能实现循环右移 k 位呢。
给定一个字符串长度 n 和循环右移次数 k，求最少反转次数。
假设字符串每一位都不同。

解题思路

令 $0<k<n$ ，三步翻转法：

将数组第 $i ( i\in [0,n-1-k] )$ 项进行对称翻转，即对数组前 $n-k$ 项进行翻转；
将数组第 $i ( i\in [n-k,n-1] )$ 项进行对称翻转，即对数组后 $k$ 项进行翻转；
将数组第 $i ( i\in [0,n-1] )$ 项进行对称翻转，即对整个数组进行翻转。

所得数组即为循环右移 $k$ 项的结果。

例如，字符串 12345678，想要进行循环右移 3 位的操作，可以执行：

先将字符串前 5 个字符进行翻转，得 54321678。
再将字符串后 3 个字符进行翻转，得 54321876。
最后将整个字符串进行翻转，得 67812345。循环右移了 3 位。

同理还存在等效方法：

将数组第 $i ( i\in [0,n-1] )$ 项进行对称翻转，即对整个数组进行翻转；
将数组第 $i ( i\in [0,k-1] )$ 项进行对称翻转，即对数组前 $k$ 项进行翻转；
将数组第 $i ( i\in [k,n-1] )$ 项进行对称翻转，即对数组后 $n-k$ 项进行翻转。

三步翻转法可以实现数组循环右移操作，其时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ 。

回到本题，根据上面所述，可以得知所有字符串的最少翻转次数小于等于 3。列出特殊情况：

如果 $k=0$ 或者 $n=1$ ，不用翻转。
如果 $k=1$ ，那么翻转第 2 步可以省略；如果 $n-k=1$ ，那么翻转第二步可以省略。
如果 $k=2$ ，可以先翻转前 $n-1$ 个字符，再翻转后 $n-1$ 个字符。例，12345678 -> 76543218 -> 78123456。
如果 $n-k=2$ ，先翻转后 $n-1$ 个字符，再翻转前 $n-1$ 个字符。

C++代码

class Solution {
public:
    /**
     * 
     * @param n int整型 字符串长度n
     * @param k int整型 循环右移次数k
     * @return int整型
     */
    int solve(int n, int k) {
        // write code here
        k %= n;
        if(n==1 || k==0)
            return 0;
        if(n==2)
            return 1;
        if(k==1 || n-k==1 || k==2 || n-k==2)
            return 2;
        return 3;
    }
};