代碼随想錄算法訓練營第七 & 八天 | 哈希表 字元串

文章目錄

• 哈希表
• • 題目
  • 對題目的想法
  • 實作中/後的感想
  • 看完代碼随想錄之後的想法
• 字元串
• • 題目
  • 對題目的想法
  • 實作中/後的感想
  • 看完代碼随想錄之後的想法

哈希表

題目

第454題.四數相加II

383. 贖金信

第15題. 三數之和

第18題. 四數之和

對題目的想法

前兩題很簡單，不過三數之和的雙指針方法有一點沒底。

實作中/後的感想

三數之和的雙指針果然沒有那麼容易，自己寫然後就失敗了。

看完代碼随想錄之後的想法

看了随想錄的解法思路時候去嘗試，還是出錯。原因出在錯誤的剪枝，以及特殊情況的資料溢出（達到了int的上限）。

字元串

題目

344.反轉字元串

541. 反轉字元串II

劍指Offer 05.替換空格

151.翻轉字元串裡的單詞

劍指Offer58-II.左旋轉字元串

對題目的想法

反轉字元串很容易實作，雙指針的又一次練習。左旋轉字元串之前看過随想錄，解法還記得，是以感覺也很輕松，翻轉字元串裡的單詞也記得思路。

實作中/後的感想

最麻煩的果然是翻轉字元串裡的單詞。

一開始試圖用StringBuilder實作，覺得會節省空間，但是寫得不倫不類，是Char []和StringBuilder的混合體。（以為StringBuilder是用List實作，是以想着周遊會很耗時，剛查了才發現底層結構其實也是數組，有點想當然了）最後從StringBuilder到char[]的輸出很奇怪，有可能是長度沒處理好。

後來索性純粹用char[]和雙指針來實作，雖然bug衆多，但還是寫出來了。

class Solution {
    public String reverseWords(String s) {
        int l = 0, r = 0;
        char res[] = s.toCharArray();
        reverse(res, 0, res.length - 1);
        while (r < res.length) {
            if (res[r] == ' ') {
                while (r < res.length && res[r] == ' ') r++;
                res[l++] = ' ';
            }
            else {
                res[l++] = res[r++];
            }
        }
        
        r = l - 1;
        l = 0;
        while (res[r] == ' ' && r > 0) r--;
        if (res[l] == ' ') l++;
        
        int lt = l, rt = l;
        for (; rt <= r; rt++) {
            if (res[rt] == ' ') {
                reverse(res, lt, rt - 1);
                lt = rt + 1;
            }
        }
        
        reverse(res, lt, r);
        
        return new String(res, l, r - l + 1);
    }
    
    public void reverse(char c[], int i, int e) {
        while (i < e) {
            char t = c[i];
            c[i] = c[e];
            c[e] = t;
            i++;
            e--;
        }
    }
}
           

還是有一點成就感的。

缺點在于對代碼的掌控力上，因為幾個出錯的點多在于超出數組長度，也即對變量的定義不夠明确。如果加了注釋應該會好一些，以後要強迫自己寫詳細的注釋，有助于排查錯誤以及保持代碼邏輯的穩定。

看完代碼随想錄之後的想法

随想錄的幾個java實作感覺太長，有點懶得看。