牛牛的字符反转 牛客编程巅峰赛S1第9场 - 青铜&白银

这道题最直观的解法并不难，需要我们分情况判断一下所有的情况。

举个例子“1234567”。循环右移的所有情况为
7123456、6712345、5671234、4567123、3456712、2345671、1234567。

我们来看看所有情况所需的最少区间反转次数。

• 1234567->6543217->7123456 先在[1,6]之间反转，最后整体[1,7]反转。至少2次
• 1234567->6543217->6712345 先在[1,6]之间反转，最后在[2,7]之间反转。至少2次
• 1234567->4321567->4321765->5671234 先在[1,4]反转，再[5,7]反转，最后整体反转。至少3次
• 1234567->3214567->3217654->4567123 先在[1,3]反转，再[4,7]反转，最后整体反转。至少3次
• 1234567->1765432->2345671 先在[2,7]之间反转，最后整体反转。至少2次
• 1234567->1765432->3456712 先在[2,7]之间反转，最后在[1,6]之间反转。至少2次
• 1234567->1234567 无需区间反转。至少0次

从这个例子可以看出，所需的最少区间反转次数符合一定对称的规律，在第一、第二、倒数第一和倒数第二的情况中只需2次区间反转。中间两次都只需3次。

因此我们可以得出以下规律，如果循环右移操作k为1、2、n-1和n-2次（此处k = k%n），则需要至少2次区间反转。否则至少3次区间反转。

if(k == 1 || k == 2 || k == n - 2 || k == n - 1)
            return 2;
        return 3;

接着我们考虑特殊情况，如果字符串长度n等于 1 或者 循环右移操作k等于 0 则返回0。
如果字符串长度n等于 2 。当 k为偶数时，返回0；当 k为奇数时，返回1；

参考代码如下：

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