代碼隨想錄第八天喷鸽， 哈希表完成鹰霍，開始String
今日任務(wù)
● 344.反轉(zhuǎn)字符串
● 541. 反轉(zhuǎn)字符串II
● 劍指Offer 05.替換空格
● 151.翻轉(zhuǎn)字符串里的單詞
● 劍指Offer58-II.左旋轉(zhuǎn)字符串
雙指針
時間復(fù)雜度： O(N)
空間復(fù)雜度： O(1)
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while(left < right){
char temp = s[right];
s[right] = s[left];
s[left] = temp;
left++;
right--;
}
}
}
給定一個字符串 s 和一個整數(shù) k建邓，從字符串開頭算起, 每計(jì)數(shù)至 2k 個字符筛武，就反轉(zhuǎn)這 2k 個字符中的前 k 個字符迈窟。
如果剩余字符少于 k 個私植，則將剩余字符全部反轉(zhuǎn)。
如果剩余字符小于 2k 但大于或等于 k 個车酣，則反轉(zhuǎn)前 k 個字符曲稼，其余字符保持原樣。
思路：
把string 轉(zhuǎn)換為character array, 與344.反轉(zhuǎn)字符相似湖员，串利用雙指針將兩個index之間字符反轉(zhuǎn)贫悄。
注意：
每隔2k個字符才有反轉(zhuǎn)操作，所以遍歷時step為2k, 即 i = i + 2*k;
最后一個循環(huán)對剩余字符(length % 2k)的操作： 如果剩余字符少于 k 個娘摔，則將剩余字符全部反轉(zhuǎn) 窄坦；如果剩余字符小于 2k 但大于或等于 k 個，則與之前循環(huán)相同凳寺，反轉(zhuǎn)前k個字符鸭津， 所以要反轉(zhuǎn)區(qū)間的upper bound 為 Math.min(i+k-1, length - 1)
class Solution {
public String reverseStr(String s, int k) {
int n = s.length();
char[] arr = s.toCharArray();
for(int i = 0; i < n; i = i + 2 * k){
//in last iteration, if there are fewer than k characters left,
// reverse all of them
reverse(arr, i, Math.min(i + k -1, n - 1));
}
return new String(arr); //convert char array back to Stringx
}
private void reverse(char[] arr, int left, int right){
while(left < right){
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
時間復(fù)雜度： O(N)
空間復(fù)雜度： O(n) 將String轉(zhuǎn)化為char array 的長度
劍指Offer 05. 替換空格
請實(shí)現(xiàn)一個函數(shù)，把字符串 s 中的每個空格替換成"%20"肠缨。
return s.replace(" ","%20");
方法一： 將string 轉(zhuǎn)化為char array, 新建一個stringBuilder 進(jìn)行修改
StringBuilder in Java represents a mutable sequence of characters. StringBuilder class provides an alternative to String Class, as it creates a mutable sequence of characters.
與StringBuffer區(qū)別： String Builder is not thread-safe and high in performance compared to String buffer. StringBuffer is synchronized, thread-safe.
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for(Character c : s.toCharArray()){
if(c == ' ') sb.append("%20");
else sb.append(c);
}
return sb.toString();
}
}
時間復(fù)雜度： O(N)
空間復(fù)雜度： O(n)
方法二： 雙指針法
首先擴(kuò)充數(shù)組到每個空格替換成"%20"之后的大小逆趋。
然后從后向前替換空格，也就是雙指針法
class Solution {
public String replaceSpace(String s) {
char[] sArr = s.toCharArray();
int n = s.length();
int count = 0; //記錄空格數(shù)量
for(int i = 0; i < n; i++){
if(s.charAt(i) == ' ') count++;
}
//添加完 "%20" 后的字符長度,string is immutable, so use charArray
//newArr 是 length 為 n + 2 * count的 empty char array
char[] newArr = new char[n + 2 * count];
//倒序遍歷修改：i 指向原字符數(shù)組尾部元素怜瞒， j 指向新字符數(shù)組V 尾部元素父泳；
//newArr is an empty array, 所以要遍歷完整個sArr to fill all the values
for(int i = n - 1, j = newArr.length - 1; i >= 0; i--, j--){
//當(dāng) s[i] 不為空格時：執(zhí)行 s[j] = s[i]
if(sArr[i] != ' '){
newArr[j] = sArr[i];
}else{
//當(dāng) s[i] 為空格時：將字符串閉區(qū)間 [j-2, j] 的元素修改為 "%20" ；
//由于修改了 3 個元素吴汪，因此需要 j -= 2
newArr[j] = '0';
newArr[j - 1] = '2';
newArr[j - 2] = '%';
j -= 2;
}
}
return new String(newArr);
}
}
時間復(fù)雜度： O(N)
空間復(fù)雜度： O(n) 字符數(shù)組
151. 翻轉(zhuǎn)字符串里的單詞
方法一：
利用StringBuilder
雙指針從右向左遍歷惠窄， 遇到space時說明得到一個word,放入StringBuilder
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
int r = s.length()-1, l = r;
//after processed the first character(last in loop), position of l is -1
while (l >= -1)
{
if (l > -1 && s.charAt(l) != ' ')
l--;
else if (l < r)
{ // l reaches " ", now between [l +1, r] is one word
//The substring begins at the specified beginIndex
//and extends to the character at index endIndex - 1
sb.append(s.substring(l+1, r+1) + " ");
l--;
r = l;
}
else // l == r && charAt(l) == ' '
{
l--;
r--;
}
}
sb.deleteCharAt(sb.length()-1); //remove space at the end
return sb.toString();
}
}
時間復(fù)雜度： O(N)
空間復(fù)雜度： O(n) StringBuilder
方法二 庫函數(shù)
class Solution {
public String reverseWords(String s) {
s = s.trim();
List<String> words = Arrays.asList(s.split("\\s+"));
Collections.reverse(words);
return String.join(" ", words);
}
}
時間復(fù)雜度： O(N)
空間復(fù)雜度： O(n) list
方法三：
移除多余空格
將整個字符串反轉(zhuǎn)
將每個單詞反轉(zhuǎn)
舉個例子，源字符串為："the sky is blue "
移除多余空格 : "the sky is blue"
字符串反轉(zhuǎn)："eulb si yks eht"
單詞反轉(zhuǎn)："blue is sky the"
class Solution {
public String reverseWords(String s) {
/**
* 不使用Java內(nèi)置方法實(shí)現(xiàn)
* <p>
* 1.去除首尾以及中間多余空格
* 2.反轉(zhuǎn)整個字符串
* 3.反轉(zhuǎn)各個單詞
*/
// System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
// 1.去除首尾以及中間多余空格
StringBuilder sb = removeSpace(s);
// 2.反轉(zhuǎn)整個字符串
reverseString(sb, 0, sb.length() - 1);
// 3.反轉(zhuǎn)各個單詞
reverseEachWord(sb);
return sb.toString();
}
private StringBuilder removeSpace(String s) {
int start = 0;
int end = s.length() - 1;
while (s.charAt(start) == ' ') start++;
while (s.charAt(end) == ' ') end--;
StringBuilder sb = new StringBuilder();
while (start <= end) {
char c = s.charAt(start);
if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
start++;
}
return sb;
}
/**
* 反轉(zhuǎn)字符串指定區(qū)間[start, end]的字符
*/
public void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
// System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
}
private void reverseEachWord(StringBuilder sb) {
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
}
時間復(fù)雜度： O(N)
空間復(fù)雜度： O(n) java string 不能原地修改漾橙，利用StringBuilder 空間為n
劍指Offer58-II. 左旋轉(zhuǎn)字符串
字符串的左旋轉(zhuǎn)操作是把字符串前面的若干個字符轉(zhuǎn)移到字符串的尾部杆融。請定義一個函數(shù)實(shí)現(xiàn)字符串左旋轉(zhuǎn)操作的功能。比如霜运，輸入字符串"abcdefg"和數(shù)字2脾歇，該函數(shù)將返回左旋轉(zhuǎn)兩位得到的結(jié)果"cdefgab"蒋腮。
方法一： substring
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
int len = s.length();
if( len <= n ) return s;
//string index 0 to len-1
sb.append(s.substring(n));
sb.append(s.substring(0,n));
return new String(sb);
}
}
時間復(fù)雜度： O(n) substring 復(fù)雜度O(n)
As of update 6 within Java 7's lifetime, the behaviour of substring changed to create a copy - so every String refers to a char[] which is not shared with any other object. So at that point, substring() became an O(n) operation where n is the numbers in the substring.
空間復(fù)雜度： O(n) StringBuilder
方法二：列表遍歷拼接
算法流程：
新建一個 list(Python)、StringBuilder(Java) 藕各，記為 res 池摧；
先向 res 添加 “第 n+1 位至末位的字符” ；
再向res 添加 “首位至第 n 位的字符” 激况；
將 res 轉(zhuǎn)化為字符串并返回作彤。
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
int len = s.length();
if( len <= n ) return s;
//string index 0 to len-1
for(int i = n; i < len; i++){
sb.append(s.charAt(i));
}
for(int i = 0; i < n; i++){
sb.append(s.charAt(i));
}
return new String(sb);
}
}
時間復(fù)雜度： O(n)
空間復(fù)雜度： O(n)
方法三：三次反轉(zhuǎn)
與151題相似， 依然可以通過局部反轉(zhuǎn)+整體反轉(zhuǎn) 達(dá)到左旋轉(zhuǎn)的目的乌逐。
具體步驟為：
反轉(zhuǎn)區(qū)間為前n的子串
反轉(zhuǎn)區(qū)間為n到末尾的子串
反轉(zhuǎn)整個字符串
C++ 可達(dá)到空間復(fù)雜度為O(1)
java python String 不可修改竭讳，仍然要用到StringBuilder O(n)
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder(s);
int len = s.length();
if( len <= n ) return s;
//string index 0 to len-1
reverseString(sb, 0, n - 1);
reverseString(sb, n, len - 1);
//reverseString(sb, 0, len - 1);
//return new String(sb);
return sb.reverse().toString();
}
private void reverseString(StringBuilder sb, int startIndex, int endIndex){
char temp;
while(startIndex < endIndex){
temp = sb.charAt(startIndex);
//public void setCharAt(int index, char ch)
sb.setCharAt(startIndex, sb.charAt(endIndex));
sb.setCharAt(endIndex, temp);
startIndex++;
endIndex--;
}
}
}
