算法 - 字符串旋转

题目简介

字符串反转，字符串旋转，例如abcdef旋转为defabc。

解法1,暴力

时间复杂度O(nm),空间O(1) (长度为n，移动m个字符）

坑：

java如果想覆盖字符串的值，不能和c/c++一样，直接传入指针就能修改原值，而是需要old = opeartion(old)这样子把旧的引用覆盖掉才行。

package string_reverse;

/**
 * @Author: codefog
 * @email: at20s@sina.com
 * @Date: 2018/9/17 10:44 PM
 */
public class Solution1 {


    /**
     * 暴力一次一个字符的移动
     * 时间复杂度O(nm),空间O(1) (长度为n，移动m个字符）
     * @param args
     */
    public static void main(String[] args) {
        String str = "hello world!";
        System.out.println(rotateString(str,3));

    }

    public static String shifting(String str) {

        char[] strs = str.toCharArray();
        char temp = strs[0];
        for (int i = 1; i < strs.length; ++i) {
            //从第一个开始，一次被后一个字符覆盖
            strs[i - 1] = strs[i];
        }
        strs[strs.length - 1] = temp;
        return String.valueOf(strs);
    }

    public static String rotateString(String string, int m) {
        while (m > 0) {
            string = shifting(string);
            m--;
        }
        return string;
    }



}

解法2，三步反转

时间复杂度O(n),空间复杂度O(1)

1. 分割原字符串
2. 分别反转
3. 整体反转

public class Solution2 {

    /**
     * 三步反转
     * @param args
     */
    public static void main(String[] args) {
        String str = "hello world!";
        System.out.println(rotateString(str,4));

    }

    /**
     * 把字符串m到n的位置反转
     * @param string
     * @return
     */
    public static String reverseString(String string,int m, int n) {
        char[] cString = string.toCharArray();

        while (m < n) {
            char temp = cString[m];
            //第一个值被最后一个覆盖，然后移动m到下一个值
            cString[m++] = cString[n];
            //最后一个值被第一个覆盖，向前移动
            cString[n--] = temp;
        }
        return String.valueOf(cString);
    }

    public static String rotateString(String str, int m) {
        //m = m % length, 如果移动的位置数量超过长度，则相当于一个环旋转
        // 3 % 5 = 3， 小于字符串长度则没有问题
        m %= str.length();
        //反转第一部分
        str = reverseString(str,0, m);
        //反转第二部分
        str = reverseString(str, m, str.length() - 1);
        //整体反转
        str = reverseString(str, 0, str.length() - 1);

        return str;

    }
}

举一反三

反转句子中单词的位置，比如i am a student.， 反转后student. a am i，标点符号作为单词的一部分处理.

思路

1. 以空格分割句子为n(单词数量)部分
2. 分别反转
3. 总体反转

public class Others {

    /**
     * 反转句子中的单词
     * @param args
     */
    public static void main(String[] args) {
        String str = "i am quite a student.";
        System.out.println(rotateString(str));

    }

    /**
     * 把字符串m到n的位置反转
     * @param string
     * @return
     */
    public static String reverseString(String string,int m, int n) {
        char[] cString = string.toCharArray();

        while (m < n) {
            char temp = cString[m];
            //第一个值被最后一个覆盖，然后移动m到下一个值
            cString[m++] = cString[n];
            //最后一个值被第一个覆盖，向前移动
            cString[n--] = temp;
        }
        return String.valueOf(cString);
    }

    public static String rotateString(String str) {
        //以空格分割，正则表达
        String[] spString = str.split("\\s+");
        str = "";
        //分别反转分割后的字符串
        if (spString.length > 0) {
            for (int i = 0; i < spString.length; ++i) {
                spString[i] = reverseString(spString[i],0,spString[i].length() - 1);
                //拼接完整字符串
                str += " " + spString[i];
            }
        }
        //总体旋转
        str = reverseString(str, 0, str.length() - 1);

        return str;
    }

}

复杂度同上.