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

题目

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

解题思路

令 ，三步翻转法：

1. 将数组第 项进行对称翻转，即对数组前 项进行翻转；
2. 将数组第 项进行对称翻转，即对数组后 项进行翻转；
3. 将数组第 项进行对称翻转，即对整个数组进行翻转。

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

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

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

同理还存在等效方法：

1. 将数组第 项进行对称翻转，即对整个数组进行翻转；
2. 将数组第 项进行对称翻转，即对数组前 项进行翻转；
3. 将数组第 项进行对称翻转，即对数组后 项进行翻转。

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

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

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

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;
    }
};