實(shí)現(xiàn) strStr()

實(shí)現(xiàn) strStr() 函數(shù)。

給你兩個(gè)字符串 haystack 和 needle ，請(qǐng)你在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置（下標(biāo)從 0 開始）。如果不存在，則返回 -1。

方法一：暴力

public int strStr(String haystack, String needle) {
    for (int i = 0; i <= haystack.length() - needle.length(); i++) {
        boolean flag = true;
        for (int j = 0; j < needle.length(); j++) {
            if (haystack.charAt(i + j) != needle.charAt(j)) {
                flag = false;
                break;
            }
        }
        if (flag)  {
            return i;
        }
    }
    return -1;
}

時(shí)間復(fù)雜度：O(m*n)

方法二：KMP

public int strStr(String haystack, String needle) {
    int m = haystack.length(), n = needle.length();
    if (n == 0) {
        return 0;
    }
    int[] next = next(needle);
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (haystack.charAt(i) == needle.charAt(j)) {
            i++;
            j++;
        } else if (j == 0) {
            i++;
        } else {
            j = next[j - 1] + 1;
        }
    }
    return j == n ? i - n : -1;
}

private int[] next(String s) {
    int[] res = new int[s.length()];
    res[0] = -1; 
    for (int i = 1; i < s.length(); i++) {
        int j = res[i - 1];
        while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
            j = res[j];
        }
        if (s.charAt(i) == s.charAt(j + 1)) {
            res[i] = j + 1;
        } else {
            res[i] = -1;
        }
    }
    return res;
}

時(shí)間復(fù)雜度：O(m+n)

344. 反轉(zhuǎn)字符串

編寫一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來(lái)。輸入字符串以字符數(shù)組 s 的形式給出。

不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問題。

示例 1：

輸入：s = ["h","e","l","l","o"]
輸出：["o","l","l","e","h"]

示例 2：

輸入：s = ["H","a","n","n","a","h"]
輸出：["h","a","n","n","a","H"]

public void reverseString(char[] s) {
    int i = 0, j = s.length - 1;
    while (i < j) {
        char tmp = s[i];
        s[i++] = s[j];
        s[j--] = tmp;
    }
}

反轉(zhuǎn)字符串 II

給定一個(gè)字符串 s 和一個(gè)整數(shù) k，從字符串開頭算起，每計(jì)數(shù)至 2k 個(gè)字符，就反轉(zhuǎn)這 2k 字符中的前 k 個(gè)字符。

• 如果剩余字符少于 k 個(gè)，則將剩余字符全部反轉(zhuǎn)。
• 如果剩余字符小于 2k 但大于或等于 k 個(gè)，則反轉(zhuǎn)前 k 個(gè)字符，其余字符保持原樣。

示例 1：

輸入：s = "abcdefg", k = 2
輸出："bacdfeg"

示例 2：

輸入：s = "abcd", k = 2
輸出："bacd"

我的：

public String reverseStr(String s, int k) {
    StringBuilder sb = new StringBuilder();
    int i = 0;
    while (i < s.length()) {
        int spilt = i + k - 1;
        if (spilt >= s.length()) {
            spilt = s.length() - 1;
        }
        int j = spilt;
        while (j >= i) {
            sb.append(s.charAt(j--));
        }
        j = spilt + 1;
        while (j <= spilt + k && j < s.length()) {
            sb.append(s.charAt(j++));
        }
        i += 2 * k;
    }
    return sb.toString();
}

轉(zhuǎn)數(shù)組：

public String reverseStr(String s, int k) {
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i += k * 2) {
        reverse(chars, i, Math.min(chars.length - 1, i + k - 1));
    }
    return new String(chars);
}

private void reverse(char[] chars, int left, int right) {
    while (left < right) {
        char tmp = chars[left];
        chars[left++] = chars[right];
        chars[right--] = tmp;
    }
}

重復(fù)的子字符串

給定一個(gè)非空的字符串 s ，檢查是否可以通過由它的一個(gè)子串重復(fù)多次構(gòu)成。

示例 1:

輸入: s = "abab"
輸出: true
解釋: 可由子串 "ab" 重復(fù)兩次構(gòu)成。

示例 2:

輸入: s = "aba"
輸出: false

示例 3:

輸入: s = "abcabcabcabc"
輸出: true
解釋: 可由子串 "abc" 重復(fù)四次構(gòu)成。 (或子串 "abcabc" 重復(fù)兩次構(gòu)成。)

方法一：枚舉
從頭開始，將已遍歷的串認(rèn)為是可能的子串，依次向后比較

public boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    // 子串為s[0, i - 1]
    for (int i = 1; i * 2 <= n; i++) {
        // 整除才有可能
        if (n % i == 0) {
            boolean match = true;
            for (int j = i; j < n; j++) {
                // i就是子串的長(zhǎng)度，-i就是上一次出現(xiàn)的位置
                if (s.charAt(j) != s.charAt(j - i)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return true;
            }
        }
    }
    return false;
}

時(shí)間復(fù)雜度：O(n²)

方法二：字符串匹配
如果字符串 S 包含一個(gè)重復(fù)的子字符串，意味著可以多次 “移位和換行”`您的字符串，并使其與原始字符串匹配。

例如：abcabc
移位一次：bcabca
移位兩次：cabcab
移位三次：abcabc
現(xiàn)在字符串和原字符串匹配了，所以可以得出結(jié)論存在重復(fù)的子串。
基于這個(gè)思想，可以每次移動(dòng)k個(gè)字符，直到匹配移動(dòng) length / 2次。但是這樣對(duì)于重復(fù)字符串很長(zhǎng)的字符串，效率會(huì)非常低。

public boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    for (int i = 0; i < s.length() / 2; i++) {
        String sub = s.substring(0, i + 1);
        if (s.equals(s.substring(i + 1) + sub)) {
            return true;
        }
    }
    return false;
}

為了避免這種無(wú)用的環(huán)繞，可以創(chuàng)建一個(gè)新的字符串 str，它等于原來(lái)的字符串 S 再加上 S 自身，這樣其實(shí)就包含了所有移動(dòng)的字符串。

比如字符串：S = acd，那么 str = S + S = acdacd

acd 移動(dòng)的可能：cda、dac。其實(shí)都包含在了 str 中了

一開始 acd (acd) ，移動(dòng)一次 a(cda)cd，移動(dòng)兩次 ac(dac)d。循環(huán)結(jié)束

所以可以直接判斷 str 中去除首尾元素之后，是否包含自身元素。如果包含。則表明存在重復(fù)子串

public boolean repeatedSubstringPattern(String s) {
    return (s + s).indexOf(s, 1) != s.length();
}

方法三：KMP
利用next數(shù)組特點(diǎn)

public boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    if (n == 0) {
        return false;
    }
    int[] next = next(s);
    // (n- (next[n- 1] + 1)) 也就是： 12(字符串的長(zhǎng)度) - 8(最長(zhǎng)公共前后綴的長(zhǎng)度) = 4， 4正好可以被 12(字符串的長(zhǎng)度) 整除，所以說(shuō)明有重復(fù)的子字符串（asdf）
    if (next[n - 1] >= 0 && n % (n - next[n - 1] - 1) == 0) {
        return true;
    }
    return false;
}

private int[] next(String s) {
    int[] res = new int[s.length()];
    res[0] = -1; 
    for (int i = 1; i < s.length(); i++) {
        int j = res[i - 1];
        while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
            j = res[j];
        }
        if (s.charAt(i) == s.charAt(j + 1)) {
            res[i] = j + 1;
        } else {
            res[i] = -1;
        }
    }
    return res;
}