算法學習小技巧

初學者學習排序之類的演算法碰到的困難是直接寫程式很少人寫的出來，大多數人恐怕還是先用紙筆推導，但是你會發現這種方法也是卡卡的，比較好一點的作法是拿方格紙來練習。

當然有些天生記憶力特強的人，可以在腦中記憶運算的過程與結果，接著程式一揮而就，那記憶力比較差的就只能趕緊去夜市找個好位子賣滷味嗎？

這邊分享一個筆者的小技巧，首先請先去文具行買幾盒空白名片，一盒約20元台幣，顏色不要買一樣的，除了操作起來比較不容易弄錯，彩色的名片也會讓你感覺人生是至少有些地方是彩色的。

然後把名片分成兩堆，一堆標上 0 - 25，另一堆標上 A-Z。準備好後就可以開始練習了。

LeetCode#26 Remove Duplicates from Sorted Array

這題是筆者第一個解開的 LeetCode 題目，不過當時解的並不順，過了幾個月差不多也忘光了，剛好來試試看這個方法好不好用。

題目指出陣列中會出現重複的元素，這時候請把 A-Z 裡面寫幾張重複的，把 0-25 的卡片當作陣列索引，A-Z 當作陣列資料，排一個 sample：

然後請伸出你的的雙手，試著照題目的要求移動這些卡片，看看能不能找出模式。

筆者這樣玩了 2-3 次後，很快就抓到手感，接著直接 coding，submit 第一次就成功！

int removeDuplicates(vector<int>& nums) {
    if(nums.size() == 0)
        return nums.size();
    
    int i, j;
    for(i = 0, j = 1; j < nums.size();){
        if(nums[i] != nums[j]){
            if((j - i) > 1){
                nums[++i] = nums[j++];
            }else{
                ++i;
                ++j;
            }
        }else{
            ++j;
        }
    }        
    
    return nums.size() - (j - i - 1);
}

如果您用卡片仍然卡卡的，千萬別動手寫程式，不過可以偷看一下題目的提示，這題的提示是 Two Pointers。

不過雖然過關了，但名次仍然不夠理想，問題在哪？

前面提過編程之魂這本書，裡面每位大師共同的建議就是多讀好程式，所以這時候可以去偷看一下別人的解答(github 上有)。

比對之下，發現自己與高手的主要差異在於高手的程式只要相鄰的元素(a[i] 與 a[i+1])不相等就進行搬移，而筆者的程式卻是判定重複的部份 > 1(Line#8)時才進行搬移，高手的程式精妙之處在於融合了兩種情形：

• 重複
• 沒有重複

再把卡片拿出來玩一次，這次就發現其實相鄰的元素不相等進行搬移也沒差，因為就只是自己 assign 給自己。

int removeDuplicates(vector<int>& nums) {
    if(nums.size() == 0)
        return nums.size();
    
    int i, j;
    for(i = 0, j = 1; j < nums.size();){
        if(nums[i] != nums[j])
            nums[++i] = nums[j++];
        else
            ++j;
    }        
    
    return nums.size() - (j - i - 1);
}

但結果仍沒改善：

再仔細檢查程式，發現無論如何都會對 j 遞增(Line#8,#10)，索性乾脆把 j 移到 for() 裡：

int removeDuplicates(vector<int>& nums) {
    if(nums.size() == 0)
        return nums.size();
    
    int i, j;
    for(i = 0, j = 1; j < nums.size(); ++j){
        if(nums[i] != nums[j])
            nums[++i] = nums[j];            
    }        
    
    return nums.size() - (j - i - 1);
}

這次測試結果大躍進：

心得

如果覺得這個方法不錯，請廣為宣傳，如果能提到本 blog 筆者會非常感謝。還有另外一種作法是用 Excel 進分析，簡單來說就是用 Excel 的表格紀錄變數變化的過程，不過最好要有兩個螢幕，這樣分析起來比較不容易分心(注意力是有限的資源)，不過成本可是高多了。希望這個低成本的作法能幫助大家學習。