每日一例 | 對(duì)java來(lái)說(shuō)這是個(gè)簡(jiǎn)單問(wèn)題：字符串左旋

題目描述

題目來(lái)源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/roman-to-integer/

難度：簡(jiǎn)單

字符串的左旋轉(zhuǎn)操作是把字符串前面的若干個(gè)字符轉(zhuǎn)移到字符串的尾部。請(qǐng)定義一個(gè)函數(shù)實(shí)現(xiàn)字符串左旋轉(zhuǎn)操作的功能。比如，輸入字符串"abcdefg"和數(shù)字2，該函數(shù)將返回左旋轉(zhuǎn)兩位得到的結(jié)果"cdefgab"。

示例 1：

輸入: s = "abcdefg", k = 2
輸出: "cdefgab"

示例 2：

輸入: s = "lrloseumgh", k = 6
輸出: "umghlrlose"

限制：

1 <= k < s.length <= 10000

提交記錄

看完這個(gè)題目，我覺(jué)得很簡(jiǎn)單，提交完，我也覺(jué)得很簡(jiǎn)單：

class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n) + s.substring(0, n);
    }
}

但是，看完提交的數(shù)據(jù)，我覺(jué)得問(wèn)題并沒(méi)有這么簡(jiǎn)單：

運(yùn)行時(shí)間上沒(méi)有任何問(wèn)題，但是內(nèi)存消耗上，并不是特別優(yōu)秀，我想看下有沒(méi)有雙100的揭發(fā)，畢竟這么簡(jiǎn)單的一個(gè)問(wèn)題，不再多研究下，都對(duì)不起出題人，我們先看編譯后的代碼：

class Solution {
    Solution() {
    }

    public String reverseLeftWords(String s, int n) {
        return s.substring(n) + s.substring(0, n);
    }
}

確實(shí)和源代碼一致，沒(méi)有什么可以?xún)?yōu)化的點(diǎn)，那我們換種方式重新實(shí)現(xiàn)，然后看下提交記錄。

stringBuilder

class Solution {
    public String reverseLeftWords(String s, int n) {
        return new StringBuilder(s.substring(n)).append(s.substring(0, n)).toString();
    }
}

換成StringBuilder字符串拼接，發(fā)現(xiàn)沒(méi)啥用，內(nèi)存反而上去了：

數(shù)組

class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] chars = s.toCharArray();
        return new String(Arrays.copyOfRange(chars, n, s.length())) + new String(Arrays.copyOfRange(chars, 0, n));
    }
}

換成數(shù)組，內(nèi)存消耗上去了，運(yùn)行時(shí)間又下來(lái)了：

然后我又換了一種數(shù)組拷貝的方式，但是執(zhí)行時(shí)間太長(zhǎng)了：

class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] chars = s.toCharArray();
        char[] targetChars = new char[chars.length];
        for (int i = 0; i < chars.length; i++) {
            if (i < n && (n + i) < chars.length) {
               targetChars[i] = chars[n + i];
            } else if (i >= chars.length - n) {
                targetChars[i] = chars[i - (chars.length - n)];
            } else {
                 targetChars[i] = chars[i + n];
            }
        }
        return new String(targetChars);
    }
}

執(zhí)行時(shí)間太長(zhǎng)了：

提交之后，我發(fā)現(xiàn)第一個(gè)if和最后面的else語(yǔ)句其實(shí)可以合并，然后就便成了這樣：

class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] chars = s.toCharArray();
        char[] targetChars = new char[chars.length];
        for (int i = 0; i < chars.length; i++) {
            if (i >= chars.length - n) {
                targetChars[i] = chars[i - (chars.length - n)];
            } else {
                 targetChars[i] = chars[i + n];
            }
        }
        return new String(targetChars);
    }
}

再次提交，性能確實(shí)比剛才好了，而且內(nèi)存方面更優(yōu)秀了，但是時(shí)間上確實(shí)還不太行：

好吧，數(shù)組這塊已經(jīng)算是到極限了，應(yīng)為要循環(huán)遍歷數(shù)組，所以時(shí)間上肯定是不行的，字符串越多，時(shí)間會(huì)越長(zhǎng)，也就是時(shí)間復(fù)雜度過(guò)高。

好吧，我放棄了，今天就到這里吧，有事要溜了……

總結(jié)

簡(jiǎn)單來(lái)說(shuō)，通過(guò)今天的示例，我發(fā)現(xiàn)想要優(yōu)化內(nèi)存方面的性能，有數(shù)組是更好的選擇，但如果要優(yōu)化時(shí)間，要避免時(shí)間復(fù)雜度過(guò)高的操作，比如循環(huán)、過(guò)多的條件語(yǔ)句。