據(jù)結構考題精講：約瑟夫問題、驗證表、循環(huán)小數(shù)與BFS)
簡介北理工大二數(shù)據(jù)結構課程樂學在線評測平臺編程題的完整C實現(xiàn)合集共29個cpp源碼文件壓縮包大小僅25KB覆蓋線性表、棧與隊列、樹與二叉樹、圖、查找與排序等數(shù)據(jù)結構核心內(nèi)容適合正在修讀該課程或準備期末機考的本科同學參考學習。具體題目包括約瑟夫問題、驗證表、循環(huán)小數(shù)、雙向約瑟夫、綜教樓后的坑、一元多項式相加/相乘、括號匹配、表達式求值、樹的建立與遍歷、哈夫曼樹、折半查找、堆排序、快速排序、關鍵路徑、迷宮問題等基本涵蓋了樂學平臺大二階段的典型編程題目。文件按章節(jié)編號獨立組織題目與代碼一一對應便于按需打開、對照調(diào)試整體難度遞進清晰既有基礎線性表與棧隊列操作也有遞歸建樹、圖遍歷與排序查找等進階內(nèi)容可作為上機實驗和期末復習的算法參考。資源目前已有2968人瀏覽學習體積雖小但覆蓋面廣適合用來鞏固基礎、查漏補缺也能幫助理解抽象數(shù)據(jù)結構如何落地為可運行的C代碼。 大二被樂學平臺這套數(shù)據(jù)結構編程題折磨過的同學應該都記得這幾個名字約瑟夫問題、驗證表、循環(huán)小數(shù)、綜教樓后的坑。它們不是同一類題但都踩中了數(shù)據(jù)結構課的經(jīng)典考點——線性表的刪除模擬、二叉樹的合法性判斷、循環(huán)節(jié)的數(shù)學建模、圖的遍歷搜索。這篇文章我把每道題的思路、實現(xiàn)、還有我當時踩過的坑全部拆開講一遍正在做這套題或者在做類似題目的同學可以直接拿去參考。先說個總體感受這套題真正考的不是“會不會背模板”而是你能不能把課堂上講的性質比如約瑟夫遞推、中序序列有序性、余數(shù)判重、BFS最短步數(shù)轉化成代碼。純靠模仿書上的完整代碼很難拿滿分樂學的測試用例卡得細邊界情況特別多。1. 先看清這波題到底在考什么1.1 樂學平臺的題風與應對思路北理工的樂學平臺不是簡單交作業(yè)它本質是個在線評測系統(tǒng)所以它對時間復雜度、空間復雜度、輸入輸出的格式要求都很嚴格。很多同學在本地DevCpp跑得好好的一提交就“運行錯誤”或者“超時”多半不是代碼邏輯錯而是沒有處理好幾類細節(jié)。這四道題我按考點拆了一下題目核心考點數(shù)據(jù)結構/算法約瑟夫問題出圈順序或幸存者編號循環(huán)鏈表模擬、遞推公式驗證表二叉樹合法性判斷二叉搜索樹性質、區(qū)間遞歸循環(huán)小數(shù)找循環(huán)節(jié)哈希/數(shù)組標記余數(shù)、豎式除法綜教樓后的坑地圖/迷宮路徑網(wǎng)格抽象、BFS/DFS做題順序上我建議先做“循環(huán)小數(shù)”和“約瑟夫問題”這兩個題目的解題路徑比較固定寫完容易驗證對錯。“驗證表”和“綜教樓后的坑”需要多花時間想清楚題目細節(jié)尤其是題目里那些括號、輸出格式的說明漏看一個條件就會白白折騰一晚。1.2 題量和精力的合理分配不要試圖一個晚上刷完四道題我試過結果就是前面兩題因為粗心反復提交失敗后面兩題完全沒時間細想。比較合理的節(jié)奏是約瑟夫和循環(huán)小數(shù)各花半天搞定驗證表單獨留一下午綜教樓后的坑留一晚上專門調(diào)BFS。每道題都要留出至少半小時用來補邊界測試用例后面我會具體講每個題的邊界長什么樣。2. 約瑟夫問題別一上來就寫循環(huán)鏈表2.1 遞歸公式推導為什么答案能一行算出約瑟夫問題的經(jīng)典描述是n個人圍成一圈從某個位置開始報數(shù)報到m的人出圈然后下一個人重新從1報數(shù)問最后剩下的人是誰。很多教材給的解法是循環(huán)鏈表刪除這個思路最直觀但如果你只需要知道最后的幸存者編號根本不用去模擬刪除過程。這里有一個非常關鍵的遞推思想。假設f(n, m) 表示n個人報數(shù)m時最后幸存者的編號從0開始編號。第一輪報數(shù)后編號為(m-1) mod n的人出圈那么剩下的人從原來的編號m mod n開始重新組成一個規(guī)模為n-1的圈子。在這個新圈子里編號從0開始數(shù)的第f(n-1, m)個人就是原來的幸存者。所以有f(1, m) 0 f(n, m) (f(n-1, m) m) mod n這個公式的巧妙之處在于它把“刪人后重新編號”的過程壓縮成了一個模運算。很多同學不理解為什么最后要加上m再取模其實它就是做了“新編號還原回舊編號”的逆運算。你可以拿n5, m3手推一遍感受一下這個還原過程。2.2 兩種解法對比與代碼實現(xiàn)我先把兩種方法的代碼都放出來再給你看它們的定位。循環(huán)鏈表模擬的代碼大致長這樣#include stdio.h #include stdlib.h typedef struct Node { int id; struct Node *next; } Node; Node* createList(int n) { Node *head (Node*)malloc(sizeof(Node)); head-id 1; head-next NULL; Node *tail head; for (int i 2; i n; i) { Node *p (Node*)malloc(sizeof(Node)); p-id i; p-next NULL; tail-next p; tail p; } tail-next head; return head; } int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { if (n 0) break; Node *cur createList(n); Node *prev NULL; while (cur-next ! cur) { for (int i 1; i m; i) { prev cur; cur cur-next; } Node *tmp cur; prev-next cur-next; cur cur-next; free(tmp); } printf(%d\n, cur-id); free(cur); } return 0; }而遞推法的代碼短得多#include stdio.h int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { if (n 0) break; int ans 0; for (int i 2; i n; i) { ans (ans m) % i; } printf(%d\n, ans 1); } return 0; }注意輸出的時候要加1因為遞推公式里的編號是從0開始的而題目通常要求輸出從1開始的編號。當時我第一次寫這題就是用鏈表模擬結果n一超過10萬就開始劇烈卡頓改成遞推后連n等于幾百萬都能秒過。但如果你遇到的輸出要求是給出完整出圈序列那么遞推法就不適用了還是得用鏈表模擬或者在循環(huán)鏈表基礎上做優(yōu)化。兩種方法的對比如下指標循環(huán)鏈表模擬遞推公式時間復雜度O(n * m)O(n)空間復雜度O(n)O(1)適合場景需要輸出完整出圈順序只求最后幸存者編號代碼量40行左右10行左右經(jīng)驗之談先讀清楚題目到底要什么。看到“最后剩下的人”就立刻用遞推看到“輸出出圈序列”才用鏈表。另外鏈表的題即使要用模擬也要注意釋放內(nèi)存樂學平臺上內(nèi)存泄漏一般不會判錯但養(yǎng)成良好的習慣對后面的課程設計有幫助。3. 循環(huán)小數(shù)模擬除法豎式比你想的要簡單3.1 循環(huán)節(jié)產(chǎn)生的本質余數(shù)重復循環(huán)小數(shù)這題核心不是小數(shù)本身而是“循環(huán)節(jié)”。輸入一個分子a和分母b我遇到的版本是a和b都是正整數(shù)要求輸出 a/b 的小數(shù)形式如果小數(shù)部分循環(huán)需要用括號標出循環(huán)節(jié)比如 1/3 輸出 1.(3)1/6 輸出 0.1(6)。為什么會產(chǎn)生循環(huán)因為除法豎式里每次都是拿余數(shù)乘10再除以除數(shù)得到新的商和新的余數(shù)。一旦某個余數(shù)之前出現(xiàn)過那么之后的所有計算過程都會完全重復小數(shù)就進入了循環(huán)。所以找循環(huán)節(jié)的關鍵就是“余數(shù)判重”記錄每個余數(shù)第一次出現(xiàn)的位置當某個余數(shù)再次出現(xiàn)時從它第一次出現(xiàn)的位置到當前位置就是循環(huán)節(jié)。3.2 從整數(shù)部分到循環(huán)節(jié)的完整流程我寫的C程序分了三步先算整數(shù)部分再算小數(shù)部分最后輸出循環(huán)節(jié)。核心代碼如下#include stdio.h #include string.h int main() { int a, b; while (scanf(%d%d, a, b) ! EOF) { if (b 0) continue; int integer a / b; int rem a % b; printf(%d., integer); if (rem 0) { printf(0\n); continue; } int pos[100005]; memset(pos, -1, sizeof(pos)); int quotient[100005]; int idx 0; int startCycle -1; while (rem ! 0) { if (pos[rem] ! -1) { startCycle pos[rem]; break; } pos[rem] idx; rem * 10; quotient[idx] rem / b; rem % b; idx; } if (startCycle -1) { for (int i 0; i idx; i) { printf(%d, quotient[i]); } printf(\n); } else { for (int i 0; i startCycle; i) { printf(%d, quotient[i]); } printf((); for (int i startCycle; i idx; i) { printf(%d, quotient[i]); } printf()\n); } } return 0; }這段代碼有幾個關鍵點。第一個是pos數(shù)組要開多大理論上余數(shù)的取值范圍是0到b-1但題目如果給出b的最大值就直接按最大值開。如果沒有明確給邊界建議用動態(tài)內(nèi)存或哈希來處理避免數(shù)組越界。第二個是整除的情況一定單獨處理比如 6/2輸出 3.0 而不是 3. 后面什么都沒有。還有一個小細節(jié)如果整數(shù)部分本來為0也要輸出0所以printf(%d., integer)這個寫法能保證格式正確。我當時在這個題上栽過兩次。第一次是忘了記錄余數(shù)第一次出現(xiàn)的位置導致循環(huán)節(jié)判斷錯亂第二次是沒處理“余數(shù)為0被整除”的情況導致程序死循環(huán)。后來我每次拿到這類題都會先想清楚“什么樣的輸入會讓循環(huán)退出”再開始寫代碼。4. 驗證表樹的題核心是先搞懂遍歷序列4.1 “驗證表”到底要驗證什么“驗證表”這題我第一次看到名字也是一頭霧水后來看了樣例才明白它給出一棵二叉樹的中序序列或者是某種遍歷結果要求判斷這棵樹是否是二叉搜索樹并輸出對應的驗證信息表。不同年份的題目描述可能不一樣我拿到的版本是給出一棵二叉樹每個節(jié)點的值以及左右子節(jié)點關系要求驗證這棵樹是否滿足二叉搜索樹的性質輸出每個節(jié)點對應的合法區(qū)間。二叉搜索樹的核心性質是中序遍歷有序但不止這一條每個節(jié)點的所有左子樹節(jié)點都小于當前節(jié)點所有右子樹節(jié)點都大于當前節(jié)點。如果只檢查相鄰兩個中序節(jié)點是否遞增會遇到一個問題樣例數(shù)據(jù)可能構造出連續(xù)值相等的序列這時候需要額外判斷是否允許重復值。我采用的思路是遞歸區(qū)間驗證從根節(jié)點開始假設它允許的取值范圍是(-∞, ∞)。對于某個節(jié)點值為val它的左子樹所有節(jié)點必須落在(min, val)區(qū)間內(nèi)右子樹所有節(jié)點必須落在(val, max)區(qū)間內(nèi)。只要在遞歸過程中任何一個節(jié)點值不在允許區(qū)間內(nèi)就說明不是二叉搜索樹。4.2 區(qū)間遞歸的邊界細節(jié)這個思路的代碼量不大但邊界處理極其容易出現(xiàn)隱蔽錯誤。我這里寫一個參考實現(xiàn)#include stdio.h #include limits.h int flag 1; typedef struct TreeNode { int val; int left; int right; } TreeNode; TreeNode nodes[10005]; void dfs(int root, long long min, long long max) { if (root -1 || !flag) return; int val nodes[root].val; if (val min || val max) { flag 0; return; } dfs(nodes[root].left, min, val); dfs(nodes[root].right, val, max); } int main() { int n; scanf(%d, n); for (int i 1; i n; i) { scanf(%d%d%d, nodes[i].val, nodes[i].left, nodes[i].right); } dfs(1, LLONG_MIN, LLONG_MAX); // 假設編號1是根 if (flag) printf(Valid\n); else printf(Invalid\n); return 0; }這里我用long long來傳區(qū)間邊界因為如果樹里出現(xiàn)了INT_MIN初始邊界設成INT_MIN會導致判斷出錯——INT_MIN和INT_MIN比較要不要取等號這是很微妙的問題。用long long把邊界放大可以避免這種糾結。另外遞歸深度也要注意如果樹退化成一條鏈深度可能達到n遞歸層數(shù)過多會導致棧溢出。這種情況可以用棧迭代替代遞歸或者用中序遍歷的棧實現(xiàn)。我當時在這題上卡了很久最后是手動構造了一個對稱的樣例才定位到問題樹的根節(jié)點不一定是編號1樂學平臺有些數(shù)據(jù)的根節(jié)點編號不是固定的。所以我加了一行查找入度為0節(jié)點的邏輯才把所有測試點跑通。如果你遇到的題目沒有明確說明根節(jié)點這一步千萬別省。5. 綜教樓后的坑圖的遍歷與最短路徑別再DFS寫爆炸5.1 題目背景與地圖抽象“綜教樓后的坑”這題名字聽著很玄實際上是一個網(wǎng)格地圖問題。我拿到的版本是給定一個n行m列的網(wǎng)格有些格子有障礙物坑有些格子可以走要求從起點走到終點輸出最短步數(shù)或者路徑。題目描述里可能會用字符矩陣表示地圖比如S表示起點E表示終點#表示障礙.表示空地。這種題要做的第一件事就是抽象把每個格子看成一個節(jié)點上下左右相鄰的可走格子之間連一條邊問題就變成了在無權圖上求最短路徑。無權圖的最短路徑用BFS就可以了第一次訪問到終點時的層數(shù)就是最短步數(shù)。我見過不少同學一上來就寫DFS理由是“深度優(yōu)先看起來像在走路”。但DFS找最短路徑需要把所有路徑都走一遍復雜度是O(2^(nm))級別的地圖稍大一點就會超時或者爆棧。BFS按層擴展每個格子最多被訪問一次復雜度是O(n*m)穩(wěn)定得多。5.2 BFS模板與防坑記錄BFS的標準實現(xiàn)是用隊列配合vis數(shù)組記錄每個格子是否訪問過。方向數(shù)組是固定的x和y的變化可以統(tǒng)一寫成一個二維數(shù)組#include stdio.h #include string.h #define MAXN 105 int n, m; char mp[MAXN][MAXN]; int vis[MAXN][MAXN]; int step[MAXN][MAXN]; int dir[4][2] {{1,0},{-1,0},{0,1},{0,-1}}; int sx, sy, ex, ey; typedef struct { int x, y; } Point; Point queue[MAXN * MAXN]; int bfs() { int head 0, tail 0; queue[tail].x sx; queue[tail].y sy; tail; vis[sx][sy] 1; step[sx][sy] 0; while (head tail) { Point now queue[head]; if (now.x ex now.y ey) { return step[now.x][now.y]; } for (int i 0; i 4; i) { int nx now.x dir[i][0]; int ny now.y dir[i][1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (mp[nx][ny] #) continue; if (vis[nx][ny]) continue; vis[nx][ny] 1; step[nx][ny] step[now.x][now.y] 1; queue[tail].x nx; queue[tail].y ny; tail; } } return -1; } int main() { while (scanf(%d%d, n, m) ! EOF) { for (int i 0; i n; i) { scanf(%s, mp[i]); for (int j 0; j m; j) { if (mp[i][j] S) { sx i; sy j; } else if (mp[i][j] E) { ex i; ey j; } } } memset(vis, 0, sizeof(vis)); memset(step, 0, sizeof(step)); int ans bfs(); if (ans -1) printf(No path\n); else printf(%d\n, ans); } return 0; }這個模板里有三個常見的坑。第一個是隊首隊尾指針的處理我習慣用數(shù)組模擬隊列因為直接調(diào)用STL的queue在部分老版本的評測環(huán)境里可能會有兼容問題而且數(shù)組模擬訪問速度快。第二個是vis標記的時機我一貫的做法是在元素入隊時立刻標記也就是節(jié)點入隊就把vis[nx][ny]置1避免同一個點被多次加入隊列。如果等到出隊時才標記那么同一個點可能被多個方向的鄰居同時發(fā)現(xiàn)隊列會膨脹嚴重時導致超時或內(nèi)存不夠。第三個是step數(shù)組如果題目只要求輸出最短步數(shù)用step數(shù)組記錄每格步數(shù)非常直觀如果題目要求輸出路徑還要另開一個數(shù)組存前驅。6. 常見錯誤與調(diào)試心得這波真的被坑過6.1 高頻報錯清單與定位方法我把自己和身邊同學在樂學平臺上遇到的高頻報錯整理成了一張表對照這個表自查比對著屏幕發(fā)呆有用得多報錯類型常見原因排查方法編譯錯誤少了頭文件、C語言用了C語法先看第一行報錯信息多半是聲明或頭文件問題運行錯誤數(shù)組越界、野指針、訪問未初始化變量檢查所有數(shù)組下標尤其是循環(huán)邊界超時算法復雜度過高、死循環(huán)檢查是否有循環(huán)變量沒更新確認數(shù)據(jù)規(guī)模答案錯誤邊界情況沒處理、輸出格式不對手推小數(shù)據(jù)逐行比對輸出運行錯誤里最陰間的就是“數(shù)組越界”。比如循環(huán)小數(shù)里如果b最大是100000我把pos數(shù)組開成100000可是余數(shù)本身可能等于99999訪問pos[99999]沒問題但后面rem * 10之后rem可能超過數(shù)組范圍這時候就需要在賦值前判斷一下rem的范圍。再比如驗證表的樹節(jié)點編號題目如果告訴你節(jié)點編號從1到n你開nodes[10005]沒問題但如果某組數(shù)據(jù)編號范圍正好是99999數(shù)組就爆了。我的習慣是凡是數(shù)組大小依賴輸入數(shù)據(jù)的題目一律按照題目給的上限再多開5到10個這是防御性編程的基本功。6.2 邊界樣例與對拍技巧我寫這些題的時候會給自己準備一組“邊界全家桶”用例每道題提交前先跑一遍約瑟夫問題n1, m1n5, m3n10, m100m大于n的情況循環(huán)小數(shù)1/2整除后余數(shù)為01/3從第一位開始循環(huán)1/6循環(huán)節(jié)不在小數(shù)第一位0/5分子為0驗證表空樹如果題目允許單節(jié)點根只有一個左孩子整棵樹退化成鏈表綜教樓后的坑地圖只有起點和終點且相鄰終點被障礙包圍2x2最小地圖還有一個很笨但很有效的調(diào)試技巧在關鍵循環(huán)里用printf打印中間變量。比如約瑟夫問題打印每次遞推的ans值循環(huán)小數(shù)里打印每次的余數(shù)和商BFS里打印每個出隊點的坐標。定位完bug再把printf刪掉雖然土但比只會加斷點快得多。如果實在找不出錯還有一個“對拍”的思路寫一個暴力做法再寫一個優(yōu)化做法用隨機小數(shù)據(jù)反復跑比較兩者輸出是否一致。這個技巧在考試和競賽里很常見我平時做樂學題也這么干一次能省出兩三個小時的排查時間。最后說一點個人體會。數(shù)據(jù)結構這門課理論課的公式推導和實驗課的編程題往往是兩回事。你在紙上能推約瑟夫遞推不代表你能處理n0的輸入你懂BFS的原理不代表你能避開隊列內(nèi)存爆炸的坑。樂學平臺這幾道題最鍛煉人的地方其實是“把課堂知識翻譯成邊界條件”的能力。建議學弟學妹們別急著提交先花十分鐘把所有可能的特殊輸入列出來跑一遍再交通過率會大幅提升。后面如果有時間可以把這幾道題再往深延伸一下——約瑟夫問題可以改成輸出出圈序列的線段樹版本循環(huán)小數(shù)可以結合大數(shù)除法處理高精度分數(shù)綜教樓后的坑可以加入多起點或傳送門練熟這些變體期末上機就真的沒什么好怕的了。本文還有配套的精品資源點擊獲取 樂學平臺數(shù)據(jù)結構考題精講：約瑟夫問題、驗證表、循環(huán)小數(shù)與BFS
簡介北理工大二數(shù)據(jù)結構課程樂學在線評測平臺編程題的完整C實現(xiàn)合集共29個cpp源碼文件壓縮包大小僅25KB覆蓋線性表、棧與隊列、樹與二叉樹、圖、查找與排序等數(shù)據(jù)結構核心內(nèi)容適合正在修讀該課程或準備期末機考的本科同學參考學習。具體題目包括約瑟夫問題、驗證表、循環(huán)小數(shù)、雙向約瑟夫、綜教樓后的坑、一元多項式相加/相乘、括號匹配、表達式求值、樹的建立與遍歷、哈夫曼樹、折半查找、堆排序、快速排序、關鍵路徑、迷宮問題等基本涵蓋了樂學平臺大二階段的典型編程題目。文件按章節(jié)編號獨立組織題目與代碼一一對應便于按需打開、對照調(diào)試整體難度遞進清晰既有基礎線性表與棧隊列操作也有遞歸建樹、圖遍歷與排序查找等進階內(nèi)容可作為上機實驗和期末復習的算法參考。資源目前已有2968人瀏覽學習體積雖小但覆蓋面廣適合用來鞏固基礎、查漏補缺也能幫助理解抽象數(shù)據(jù)結構如何落地為可運行的C代碼。 大二被樂學平臺這套數(shù)據(jù)結構編程題折磨過的同學應該都記得這幾個名字約瑟夫問題、驗證表、循環(huán)小數(shù)、綜教樓后的坑。它們不是同一類題但都踩中了數(shù)據(jù)結構課的經(jīng)典考點——線性表的刪除模擬、二叉樹的合法性判斷、循環(huán)節(jié)的數(shù)學建模、圖的遍歷搜索。這篇文章我把每道題的思路、實現(xiàn)、還有我當時踩過的坑全部拆開講一遍正在做這套題或者在做類似題目的同學可以直接拿去參考。先說個總體感受這套題真正考的不是“會不會背模板”而是你能不能把課堂上講的性質比如約瑟夫遞推、中序序列有序性、余數(shù)判重、BFS最短步數(shù)轉化成代碼。純靠模仿書上的完整代碼很難拿滿分樂學的測試用例卡得細邊界情況特別多。1. 先看清這波題到底在考什么1.1 樂學平臺的題風與應對思路北理工的樂學平臺不是簡單交作業(yè)它本質是個在線評測系統(tǒng)所以它對時間復雜度、空間復雜度、輸入輸出的格式要求都很嚴格。很多同學在本地DevCpp跑得好好的一提交就“運行錯誤”或者“超時”多半不是代碼邏輯錯而是沒有處理好幾類細節(jié)。這四道題我按考點拆了一下題目核心考點數(shù)據(jù)結構/算法約瑟夫問題出圈順序或幸存者編號循環(huán)鏈表模擬、遞推公式驗證表二叉樹合法性判斷二叉搜索樹性質、區(qū)間遞歸循環(huán)小數(shù)找循環(huán)節(jié)哈希/數(shù)組標記余數(shù)、豎式除法綜教樓后的坑地圖/迷宮路徑網(wǎng)格抽象、BFS/DFS做題順序上我建議先做“循環(huán)小數(shù)”和“約瑟夫問題”這兩個題目的解題路徑比較固定寫完容易驗證對錯。“驗證表”和“綜教樓后的坑”需要多花時間想清楚題目細節(jié)尤其是題目里那些括號、輸出格式的說明漏看一個條件就會白白折騰一晚。1.2 題量和精力的合理分配不要試圖一個晚上刷完四道題我試過結果就是前面兩題因為粗心反復提交失敗后面兩題完全沒時間細想。比較合理的節(jié)奏是約瑟夫和循環(huán)小數(shù)各花半天搞定驗證表單獨留一下午綜教樓后的坑留一晚上專門調(diào)BFS。每道題都要留出至少半小時用來補邊界測試用例后面我會具體講每個題的邊界長什么樣。2. 約瑟夫問題別一上來就寫循環(huán)鏈表2.1 遞歸公式推導為什么答案能一行算出約瑟夫問題的經(jīng)典描述是n個人圍成一圈從某個位置開始報數(shù)報到m的人出圈然后下一個人重新從1報數(shù)問最后剩下的人是誰。很多教材給的解法是循環(huán)鏈表刪除這個思路最直觀但如果你只需要知道最后的幸存者編號根本不用去模擬刪除過程。這里有一個非常關鍵的遞推思想。假設f(n, m) 表示n個人報數(shù)m時最后幸存者的編號從0開始編號。第一輪報數(shù)后編號為(m-1) mod n的人出圈那么剩下的人從原來的編號m mod n開始重新組成一個規(guī)模為n-1的圈子。在這個新圈子里編號從0開始數(shù)的第f(n-1, m)個人就是原來的幸存者。所以有f(1, m) 0 f(n, m) (f(n-1, m) m) mod n這個公式的巧妙之處在于它把“刪人后重新編號”的過程壓縮成了一個模運算。很多同學不理解為什么最后要加上m再取模其實它就是做了“新編號還原回舊編號”的逆運算。你可以拿n5, m3手推一遍感受一下這個還原過程。2.2 兩種解法對比與代碼實現(xiàn)我先把兩種方法的代碼都放出來再給你看它們的定位。循環(huán)鏈表模擬的代碼大致長這樣#include stdio.h #include stdlib.h typedef struct Node { int id; struct Node *next; } Node; Node* createList(int n) { Node *head (Node*)malloc(sizeof(Node)); head-id 1; head-next NULL; Node *tail head; for (int i 2; i n; i) { Node *p (Node*)malloc(sizeof(Node)); p-id i; p-next NULL; tail-next p; tail p; } tail-next head; return head; } int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { if (n 0) break; Node *cur createList(n); Node *prev NULL; while (cur-next ! cur) { for (int i 1; i m; i) { prev cur; cur cur-next; } Node *tmp cur; prev-next cur-next; cur cur-next; free(tmp); } printf(%d\n, cur-id); free(cur); } return 0; }而遞推法的代碼短得多#include stdio.h int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { if (n 0) break; int ans 0; for (int i 2; i n; i) { ans (ans m) % i; } printf(%d\n, ans 1); } return 0; }注意輸出的時候要加1因為遞推公式里的編號是從0開始的而題目通常要求輸出從1開始的編號。當時我第一次寫這題就是用鏈表模擬結果n一超過10萬就開始劇烈卡頓改成遞推后連n等于幾百萬都能秒過。但如果你遇到的輸出要求是給出完整出圈序列那么遞推法就不適用了還是得用鏈表模擬或者在循環(huán)鏈表基礎上做優(yōu)化。兩種方法的對比如下指標循環(huán)鏈表模擬遞推公式時間復雜度O(n * m)O(n)空間復雜度O(n)O(1)適合場景需要輸出完整出圈順序只求最后幸存者編號代碼量40行左右10行左右經(jīng)驗之談先讀清楚題目到底要什么。看到“最后剩下的人”就立刻用遞推看到“輸出出圈序列”才用鏈表。另外鏈表的題即使要用模擬也要注意釋放內(nèi)存樂學平臺上內(nèi)存泄漏一般不會判錯但養(yǎng)成良好的習慣對后面的課程設計有幫助。3. 循環(huán)小數(shù)模擬除法豎式比你想的要簡單3.1 循環(huán)節(jié)產(chǎn)生的本質余數(shù)重復循環(huán)小數(shù)這題核心不是小數(shù)本身而是“循環(huán)節(jié)”。輸入一個分子a和分母b我遇到的版本是a和b都是正整數(shù)要求輸出 a/b 的小數(shù)形式如果小數(shù)部分循環(huán)需要用括號標出循環(huán)節(jié)比如 1/3 輸出 1.(3)1/6 輸出 0.1(6)。為什么會產(chǎn)生循環(huán)因為除法豎式里每次都是拿余數(shù)乘10再除以除數(shù)得到新的商和新的余數(shù)。一旦某個余數(shù)之前出現(xiàn)過那么之后的所有計算過程都會完全重復小數(shù)就進入了循環(huán)。所以找循環(huán)節(jié)的關鍵就是“余數(shù)判重”記錄每個余數(shù)第一次出現(xiàn)的位置當某個余數(shù)再次出現(xiàn)時從它第一次出現(xiàn)的位置到當前位置就是循環(huán)節(jié)。3.2 從整數(shù)部分到循環(huán)節(jié)的完整流程我寫的C程序分了三步先算整數(shù)部分再算小數(shù)部分最后輸出循環(huán)節(jié)。核心代碼如下#include stdio.h #include string.h int main() { int a, b; while (scanf(%d%d, a, b) ! EOF) { if (b 0) continue; int integer a / b; int rem a % b; printf(%d., integer); if (rem 0) { printf(0\n); continue; } int pos[100005]; memset(pos, -1, sizeof(pos)); int quotient[100005]; int idx 0; int startCycle -1; while (rem ! 0) { if (pos[rem] ! -1) { startCycle pos[rem]; break; } pos[rem] idx; rem * 10; quotient[idx] rem / b; rem % b; idx; } if (startCycle -1) { for (int i 0; i idx; i) { printf(%d, quotient[i]); } printf(\n); } else { for (int i 0; i startCycle; i) { printf(%d, quotient[i]); } printf((); for (int i startCycle; i idx; i) { printf(%d, quotient[i]); } printf()\n); } } return 0; }這段代碼有幾個關鍵點。第一個是pos數(shù)組要開多大理論上余數(shù)的取值范圍是0到b-1但題目如果給出b的最大值就直接按最大值開。如果沒有明確給邊界建議用動態(tài)內(nèi)存或哈希來處理避免數(shù)組越界。第二個是整除的情況一定單獨處理比如 6/2輸出 3.0 而不是 3. 后面什么都沒有。還有一個小細節(jié)如果整數(shù)部分本來為0也要輸出0所以printf(%d., integer)這個寫法能保證格式正確。我當時在這個題上栽過兩次。第一次是忘了記錄余數(shù)第一次出現(xiàn)的位置導致循環(huán)節(jié)判斷錯亂第二次是沒處理“余數(shù)為0被整除”的情況導致程序死循環(huán)。后來我每次拿到這類題都會先想清楚“什么樣的輸入會讓循環(huán)退出”再開始寫代碼。4. 驗證表樹的題核心是先搞懂遍歷序列4.1 “驗證表”到底要驗證什么“驗證表”這題我第一次看到名字也是一頭霧水后來看了樣例才明白它給出一棵二叉樹的中序序列或者是某種遍歷結果要求判斷這棵樹是否是二叉搜索樹并輸出對應的驗證信息表。不同年份的題目描述可能不一樣我拿到的版本是給出一棵二叉樹每個節(jié)點的值以及左右子節(jié)點關系要求驗證這棵樹是否滿足二叉搜索樹的性質輸出每個節(jié)點對應的合法區(qū)間。二叉搜索樹的核心性質是中序遍歷有序但不止這一條每個節(jié)點的所有左子樹節(jié)點都小于當前節(jié)點所有右子樹節(jié)點都大于當前節(jié)點。如果只檢查相鄰兩個中序節(jié)點是否遞增會遇到一個問題樣例數(shù)據(jù)可能構造出連續(xù)值相等的序列這時候需要額外判斷是否允許重復值。我采用的思路是遞歸區(qū)間驗證從根節(jié)點開始假設它允許的取值范圍是(-∞, ∞)。對于某個節(jié)點值為val它的左子樹所有節(jié)點必須落在(min, val)區(qū)間內(nèi)右子樹所有節(jié)點必須落在(val, max)區(qū)間內(nèi)。只要在遞歸過程中任何一個節(jié)點值不在允許區(qū)間內(nèi)就說明不是二叉搜索樹。4.2 區(qū)間遞歸的邊界細節(jié)這個思路的代碼量不大但邊界處理極其容易出現(xiàn)隱蔽錯誤。我這里寫一個參考實現(xiàn)#include stdio.h #include limits.h int flag 1; typedef struct TreeNode { int val; int left; int right; } TreeNode; TreeNode nodes[10005]; void dfs(int root, long long min, long long max) { if (root -1 || !flag) return; int val nodes[root].val; if (val min || val max) { flag 0; return; } dfs(nodes[root].left, min, val); dfs(nodes[root].right, val, max); } int main() { int n; scanf(%d, n); for (int i 1; i n; i) { scanf(%d%d%d, nodes[i].val, nodes[i].left, nodes[i].right); } dfs(1, LLONG_MIN, LLONG_MAX); // 假設編號1是根 if (flag) printf(Valid\n); else printf(Invalid\n); return 0; }這里我用long long來傳區(qū)間邊界因為如果樹里出現(xiàn)了INT_MIN初始邊界設成INT_MIN會導致判斷出錯——INT_MIN和INT_MIN比較要不要取等號這是很微妙的問題。用long long把邊界放大可以避免這種糾結。另外遞歸深度也要注意如果樹退化成一條鏈深度可能達到n遞歸層數(shù)過多會導致棧溢出。這種情況可以用棧迭代替代遞歸或者用中序遍歷的棧實現(xiàn)。我當時在這題上卡了很久最后是手動構造了一個對稱的樣例才定位到問題樹的根節(jié)點不一定是編號1樂學平臺有些數(shù)據(jù)的根節(jié)點編號不是固定的。所以我加了一行查找入度為0節(jié)點的邏輯才把所有測試點跑通。如果你遇到的題目沒有明確說明根節(jié)點這一步千萬別省。5. 綜教樓后的坑圖的遍歷與最短路徑別再DFS寫爆炸5.1 題目背景與地圖抽象“綜教樓后的坑”這題名字聽著很玄實際上是一個網(wǎng)格地圖問題。我拿到的版本是給定一個n行m列的網(wǎng)格有些格子有障礙物坑有些格子可以走要求從起點走到終點輸出最短步數(shù)或者路徑。題目描述里可能會用字符矩陣表示地圖比如S表示起點E表示終點#表示障礙.表示空地。這種題要做的第一件事就是抽象把每個格子看成一個節(jié)點上下左右相鄰的可走格子之間連一條邊問題就變成了在無權圖上求最短路徑。無權圖的最短路徑用BFS就可以了第一次訪問到終點時的層數(shù)就是最短步數(shù)。我見過不少同學一上來就寫DFS理由是“深度優(yōu)先看起來像在走路”。但DFS找最短路徑需要把所有路徑都走一遍復雜度是O(2^(nm))級別的地圖稍大一點就會超時或者爆棧。BFS按層擴展每個格子最多被訪問一次復雜度是O(n*m)穩(wěn)定得多。5.2 BFS模板與防坑記錄BFS的標準實現(xiàn)是用隊列配合vis數(shù)組記錄每個格子是否訪問過。方向數(shù)組是固定的x和y的變化可以統(tǒng)一寫成一個二維數(shù)組#include stdio.h #include string.h #define MAXN 105 int n, m; char mp[MAXN][MAXN]; int vis[MAXN][MAXN]; int step[MAXN][MAXN]; int dir[4][2] {{1,0},{-1,0},{0,1},{0,-1}}; int sx, sy, ex, ey; typedef struct { int x, y; } Point; Point queue[MAXN * MAXN]; int bfs() { int head 0, tail 0; queue[tail].x sx; queue[tail].y sy; tail; vis[sx][sy] 1; step[sx][sy] 0; while (head tail) { Point now queue[head]; if (now.x ex now.y ey) { return step[now.x][now.y]; } for (int i 0; i 4; i) { int nx now.x dir[i][0]; int ny now.y dir[i][1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (mp[nx][ny] #) continue; if (vis[nx][ny]) continue; vis[nx][ny] 1; step[nx][ny] step[now.x][now.y] 1; queue[tail].x nx; queue[tail].y ny; tail; } } return -1; } int main() { while (scanf(%d%d, n, m) ! EOF) { for (int i 0; i n; i) { scanf(%s, mp[i]); for (int j 0; j m; j) { if (mp[i][j] S) { sx i; sy j; } else if (mp[i][j] E) { ex i; ey j; } } } memset(vis, 0, sizeof(vis)); memset(step, 0, sizeof(step)); int ans bfs(); if (ans -1) printf(No path\n); else printf(%d\n, ans); } return 0; }這個模板里有三個常見的坑。第一個是隊首隊尾指針的處理我習慣用數(shù)組模擬隊列因為直接調(diào)用STL的queue在部分老版本的評測環(huán)境里可能會有兼容問題而且數(shù)組模擬訪問速度快。第二個是vis標記的時機我一貫的做法是在元素入隊時立刻標記也就是節(jié)點入隊就把vis[nx][ny]置1避免同一個點被多次加入隊列。如果等到出隊時才標記那么同一個點可能被多個方向的鄰居同時發(fā)現(xiàn)隊列會膨脹嚴重時導致超時或內(nèi)存不夠。第三個是step數(shù)組如果題目只要求輸出最短步數(shù)用step數(shù)組記錄每格步數(shù)非常直觀如果題目要求輸出路徑還要另開一個數(shù)組存前驅。6. 常見錯誤與調(diào)試心得這波真的被坑過6.1 高頻報錯清單與定位方法我把自己和身邊同學在樂學平臺上遇到的高頻報錯整理成了一張表對照這個表自查比對著屏幕發(fā)呆有用得多報錯類型常見原因排查方法編譯錯誤少了頭文件、C語言用了C語法先看第一行報錯信息多半是聲明或頭文件問題運行錯誤數(shù)組越界、野指針、訪問未初始化變量檢查所有數(shù)組下標尤其是循環(huán)邊界超時算法復雜度過高、死循環(huán)檢查是否有循環(huán)變量沒更新確認數(shù)據(jù)規(guī)模答案錯誤邊界情況沒處理、輸出格式不對手推小數(shù)據(jù)逐行比對輸出運行錯誤里最陰間的就是“數(shù)組越界”。比如循環(huán)小數(shù)里如果b最大是100000我把pos數(shù)組開成100000可是余數(shù)本身可能等于99999訪問pos[99999]沒問題但后面rem * 10之后rem可能超過數(shù)組范圍這時候就需要在賦值前判斷一下rem的范圍。再比如驗證表的樹節(jié)點編號題目如果告訴你節(jié)點編號從1到n你開nodes[10005]沒問題但如果某組數(shù)據(jù)編號范圍正好是99999數(shù)組就爆了。我的習慣是凡是數(shù)組大小依賴輸入數(shù)據(jù)的題目一律按照題目給的上限再多開5到10個這是防御性編程的基本功。6.2 邊界樣例與對拍技巧我寫這些題的時候會給自己準備一組“邊界全家桶”用例每道題提交前先跑一遍約瑟夫問題n1, m1n5, m3n10, m100m大于n的情況循環(huán)小數(shù)1/2整除后余數(shù)為01/3從第一位開始循環(huán)1/6循環(huán)節(jié)不在小數(shù)第一位0/5分子為0驗證表空樹如果題目允許單節(jié)點根只有一個左孩子整棵樹退化成鏈表綜教樓后的坑地圖只有起點和終點且相鄰終點被障礙包圍2x2最小地圖還有一個很笨但很有效的調(diào)試技巧在關鍵循環(huán)里用printf打印中間變量。比如約瑟夫問題打印每次遞推的ans值循環(huán)小數(shù)里打印每次的余數(shù)和商BFS里打印每個出隊點的坐標。定位完bug再把printf刪掉雖然土但比只會加斷點快得多。如果實在找不出錯還有一個“對拍”的思路寫一個暴力做法再寫一個優(yōu)化做法用隨機小數(shù)據(jù)反復跑比較兩者輸出是否一致。這個技巧在考試和競賽里很常見我平時做樂學題也這么干一次能省出兩三個小時的排查時間。最后說一點個人體會。數(shù)據(jù)結構這門課理論課的公式推導和實驗課的編程題往往是兩回事。你在紙上能推約瑟夫遞推不代表你能處理n0的輸入你懂BFS的原理不代表你能避開隊列內(nèi)存爆炸的坑。樂學平臺這幾道題最鍛煉人的地方其實是“把課堂知識翻譯成邊界條件”的能力。建議學弟學妹們別急著提交先花十分鐘把所有可能的特殊輸入列出來跑一遍再交通過率會大幅提升。后面如果有時間可以把這幾道題再往深延伸一下——約瑟夫問題可以改成輸出出圈序列的線段樹版本循環(huán)小數(shù)可以結合大數(shù)除法處理高精度分數(shù)綜教樓后的坑可以加入多起點或傳送門練熟這些變體期末上機就真的沒什么好怕的了。本文還有配套的精品資源點擊獲取