當然有些天生記憶力特強的人,可以在腦中記憶運算的過程與結果,接著程式一揮而就,那記憶力比較差的就只能趕緊去夜市找個好位子賣滷味嗎?
這邊分享一個筆者的小技巧,首先請先去文具行買幾盒空白名片,一盒約20元台幣,顏色不要買一樣的,除了操作起來比較不容易弄錯,彩色的名片也會讓你感覺人生是至少有些地方是彩色的。
然後把名片分成兩堆,一堆標上 0 - 25,另一堆標上 A-Z。準備好後就可以開始練習了。
LeetCode#26 Remove Duplicates from Sorted Array
這題是筆者第一個解開的 LeetCode 題目,不過當時解的並不順,過了幾個月差不多也忘光了,剛好來試試看這個方法好不好用。
然後請伸出你的的雙手,試著照題目的要求移動這些卡片,看看能不能找出模式。
筆者這樣玩了 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 的表格紀錄變數變化的過程,不過最好要有兩個螢幕,這樣分析起來比較不容易分心(注意力是有限的資源),不過成本可是高多了。希望這個低成本的作法能幫助大家學習。
沒有留言:
張貼留言