快捷導(dǎo)航

.net 反序題目的詳細(xì)解答第1/2頁(yè)

更新時(shí)間：2009年06月13日 20:34:47 作者：

在各種答案，以及平時(shí)面試過(guò)程中，這道題總歸會(huì)有一些非常典型的錯(cuò)誤發(fā)生。其中給老趙的感覺(jué)也非常有意思，不知其中的“思路”是否如老趙猜測(cè)那樣。

請(qǐng)將方法補(bǔ)充完整：

static void Reverse(int[] array, int begin, int end) 
{ 
... 
} 

Reverse方法的作用是將array數(shù)組中，從begin下標(biāo)到end下標(biāo)之間的元素反序一下，如一個(gè)數(shù)組初始值是[1, 2, 3, 4, 5, 6]，begin為1，end為4，那么當(dāng)調(diào)用了Reverse之后，array數(shù)組中的元素便依次成為[1, 5, 4, 3, 2, 6]，其中從array[1]到array[4]之前的元素被反序了。此外補(bǔ)充一點(diǎn)……其實(shí)本不用補(bǔ)充：這個(gè)方法需要對(duì)傳入?yún)?shù)的正確性進(jìn)行校驗(yàn)，如果用戶(hù)調(diào)用該方法時(shí)傳入了非法的參數(shù)，那么則需要拋出異常，并寫(xiě)清原因。您可以使用您喜歡的語(yǔ)言來(lái)實(shí)現(xiàn)：C#，VB，Java，Ruby，Python……但是請(qǐng)不要使用內(nèi)置庫(kù)中已經(jīng)有的功能。:)

　　很簡(jiǎn)單，不是嗎？只可惜截止到目前，也只有1人給出了正確答案。如果您沒(méi)有做過(guò)這道題目，那么在查看下面的分析之前，不妨拿張紙拿支筆，寫(xiě)下您的答案，然后再聽(tīng)老趙慢慢講來(lái)…

主體邏輯
　　這道題目的主題邏輯其實(shí)非常簡(jiǎn)單。不就是把數(shù)組中的一部分反序嗎？不過(guò)從這一點(diǎn)上面來(lái)說(shuō)，代碼的清晰程度也有較大差距。好的做法和普通的做法，從編程難度和理解上都有一定差距。例如：

1、許多朋友的做法是：既然是反轉(zhuǎn)數(shù)組的一部分元素，那么只要找到中間的位置，然后計(jì)算出和begin的偏移量，然后……怎么怎么一搞，就完成了——嗯，似乎還需要根據(jù)進(jìn)行begin和end中間的元素個(gè)數(shù)是奇數(shù)還是偶數(shù)分別處理。

2、另一些朋友的做法是：開(kāi)一個(gè)新數(shù)組（長(zhǎng)度為end - begin + 1），將begin到end之間的元素放到新數(shù)組中去，然后反序，然后再?gòu)?fù)制回來(lái)。

3、還有一個(gè)朋友認(rèn)為用棧：把begin到end之間的元素給push到棧中，再一個(gè)一個(gè)pop出來(lái)依次賦值給begin到end，這樣就反序了……唔！數(shù)據(jù)結(jié)構(gòu)學(xué)的不錯(cuò)！

　　只可惜，這樣的做法都復(fù)雜了一些。3種做法的時(shí)間復(fù)雜度均為O(end – begin)，但是只有第一種做法的空間復(fù)雜度是O(1)，而后兩者也都是線性的空間復(fù)雜度。那么老趙眼里最好的做法是什么呢？

復(fù)制代碼代碼如下:

public static void Reverse(int[] array, int begin, int end) 
{ 
while (end > begin) 
{ 
int temp = array[begin]; 
array[begin] = array[end]; 
array[end] = temp; 

begin++; 
end--; 
} 
}

end和begin兩個(gè)下標(biāo)從初始值開(kāi)始依次向中間逼近，每次都交換一下數(shù)組中的元素。最終，while在判斷的時(shí)候會(huì)發(fā)現(xiàn)end == begin（begin和end之間總共奇數(shù)個(gè)元素），或end < begin（begin和end之間總共偶數(shù)個(gè)元素）。無(wú)論哪種情況，都表示反序已經(jīng)完成。
參數(shù)校驗(yàn)
上面的做法應(yīng)該說(shuō)是最簡(jiǎn)單的一種，不過(guò)實(shí)際在評(píng)判答案的時(shí)候，直接結(jié)果正確，老趙都認(rèn)為是正確的。只可惜，幾乎沒(méi)有朋友在“參數(shù)校驗(yàn)”這方面作對(duì)。

　　順便提一下的是，有位朋友給我留言很有意思：“老師只給了一個(gè)測(cè)試數(shù)據(jù)，如果要用其它測(cè)試數(shù)據(jù)的話(huà)比如比較特殊的，那請(qǐng)老師下次把測(cè)試數(shù)據(jù)列好?！边@句話(huà)讓我木然：測(cè)試數(shù)據(jù)是無(wú)窮無(wú)盡的，難道需要都列出來(lái)？平時(shí)寫(xiě)程序，用戶(hù)會(huì)指出他的所有操作步驟嗎？給測(cè)試數(shù)據(jù)的目的是為了幫助理解題意，題目的要求都寫(xiě)清楚了，做題才有意義。如果一道題目只要求把給出的測(cè)試數(shù)據(jù)運(yùn)行，那么又有誰(shuí)不會(huì)做呢？老趙這里就可以立即給出一個(gè)萬(wàn)能模板：

復(fù)制代碼代碼如下:

if (...) 
{ 
return ... 
} 
else if (...) 
{ 
return ... 
} 

... 

按理來(lái)說(shuō)，即使題目中沒(méi)有寫(xiě)明需要參數(shù)校驗(yàn)，一個(gè)優(yōu)秀的實(shí)現(xiàn)也應(yīng)該自帶這一點(diǎn)。

其實(shí)只要仔細(xì)一些，把參數(shù)所有的錯(cuò)誤情況列舉出來(lái)并不是難事：

復(fù)制代碼代碼如下:

1、array == null 
2、begin < 0; 
3、end < begin 
4、end >= array.Length 

那么，其他一些情況是否應(yīng)該一并判斷呢？例如end < 0，array.Length == 0或者begin >= length。老趙認(rèn)為“不判斷也沒(méi)有關(guān)系”，因?yàn)橐陨系呐袛嘁呀?jīng)確保不會(huì)出現(xiàn)額外的錯(cuò)誤情況了。那么begin == end是否算是問(wèn)題呢？老趙認(rèn)為，這個(gè)判斷也可以省略。不過(guò)……如果begin > end，那么是否應(yīng)該把兩者的數(shù)值進(jìn)行交換？我不知道為什么有些朋友這么做了，不過(guò)老趙認(rèn)為，一般來(lái)說(shuō)一個(gè)方法不應(yīng)該為參數(shù)進(jìn)行額外“調(diào)整”——其實(shí)各大類(lèi)庫(kù)都不會(huì)如此畫(huà)蛇添足。如果哪位朋友有不同看法，我們可以繼續(xù)討論。

12 下一頁(yè)閱讀全文