翻轉(zhuǎn)單詞順序 vs 左旋轉(zhuǎn)字符串

題目一：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字啊的順序不變。為簡單起見，標(biāo)點符號和普通字母一樣處理。

舉例說明

例如輸入字符串”I am a student. ”，則輸出”student. a am I”。

解題思路

第一步翻轉(zhuǎn)句子中所有的字符。比如翻轉(zhuǎn)“I am a student. ”中所有的字符得到”.tneduts a m a I”，此時不但翻轉(zhuǎn)了句子中單詞的順序，連單詞內(nèi)的字符順序也被翻轉(zhuǎn)了。第二步再翻轉(zhuǎn)每個單詞中字符的順序，就得到了”student. a am I”。這正是符合題目要求的輸出。

代碼實現(xiàn)

/**
 * 將data中start到end之間的數(shù)字反轉(zhuǎn)
 *
 * @param data
 * @param start
 * @param end
 */
public static void reverse(char[] data, int start, int end) {
    if (data == null || data.length < 1 || start < 0 || end > data.length || start > end) {
        return;
    }
    while (start < end) {
        char tmp = data[start];
        data[start] = data[end];
        data[end] = tmp;
        start++;
        end--;
    }
}
/**
 * 題目一：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字啊的順序不變。
 * 為簡單起見，標(biāo)點符號和普通字母一樣處理。
 *
 * @param data
 * @return
 */
public static char[] reverseSentence(char[] data) {
    if (data == null || data.length < 1) {
        return data;
    }
    reverse(data, 0, data.length - 1);
    int start = 0;
    int end = 0;
    while (start < data.length) {
        if (data[start] == ' ') {
            start++;
            end++;
        } else if (end == data.length || data[end] == ' ') {
            reverse(data, start, end - 1);
            end++;
            start = end;
        } else {
            end++;
        }
    }
    return data;
}

題目二：字符串的左旋轉(zhuǎn)操作是把字符串前面的若干個字符轉(zhuǎn)移到字符串的尾部。請定義一個函數(shù)實現(xiàn)字符串左旋轉(zhuǎn)操作的功能。

舉例說明

比如輸入字符串”abcefg”和數(shù)字 2，該函數(shù)將返回左旋轉(zhuǎn) 2 位得到的結(jié)”cdefab”。

解題思路

以”abcdefg”為例，我們可以把它分為兩部分。由于想把它的前兩個字符移到后面，我們就把前兩個字符分到第一部分，把后面的所有字符都分到第二部分。我們先分別翻轉(zhuǎn)這兩部分，于是就得到”bagfedc”。接下來我們再翻轉(zhuǎn)整個字符串， 得到的”cde 也 ab”同 lj 好就是把原始字符串左旋轉(zhuǎn) 2 位的結(jié)果。

代碼實現(xiàn)

/**
 * 題目二：字符串的左旋轉(zhuǎn)操作是把字符串前面的若干個字符轉(zhuǎn)移到字符串的尾部。
 * 請定義一個函數(shù)實現(xiàn)字符串左旋轉(zhuǎn)操作的功能。
 * @param data
 * @param n
 * @return
 */
public static char[] leftRotateString(char[] data, int n) {
    if (data == null || n < 0 || n > data.length) {
        return data;
    }
    reverse(data, 0, data.length - 1);
    reverse(data, 0, data.length - n - 1);
    reverse(data, data.length - n, data.length - 1);
    return data;
}

完整代碼

public class Test42 {
    /**
     * 將data中start到end之間的數(shù)字反轉(zhuǎn)
     *
     * @param data
     * @param start
     * @param end
     */
    public static void reverse(char[] data, int start, int end) {
        if (data == null || data.length < 1 || start < 0 || end > data.length || start > end) {
            return;
        }
        while (start < end) {
            char tmp = data[start];
            data[start] = data[end];
            data[end] = tmp;
            start++;
            end--;
        }
    }
    /**
     * 題目一：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字啊的順序不變。
     * 為簡單起見，標(biāo)點符號和普通字母一樣處理。
     *
     * @param data
     * @return
     */
    public static char[] reverseSentence(char[] data) {
        if (data == null || data.length < 1) {
            return data;
        }
        reverse(data, 0, data.length - 1);
        int start = 0;
        int end = 0;
        while (start < data.length) {
            if (data[start] == ' ') {
                start++;
                end++;
            } else if (end == data.length || data[end] == ' ') {
                reverse(data, start, end - 1);
                end++;
                start = end;
            } else {
                end++;
            }
        }
        return data;
    }
    /**
     * 題目二：字符串的左旋轉(zhuǎn)操作是把字符串前面的若干個字符轉(zhuǎn)移到字符串的尾部。
     * 請定義一個函數(shù)實現(xiàn)字符串左旋轉(zhuǎn)操作的功能。
     * @param data
     * @param n
     * @return
     */
    public static char[] leftRotateString(char[] data, int n) {
        if (data == null || n < 0 || n > data.length) {
            return data;
        }
        reverse(data, 0, data.length - 1);
        reverse(data, 0, data.length - n - 1);
        reverse(data, data.length - n, data.length - 1);
        return data;
    }
    public static void main(String[] args) {
        test01();
        test02();
    }
    private static void test01() {
        System.out.println(new String(reverseSentence("I am a student.".toCharArray())));
        System.out.println(new String(reverseSentence("Wonderful".toCharArray())));
        System.out.println(new String(reverseSentence("".toCharArray())));
        System.out.println(new String(reverseSentence("    ".toCharArray())));
    }
    private static void test02() {
        System.out.println(new String(leftRotateString("abcdefg".toCharArray(), 2)));
        System.out.println(new String(leftRotateString("abcdefg".toCharArray(), 1)));
        System.out.println(new String(leftRotateString("abcdefg".toCharArray(), 6)));
        System.out.println(new String(leftRotateString("abcdefg".toCharArray(), 7)));
        System.out.println(new String(leftRotateString("abcdefg".toCharArray(), 0)));
    }
}

運行結(jié)果：

http://wiki.jikexueyuan.com/project/for-offer/images/60.png" alt="" />