算法 - 字符串旋转

题目简介#

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

解法1,暴力#

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

坑：#

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

1
package string_reverse;
2

3
/**
4
 * @Author: codefog
5
 * @email: at20s@sina.com
6
 * @Date: 2018/9/17 10:44 PM
7
 */
8
public class Solution1 {
9

10

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

20
    }
21

22
    public static String shifting(String str) {
23

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

34
    public static String rotateString(String string, int m) {
35
        while (m > 0) {
36
            string = shifting(string);
37
            m--;
38
        }
39
        return string;
40
    }
41

42

43

44
}

解法2，三步反转#

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

分割原字符串
分别反转
整体反转

1
public class Solution2 {
2

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

11
    }
12

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

21
        while (m < n) {
22
            char temp = cString[m];
23
            //第一个值被最后一个覆盖，然后移动m到下一个值
24
            cString[m++] = cString[n];
25
            //最后一个值被第一个覆盖，向前移动
26
            cString[n--] = temp;
27
        }
28
        return String.valueOf(cString);
29
    }
30

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

42
        return str;
43

44
    }
45
}

举一反三#

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

思路#

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

1
public class Others {
2

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

11
    }
12

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

21
        while (m < n) {
22
            char temp = cString[m];
23
            //第一个值被最后一个覆盖，然后移动m到下一个值
24
            cString[m++] = cString[n];
25
            //最后一个值被第一个覆盖，向前移动
26
            cString[n--] = temp;
27
        }
28
        return String.valueOf(cString);
29
    }
30

31
    public static String rotateString(String str) {
32
        //以空格分割，正则表达
33
        String[] spString = str.split("\\s+");
34
        str = "";
35
        //分别反转分割后的字符串
36
        if (spString.length > 0) {
37
            for (int i = 0; i < spString.length; ++i) {
38
                spString[i] = reverseString(spString[i],0,spString[i].length() - 1);
39
                //拼接完整字符串
40
                str += " " + spString[i];
41
            }
42
        }
43
        //总体旋转
44
        str = reverseString(str, 0, str.length() - 1);
45

46
        return str;
47
    }
48

49
}

复杂度同上.