本文是[TDD磕算法] 我為什么嘗試用TDD解算法題系列的一篇。
題目
原諒我標(biāo)題黨了扳肛，其實(shí)是這次解的題目很難一言兩語概括出來傻挂。這里我嘗試解釋解釋。
假定一隊(duì)人排成一列
每個(gè)人向前看挖息，如果看到前面有1個(gè)比自己高金拒、或者和自己同樣高的人。就舉個(gè)牌子報(bào)數(shù)1。同理如果有3個(gè)绪抛，就報(bào)3资铡。
如果把每個(gè)人的身高和報(bào)數(shù)列出來，就形成一個(gè)二元組的隊(duì)列幢码，比如：
[(172, 0), (160, 1), (182, 0), (170, 2)]
就表示第一個(gè)人172cm笤休，前面沒有高于或等于他高度的人；第二個(gè)160cm症副，前面有一個(gè)店雅；……
這道題目是，給定打亂順序的一個(gè)序列贞铣，把他們排回應(yīng)有的順序闹啦。
比如：
輸入：[ (7,2), (4,3), (8,0), (7,1), (6,0)]
輸出：[ (6,0), (8,0), (7,1), (4,3), (7,2)]
這道題可以在刷題網(wǎng)站Leetcode上看到，編號406
https://leetcode.com/problems/queue-reconstruction-by-height
初步分析
初看起來題目非常適合TDD解決辕坝。排序的邏輯似乎有點(diǎn)復(fù)雜窍奋，但是應(yīng)該比較容易一步步從簡單到復(fù)雜演進(jìn)。比如先從最簡單的情況開始酱畅，隊(duì)列里只有一個(gè)人琳袄，可以直接返回。兩個(gè)人的話有兩種情況……
另外這道題目不禁讓我想起了Combined Number這道Kata纺酸。同樣也是實(shí)現(xiàn)排序窖逗，排序的邏輯有些繞。最終可以很漂亮的把問題的幾個(gè)方面分離開解決掉吁峻。
關(guān)于Combined Number滑负，可以在這里看到更詳細(xì)的練習(xí)和討論。
http://cyber-dojo.org/kata/edit/FCDDF1?avatar=zebra
https://groups.google.com/forum/#!topic/agileshanghai/d6cy6tCXHA8
失敗嘗試
大致想想之后就開始信心滿滿的TDD起來了用含，果不其然失敗了……
全過程見 http://cyber-dojo.org/review/show/8922CE128B?avatar=ray&was_tag=1&now_tag=1
大體歷程如下
第一個(gè)測試
只有一個(gè)人的話矮慕，必然前面沒有更高的人。
reconstruct_should_be([[3,0]], [[3,0]]);
reconstruct_should_be的第一個(gè)參數(shù)是輸入啄骇，第二個(gè)是預(yù)期的輸出痴鳄。
實(shí)現(xiàn)代碼，輸入什么就返回什么缸夹。
function reconstrutQueue(people) {
return people;
}
第二個(gè)測試
兩個(gè)人痪寻，有一個(gè)前面有更高的人，另一個(gè)沒有虽惭。
reconstruct_should_be([[2,1],[3,0]], [[3,0],[2,1]]);
實(shí)現(xiàn)代碼橡类，按前面人數(shù)排序。
function reconstructQueue(people) {
return people.sort( (p1, p2) => p1[1] -p2[1]);
}
稍作重構(gòu)芽唇，抽取常量
return people.sort( (p1, p2) => p1[PRE] -p2[PRE]);
第三個(gè)測試
兩個(gè)人顾画，前面都沒有更高的人取劫。也就是說是低的在前。
reconstruct_should_be([[2,0],[3,0]], [[2,0],[3,0]]);
直接通過了研侣。
第四個(gè)測試
三個(gè)人谱邪，從低到高排。
reconstruct_should_be([[2,0],[3,0],[1,0]], [[1,0],[2,0],[3,0]]);
實(shí)現(xiàn)代碼庶诡，如果前面人數(shù)一樣惦银，按高度排序。
return people.sort( (p1, p2) => {
if (p1[PRE] === p2[PRE]) return p1[0] - p2[0]
return p1[PRE] -p2[PRE]
});
第五個(gè)測試
三個(gè)人末誓，中等高度的排在最高的后面扯俱。
reconstruct_should_be([[2,1],[3,0],[1,0]], [[1,0],[3,0],[2,1]]);
又一次直接通過了。
第六個(gè)測試
三個(gè)人基显，最矮的排在中間蘸吓。
reconstruct_should_be([[2,0],[3,0],[1,1]], [[2,0],[1,1],[3,0]]);
實(shí)現(xiàn)代碼善炫，排序方式改為先按高度排列撩幽，相同高度的按前面人數(shù)排列。這樣三個(gè)人就會(huì)排成[1,1],[2,0],[3,0]箩艺。
let result = people.sort( (p1, p2) => {
if (p1[VAL] === p2[VAL]) {
return p1[PRE] - p2[PRE];
}
return p1[VAL] - p2[VAL];
});
在排序之后增加一個(gè)調(diào)整順序的過程窜醉。硬編碼快速通過，把前面有1個(gè)人的項(xiàng)目向后挪一位艺谆。也就是[1,1]挪到[2,0]后面榨惰。
for (let i=0; i<result.length; i++) {
if (result[i][PRE] === 1) {
let temp = result[i];
result[i] = result[i+1];
result[i+1] = temp;
i++;
}
}
第七個(gè)測試
三個(gè)人，最矮的排在最后静汤。
reconstruct_should_be([[2,0],[3,0],[1,2]], [[2,0],[3,0],[1,2]]);
實(shí)現(xiàn)代碼琅催，增加第二個(gè)硬編碼分支，處理有2個(gè)人在前面的情況虫给。
for (let i=0; i<result.length; i++) {
if (result[i][PRE] === 1) {
...
}
if (result[i][PRE] === 2) {
let temp = result.splice(i,1)[0];
result.splice(i+2,0,temp);
i+=2;
}
}
重構(gòu)藤抡，把兩個(gè)分支改寫成相同的邏輯。
if (result[i][PRE] === 1) {
let temp = result.splice(i,1)[0];
result.splice(i+1,0,temp);
i+=1;
}
if (result[i][PRE] === 2) {
let temp = result.splice(i,1)[0];
result.splice(i+2,0,temp);
i+=2;
}
重構(gòu)抹估，統(tǒng)一為一個(gè)分支缠黍。
if (sortedByVal[i][PRE] > 0) {
let nLater = sortedByVal[i][PRE];
let temp = sortedByVal.splice(i,1)[0];
sortedByVal.splice(i+nLater,0,temp);
i+=nLater;
}
第八個(gè)測試
最高的人在前面，后面的兩個(gè)按高度排药蜻。
reconstruct_should_be([[2,1],[3,0],[1,1]], [[3,0],[1,1],[2,1]]);
實(shí)現(xiàn)代碼瓷式，呃…… 就這么掉坑里了。
首先是沒有很容易的快速通過的思路语泽。
反復(fù)幾次后發(fā)現(xiàn)在排好的數(shù)組里挪動(dòng)的方式贸典，把一個(gè)人向后挪了之后，換來的人可能也需要后移踱卵。
所以決定不在原來的數(shù)組里挪動(dòng)位置廊驼，而是全部插入一個(gè)新數(shù)組。插入時(shí)比較新數(shù)組里的位置和這個(gè)人前面人的個(gè)數(shù)，直到所有的人都插入新數(shù)組為止蔬充。
function reorder(sortedByVal) {
let result = [];
let length = sortedByVal.length;
for (let i=0; i<length; i++) {
for (let j=0; j<sortedByVal.length; j++) {
if (sortedByVal[j][PRE] <= i) {
result.push(sortedByVal[j]);
sortedByVal.splice(j,1);
break;
}
}
}
return result;
}
但是發(fā)現(xiàn)這時(shí)候[ [ 1, 0 ], [ 3, 0 ], [ 2, 1 ] ]這個(gè)測試又失敗了蝶俱。
經(jīng)過一段思索無法繼續(xù)后，我覺得就算通過苦思冥想把這個(gè)題解出來饥漫，也已經(jīng)和TDD無關(guān)了榨呆。就此停止了這次練習(xí)。
感想
從來沒有嘗試過仔細(xì)描述一段失敗的過程庸队。不知道你讀到這里是和感受积蜻？
- “簡直是浪費(fèi)時(shí)間嘛”？
- “早就知道這樣做不靠譜”彻消？
- “看起來還有救啊竿拆，怎么就失敗了”？
- “太菜了宾尚，讓我來”丙笋？
這里說說掉坑的心得。怎么知道自己掉坑了煌贴。
- 最終爬不出來的點(diǎn)很容易判定御板。突然發(fā)現(xiàn)自己思考了10分鐘，還是沒有寫代碼牛郑。
- 顧此失彼怠肋，寫了一段代碼快速通過當(dāng)前測試，結(jié)果前面的測試掛了淹朋。
- 感覺前面重構(gòu)出的結(jié)構(gòu)在阻礙新的用例快速通過笙各。
- 一個(gè)早期征兆是想不清楚下一個(gè)測試是什么？比如這個(gè)過程中兩次直接通過的測試础芍，都代表了對當(dāng)前程序的行為沒有理解清楚杈抢。
- 測試想不清楚的背后是沒有想出逐步分解問題的思路，進(jìn)而加入測試的順序可能不是適宜代碼演進(jìn)者甲。導(dǎo)致重構(gòu)時(shí)對實(shí)現(xiàn)進(jìn)行重大調(diào)整春感。比如第六步和最后一步。
下一篇文章會(huì)總結(jié)我在反思之后重新解決的過程虏缸，敬請期待鲫懒。
