前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个字符串str，如：“dog is right”, 求字符串翻转字符串，要求单词不翻转
即：right is dog
进阶问题
给定一个字符串str，求str的左边size部分移动到右边
如 str = ABC1234 size = 3
结果为：1234ABC

解决方案

原问题：
1、将整个字符串翻转，再翻转内部字符串即可
进阶问题
解法一：
前size个字符翻转，后len-size个字符翻转，整体再翻转一下即可
解法二：
首先将前size个字符移动到后面，以题目为例，结果为 2341ABC
现在乱序的变成了2341，size为3的问题了，以递归的方式解决即可

代码编写

java语言版本

原问题：

    /**
     * 二轮测试：翻转字符串,内部不翻转
     */
    public static void reverseCP1(char[] chars) {
        if (chars == null || chars.length == 0) {
            return;
        }
        // 先翻转
        reverseChar(chars, 0, chars.length-1);
        int left = -1, right = -1;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != ' ') {
                // 可能是开头，也可能是中间
                left = i == 0 || chars[i-1] == ' ' ? i : left;
                // 可能是中间，也可能是结尾
                right = i == chars.length-1 || chars[i+1] == ' ' ? i : -1;
            }
            if (left != -1 && right != -1) {
                // 左右都找到了，直接翻转
                reverseChar(chars, left, right);
                // 重置
                left = -1;
                right = -1;
            }
        }
    }

进阶问题：

    /**
     * 问题二： 二轮测试，方法一
     */
    public static void reverseBySizeCp2(char[] chars, int size) {
        if (chars == null || chars.length == 0) {
            return;
        }
        reverseChar(chars, 0, size - 1);
        reverseChar(chars, size, chars.length-1);
        reverseChar(chars, 0, chars.length-1);
    }

    /**
     * 二轮测试：递归法
     * @param chars
     * @param size
     */
    public static void reverseBySize2Cp2(char[] chars, int size) {
        if (chars == null || chars.length == 0 || size <= 0) {
            return;
        }
        reverseBySize2CpHelper(chars, 0, size-1, size, chars.length-1);
    }

    /**
     * 递归主体
     * @param chars
     * @param left1
     * @param right1
     * @param left2
     * @param right2
     */
    private static void reverseBySize2CpHelper(char[] chars, int left1, int right1, int left2, int right2) {
        // 先做一个长度差值
        int len1 = right1 - left1 + 1;
        int len2 = right2 - left2 + 1;
        // 将值复制一份，最好不要使用参数
        int left1New = left1;
        int right1New = right1;
        int left2New = left2;
        int right2New = right2;
        int offset = Math.abs(len1 - len2);

        // 注意这里只有右边长的时候才需要offset
        if (len2 > len1) {
            left2New += offset;
        }
        // 开始替换:这里其实一个判断就可以
        while (left1New <= right1New && left2New <= right2New) {
            char tmp = chars[left1New];
            chars[left1New] = chars[left2New];
            chars[left2New] = tmp;
            left1New++;
            left2New++;
        }
        // 替换完成后,开始准备下一轮递归
        if (len1 > len2) {
            reverseBySize2CpHelper(chars, left1New, right1, left2, right2);
        }else if (len1 == len2){
            return;
        }else {
            reverseBySize2CpHelper(chars, left1, right1, left2, left2 + offset - 1);
        }
    }

    public static void main(String[] args) {
        char[] chars = "pig loves dog".toCharArray();

        reverseCP1(chars);
    }

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

翻转字符串类型的问题，可以解决字符串的移动、字符串的部分翻转类型问题，递归的方式是书里的方法，要我想的话可能想不太到，不过实现一下感觉也挺有意思的。
进阶问题的翻转方法其实对我有些启发，日常业务可能也会用到，三次的翻转可以达到空间复杂度为O(1)的移动字符串效果还是值得借鉴的。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！