先說(shuō)一個(gè)我在PTA上常見的現(xiàn)象10分的題看起來(lái)簡(jiǎn)單但實(shí)驗(yàn)7-1-7 查找整數(shù) 這道題每年都能讓一批剛學(xué)C語(yǔ)言的同學(xué)卡上好幾個(gè)小時(shí)。我見過太多類似的情況本地編譯運(yùn)行一切正常一提交就是答案錯(cuò)誤問了一圈發(fā)現(xiàn)是位置編號(hào)從0開始輸出而不是從1開始。這道題雖然分值不大但它是順序查找、數(shù)組遍歷、條件輸出這幾個(gè)基本功的集合作業(yè)也是后續(xù)二分查找查找第k個(gè)滿足條件的數(shù)等進(jìn)階題目的地基。這篇文章我會(huì)把題目背后的考點(diǎn)、讀題時(shí)容易忽略的信息、三種不同風(fēng)格的寫法、PTA判題時(shí)常見的坑以及怎么把這道10分題的價(jià)值榨干一次性講透。不管是剛開始學(xué)數(shù)組的大一新生還是已經(jīng)刷到函數(shù)題、想回來(lái)補(bǔ)基礎(chǔ)的同學(xué)都可以對(duì)照著看。1. 題目到底在考什么10分背后的三個(gè)基本功很多同學(xué)拿到這道題的第一反應(yīng)是就這然后十分鐘寫完提交。但據(jù)我觀察一遍過的人其實(shí)沒有想象中那么多。這道題表面是找一個(gè)數(shù)實(shí)際上是在考察三個(gè)基礎(chǔ)能力數(shù)組的聲明與遍歷、用循環(huán)配合條件判斷實(shí)現(xiàn)查找邏輯、以及嚴(yán)格遵循題目要求的輸入輸出格式。任何一個(gè)環(huán)節(jié)出了問題PTA都會(huì)毫不留情地給你一個(gè)紅叉。1.1 數(shù)組把一堆數(shù)裝進(jìn)同一個(gè)變量名里題目要求從輸入的N個(gè)整數(shù)中查找給定的X這意味著你面對(duì)的是一組同類型的數(shù)據(jù)而不是一個(gè)單獨(dú)的數(shù)。在C語(yǔ)言里處理一組同類型數(shù)據(jù)的最自然方案就是數(shù)組。int a[20];這一行聲明了20個(gè)int類型的變量它們通過下標(biāo)訪問a[0]、a[1]一直到a[19]。數(shù)組最大的好處是能用循環(huán)遍歷比如把n個(gè)數(shù)讀進(jìn)來(lái)for (i 0; i n; i) { scanf(%d, a[i]); }這里有一個(gè)初學(xué)者很容易繞不過來(lái)的點(diǎn)為什么不用20個(gè)獨(dú)立的變量比如int a1, a2, a3, ...這樣寫原因很簡(jiǎn)單變量的個(gè)數(shù)是題目運(yùn)行時(shí)才能確定的第一行的n你不能預(yù)先寫好n個(gè)scanf。而且就算你寫死20個(gè)變量要逐個(gè)比較也是一件極其痛苦的事。數(shù)組的意義就在于用下標(biāo)把第幾個(gè)和值是多少綁定讓循環(huán)可以統(tǒng)一處理。1.2 順序查找最樸素也最通用的查找方式查找一個(gè)數(shù)在數(shù)組里的位置最直接的做法就是從第一個(gè)元素開始一個(gè)一個(gè)比直到找到目標(biāo)或者把所有元素都比完。這個(gè)思路就是順序查找也叫線性查找時(shí)間復(fù)雜度是O(n)。順序查找雖然聽起來(lái)笨但它是理解后續(xù)所有查找算法的基礎(chǔ)。二分查找要求數(shù)據(jù)有序哈希查找要求設(shè)計(jì)哈希函數(shù)而順序查找什么都不要求——哪怕數(shù)據(jù)是無(wú)序的、有重復(fù)的它都能工作。這道題用順序查找不是因?yàn)樗?jiǎn)單而是因?yàn)樗窃跀?shù)組中做操作最典型的開端。1.3 輸入輸出的隱形扣分點(diǎn)PTA判題是嚴(yán)格比對(duì)輸出字符的多一個(gè)空格、少一個(gè)換行、大小寫不一致都算錯(cuò)誤。這道題輸出要么是位置編號(hào)換行要么是Not Found換行。這里我特別強(qiáng)調(diào)一下Not Found的格式N是大寫F是大寫其余是小寫中間一個(gè)空格后面沒有句號(hào)。我見過不少同學(xué)寫成Not foundNOT FOUNDNot Found.的這些全部會(huì)判錯(cuò)。有時(shí)候你代碼邏輯完全沒問題就是格式細(xì)節(jié)不對(duì)這種錯(cuò)誤最冤。所以拿到任何PTA題目第一步不是寫代碼而是把輸出說(shuō)明看三遍。2. 拿到題目先別急著寫代碼把題干拆成這幾條寫程序之前先把題目里的每個(gè)條件都翻譯成代碼層面的約束。我習(xí)慣用筆在草稿紙上把輸入格式、輸出格式、特殊要求列成三條然后再動(dòng)手。這道題的題干雖然短但信息密度不小。2.1 輸入格式里藏著哪些信息題目輸入分兩行第一行給出兩個(gè)正整數(shù)N和X第二行給出N個(gè)整數(shù)。N是要輸入的整數(shù)個(gè)數(shù)這道題通常限制為N≤20。這個(gè)限制意味著你可以放心地用固定大小數(shù)組int a[20]而不用擔(dān)心越界。X是要查找的目標(biāo)。第二行的N個(gè)整數(shù)用空格分隔你需要用循環(huán)把它們逐一讀入。有一個(gè)細(xì)節(jié)值得注意題目說(shuō)N是正整數(shù)但如果你提交的測(cè)試點(diǎn)里出現(xiàn)了讀入失敗的情況多半是輸入格式?jīng)]對(duì)上。另外C語(yǔ)言里scanf(%d %d, n, x)會(huì)自動(dòng)跳過空白字符空格、換行、制表符所以第一行的換行并不影響第二行的讀入。2.2 第一次出現(xiàn)的位置為什么是題眼這是整道題最容易被忽略的地方。題干說(shuō)的是如果找到輸出X在數(shù)列中第一次出現(xiàn)的位置關(guān)鍵詞有兩個(gè)第一次和位置。第一次意味著輸入數(shù)據(jù)里可能有重復(fù)數(shù)字。比如輸入2 4 2 8查找2正確輸出是1而不是3。如果你在循環(huán)里把所有匹配的位置都記錄下來(lái)最后不小心輸出了最后一次匹配的位置就會(huì)答案錯(cuò)誤。位置意味著編號(hào)從1開始。這個(gè)和數(shù)組下標(biāo)從0開始的規(guī)則不一致。你找到的是下標(biāo)i但輸出時(shí)要輸出i1。我見過太多同學(xué)調(diào)試的時(shí)候發(fā)現(xiàn)明明找到了輸出卻是0就是因?yàn)樯倭诉@個(gè)映射。建議在寫輸出語(yǔ)句時(shí)直接寫成printf(%d\n, i 1);而不是先算一個(gè)位置變量再輸出減少一步出錯(cuò)的機(jī)會(huì)。2.3 輸出格式大小寫和換行一個(gè)都不能錯(cuò)輸出沒有找到時(shí)要輸出Not Found注意三點(diǎn)一是大小寫二是中間這個(gè)空格三是末尾的換行。用printf輸出時(shí)直接寫Not Found\n不要拼寫、不要加標(biāo)點(diǎn)。另外找到時(shí)輸出的位置之后也要換行。PTA的判題腳本對(duì)換行敏感但通常不會(huì)因?yàn)樽詈笠恍腥鄙贀Q行就判錯(cuò)不過我建議還是規(guī)規(guī)矩矩加\n養(yǎng)成習(xí)慣對(duì)后續(xù)題目有好處。3. 代碼實(shí)現(xiàn)從最樸素的寫法到能加分的寫法這一章我給出三種思路的完整代碼每一種都會(huì)逐行解釋。你可以根據(jù)自己的水平選擇如果是初學(xué)者老老實(shí)實(shí)寫第一種如果已經(jīng)理解數(shù)組和循環(huán)可以試試第二種如果想把基礎(chǔ)打得更扎實(shí)建議把第三種封裝函數(shù)的寫法也掌握。3.1 基礎(chǔ)版開了數(shù)組用flag標(biāo)記結(jié)果#include stdio.h int main() { int n, x; scanf(%d %d, n, x); int a[20]; int i; for (i 0; i n; i) { scanf(%d, a[i]); } int flag 0; for (i 0; i n; i) { if (a[i] x) { printf(%d\n, i 1); flag 1; break; } } if (flag 0) { printf(Not Found\n); } return 0; }這段代碼的思路是先用兩個(gè)循環(huán)完成讀入所有整數(shù)和逐個(gè)查找目標(biāo)兩個(gè)階段再用一個(gè)flag變量記錄是否找到。為什么需要flag因?yàn)榈诙€(gè)for循環(huán)有兩個(gè)出口一是break跳出來(lái)的找到了二是i循環(huán)到n正常結(jié)束的沒找到。循環(huán)結(jié)束后程序無(wú)法區(qū)分自己是從哪個(gè)出口出來(lái)的所以要借助flag。一旦找到先輸出位置把flag置1然后break跳出循環(huán)如果循環(huán)正常結(jié)束說(shuō)明全程沒有匹配flag保持0執(zhí)行Not Found輸出。這里有個(gè)小細(xì)節(jié)找到后立即break是因?yàn)轭}目只要第一次出現(xiàn)的位置。如果你不break后面即使找到了也不會(huì)有更新的輸出但在效率上是浪費(fèi)的。更重要的是不break的話循環(huán)會(huì)繼續(xù)跑如果后面還有匹配項(xiàng)你的flag可能被反復(fù)置1雖然結(jié)果可能還是對(duì)的但代碼邏輯就不干凈了。3.2 優(yōu)化版邊讀邊找連數(shù)組都不用開#include stdio.h int main() { int n, x; scanf(%d %d, n, x); int num; int i; for (i 1; i n; i) { scanf(%d, num); if (num x) { printf(%d\n, i); return 0; } } printf(Not Found\n); return 0; }這個(gè)版本更巧妙因?yàn)轭}目只要求輸出第一次出現(xiàn)的位置所以你沒有必要把讀入的所有數(shù)都存下來(lái)再回頭找。你可以一邊讀一邊比較讀到第幾個(gè)數(shù)的時(shí)候就檢查它是不是目標(biāo)是的話立刻輸出并結(jié)束程序。注意這里的循環(huán)變量i是從1開始的正好對(duì)應(yīng)位置編號(hào)。讀入scanf(%d, num)如果num x直接printf(%d\n, i)然后return 0結(jié)束整個(gè)main函數(shù)后面的Not Found自然就不會(huì)執(zhí)行。如果循環(huán)正常結(jié)束說(shuō)明從頭到尾沒有匹配過這時(shí)再用printf輸出Not Found。這種邊讀邊處理的思路在處理流式數(shù)據(jù)時(shí)非常有用也是后續(xù)學(xué)習(xí)文件讀寫時(shí)的一個(gè)重要思維。不過我要提醒一句如果題目要求輸出X出現(xiàn)的所有位置或者輸出最后一次出現(xiàn)的位置這個(gè)邊讀邊處理的方案就不夠了你得老老實(shí)實(shí)存數(shù)組。所以不要覺得這個(gè)版本最優(yōu)就只背它兩種寫法都需要理解。3.3 函數(shù)封裝為后續(xù)進(jìn)階題目做準(zhǔn)備#include stdio.h int search(int a[], int n, int x) { int i; for (i 0; i n; i) { if (a[i] x) { return i 1; } } return -1; } int main() { int n, x; scanf(%d %d, n, x); int a[20]; int i; for (i 0; i n; i) { scanf(%d, a[i]); } int pos search(a, n, x); if (pos -1) { printf(Not Found\n); } else { printf(%d\n, pos); } return 0; }第三種寫法把查找邏輯單獨(dú)封裝成了函數(shù)search。函數(shù)接收三個(gè)參數(shù)數(shù)組a、長(zhǎng)度n、目標(biāo)x返回值是找到時(shí)的位置從1開始或-1未找到.為什么用-1作為失敗標(biāo)記因?yàn)轭}目里的位置是正整數(shù)-1不可能出現(xiàn)在合法輸出中所以可以安全地充當(dāng)異常/未找到信號(hào)。main函數(shù)里只需要判斷返回值即可。這種封裝的價(jià)值在后續(xù)PTA的函數(shù)題中會(huì)體現(xiàn)得非常明顯。比如二分查找PTA函數(shù)這類題目題目會(huì)直接給你一個(gè)函數(shù)接口讓你實(shí)現(xiàn)你的查找邏輯就寫在那個(gè)實(shí)現(xiàn)里。提前養(yǎng)成把具體算法封裝成函數(shù)的習(xí)慣后面做函數(shù)題會(huì)輕松很多。3.4 復(fù)雜度分析這個(gè)答案為什么是對(duì)的還是有必要把復(fù)雜度說(shuō)清楚PTA雖然不考復(fù)雜度分析但后續(xù)課程和面試會(huì)考。時(shí)間最壞情況下把n個(gè)數(shù)全部比較一遍時(shí)間復(fù)雜度O(n)平均情況是O(n/2)依然記作O(n)?？臻g如果用數(shù)組存儲(chǔ)空間復(fù)雜度O(n)如果用邊讀邊找的版本除了一些變量外不占用額外空間空間復(fù)雜度O(1)。對(duì)于N≤20的數(shù)據(jù)規(guī)模即使是最差的O(n)方案也綽綽有余。這也是PTA上一個(gè)有趣的地方數(shù)據(jù)規(guī)模往往決定了算法選擇的自由度。如果N變成10的7次方順序查找就不一定能過了那時(shí)候才需要二分查找、哈希表這些更高效的手段。4. 常見錯(cuò)誤與排查技巧PTA判題到底在judge什么我在幫同學(xué)看代碼的時(shí)候發(fā)現(xiàn)這道題的報(bào)錯(cuò)場(chǎng)景高度集中。這里我把高頻錯(cuò)誤整理成速查表然后再展開講幾個(gè)典型的翻車現(xiàn)場(chǎng)。4.1 高頻錯(cuò)誤對(duì)照速查表錯(cuò)誤現(xiàn)象可能原因解決方法答案錯(cuò)誤始終輸出0輸出的是數(shù)組下標(biāo)i不是位置i1輸出時(shí)改為i1答案錯(cuò)誤重復(fù)數(shù)字時(shí)輸出位置靠后記錄所有匹配位置最后輸出了最后一個(gè)找到第一個(gè)匹配就break或return答案錯(cuò)誤沒有找到時(shí)輸出亂碼未初始化flag變量未找到時(shí)flag值不確定定義flag時(shí)初始化為0格式錯(cuò)誤Not Found不對(duì)大小寫錯(cuò)誤、單詞拼錯(cuò)、加了標(biāo)點(diǎn)嚴(yán)格按Not Found輸出答案錯(cuò)誤輸出位置全部偏移一位循環(huán)從i1開始但數(shù)組訪問使用a[i]區(qū)分位置編號(hào)和數(shù)組下標(biāo)編譯錯(cuò)誤數(shù)組大小不對(duì)用了int a[n]但編譯環(huán)境不支持變長(zhǎng)數(shù)組用int a[20]或int a[100]段錯(cuò)誤/運(yùn)行時(shí)錯(cuò)誤循環(huán)條件in導(dǎo)致訪問a[n]越界循環(huán)條件改為in4.2 一個(gè)典型的翻車現(xiàn)場(chǎng)輸出下標(biāo)還是位置我印象最深的是一個(gè)學(xué)弟的代碼邏輯完全正確就是輸出那行寫了printf(%d\n, i)。他本地測(cè)試了好幾組數(shù)據(jù)查找1數(shù)組是2 3 1 4他驚人有輸出的編號(hào)少了1。他問我為什么我說(shuō)你把數(shù)組下標(biāo)當(dāng)位置輸出了。改成i1一次過。這種錯(cuò)誤調(diào)試起來(lái)很難發(fā)現(xiàn)因?yàn)榇蟛糠謺r(shí)候找到的數(shù)在數(shù)組中間你光看輸出2可能覺得就是第二個(gè)位置實(shí)際它代表的是下標(biāo)2、位置3語(yǔ)義已經(jīng)完全偏了。我的建議是寫輸出語(yǔ)句之前先在心里問自己一句當(dāng)前變量到底代表下標(biāo)還是位置這道題以及后續(xù)很多數(shù)組題目都會(huì)頻繁出現(xiàn)這種下標(biāo)從0、編號(hào)從1的映射問題。4.3 本地正確、提交報(bào)錯(cuò)可能是這些原因本地運(yùn)行是對(duì)的一提交就紅是PTA新手最崩潰的情景。結(jié)合這道題常見原因有三個(gè)。第一你的本地測(cè)試用例太弱。比如你只測(cè)試了找到且目標(biāo)在第一個(gè)位置的情況恰好輸出數(shù)組下標(biāo)和位置都是1看起來(lái)對(duì)了但一換測(cè)試數(shù)據(jù)就露餡。建議至少覆蓋目標(biāo)在中間、目標(biāo)在末尾、目標(biāo)不存在、目標(biāo)重復(fù)出現(xiàn)這四種情況。第二數(shù)組越界導(dǎo)致的未定義行為。舉個(gè)常見例子循環(huán)寫成for(i 0; i n; i)在本地可能因?yàn)閮?nèi)存布局運(yùn)氣好沒崩但PTA的數(shù)據(jù)集一旦讓越界訪問觸及不該碰的內(nèi)存就會(huì)段錯(cuò)誤。這點(diǎn)一定要小心數(shù)組訪問范圍是[0, n-1]不是[0, n]。第三輸入數(shù)據(jù)沒有讀完。有人會(huì)在循環(huán)里遇到目標(biāo)后直接return但此時(shí)如果還有剩余輸入沒讀理論上不算問題?？扇绻阌昧四承┨厥鈱懛ū热缦萻canf了一部分然后沒有繼續(xù)讀入而程序又依賴后面某個(gè)變量來(lái)判斷流程那就會(huì)出問題。最簡(jiǎn)單的對(duì)策嚴(yán)格按照讀入全部數(shù)據(jù) - 查找 - 輸出的順序來(lái)寫。4.4 設(shè)計(jì)測(cè)試用例的方法這里分享一個(gè)我驗(yàn)證數(shù)組類題目時(shí)固定使用的測(cè)試用例矩陣。不需要多復(fù)雜但一定要覆蓋邊界和重復(fù)場(chǎng)景。用例1n1x等于唯一的那個(gè)數(shù)預(yù)期輸出1。用例2n5x不存在預(yù)期輸出Not Found。用例3目標(biāo)在第一個(gè)位置驗(yàn)證位置編號(hào)是否從1開始。用例4目標(biāo)在最后一個(gè)位置驗(yàn)證循環(huán)邊界是否正確。用例5輸入含負(fù)數(shù)驗(yàn)證scanf的%d能正常讀負(fù)號(hào)。用例6重復(fù)數(shù)字目標(biāo)出現(xiàn)多次預(yù)期輸出第一次的位置。把這六個(gè)用例如法炮制一遍代碼的可靠性會(huì)大幅提升。養(yǎng)成這種測(cè)試習(xí)慣比多背十道題都有用。5. 從查找整數(shù)出發(fā)算法學(xué)習(xí)的一個(gè)小節(jié)點(diǎn)這道題做完之后不要急著關(guān)掉頁(yè)面。你剛掌握的在數(shù)組里找東西這個(gè)能力會(huì)在一系列后續(xù)題目中不斷變形出現(xiàn)。提前了解一下這些變體后面刷題會(huì)順很多。5.1 順序查找之后下一步學(xué)什么順序查找是無(wú)腦遍歷但它的天花板很低數(shù)據(jù)一大就慢。接下來(lái)在PTA和數(shù)據(jù)結(jié)構(gòu)課程里你會(huì)陸續(xù)遇到兩類查找問題。第一類是有序數(shù)組的查找代表就是二分查找。二分查找每次把查找區(qū)間折半時(shí)間復(fù)雜度是O(log n)但前提是數(shù)組已經(jīng)有序。PTA上經(jīng)典的二分查找PTA函數(shù)題要求你實(shí)現(xiàn)一個(gè)函數(shù)接口在有序數(shù)組里查找目標(biāo)并返回位置。如果你能先把這道查找整數(shù)的順序查找思路寫熟再對(duì)比二分查找的每次砍一半理解起來(lái)會(huì)快很多。第二類是字符串里的查找比如在字符串中逆序輸出、模式匹配等。原理上依然是順序查找的變體把字符數(shù)組里的每個(gè)元素和目標(biāo)去比較。不同的是字符串多了\0結(jié)尾的判斷遍歷條件和整數(shù)數(shù)組略有差別。5.2 哪些題目和這道題是同類項(xiàng)在你接下來(lái)刷PTA的過程中很多題都會(huì)用到這里面的核心能力找最大值和最小值同樣是遍歷數(shù)組只是比較條件從等于target變成比當(dāng)前最值大/小。統(tǒng)計(jì)某個(gè)數(shù)出現(xiàn)的次數(shù)把break去掉每次匹配就count最后輸出count。找出數(shù)組中所有和目標(biāo)相等的數(shù)找到就輸出而不是找到就返回。數(shù)組逆序輸出核心也是數(shù)組遍歷只是從最后一個(gè)下標(biāo)往0循環(huán)。去重遍歷數(shù)組檢查當(dāng)前元素是否在之前出現(xiàn)過——又是一個(gè)查找。你會(huì)發(fā)現(xiàn)幾乎所有數(shù)組類題目都離不開順序查找這個(gè)底層思想。把這道題吃透等于給自己打下了數(shù)組操作的基本盤。5.3 一個(gè)值得養(yǎng)成的代碼習(xí)慣借著這道題我想分享一個(gè)實(shí)際寫代碼時(shí)非常受益的習(xí)慣先畫循環(huán)不變式再寫循環(huán)。聽起來(lái)很高大上其實(shí)就是寫循環(huán)前先明確一件事——這個(gè)循環(huán)結(jié)束時(shí)哪些變量應(yīng)該處于什么狀態(tài)。以這道題的第二個(gè)for循環(huán)為例循環(huán)結(jié)束時(shí)有且僅有兩種情況情況一break跳出此時(shí)flag1i是目標(biāo)所在的下標(biāo)情況二in正常結(jié)束此時(shí)flag0代表沒有找到。知道了這兩種結(jié)束狀態(tài)你就知道為什么需要flag以及為什么break后不應(yīng)該再執(zhí)行Not Found輸出。很多同學(xué)的bug本質(zhì)上就是沒想清楚循環(huán)結(jié)束后的狀態(tài)。把這個(gè)習(xí)慣帶到后續(xù)所有循環(huán)題目里能省掉大量調(diào)試時(shí)間。最后說(shuō)點(diǎn)個(gè)人的體會(huì)。我刷題這些年遇到的最多的不是不會(huì)寫而是差不多就行了的心態(tài)。像查找整數(shù)這種10分題寫完提交通過后就再也不看一眼實(shí)際上很浪費(fèi)——它包含的數(shù)組遍歷、flag標(biāo)記、邊界處理和測(cè)試用例設(shè)計(jì)是以后上百道題都會(huì)反復(fù)用到的基礎(chǔ)能力。每次做完一道題多花十分鐘做三件事重新讀一遍自己的代碼、跑一遍邊界測(cè)試用例、想一想如果數(shù)據(jù)規(guī)模放大一百倍該怎么改。堅(jiān)持下去你對(duì)算法和數(shù)據(jù)結(jié)構(gòu)的理解會(huì)明顯比同齡人深一截。