151.反轉字符串中的單詞
題目鏈接：151. 反轉字符串中的單詞 - 力扣（LeetCode）
視頻鏈接：代碼隨想錄 (programmercarl.com)
第一想法
使用split函數然后倒序相加
代碼隨想錄想法
先去除空格，再將整個字符串反轉，再將單個單詞反轉
去除空格
如果時間復雜度為O(n)的話，新new StringBuilder sb追加加字符即可。既要判斷非空格字符原樣追加又要保證單詞間距一個空格的距離的邏輯是
if(s.charAt(start)!=' '||sb.charAt(sb.length()-1)!=' ')//如果當前字符不為空或者已追加新單詞后沒有空格sb.append(s.charAt(start));
代碼
class Solution {public String reverseWords(String s) {//去除空格StringBuilder sb = RemoveSpace(s);//反轉整個字符串reverseWholeWord(sb,0,sb.length()-1);//反轉單個字符串ReverseSingleWord(sb);//返回return sb.toString();}public StringBuilder RemoveSpace(String s){int start = 0;int end = s.length() - 1;StringBuilder sb = new StringBuilder();while (s.charAt(start)==' ')start++;//去除前導空字符while (s.charAt(end)==' ')end--;//去除后導空字符while (start<=end){if(s.charAt(start)!=' '||sb.charAt(sb.length()-1)!=' ')//如果當前字符不為空或者已追加新單詞后沒有空格sb.append(s.charAt(start));start++;}return sb;}public void reverseWholeWord(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--;}}public void ReverseSingleWord(StringBuilder sb){int start = 0;int end = 1;while (start < sb.length()) {while (end<sb.length()&&sb.charAt(end)!=' ')end++;reverseWholeWord(sb,start,end-1);start = end + 1;end = start + 1;}}
}
class Solution2 {public String reverseWords(String s) {char[] oldCharArray = s.toCharArray();char[] newCharArray = new char[oldCharArray.length];int newIndex = 0;int i = oldCharArray.length - 1;while (i>=0){while (i>=0&&oldCharArray[i]==' ')i--;//去除末尾空格，循環結束時，i指向第一個非空格元素int right = i;//設定右邊界while (i>=0&&oldCharArray[i]!=' ')i--;//跳過一個單詞，循環結束時，i指向該元素的左邊界。首元素則指向-1，非首元素則指向前面的空格//單獨獲取一個單詞的邊界[i+1,right];for(int j = i+1;j<=right;j++){newCharArray[newIndex++] = oldCharArray[j];if(j==right)//如果抵達右邊界，則末尾加一個空格newCharArray[newIndex++] = ' ';}}if(newIndex == 0) return "";else return new String(newCharArray,0,newIndex - 1);}
}卡碼網55.右旋字符串
題目鏈接：55. 右旋字符串（第八期模擬筆試） (kamacoder.com)
文檔/視頻鏈接：代碼隨想錄 (programmercarl.com)
第一想法
定義雙端隊列，右端出n個元素加入到左端。但是這樣做就沒意義了。
或者先將整個字符串反轉，分別將子字符串反轉回來。
假設字符串為"abcdefg" ,n = 2
先反轉整體"gfedcba"，
再反轉局部：[0,n-1],變成 fg edcba;
? ? ? ? ? ? ? ? ? ? ? [n,length -1]變成 fg abcde
代碼隨想錄想法
看了感覺和第一想法差不多。
代碼
class Solution2{public String RightReverse(String s,int n){char[] charArray = s.toCharArray();//先反轉整體的Reverse(charArray,0,charArray.length-1);//再反轉局部Reverse(charArray,0,n-1);Reverse(charArray,n,charArray.length-1);return new String(charArray);}public void Reverse(char[] s, int start,int end){while (start<end){char temp = s[start];s[start] = s[end];s[end] = temp;start++;end--;}}
}KMP留到以后補吧，今天就暫且不看了。
)
)
