程式碼隨想錄-day3
字串
字串的題目，通常涉及到對字串進行各種操作，由於JAVA提供了非常多的庫函數，所以在很多題目中我們可以使用庫函數快速使這道題解決，但是這與我們訓練演演算法和編碼能力相違背。
所以我們在本章專題裡面，主要是使用我們自己構造的函數對字串進行，操作加深我們對字串操作的理解，當我們訓練熟悉後可以使用庫函數直接執行。
344.反轉字串
題意：編寫一個函數，其作用是將輸入的字串反轉過來。輸入字串以字元陣列 char[] 的形式給出。
不要給另外的陣列分配額外的空間，你必須原地修改輸入陣列、使用 O(1) 的額外空間解決這一問題。
你可以假設陣列中的所有字元都是 ASCII 碼錶中的可列印字元。
範例 1：
輸入：["h","e","l","l","o"]
輸出：["o","l","l","e","h"]
範例 2：
輸入：["H","a","n","n","a","h"]
輸出：["h","a","n","n","a","H"]
思路
在此我們考慮不使用額外空間的一種做法，我們可以使用一個在頭，一個在尾部的雙指標對字串做一個反轉。
每次雙指標所指向的字元進行交換，當兩個指標穿越的時候就表示已經處理完整個字串。
程式碼
class Solution {
public void reverseString(char[] s) {
int n = s.length;
int l = 0, r = n - 1;
while (l < r) {
swap(s, l, r);
l ++;
r --;
}
}
public void swap(char[] s, int i, int j) {
if (i == j) return ; // 如果沒有這行當交換相同元素時結果會是0
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
}
}
541. 反轉字串II
題意：給定一個字串 s 和一個整數 k，從字串開頭算起, 每計數至 2k 個字元，就反轉這 2k 個字元中的前 k 個字元。
如果剩餘字元少於 k 個，則將剩餘字元全部反轉。
如果剩餘字元小於 2k 但大於或等於 k 個，則反轉前 k 個字元，其餘字元保持原樣。
範例:
輸入: s = "abcdefg", k = 2
輸出: "bacdfeg"
思路
本題邏輯並不能，但是存在多種情況，導致在編寫程式碼的可能有多個if-else，並且對某個特點的情況存在遺漏。
為了解決這個問題，我們可以每次移動2k個區間，如何判斷是否有要翻轉的區間。
程式碼
class Solution {
public String reverseStr(String s, int k) {
char[] ca = s.toCharArray();
int n = ca.length;
for (int i = 0; i < n; i += 2 * k) {
if (i + k <= n) { // 剩餘區間大於等於k
reverse(ca, i, i + k - 1);
continue;
}
reverse(ca, i, n - 1); // 剩餘區間小於k
}
return new String(ca);
}
public void reverse(char[] s, int start, int end) {
for (int i = start, j = end; i < j; i ++, j --) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
}
劍指Offer 05.替換空格
題意：請實現一個函數，把字串 s 中的每個空格替換成"%20"。
範例 1： 輸入：s = "We are happy."
輸出："We%20are%20happy."
思路
如果不限制使用O（1）的空間，我們可以直接使用一個StringBuilder進行操作，這樣的程式碼不能直接寫成，在此我們繼續討論限制O(1)的空間複雜度進行操作。
我們可以先對字串進行擴充，然後從後向前遍歷。我們不在前面進行擴充的原因：如果在前面擴充，如果我們要新增一個元素，就得把一個元素往後移動，這樣我們每次操作的時間複雜度就為O(n2)
其實很多陣列填充類的問題，都可以先預先給陣列擴容帶填充後的大小，然後在從後向前進行操作。 ——程式碼隨想錄
我們設定兩個指標一個i指向原字串的末尾，一個j指向擴充後的末尾，如果此時s[i] != ' '，我們把s[j] = s[i]。反之我們把空格替換為%20，j再往後移動2位。
程式碼
class Solution {
public String replaceSpace(String s) {
if (s == null || s.length() == 0) return s; // 空字串跳過
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i ++ ) {
if (s.charAt(i) == ' ')
sb.append(" ");
}
if (sb.length() == 0) return s; // 沒有空格
int oldSize = s.length();
s += sb.toString();
int newSize = s.length();
char[] ca = s.toCharArray();
for (int i = oldSize - 1, j = newSize - 1; i < j; i --, j --) {
if (ca[i] != ' ') {
ca[j] = ca[i];
} else {
ca[j] = '0';
ca[j - 1] = '2';
ca[j - 2] = '%';
j -= 2;
}
}
return new String(ca);
}
}
151.翻轉字串裡的單詞
題意：給定一個字串，逐個翻轉字串中的每個單詞。
範例 1：
輸入: "the sky is blue"
輸出: "blue is sky the"
範例 2：
輸入: " hello world! "
輸出: "world! hello"
解釋: 輸入字串可以在前面或者後面包含多餘的空格，但是反轉後的字元不能包括。
範例 3：
輸入: "a good example"
輸出: "example good a"
解釋: 如果兩個單詞間有多餘的空格，將反轉後單詞間的空格減少到只含一個。
思路
在之前，我們已經通過自己實現的reverse()對字串進行了翻轉，本題在之前翻轉字串的問題的基礎上進行了擴充套件，我們要去掉字串前後多餘的空格和單詞之前多餘的空格。
值得注意的是，每個單詞之間必須保留一個空格。然後在此基礎上我們先翻轉整個字串，再翻轉每個單詞即可。
本題的重難點其實不在翻轉，而是在去除空格。我們採用與之前「移除元素」那題的邏輯書寫一個函數去除空格。
public char[] removeExtraSpaces(char[] s) {
int slow = 0; // 表示處理完的字串的末尾
for (int fast = 0; fast < s.length; fast ++ ) {
if (s[fast] != ' ') {
if (slow != 0) s[slow ++] = ' '; // 如果不是第一個單詞就先在前面加一個空格先
while (fast < s.length && s[fast] != ' ') {
s[slow ++] = s[fast ++];
}
}
}
char[] newChars = new char[slow];
System.arraycopy(s, 0, newChars, 0, slow); // 重設大小後拷貝
return newChars;
}
程式碼
class Solution {
public String reverseWords(String s) {
char[] ca = s.toCharArray();
ca = removeExtraSpaces(ca);
reverse(ca, 0, ca.length - 1);
for (int i = 0, j = 0; i <= ca.length; i ++ ) {
if (i == ca.length || ca[i] == ' ') { // 先特判最後一個單詞
reverse(ca, j , i - 1);
j = i + 1; // j重新指向下一個單詞的開頭
}
}
return new String(ca);
}
public void reverse(char[] s, int i, int j) {
while (i < j) {
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
i ++;
j --;
}
}
public char[] removeExtraSpaces(char[] s) {
int slow = 0;
for (int fast = 0; fast < s.length; fast ++ ) {
if (s[fast] != ' ') {
if (slow != 0) s[slow ++] = ' '; // 如果不是第一個單詞就先在前面加一個空格先
while (fast < s.length && s[fast] != ' ') {
s[slow ++] = s[fast ++];
}
}
}
char[] newChars = new char[slow];
System.arraycopy(s, 0, newChars, 0, slow);
return newChars;
}
}
劍指Offer58-II.左旋轉字串
題意：字串的左旋轉操作是把字串前面的若干個字元轉移到字串的尾部。請定義一個函數實現字串左旋轉操作的功能。比如，輸入字串"abcdefg"和數位2，該函數將返回左旋轉兩位得到的結果"cdefgab"。
範例 1：
輸入: s = "abcdefg", k = 2
輸出: "cdefgab"
範例 2：
輸入: s = "lrloseumgh", k = 6
輸出: "umghlrlose"
限制：
1 <= k < s.length <= 10000
思路
在本題中我們還是利用整體-區域性翻轉的方法來實現左旋轉字串的操作，通過簡單的模擬我們不難得出：我們可以先翻轉前k個字串，再翻轉剩下的字元，最後整體翻轉即可實現左旋轉的效果。
程式碼
class Solution {
public String reverseLeftWords(String s, int n) {
char[] ca = s.toCharArray();
reverse(ca, 0, n - 1);
reverse(ca, n, ca.length - 1);
reverse(ca, 0, ca.length - 1);
return new String(ca);
}
public void reverse(char[] s, int i, int j) {
while (i < j) {
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
i ++;
j --;
}
}
}
28. 找出字串中第一個匹配項的下標
題意：給定一個 haystack 字串和一個 needle 字串，在 haystack 字串中找出 needle 字串出現的第一個位置 (從0開始)。如果不存在，則返回 -1。
範例 1: 輸入: haystack = "hello", needle = "ll" 輸出: 2
範例 2: 輸入: haystack = "aaaaa", needle = "bba" 輸出: -1
說明: 當 needle 是空字串時，我們應當返回什麼值呢？這是一個在面試中很好的問題。 對於本題而言，當 needle 是空字串時我們應當返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。
思路
本題是一道經典的KMP，KMP是為了快速找到一個字串是否是另一個字串的子串。為了實現KMP演演算法，我們必須要求一個字首表，即next陣列。