每年到這個時間點(diǎn)總有一批準(zhǔn)備暑期實(shí)習(xí)的同學(xué)開始在?？途W(wǎng)上刷題。最近好幾個學(xué)弟學(xué)妹跑來問我同一個問題網(wǎng)易的筆試到底難不難我的回答一般是你去把《網(wǎng)易2019實(shí)習(xí)生招聘編程題集合》從頭到尾過一遍就知道了。這套題流傳很廣幾乎成了大廠實(shí)習(xí)筆試的入門樣本。它整體難度不勸退沒有那種一上來就甩你一道后綴自動機(jī)的硬核題但每一道都不白給模擬題的邊界條件、數(shù)學(xué)題的規(guī)律總結(jié)、貪心題的嚴(yán)格證明每一樣都能篩掉一批人。這篇文章我就把這套題完整拆開從考點(diǎn)到代碼到坑位按我自己的做題順序全部過一遍最后再聊聊考場上的時間分配和做題策略給準(zhǔn)備參加大廠實(shí)習(xí)筆試的同學(xué)一個可以參考的路徑。1. 網(wǎng)易2019實(shí)習(xí)生筆試這批題到底在篩選什么樣的人1.1 八道題的考點(diǎn)分布與整體風(fēng)格先看整體結(jié)構(gòu)。這套題在?？途W(wǎng)上一共八道考得非常集中題號題目核心考點(diǎn)難度1牛牛的鬧鐘模擬、時間換算簡單2迷路的牛牛模擬、方向狀態(tài)機(jī)簡單3被3整除數(shù)學(xué)規(guī)律、前綴和思想中等4數(shù)對數(shù)學(xué)推導(dǎo)、取模性質(zhì)中等偏難5安置路燈貪心、區(qū)間覆蓋中等6俄羅斯方塊貪心、思維題中等偏難7牛牛的背包問題折半搜索/DFS剪枝較難8牛牛的數(shù)列動態(tài)規(guī)劃、連續(xù)遞增子序列變體中等偏難你會發(fā)現(xiàn)網(wǎng)易這批題幾乎沒有考復(fù)雜數(shù)據(jù)結(jié)構(gòu)和冷門算法什么線段樹、樹狀數(shù)組、KMP、并查集全部沒有核心就四個字邏輯、數(shù)學(xué)。前兩道題純粹考你會不會把現(xiàn)實(shí)場景抽象成代碼中間幾道題考的是你愿不愿意先動筆推導(dǎo)再動手寫碼最后兩道題稍微上強(qiáng)度但也就是折半搜索和線性DP的范疇屬于認(rèn)真刷過題的同學(xué)都應(yīng)該見過的套路。1.2 為什么這套題值得反復(fù)刷我對這套題的評價是它是一套非常典型的“大廠海選題”。海選階段不是要招天才是要把兩類人篩掉一類是只會背模板、題目稍微換個包裝就認(rèn)不出來的另一類是基礎(chǔ)不扎實(shí)、老是掛在邊界條件上的。這兩類人在這套題里會死得很難看。舉個例子牛牛的鬧鐘那道題很多人一看到時間就想到用字符串處理硬生生把一道水題寫成大模擬最后還因?yàn)榍皩?dǎo)零問題WA了兩次。用整數(shù)分鐘數(shù)換算它不香嗎這就是典型的“認(rèn)不出包裝”。再比如被3整除那道題暴力解法在數(shù)據(jù)小的時候能過但題目把區(qū)間范圍拉到10^9量級就是逼你去找規(guī)律如果一上來就無腦for循環(huán)等超時提示彈出來再回頭看題幾十分鐘就沒了。所以這套題真正的價值在于它用八道題把筆試中最常見的幾類陷阱全部覆蓋了一遍而且每道題都有不止一種做法。刷這套題不是刷完就完事了你得把每道題的“為什么這么做”想透然后再去找同類題鞏固。2. 兩道模擬題鬧鐘和迷路邊界條件才是真正的考點(diǎn)2.1 牛牛的鬧鐘一切時間問題先換算成分鐘題目大意是牛牛定了N個鬧鐘他起床后需要X分鐘才能到教室上課時間是當(dāng)天的A時B分。問他在不遲到的前提下最晚可以定在哪個鬧鐘時間起床。輸入輸出都是“時 分”的格式。我的第一反應(yīng)是所有時間全部換算成“從零點(diǎn)開始的分鐘數(shù)”沒有第二種做法。小時乘以60加分再加上起床后需要的X分鐘得到“這個鬧鐘響時到達(dá)教室的時間”。然后從所有鬧鐘里挑出到達(dá)時間不大于上課時間的最大值把這個鬧鐘的原始時間輸出。import java.util.*; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(); int[] alarm new int[n]; for (int i 0; i n; i) { int h in.nextInt(); int m in.nextInt(); alarm[i] h * 60 m; } int x in.nextInt(); int classTime in.nextInt() * 60 in.nextInt(); int ans 0; for (int i 0; i n; i) { if (alarm[i] x classTime) { ans Math.max(ans, alarm[i]); } } System.out.printf(%d %d\n, ans / 60, ans % 60); } }這個題有沒有坑有。第一個坑是“最晚”這兩個字很多人第一遍讀題只注意到“不能遲到”直接輸出最后一個滿足條件的鬧鐘忘了先排個序。雖然題目樣例里鬧鐘是按時間順序給的但沒有明確說明輸入一定有序穩(wěn)妥起見還是先排序或者像上面代碼一樣直接取最大值。第二個坑是輸出格式前導(dǎo)零的問題在?？蜕弦话闶窃试S的但用printf格式化輸出總是最保險的。第三個坑比較隱蔽就是X可能很大鬧鐘時間加上X之后可能超過24小時不過題目限定是同一天上課所以只要判斷小于等于上課時間就行不用處理跨天。2.2 迷路的牛牛方向狀態(tài)機(jī)怎么寫不出Bug第二道模擬題是牛牛從家出發(fā)先向東走然后轉(zhuǎn)N次方向每次要么左轉(zhuǎn)L要么右轉(zhuǎn)R問最后面向哪邊。這道題比鬧鐘還簡單但錯的人也不少問題基本出在方向數(shù)組的取模上。我習(xí)慣用四個數(shù)字表示朝向0代表東1代表南2代表西3代表北。為什么這么定因?yàn)橛肄D(zhuǎn)是順時針方向?qū)?yīng)數(shù)值加1左轉(zhuǎn)是逆時針對應(yīng)數(shù)值減1。然后統(tǒng)一用加4再取模的方式處理負(fù)數(shù)。import java.util.*; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(); String s in.next(); String[] dir {E, S, W, N}; int cur 0; // 0:E 1:S 2:W 3:N for (char c : s.toCharArray()) { if (c R) cur (cur 1) % 4; else cur (cur 3) % 4; // 等價于減1再取模 } System.out.println(dir[cur]); } }這里有一個很容易被忽略的細(xì)節(jié)cur (cur - 1 4) % 4寫成(cur 3) % 4在普通情況下沒問題但如果你讓別人review你的代碼還是寫成cur (cur - 1 4) % 4更清晰。我在這道題上想提醒的不是取模而是刷題時拿到這種“轉(zhuǎn)方向”的題目第一件事不是在草稿紙上畫坐標(biāo)軸而是先把方向數(shù)組和數(shù)值映射定義好。很多同學(xué)在面試時一緊張就在代碼里直接寫死四個if分支一旦方向多了或者要連續(xù)處理就會漏分支。用狀態(tài)機(jī)的方式寫邏輯全部收斂在一行里反而最不容易出錯。3. 數(shù)學(xué)規(guī)律題被3整除與數(shù)對把枚舉問題變成公式推導(dǎo)3.1 被3整除從數(shù)字和到步長為3的規(guī)律題目描述了一個神奇數(shù)列第1項(xiàng)是1第2項(xiàng)是12第3項(xiàng)是123第4項(xiàng)是1234依此類推。問這個數(shù)列的第l項(xiàng)到第r項(xiàng)里有多少項(xiàng)能被3整除。數(shù)據(jù)范圍很大l和r可以到10^9擺明了不讓你逐項(xiàng)判斷。能整除3的充要條件是各位數(shù)字之和能被3整除。那么第i項(xiàng)的數(shù)字和是多少它是1到i的所有數(shù)字加起來也就是i(i1)/2。這個結(jié)論一出來問題就變成了判斷i(i1)/2是否整除3。注意這里的關(guān)鍵點(diǎn)i和i1是兩個連續(xù)整數(shù)它們相乘一定有一個是偶數(shù)所以i(i1)/2一定是整數(shù)這也是為什么這個數(shù)列的每一項(xiàng)一定都是整數(shù)拼接而成不會有分?jǐn)?shù)的問題。接下來找規(guī)律。我不喜歡憑空記結(jié)論所以當(dāng)時是在草稿紙上老老實(shí)實(shí)列了前幾項(xiàng)i1數(shù)字和1不整除3i2數(shù)字和3整除3i3數(shù)字和6整除3i4數(shù)字和10不整除3i5數(shù)字和15整除3i6數(shù)字和21整除3規(guī)律已經(jīng)很明顯了每三個數(shù)里有兩個能被3整除具體來說i模3余1的時候不行模3余0或2的時候都行。所以1到r這段區(qū)間里不能被整除的數(shù)量就是那些i模3余1的數(shù)數(shù)量是(r 2) / 3能被整除的數(shù)量就是r - (r 2) / 3。區(qū)間變成前綴和做差import java.util.*; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); long l in.nextLong(); long r in.nextLong(); System.out.println(calc(r) - calc(l - 1)); } static long calc(long x) { return x - (x 2) / 3; } }這道題想說的經(jīng)驗(yàn)是凡是遇到“一個數(shù)列從第l項(xiàng)到第r項(xiàng)有多少個滿足某性質(zhì)”這種問題第一反應(yīng)不要是遍歷而是先求出“第i項(xiàng)的通項(xiàng)表達(dá)式”再找“滿足性質(zhì)的條件”最后用前綴和做差O(1)出答案。這才是出題人真正想考的東西。3.2 數(shù)對枚舉y用商和余數(shù)計(jì)算貢獻(xiàn)數(shù)對這道題描述起來很簡單給一個n和一個k問有多少個正整數(shù)數(shù)對(x, y)滿足x和y都不大于n并且x mod y的值不小于k。n和k的范圍很大暴力是O(n^2)必死。我的第一直覺是枚舉y。因?yàn)橐坏┕潭藋x mod y的取值就有周期性可以分類討論。這里先考慮特殊邊界如果k等于0那么任何x mod y都大于等于0答案就是n的平方。這個特判不加后面所有枚舉邏輯都會出問題因?yàn)閗0時y從1開始枚舉單個周期內(nèi)滿足條件的個數(shù)變成了y個會導(dǎo)致答案對不上。當(dāng)k大于0時x mod y k意味著余數(shù)不能為0所以y至少是k1否則x mod y最大是y-1一定小于k可以直接跳過。固定y之后x從1到n每個周期長度是y余數(shù)序列是1,2,...,y-1,0循環(huán)。一個完整周期里滿足余數(shù)不小于k的有y-k個數(shù)余數(shù)k到y(tǒng)-1。n里面完整周期有n/y個貢獻(xiàn)是(n/y)*(y-k)。剩下n%y個數(shù)字對應(yīng)余數(shù)1到n%y貢獻(xiàn)是max(0, n%y - k 1)。import java.util.*; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); long n in.nextLong(); long k in.nextLong(); if (k 0) { System.out.println(n * n); return; } long ans 0; for (long y k 1; y n; y) { long full n / y; long rest n % y; ans full * (y - k); if (rest k) { ans rest - k 1; } } System.out.println(ans); } }這道題最容易踩的坑就是k0。我當(dāng)年刷的時候自認(rèn)為考慮得很全面結(jié)果提交上去WA查了半天才發(fā)現(xiàn)是k0導(dǎo)致公式里的y - k變成了y而后面的rest - k 1也變了整個累加邏輯就錯了。所以遇到這種帶參數(shù)的數(shù)學(xué)題先看看參數(shù)能不能取到邊界值邊界值往往就是出題人埋的雷。4. 貪心題安置路燈與俄羅斯方塊關(guān)鍵在于證明局部最優(yōu)就是全局最優(yōu)4.1 安置路燈每個點(diǎn)亮的坑位都該被右側(cè)路燈覆蓋這道題是典型的區(qū)間覆蓋貪心。一條長度為n的路用字符串表示.表示需要照明X表示障礙物不需要照明。一個路燈能照亮自己所在位置以及左右相鄰各一個位置問最少放多少個路燈。n可以達(dá)到1000暴力搜索是不可能的。貪心策略是從左往右掃描遇到第一個需要照明的點(diǎn)就把路燈放在它右側(cè)相鄰的位置然后跳過三個位置。為什么放右側(cè)而不是放在當(dāng)前點(diǎn)因?yàn)樽髠?cè)已經(jīng)全部被處理過了燈放在當(dāng)前點(diǎn)只能覆蓋當(dāng)前點(diǎn)和右邊第一個點(diǎn)放在右邊第一個點(diǎn)則能覆蓋當(dāng)前點(diǎn)、右邊第一個點(diǎn)、右邊第二個點(diǎn)右邊多賺一個位置的覆蓋。所以從全局來看從左往右處理時“放在當(dāng)前位置的右側(cè)”永遠(yuǎn)不劣于放在當(dāng)前位置這就是貪心選擇性質(zhì)的證明。import java.util.*; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int T in.nextInt(); while (T-- 0) { int n in.nextInt(); String s in.next(); int ans 0; for (int i 0; i n; ) { if (s.charAt(i) .) { ans; i 3; } else { i; } } System.out.println(ans); } } }這個題有個非常經(jīng)典的誤區(qū)有人覺得應(yīng)該優(yōu)先在當(dāng)前點(diǎn)放燈因?yàn)檫@樣當(dāng)前點(diǎn)一定被覆蓋。這種想法錯在忽略了“當(dāng)前點(diǎn)左側(cè)已經(jīng)被覆蓋”這個前提。每次遇到第一個未覆蓋的亮燈點(diǎn)它左邊一定是已經(jīng)處理完的區(qū)域所以放右邊不會留下任何左邊漏網(wǎng)之魚。只要把這句話想明白貪心就站得住腳。另一個容易錯的地方是i 3的位置因?yàn)闊舴旁趇1覆蓋范圍是i、i1、i2所以下一個需要檢查的位置是i3而不是i2很多人在這一步寫錯邊界。4.2 俄羅斯方塊平均分配思維別真的去堆方塊這道題的原題描述是屏幕下方寬度為n列有m個方塊依次從上方落下每個方塊會掉落到當(dāng)前高度最低的那一列如果有多列高度相同選擇最左邊的一列。每落一個方塊該列的分?jǐn)?shù)加1。問最終屏幕上的最高分?jǐn)?shù)是多少。大部分人的第一反應(yīng)是用一個小頂堆模擬每次彈出堆頂也就是當(dāng)前最矮的那一列讓它加1再放回去。這樣復(fù)雜度是O(m log n)m如果到10^9直接爆炸。但是如果你理解了“每次都讓全局最矮的列加1”這個操作就會發(fā)現(xiàn)這其實(shí)就是一個均攤過程n列的高度永遠(yuǎn)只會相差1。最終m個方塊被分配到了n列上最高的列拿到的是ceil(m/n)。import java.util.*; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(); int m in.nextInt(); System.out.println((m n - 1) / n); } }這道題的價值在于它提醒我們寫代碼之前先花30秒想想題目給的模擬過程最終會收斂到什么狀態(tài)。如果每一步操作都是“當(dāng)前全局最小值加1”那么整個過程等價于往n個桶里輪流倒水不管順序如何最終各桶高度差不會超過1。這種題在筆試?yán)飳儆凇翱粗駭?shù)據(jù)結(jié)構(gòu)其實(shí)是腦筋急轉(zhuǎn)彎”的類型。你如果一上來就寫堆數(shù)據(jù)大的時候照樣超時最后還覺得自己算法沒錯其實(shí)是被題目包裝騙了。5. 牛牛的背包問題30件零食的大容量背包折半搜索是正解5.1 為什么普通01背包做不了題目是牛牛背包容量為w家里有n袋零食每袋體積為v[i]問在總體積不超過w的情況下有多少種放法包括什么都不放的那種。乍一看是01背包求方案數(shù)但仔細(xì)看范圍n最大30w最大可以到2^31-1。如果用經(jīng)典的DPdp數(shù)組開不下因?yàn)槿萘刻缶退汩_得下復(fù)雜度也是O(n*w)w都是int上限了完全不可行。這里要有一個條件反射當(dāng)n很小30左右但每個物品的體積或背包容量很大的時候折半搜索比背包DP更合適。因?yàn)閚30意味著總子集數(shù)是2^30大約10億直接枚舉肯定超時。但把30個物品分成兩半每邊15個子集數(shù)就是2^1532768這個規(guī)模完全可以接受。5.2 折半搜索的完整實(shí)現(xiàn)思路第一半枚舉出所有可能的子集和放進(jìn)一個數(shù)組里排好序。第二半每枚舉出一個子集和s2就在第一半的數(shù)組里二分查找有多少個元素小于等于w - s2累加進(jìn)答案。這樣做的正確性在于任意一個合法的全局裝法都可以看作“第一半的某個子集”和“第二半的某個子集”的并集而且兩半是獨(dú)立的總?cè)萘坎怀^w所以第一半的子集和必須小于等于w - s2二分就是在統(tǒng)計(jì)滿足這個條件的數(shù)量。import java.util.*; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(); long w in.nextLong(); long[] v new long[n]; for (int i 0; i n; i) { v[i] in.nextLong(); } int mid n / 2; ListLong left new ArrayList(); ListLong right new ArrayList(); dfs(v, 0, mid, 0L, left); dfs(v, mid, n, 0L, right); Collections.sort(left); long ans 0; for (long s : right) { if (s w) { ans upperBound(left, w - s); } } System.out.println(ans); } static void dfs(long[] v, int idx, int end, long sum, ListLong out) { if (idx end) { out.add(sum); return; } // 不選當(dāng)前零食 dfs(v, idx 1, end, sum, out); // 選當(dāng)前零食 if (sum v[idx] Long.MAX_VALUE) { dfs(v, idx 1, end, sum v[idx], out); } } static int upperBound(ListLong list, long target) { int l 0, r list.size(); while (l r) { int mid (l r) 1; if (list.get(mid) target) { l mid 1; } else { r mid; } } return l; } }這里有兩個細(xì)節(jié)。第一所有變量包括dfs里的sum都要用long因?yàn)閣最大是2^31-1兩個子集和加起來很可能超過int范圍。第二遞歸邊界條件里我故意寫了一個sum v[idx] Long.MAX_VALUE的判斷其實(shí)當(dāng)n只有30、體積是int范圍時不會溢出但這個習(xí)慣建議保留因?yàn)檎郯胨阉饕坏U(kuò)展到更多物品溢出是真實(shí)存在的風(fēng)險。5.3 這題的擴(kuò)展與考場取舍如果面試官把n改成40折半搜索還能不能做可以。40個物品分成兩半就是2^20大約100萬排序和二分依然在可接受范圍內(nèi)。如果再大到50那就得考慮用“按體積排序后DFS剪枝”的做法或者用雙向搜索配合雙指針優(yōu)化。這就引出一個很重要的應(yīng)試經(jīng)驗(yàn)看到n是30、40這種“暴力會超但又不完全超”的規(guī)模優(yōu)先想折半搜索看到n是1000以上才考慮優(yōu)化的DP或貪心。這個判斷不需要很精確但能幫你快速鎖定正確的算法方向。6. 牛牛的數(shù)列最長連續(xù)遞增子序列的“改一個數(shù)”變體6.1 預(yù)處理左遞增和右遞增題目要求在一個數(shù)列中找一個最長的連續(xù)子序列要求這個子序列最多改變一個數(shù)之后能變成嚴(yán)格遞增的。變化一下就是你可以最多修改原序列中的一個值然后找最長的嚴(yán)格遞增連續(xù)子串。注意這里是“連續(xù)子序列”不是可以跳著選的那種所以不能直接套LIS應(yīng)該往連續(xù)子串的方向想。經(jīng)典做法是預(yù)處理兩個數(shù)組left[i]表示以位置i結(jié)尾的最長嚴(yán)格遞增連續(xù)段的長度right[i]表示以位置i開頭的最長嚴(yán)格遞增連續(xù)段的長度。這兩個數(shù)組都可以在O(n)內(nèi)遞推出來left[i]在a[i]大于a[i-1]時等于left[i-1]加1否則等于1right[i]在a[i]小于a[i1]時等于right[i1]加1否則等于1。6.2 枚舉被修改的位置預(yù)處理完之后枚舉每一個可能被修改的位置i。修改a[i]的目的是讓它同時銜接上左邊的遞增段和右邊的遞增段。如果a[i-1] a[i1] - 1說明我一定能構(gòu)造出一個新的值放在a[i]的位置使得左邊以a[i-1]結(jié)尾的段、a[i]自己、右邊以a[i1]開頭的段能合并成一段長度就是left[i-1] 1 right[i1]。如果a[i-1]和a[i1]之間沒有整數(shù)空間比如a[i-1]3、a[i1]3那么改a[i]不可能同時接上兩邊只能選擇保留左邊段加上自己或者保留自己加上右邊段取兩者較大的那個。還有一種情況i是端點(diǎn)比如i0那么直接改a[0]就能接上右側(cè)段長度就是right[1] 1如果n1的話所有情況都枚舉完再和“一個數(shù)都不改”的最長段長度比較取最大值。import java.util.*; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] in.nextInt(); } if (n 2) { System.out.println(n); return; } int[] left new int[n]; int[] right new int[n]; left[0] 1; for (int i 1; i n; i) { left[i] (a[i] a[i - 1]) ? left[i - 1] 1 : 1; } right[n - 1] 1; for (int i n - 2; i 0; i--) { right[i] (a[i] a[i 1]) ? right[i 1] 1 : 1; } int ans 1; for (int i 0; i n; i) { ans Math.max(ans, left[i]); if (i 0) ans Math.max(ans, left[i - 1] 1); if (i n - 1) ans Math.max(ans, right[i 1] 1); if (i 0 i n - 1 a[i - 1] a[i 1] - 1) { ans Math.max(ans, left[i - 1] 1 right[i 1]); } } System.out.println(ans); } }這個題有個容易踩的細(xì)節(jié)判斷條件是a[i - 1] a[i 1] - 1注意這里必須有嚴(yán)格小于而且差至少是2因?yàn)橐舫稣麛?shù)位置給修改后的a[i]。很多人寫成了a[i - 1] a[i 1]看著差不多實(shí)際上a[i-1]3、a[i1]4的時候中間沒有整數(shù)可以放合并就是錯誤的。還有一個問題是數(shù)組長度小于等于2時直接返回n否則后面訪問i1或i-1會越界。這種邊界在筆試?yán)锾貏e坑明明算法對了因?yàn)橐粋€越界RE整道題白做。7. 考場實(shí)戰(zhàn)經(jīng)驗(yàn)我這套題刷下來的踩坑清單7.1 做題順序建議網(wǎng)易這批題的難度并不是嚴(yán)格遞增的所以我個人的做題順序建議是先把兩道模擬題鬧鐘、迷路秒掉它們是最穩(wěn)的送分題10分鐘之內(nèi)搞定能迅速建立信心。再做被3整除和安置路燈這兩道題代碼量小但需要一點(diǎn)數(shù)學(xué)或貪心思考屬于“稍微想一想就能AC”的題。然后是數(shù)對和俄羅斯方塊這兩道題考的是思維拐彎不要一上來就暴力先想想有沒有數(shù)學(xué)結(jié)論。最后留時間給牛牛的背包和牛牛的數(shù)列這兩道題如果思路卡住先跳過去做別的回頭再戰(zhàn)。這個順序的核心邏輯是筆試時間有限先把確定能拿的分拿滿再啃硬骨頭。千萬別在第一道模擬題上反復(fù)優(yōu)化輸出格式或者在一道貪心題上死磕證明導(dǎo)致后面更值錢的題沒時間讀。7.2 輸入輸出上的常見坑?？途W(wǎng)的筆試環(huán)境對代碼格式要求很嚴(yán)格類名必須是Main不能有package聲明不需要讀入文件所有的輸入都從System.in讀。很多第一次在?？蜕献鲱}的同學(xué)會在這些地方栽跟頭。另外多組測試數(shù)據(jù)的題比如安置路燈要用while循環(huán)處理T組數(shù)據(jù)處理完一組輸出一組不要想當(dāng)然地只處理一組。還有一個很實(shí)際的經(jīng)驗(yàn)對于Java選手能用BufferedReader就用BufferedReaderScanner在數(shù)據(jù)量大的時候會慢不少但在這套題的規(guī)模下Scanner完全夠用。真正要關(guān)注的是輸出的效率如果用System.out.println高頻輸出有概率觸發(fā)超時可以換成StringBuilder拼接后統(tǒng)一輸出。7.3 這套題暴露出的通用能力短板刷完這八道題我最大的感受是大廠筆試考的不是你會多少算法而是你在有限時間內(nèi)能不能快速識別出題人的真實(shí)意圖。牛牛的鬧鐘包裝成一個鬧鐘場景本質(zhì)是時間換算和最大值篩選俄羅斯方塊看起來要模擬游戲本質(zhì)是均攤思維牛牛的背包問題披著01背包的外衣實(shí)際上是搜索。這種“脫包裝”的能力需要靠大量刷題和對經(jīng)典模型的熟悉程度來積累。如果你現(xiàn)在準(zhǔn)備的是2025年的暑期實(shí)習(xí)我建議可以把這套題和2018、2020年的網(wǎng)易真題對照著看。你會發(fā)現(xiàn)命題風(fēng)格有一定連貫性模擬題和數(shù)學(xué)題是常年保留項(xiàng)目貪心和DP是拉開差距的關(guān)鍵。把這套題吃透再去刷其他大廠的真題你會明顯感覺到自己的“脫包裝”速度快了不少。