代碼随想錄刷題記錄day08-倒在了去除多餘的空格（雙指針）

代碼随想錄刷題記錄day08

leetcode :344. 反轉字元串

思想：

雙指針

代碼

class Solution {
    public void reverseString(char[] s) {
        //雙指針
        int left=0;
        int right=s.length-1;

        while(left<right){
            char temp=s[left];
            s[left]=s[right];
            s[right]=temp;
            left++;
            right--;
        }
    }
}
           

leetcode:541. 反轉字元串 II

給定一個字元串 s 和一個整數 k，從字元串開頭算起，每計數至 2k 個字元，就反轉這 2k 字元中的前 k 個字元。

如果剩餘字元少于 k 個，則将剩餘字元全部反轉。

如果剩餘字元小于 2k 但大于或等于 k 個，則反轉前 k 個字元，其餘字元保持原樣。

示例 1：

輸入：s = “abcdefg”, k = 2

輸出：“bacdfeg”

示例 2：

輸入：s = “abcd”, k = 2

輸出：“bacd”

提示：

1 <= s.length <= 104

s 僅由小寫英文組成

1 <= k <= 104

思想：

一個for循環控制 每次前進2k個，判斷剩餘的長度是否大于等于k個

再反轉指定的k個

代碼

class Solution {
    public String reverseStr(String s, int k) {
        //2k個得前k個字元
        //String 在java得設計中是定量，不能原地交換值 是以需要轉換成數組
        char[] ch=s.toCharArray();

        for(int i=0;i<s.length();i+=2*k){
            //前進2k個 反轉2k個得前k個
            //判斷 如果剩餘得字元大于或者等于k個
            if(s.length()-i>=k){
                helpReverse(ch,i,i+k-1);
            }
            else{
                helpReverse(ch,i,s.length()-1);
            }
            // System.out.println(Arrays.toString(ch));
            
        }
        return new String(ch);
    }

    public void helpReverse(char[] ch,int start,int end){
        int left=start;
        int right=end;

        while(left<right){
            char temp=ch[left];
            ch[left]=ch[right];
            ch[right]=temp;
            left++;
            right--;
        }
    }
}
           

leetcode：劍指 Offer 05. 替換空格

請實作一個函數，把字元串 s 中的每個空格替換成"%20"。

示例 1：

輸入：s = “We are happy.”

輸出：“We%20are%20happy.”

思想：

java中調用stringBuilde長度來實作變化的字元串

用雙指針法需要重新建構長度，感覺有點強行用，但是思路要學習下。

left指向源數組的最後一個位置，right指向信數組的最後一個位置，根據原數組==‘ ’ 去實作right的移動

代碼

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb=new StringBuilder();

        for(int i=0;i<s.length();i++){
            if(s.charAt(i)!=' '){
                sb.append(s.charAt(i));
            }else{
                sb.append("%20");
            }
        }

        return new String(sb);
    }
}
           

leetcode:151. 反轉字元串中的單詞

給你一個字元串 s ，請你反轉字元串中 單詞 的順序。

單詞 是由非空格字元組成的字元串。s 中使用至少一個空格将字元串中的 單詞 分隔開。

傳回 單詞 順序颠倒且 單詞 之間用單個空格連接配接的結果字元串。

注意：輸入字元串 s中可能會存在前導空格、尾随空格或者單詞間的多個空格。傳回的結果字元串中，單詞間應當僅用單個空格分隔，且不包含任何額外的空格。

示例 1：

輸入：s = “the sky is blue”

輸出：“blue is sky the”

示例 2：

輸入：s = " hello world "

輸出：“world hello”

解釋：反轉後的字元串中不能存在前導空格和尾随空格。

示例 3：

輸入：s = “a good example”

輸出：“example good a”

解釋：如果兩個單詞間有多餘的空格，反轉後的字元串需要将單詞間的空格減少到僅有一個。

思想

1.先把字元串多餘的空格給處理了，前後不能有空格，單詞與單詞之間隻能有一個空格。

2.将這個字元串反轉

3.逐個把單詞反轉

整體思路還是比較好了解的，但是删除多餘的空格這一步比較難以處理。

具體如下：

• 定義兩個快慢指針，快指針去找符合條件的字元，
• 因為字元之間需要有一個空格，是以slow指針不是指向第一個的時候 需要置為‘ ’同時往後移動一格
• 再用一個while來進行指派操作
• 調用Arrays.copyOfRange傳回去掉空格後的字元數組

  

代碼

class Solution {
    public String reverseWords(String s) {
        //先反轉整個字元串 再反正具體得每個單詞
        s=s.trim();
        
        char[] ch=s.toCharArray();
        char[] newCh=removeExtraSpaces(ch);
        System.out.println(Arrays.toString(newCh));

        reverseCharArray(newCh,0,newCh.length-1);

        System.out.println(Arrays.toString(newCh));

        int record=0;
        for(int i=0;i<newCh.length;i++){
            if(newCh[i]==' '){
                //找到一個空格 反轉這個單詞
                reverseCharArray(newCh,record,i-1);
                // System.out.println(Arrays.toString(ch));
                record=i+1;
            }
            if(i==newCh.length-1){
                reverseCharArray(newCh,record,newCh.length-1);
            }
        }

        return new String(newCh);
    }

    public char[] removeExtraSpaces(char[] ch){
        //移除多餘的空格 
        //快慢指針
        int slow=0;
        int fast=0;

        for(;fast<ch.length;fast++){
            //fast 指向找到的元素
            if(ch[fast]!=' '){
                if(slow!=0) ch[slow++]=' ';
                 while (fast < ch.length && ch[fast] != ' ') { //補上該單詞，遇到空格說明單詞結束。
                    ch[slow++] = ch[fast++];
                }
            }
        }

        return Arrays.copyOfRange(ch,0,slow);



    }

    public void reverseCharArray(char [] ch,int start,int end){
        int left=start;
        int right=end;

        while(left<right){
            char temp=ch[left];
            ch[left]=ch[right];
            ch[right]=temp;
            left++;
            right--;
        }
    }
}
           

leetcode:劍指 Offer 58 - II. 左旋轉字元串

字元串的左旋轉操作是把字元串前面的若幹個字元轉移到字元串的尾部。請定義一個函數實作字元串左旋轉操作的功能。比如，輸入字元串"abcdefg"和數字2，該函數将傳回左旋轉兩位得到的結果"cdefgab"。

示例 1：

輸入: s = “abcdefg”, k = 2

輸出: “cdefgab”

示例 2：

輸入: s = “lrloseumgh”, k = 6

輸出: “umghlrlose”

思想：

類似于上面一題的思想，//先反轉前0到n-1個 再反轉n到 s.length()-1個

class Solution {
    public String reverseLeftWords(String s, int n) {

        char [] ch=s.toCharArray();

        //先反轉前0到n-1個 再反轉n到 s.length()-1個
        help(ch,0,n-1);
        help(ch,n,s.length()-1);
        help(ch,0,s.length()-1);
        return new String(ch);


    }

    public void help(char[] ch,int start,int end){

        while(start<end){
            char temp=ch[start];
            ch[start]=ch[end];
            ch[end]=temp;
            start++;
            end--;
        }
    }
}