360的校招筆試向來以“題量大、時間緊、考基礎(chǔ)”著稱2019年那批編程題合集我翻來覆去刷了好幾遍發(fā)現(xiàn)它跟騰訊、阿里那些偏重工程場景的題目風格差異很大更看重你對數(shù)據(jù)結(jié)構(gòu)和基礎(chǔ)算法的熟練度。這篇文章不打算把題目簡單羅列一遍而是從題型分類、解題思路、邊界條件幾個角度拆解這套題適合正在準備校招、尤其是目標安全廠商技術(shù)崗的同學參考。哪怕你投的不是360這套題集的訓練價值也相當高因為它的出題風格非常經(jīng)典。1. 360校招筆試先搞清這場考試在考什么1.1 筆試題型分布與時間策略2019年360校招的技術(shù)崗筆試整體結(jié)構(gòu)是客觀題加編程題兩部分。客觀題涵蓋計算機基礎(chǔ)、網(wǎng)絡(luò)、操作系統(tǒng)、安全基礎(chǔ)等編程題通常是兩道到三道要求在一個小時內(nèi)完成。關(guān)鍵是客觀題和編程題是同一份卷子不是分開計時的所以很多人在客觀題上多花了十分鐘最后編程題時間就吃緊了。這一點特別提醒大家注意。我自己見過太多同學在客觀題上糾結(jié)一道不確定的Linux命令題結(jié)果編程題只寫了半道。合理的策略是把客觀題單題時間控制在1分鐘以內(nèi)不會的直接標記跳過把完整的大塊時間留給編程題。因為客觀題分值再大一道也就一兩分編程題出一道就是二三十分性價比完全不在一個量級。從題目難度上看2019年的編程題沒有特別偏難怪的題基本都是leetcode中等偏下的水平但有個特點題干很長里面會混入大量跟解題無關(guān)的業(yè)務(wù)背景描述。這就非?？简瀼拈L文本里提取關(guān)鍵信息的能力稍不注意就被帶偏了。1.2 為什么安全廠商的程序題更“偏基礎(chǔ)”360是一家安全公司這個屬性會直接反映在筆試題的側(cè)重點上。安全方向的工程師日常要處理大量底層數(shù)據(jù)、協(xié)議解析、日志分析、加密算法相關(guān)的開發(fā)工作所以筆試不會像純業(yè)務(wù)互聯(lián)網(wǎng)公司那樣出大而全的后端業(yè)務(wù)設(shè)計題反而更看重你對內(nèi)存布局、字符串處理、邊界條件的敏感度。這一點跟很多同學的理解不一樣。有人覺得安全公司筆試會不會考什么漏洞利用、逆向分析其實校招筆試幾乎不會考這些因為大多數(shù)應(yīng)屆生沒做過真實的安全項目。筆試考察的還是通用編程能力但會在題目背景里嵌一點安全場景比如日志分析、字符串過濾、協(xié)議解析這種殼子內(nèi)核還是算法和數(shù)據(jù)結(jié)構(gòu)。所以準備360這類安全廠商的筆試核心策略很清晰不要花太多時間刷冷門算法把高頻的數(shù)據(jù)結(jié)構(gòu)操作練到條件反射比什么都強。2. 字符串與進制轉(zhuǎn)換筆試里最容易被低估的送分題2.1 十六進制轉(zhuǎn)十進制邊界條件大坑2019年這套題里有一類題看起來很基礎(chǔ)但通過率反而不高就是進制轉(zhuǎn)換。比如給你一串十六進制字符串要求轉(zhuǎn)成十進制輸出看似直接調(diào)int(s, 16)就完事了但題目如果換了個說法比如字符串可能包含前導零、可能超過整型范圍、可能是負數(shù)情況就完全不一樣了。這類題在筆試里出現(xiàn)的意義就是考察你寫代碼的時候考慮邊界條件的能力。我印象里有一道題輸入是一串十六進制字符串輸出要求是十進制但是字符串是反著給的也就是從低位到高位排列。很多人讀題太快直接當成正常字符串處理然后輸出就反了。我當時用的思路是先把字符串倒過來再逐位處理代碼如下def hex_reversed_to_dec(s): s s[::-1] result 0 power 0 hex_chars 0123456789abcdef for ch in s: val hex_chars.index(ch.lower()) result val * (16 ** power) power 1 return result這段代碼本身很簡單但它體現(xiàn)了兩個關(guān)鍵習慣第一讀題后先在草稿紙上寫一兩個用例驗證理解是否準確第二進制轉(zhuǎn)換手寫一遍而不是直接調(diào)庫函數(shù)能有效避免題目里暗藏的翻轉(zhuǎn)、負數(shù)、溢出等變體。2.2 字符串反轉(zhuǎn)與括號匹配的隱藏考點字符串處理類題目在2019年筆試中出現(xiàn)頻率很高除了進制轉(zhuǎn)換還有括號匹配、字符串去重、反轉(zhuǎn)單詞等經(jīng)典問題。括號匹配這道題幾乎年年都有今年是合法括號序列判斷明年可能就變成了最長有效括號長度換湯不換藥核心就是棧。用棧做括號匹配的經(jīng)典寫法def is_valid_brackets(s): stack [] mapping {): (, ]: [, }: {} for ch in s: if ch in mapping.values(): stack.append(ch) elif ch in mapping.keys(): if not stack or stack.pop() ! mapping[ch]: return False else: continue return not stack這個寫法本身沒什么難度但筆試里有個常見陷阱字符串里會混入空格和其他字符。如果審題不仔細沒有跳過非括號字符就會誤判。這一點很多經(jīng)驗貼里沒提過是我自己踩坑踩出來的。關(guān)于字符串反轉(zhuǎn)2019年的題目里有一個變體不是把所有字符反轉(zhuǎn)而是只反轉(zhuǎn)字母數(shù)字的位置保持不變。這就不能直接[::-1]]了需要用雙指針來做def reverse_only_letters(s): s list(s) left, right 0, len(s) - 1 while left right: if not s[left].isalpha(): left 1 elif not s[right].isalpha(): right - 1 else: s[left], s[right] s[right], s[left] left 1 right - 1 return .join(s)對這種題我建議大家在準備階段把常見的字符串操作都手寫一遍包括反轉(zhuǎn)、判斷回文、統(tǒng)計詞頻、分割單詞、去除重復(fù)字符。因為筆試平臺有時候不讓你用高級庫函數(shù)或者題目本身就在這些基礎(chǔ)操作上套了一層殼。3. 動態(tài)規(guī)劃與狀態(tài)設(shè)計2019年筆試的高頻主戰(zhàn)場3.1 從爬樓梯到區(qū)間DP的層層遞進動態(tài)規(guī)劃幾乎是所有大廠校招筆試的必考內(nèi)容360也不例外。2019年這套題里有兩道動態(tài)規(guī)劃相關(guān)的題一道非常直白就是爬樓梯的變體另一道則繞了很多彎子需要你先建立模型才能看出這是動態(tài)規(guī)劃。爬樓梯變體的題目通常長這樣每次可以走1步或2步但是不能連續(xù)走2步。這就是經(jīng)典的“不能連續(xù)兩次選擇同一個動作”的限制條件。這時候普通的一維DP就不夠了需要二維狀態(tài)來記錄上一步走的是幾步def climb_stairs_modified(n): # dp[i][0] 最后一步走1步到達第i級 # dp[i][1] 最后一步走2步到達第i級 dp [[0, 0] for _ in range(n 1)] dp[1][0] 1 if n 2: dp[2][0] 1 dp[2][1] 1 for i in range(3, n 1): dp[i][0] dp[i-1][0] dp[i-1][1] dp[i][1] dp[i-2][0] return dp[n][0] dp[n][1]這里的關(guān)鍵在于因為不能連續(xù)走兩步所以“走兩步到達第i級”只能由上一步是走一步的狀態(tài)轉(zhuǎn)移過來。加一個維度問題就解開了。這就是動態(tài)規(guī)劃的典型思維方式不要急著寫代碼先想清楚有哪些狀態(tài)狀態(tài)之間怎么轉(zhuǎn)移。3.2 最長遞增子序列的兩種寫法與取舍另一道動態(tài)規(guī)劃題是求最長遞增子序列的長度。這道題有兩種主流解法一種是O(n2)的DP一種是O(nlogn)的貪心加二分。筆試的時候?qū)慜(n2)就夠了因為數(shù)據(jù)范圍通常不大但如果你想在面試環(huán)節(jié)展示一下O(nlogn)的寫法也值得掌握。O(n2)寫法非常直觀def length_of_lis(nums): if not nums: return 0 dp [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)O(nlogn)的寫法用了一個輔助數(shù)組維護當前遞增子序列的末尾元素的最小值import bisect def length_of_lis_fast(nums): tails [] for x in nums: i bisect.bisect_left(tails, x) if i len(tails): tails.append(x) else: tails[i] x return len(tails)很多同學不理解為什么這個算法的tails數(shù)組里存的不是真正的遞增子序列長度卻是對的。簡單解釋一下tails[i]表示長度為i1的所有遞增子序列里末尾數(shù)字最小的那個。每遍歷一個數(shù)就在tails里找第一個大于等于它的位置替換掉。這個過程保證了tails一直是遞增的所以可以用二分。筆試時我更推薦先寫O(n2)版本因為思路簡單不容易出錯。如果你對O(nlogn)的寫法不夠熟在緊張狀態(tài)下很容易寫錯二分邊界。拿到基礎(chǔ)分比追求最優(yōu)解但寫bug強得多。4. 數(shù)據(jù)結(jié)構(gòu)和貪心短時間拿到高分的性價比之王4.1 棧與隊列的結(jié)合題用兩個棧實現(xiàn)隊列2019年這套題里有道很經(jīng)典的數(shù)據(jù)結(jié)構(gòu)題用兩個棧實現(xiàn)隊列。這道題在劍指offer里出現(xiàn)過很多同學以為考爛了但筆試里再次出現(xiàn)時還是有一批人寫不出來。為什么因為“會看題解”和“能靠自己寫出來”是兩回事。原理其實很樸素一個棧負責入隊一個棧負責出隊。入隊時直接壓入入隊棧出隊時如果出隊棧為空就把入隊棧的所有元素彈出來壓進出隊棧然后再彈出。數(shù)據(jù)來回倒了兩次先進去的元素就從棧底變成了棧頂實現(xiàn)了FIFO的效果。class MyQueue: def __init__(self): self.stack_in [] self.stack_out [] def push(self, x): self.stack_in.append(x) def pop(self): if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out.pop() def peek(self): if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out[-1] def empty(self): return not self.stack_in and not self.stack_out這道題的關(guān)鍵不在實現(xiàn)而在分析復(fù)雜度。每次pop操作最壞情況是O(n)但攤還下來每個元素最多被倒騰兩次所以均攤是O(1)。能把這一點在答案里寫出來會跟其他候選人拉開差距。4.2 區(qū)間調(diào)度問題的貪心證明與模板貪心算法在這套題里也有出現(xiàn)。最常見的一道是區(qū)間調(diào)度給一堆區(qū)間的開始和結(jié)束時間選出盡可能多的互不重疊的區(qū)間。解法是貪心先把所有區(qū)間按結(jié)束時間排序然后遍歷只要當前區(qū)間的開始時間不早于上一個選中區(qū)間的結(jié)束時間就選中它。為什么按結(jié)束時間排序是對的因為結(jié)束時間越早剩下的空間就越多越容易選出更多的區(qū)間。證明方法叫“交換論證法”假設(shè)最優(yōu)解里第一個區(qū)間不是結(jié)束時間最早的區(qū)間我們可以把它換成結(jié)束時間最早的區(qū)間不會讓解變差因為最小區(qū)間的結(jié)束時間更早留給后續(xù)區(qū)間的空間只會更大。這個證明思路在面試里經(jīng)常被追問建議每個人都學會。def max_non_overlapping_intervals(intervals): intervals.sort(keylambda x: x[1]) count 0 last_end float(-inf) for start, end in intervals: if start last_end: count 1 last_end end return count區(qū)間調(diào)度這類題熟手一分鐘能寫完但要答得好需要在代碼之外說出貪心策略的正確性理由。這是我反復(fù)強調(diào)的點筆試做題不光要AC還要在注釋或者旁邊的思路描述里留下你的分析痕跡。有些筆試平臺會人工審代碼你的注釋就是你表達思考過程的窗口。5. 一道綜合題的完整解題推導從讀題到AC的每一步5.1 審題把題目里的話翻譯成代碼邏輯2019年這套題里有一道綜合題很能代表360的出題風格。題目大意是一個日志系統(tǒng)記錄的每條日志有編號和優(yōu)先級系統(tǒng)會定期清理優(yōu)先級最低的日志如果優(yōu)先級相同就清理編號最小的。現(xiàn)在給出一系列操作要求輸出每次清理的日志編號。這道題表面上看是個模擬題但你真按模擬來寫每次都找最小優(yōu)先級數(shù)據(jù)量一大就超時。正確的思路是用優(yōu)先隊列最小堆來維護日志每次清理就彈出堆頂。相比每次遍歷O(n)堆操作的復(fù)雜度是O(logn)整體性能完全不同。讀題的時候第一件事不是想用什么算法而是把“日志”、“優(yōu)先級”這些業(yè)務(wù)概念映射到數(shù)據(jù)結(jié)構(gòu)上。在這道題里“編號”和“優(yōu)先級”就是元組的兩個元素“清理優(yōu)先級最低的”就是求最小值“如果相同則清理編號最小的”就是定義比較規(guī)則。這么一翻譯題目就從一段業(yè)務(wù)描述變成了一道標準題維護一個帶自定義比較規(guī)則的最小堆。5.2 暴力解法為什么一定能過一部分樣例筆試平臺通常是按通過的測試用例比例給分的。一道題過了部分用例也能拿到部分分數(shù)。所以哪怕是幾分鐘后才想到最優(yōu)解也應(yīng)該先把暴力解法寫上去拿基礎(chǔ)分。這是校招筆試里的一個重要生存技巧。比如日志清理這道題最暴力的做法就是每次清理時遍歷所有日志找到優(yōu)先級最低的標記為已刪除直到刪夠數(shù)量。時間復(fù)雜度O(n2)如果數(shù)據(jù)量只有幾百完全能過如果數(shù)據(jù)量是十萬甚至百萬就會超時但你還是拿到了前面的用例分。logs [] # (priority, id) cleaned set() def simulate_brute(ops): for op in ops: if op[0] add: logs.append((op[2], op[1])) # (priority, id) else: # clean min_priority float(inf) min_id float(inf) for i, (p, idx) in enumerate(logs): if i in cleaned: continue if p min_priority or (p min_priority and idx min_id): min_priority p min_id idx target i cleaned.add(target) print(min_id)暴力解法能幫你快速理解題目規(guī)則也保證了你不會因為卡在優(yōu)化上整道題拿零分。寫完暴力解法之后再回頭分析復(fù)雜度看哪里可以優(yōu)化這是比較穩(wěn)妥的做題節(jié)奏。5.3 優(yōu)化思路和代碼實現(xiàn)從暴力解到堆優(yōu)化關(guān)鍵在于識別出“每次找最小值”這個操作是性能瓶頸。如果你在草稿紙上列一下這個操作需要做什么會發(fā)現(xiàn)它本質(zhì)上就是“從集合中重復(fù)取最小元素”這就是優(yōu)先隊列的經(jīng)典使用場景。用Python的heapq實現(xiàn)import heapq def simulate_fast(ops): heap [] removed set() next_id 1 for op in ops: if op[0] add: priority op[2] heapq.heappush(heap, (priority, next_id)) next_id 1 else: # clean while heap: p, idx heapq.heappop(heap) if idx not in removed: removed.add(idx) print(idx) break這個優(yōu)化版本的時間復(fù)雜度降到O(nlogn)肯定能通過全部測試用例。這里有個易錯的細節(jié)heapq在比較元組時會先比較第一個元素如果第一個元素相同就自動比較第二個元素。這正好滿足題目“優(yōu)先級相同時清理編號最小”的要求不需要額外寫比較函數(shù)。但如果題目要求“優(yōu)先級相同時清理編號最大”就得在入堆時把id取負數(shù)或者自定義比較類了。5.4 優(yōu)化思路的通用遷移這類“暴力寫法堆優(yōu)化”的組合幾乎在所有大廠筆試題里都能用上。比如求Top K大元素、合并K個有序數(shù)組、任務(wù)調(diào)度等直接把“找最值”的操作交給自己實現(xiàn)的堆或者語言自帶的優(yōu)先隊列大概率是對的。做完這道題之后我給自己定了一個規(guī)則凡是看到“每次取當前集合中的最大/最小元素”的題型一律先往堆的方向想。這個條件反射在之后的騰訊、百度筆試里幫我省下大量時間。6. 筆試后的復(fù)盤這些事比多刷十道題更管用6.1 錯題整理的核心方法筆試結(jié)束不代表這件事就結(jié)束了。我見過太多人考完試對一下答案然后就丟在一邊下次遇到同類題照樣錯。真正有效的做法是把錯題整理成“考點卡片”每張卡片包含四塊錯誤原因、涉及考點、正確思路、同類變體。比如我當年整理的一道題錯誤原因是題目要求“十進制輸出”但數(shù)據(jù)超出32位整型范圍我當時用了int就以為沒問題結(jié)果在C里溢出。這屬于邊界條件意識不足。整理成卡片之后我會在每次筆試前快速翻一遍這些卡片提醒自己容易在什么地方翻車。錯題整理這件事價值不在于寫了多少張卡片而在于你每次復(fù)盤的時候把自己“重新做一遍題”的思考過程寫下來。這個思考過程才是真正的收獲。6.2 從筆試題看360技術(shù)崗的關(guān)注點整套題刷下來你能明顯感覺到360技術(shù)崗的幾個關(guān)注點基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的熟練度、邊界條件的處理能力、長文本的信息提取能力。它不會考你某個冷門的算法模板但會把非?；A(chǔ)的考點藏在很有迷惑性的題干里。這就給備考方向指了條明路與其花大量時間去啃競賽級別的算法不如把劍指offer和LeetCode熱門100題刷熟。每一道題都問自己三個問題如果數(shù)據(jù)量擴大十倍我的代碼還能跑嗎如果輸入是空值、邊界值、超大值會怎么樣如果我不用庫函數(shù)能不能手寫這個功能把這三個問題想清楚應(yīng)付這類筆試就很有底氣了。我當初刷這套題的時候最大的感受是它不像傳說中那么難但非?？简灮竟ΑＤ阋悄馨炎址?、棧、堆、動態(tài)規(guī)劃這些常規(guī)考點練到“肌肉記憶”的程度這套題對你來說就是送分題合集。反過來你要是刷題只刷難題基礎(chǔ)題反而容易翻車。所以準備360的筆試沉住氣打好基礎(chǔ)比什么技巧都重要。 360校招筆試編程題解析：題型分類、解題思路與邊界條件
360的校招筆試向來以“題量大、時間緊、考基礎(chǔ)”著稱2019年那批編程題合集我翻來覆去刷了好幾遍發(fā)現(xiàn)它跟騰訊、阿里那些偏重工程場景的題目風格差異很大更看重你對數(shù)據(jù)結(jié)構(gòu)和基礎(chǔ)算法的熟練度。這篇文章不打算把題目簡單羅列一遍而是從題型分類、解題思路、邊界條件幾個角度拆解這套題適合正在準備校招、尤其是目標安全廠商技術(shù)崗的同學參考。哪怕你投的不是360這套題集的訓練價值也相當高因為它的出題風格非常經(jīng)典。1. 360校招筆試先搞清這場考試在考什么1.1 筆試題型分布與時間策略2019年360校招的技術(shù)崗筆試整體結(jié)構(gòu)是客觀題加編程題兩部分。客觀題涵蓋計算機基礎(chǔ)、網(wǎng)絡(luò)、操作系統(tǒng)、安全基礎(chǔ)等編程題通常是兩道到三道要求在一個小時內(nèi)完成。關(guān)鍵是客觀題和編程題是同一份卷子不是分開計時的所以很多人在客觀題上多花了十分鐘最后編程題時間就吃緊了。這一點特別提醒大家注意。我自己見過太多同學在客觀題上糾結(jié)一道不確定的Linux命令題結(jié)果編程題只寫了半道。合理的策略是把客觀題單題時間控制在1分鐘以內(nèi)不會的直接標記跳過把完整的大塊時間留給編程題。因為客觀題分值再大一道也就一兩分編程題出一道就是二三十分性價比完全不在一個量級。從題目難度上看2019年的編程題沒有特別偏難怪的題基本都是leetcode中等偏下的水平但有個特點題干很長里面會混入大量跟解題無關(guān)的業(yè)務(wù)背景描述。這就非?？简瀼拈L文本里提取關(guān)鍵信息的能力稍不注意就被帶偏了。1.2 為什么安全廠商的程序題更“偏基礎(chǔ)”360是一家安全公司這個屬性會直接反映在筆試題的側(cè)重點上。安全方向的工程師日常要處理大量底層數(shù)據(jù)、協(xié)議解析、日志分析、加密算法相關(guān)的開發(fā)工作所以筆試不會像純業(yè)務(wù)互聯(lián)網(wǎng)公司那樣出大而全的后端業(yè)務(wù)設(shè)計題反而更看重你對內(nèi)存布局、字符串處理、邊界條件的敏感度。這一點跟很多同學的理解不一樣。有人覺得安全公司筆試會不會考什么漏洞利用、逆向分析其實校招筆試幾乎不會考這些因為大多數(shù)應(yīng)屆生沒做過真實的安全項目。筆試考察的還是通用編程能力但會在題目背景里嵌一點安全場景比如日志分析、字符串過濾、協(xié)議解析這種殼子內(nèi)核還是算法和數(shù)據(jù)結(jié)構(gòu)。所以準備360這類安全廠商的筆試核心策略很清晰不要花太多時間刷冷門算法把高頻的數(shù)據(jù)結(jié)構(gòu)操作練到條件反射比什么都強。2. 字符串與進制轉(zhuǎn)換筆試里最容易被低估的送分題2.1 十六進制轉(zhuǎn)十進制邊界條件大坑2019年這套題里有一類題看起來很基礎(chǔ)但通過率反而不高就是進制轉(zhuǎn)換。比如給你一串十六進制字符串要求轉(zhuǎn)成十進制輸出看似直接調(diào)int(s, 16)就完事了但題目如果換了個說法比如字符串可能包含前導零、可能超過整型范圍、可能是負數(shù)情況就完全不一樣了。這類題在筆試里出現(xiàn)的意義就是考察你寫代碼的時候考慮邊界條件的能力。我印象里有一道題輸入是一串十六進制字符串輸出要求是十進制但是字符串是反著給的也就是從低位到高位排列。很多人讀題太快直接當成正常字符串處理然后輸出就反了。我當時用的思路是先把字符串倒過來再逐位處理代碼如下def hex_reversed_to_dec(s): s s[::-1] result 0 power 0 hex_chars 0123456789abcdef for ch in s: val hex_chars.index(ch.lower()) result val * (16 ** power) power 1 return result這段代碼本身很簡單但它體現(xiàn)了兩個關(guān)鍵習慣第一讀題后先在草稿紙上寫一兩個用例驗證理解是否準確第二進制轉(zhuǎn)換手寫一遍而不是直接調(diào)庫函數(shù)能有效避免題目里暗藏的翻轉(zhuǎn)、負數(shù)、溢出等變體。2.2 字符串反轉(zhuǎn)與括號匹配的隱藏考點字符串處理類題目在2019年筆試中出現(xiàn)頻率很高除了進制轉(zhuǎn)換還有括號匹配、字符串去重、反轉(zhuǎn)單詞等經(jīng)典問題。括號匹配這道題幾乎年年都有今年是合法括號序列判斷明年可能就變成了最長有效括號長度換湯不換藥核心就是棧。用棧做括號匹配的經(jīng)典寫法def is_valid_brackets(s): stack [] mapping {): (, ]: [, }: {} for ch in s: if ch in mapping.values(): stack.append(ch) elif ch in mapping.keys(): if not stack or stack.pop() ! mapping[ch]: return False else: continue return not stack這個寫法本身沒什么難度但筆試里有個常見陷阱字符串里會混入空格和其他字符。如果審題不仔細沒有跳過非括號字符就會誤判。這一點很多經(jīng)驗貼里沒提過是我自己踩坑踩出來的。關(guān)于字符串反轉(zhuǎn)2019年的題目里有一個變體不是把所有字符反轉(zhuǎn)而是只反轉(zhuǎn)字母數(shù)字的位置保持不變。這就不能直接[::-1]]了需要用雙指針來做def reverse_only_letters(s): s list(s) left, right 0, len(s) - 1 while left right: if not s[left].isalpha(): left 1 elif not s[right].isalpha(): right - 1 else: s[left], s[right] s[right], s[left] left 1 right - 1 return .join(s)對這種題我建議大家在準備階段把常見的字符串操作都手寫一遍包括反轉(zhuǎn)、判斷回文、統(tǒng)計詞頻、分割單詞、去除重復(fù)字符。因為筆試平臺有時候不讓你用高級庫函數(shù)或者題目本身就在這些基礎(chǔ)操作上套了一層殼。3. 動態(tài)規(guī)劃與狀態(tài)設(shè)計2019年筆試的高頻主戰(zhàn)場3.1 從爬樓梯到區(qū)間DP的層層遞進動態(tài)規(guī)劃幾乎是所有大廠校招筆試的必考內(nèi)容360也不例外。2019年這套題里有兩道動態(tài)規(guī)劃相關(guān)的題一道非常直白就是爬樓梯的變體另一道則繞了很多彎子需要你先建立模型才能看出這是動態(tài)規(guī)劃。爬樓梯變體的題目通常長這樣每次可以走1步或2步但是不能連續(xù)走2步。這就是經(jīng)典的“不能連續(xù)兩次選擇同一個動作”的限制條件。這時候普通的一維DP就不夠了需要二維狀態(tài)來記錄上一步走的是幾步def climb_stairs_modified(n): # dp[i][0] 最后一步走1步到達第i級 # dp[i][1] 最后一步走2步到達第i級 dp [[0, 0] for _ in range(n 1)] dp[1][0] 1 if n 2: dp[2][0] 1 dp[2][1] 1 for i in range(3, n 1): dp[i][0] dp[i-1][0] dp[i-1][1] dp[i][1] dp[i-2][0] return dp[n][0] dp[n][1]這里的關(guān)鍵在于因為不能連續(xù)走兩步所以“走兩步到達第i級”只能由上一步是走一步的狀態(tài)轉(zhuǎn)移過來。加一個維度問題就解開了。這就是動態(tài)規(guī)劃的典型思維方式不要急著寫代碼先想清楚有哪些狀態(tài)狀態(tài)之間怎么轉(zhuǎn)移。3.2 最長遞增子序列的兩種寫法與取舍另一道動態(tài)規(guī)劃題是求最長遞增子序列的長度。這道題有兩種主流解法一種是O(n2)的DP一種是O(nlogn)的貪心加二分。筆試的時候?qū)慜(n2)就夠了因為數(shù)據(jù)范圍通常不大但如果你想在面試環(huán)節(jié)展示一下O(nlogn)的寫法也值得掌握。O(n2)寫法非常直觀def length_of_lis(nums): if not nums: return 0 dp [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)O(nlogn)的寫法用了一個輔助數(shù)組維護當前遞增子序列的末尾元素的最小值import bisect def length_of_lis_fast(nums): tails [] for x in nums: i bisect.bisect_left(tails, x) if i len(tails): tails.append(x) else: tails[i] x return len(tails)很多同學不理解為什么這個算法的tails數(shù)組里存的不是真正的遞增子序列長度卻是對的。簡單解釋一下tails[i]表示長度為i1的所有遞增子序列里末尾數(shù)字最小的那個。每遍歷一個數(shù)就在tails里找第一個大于等于它的位置替換掉。這個過程保證了tails一直是遞增的所以可以用二分。筆試時我更推薦先寫O(n2)版本因為思路簡單不容易出錯。如果你對O(nlogn)的寫法不夠熟在緊張狀態(tài)下很容易寫錯二分邊界。拿到基礎(chǔ)分比追求最優(yōu)解但寫bug強得多。4. 數(shù)據(jù)結(jié)構(gòu)和貪心短時間拿到高分的性價比之王4.1 棧與隊列的結(jié)合題用兩個棧實現(xiàn)隊列2019年這套題里有道很經(jīng)典的數(shù)據(jù)結(jié)構(gòu)題用兩個棧實現(xiàn)隊列。這道題在劍指offer里出現(xiàn)過很多同學以為考爛了但筆試里再次出現(xiàn)時還是有一批人寫不出來。為什么因為“會看題解”和“能靠自己寫出來”是兩回事。原理其實很樸素一個棧負責入隊一個棧負責出隊。入隊時直接壓入入隊棧出隊時如果出隊棧為空就把入隊棧的所有元素彈出來壓進出隊棧然后再彈出。數(shù)據(jù)來回倒了兩次先進去的元素就從棧底變成了棧頂實現(xiàn)了FIFO的效果。class MyQueue: def __init__(self): self.stack_in [] self.stack_out [] def push(self, x): self.stack_in.append(x) def pop(self): if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out.pop() def peek(self): if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out[-1] def empty(self): return not self.stack_in and not self.stack_out這道題的關(guān)鍵不在實現(xiàn)而在分析復(fù)雜度。每次pop操作最壞情況是O(n)但攤還下來每個元素最多被倒騰兩次所以均攤是O(1)。能把這一點在答案里寫出來會跟其他候選人拉開差距。4.2 區(qū)間調(diào)度問題的貪心證明與模板貪心算法在這套題里也有出現(xiàn)。最常見的一道是區(qū)間調(diào)度給一堆區(qū)間的開始和結(jié)束時間選出盡可能多的互不重疊的區(qū)間。解法是貪心先把所有區(qū)間按結(jié)束時間排序然后遍歷只要當前區(qū)間的開始時間不早于上一個選中區(qū)間的結(jié)束時間就選中它。為什么按結(jié)束時間排序是對的因為結(jié)束時間越早剩下的空間就越多越容易選出更多的區(qū)間。證明方法叫“交換論證法”假設(shè)最優(yōu)解里第一個區(qū)間不是結(jié)束時間最早的區(qū)間我們可以把它換成結(jié)束時間最早的區(qū)間不會讓解變差因為最小區(qū)間的結(jié)束時間更早留給后續(xù)區(qū)間的空間只會更大。這個證明思路在面試里經(jīng)常被追問建議每個人都學會。def max_non_overlapping_intervals(intervals): intervals.sort(keylambda x: x[1]) count 0 last_end float(-inf) for start, end in intervals: if start last_end: count 1 last_end end return count區(qū)間調(diào)度這類題熟手一分鐘能寫完但要答得好需要在代碼之外說出貪心策略的正確性理由。這是我反復(fù)強調(diào)的點筆試做題不光要AC還要在注釋或者旁邊的思路描述里留下你的分析痕跡。有些筆試平臺會人工審代碼你的注釋就是你表達思考過程的窗口。5. 一道綜合題的完整解題推導從讀題到AC的每一步5.1 審題把題目里的話翻譯成代碼邏輯2019年這套題里有一道綜合題很能代表360的出題風格。題目大意是一個日志系統(tǒng)記錄的每條日志有編號和優(yōu)先級系統(tǒng)會定期清理優(yōu)先級最低的日志如果優(yōu)先級相同就清理編號最小的。現(xiàn)在給出一系列操作要求輸出每次清理的日志編號。這道題表面上看是個模擬題但你真按模擬來寫每次都找最小優(yōu)先級數(shù)據(jù)量一大就超時。正確的思路是用優(yōu)先隊列最小堆來維護日志每次清理就彈出堆頂。相比每次遍歷O(n)堆操作的復(fù)雜度是O(logn)整體性能完全不同。讀題的時候第一件事不是想用什么算法而是把“日志”、“優(yōu)先級”這些業(yè)務(wù)概念映射到數(shù)據(jù)結(jié)構(gòu)上。在這道題里“編號”和“優(yōu)先級”就是元組的兩個元素“清理優(yōu)先級最低的”就是求最小值“如果相同則清理編號最小的”就是定義比較規(guī)則。這么一翻譯題目就從一段業(yè)務(wù)描述變成了一道標準題維護一個帶自定義比較規(guī)則的最小堆。5.2 暴力解法為什么一定能過一部分樣例筆試平臺通常是按通過的測試用例比例給分的。一道題過了部分用例也能拿到部分分數(shù)。所以哪怕是幾分鐘后才想到最優(yōu)解也應(yīng)該先把暴力解法寫上去拿基礎(chǔ)分。這是校招筆試里的一個重要生存技巧。比如日志清理這道題最暴力的做法就是每次清理時遍歷所有日志找到優(yōu)先級最低的標記為已刪除直到刪夠數(shù)量。時間復(fù)雜度O(n2)如果數(shù)據(jù)量只有幾百完全能過如果數(shù)據(jù)量是十萬甚至百萬就會超時但你還是拿到了前面的用例分。logs [] # (priority, id) cleaned set() def simulate_brute(ops): for op in ops: if op[0] add: logs.append((op[2], op[1])) # (priority, id) else: # clean min_priority float(inf) min_id float(inf) for i, (p, idx) in enumerate(logs): if i in cleaned: continue if p min_priority or (p min_priority and idx min_id): min_priority p min_id idx target i cleaned.add(target) print(min_id)暴力解法能幫你快速理解題目規(guī)則也保證了你不會因為卡在優(yōu)化上整道題拿零分。寫完暴力解法之后再回頭分析復(fù)雜度看哪里可以優(yōu)化這是比較穩(wěn)妥的做題節(jié)奏。5.3 優(yōu)化思路和代碼實現(xiàn)從暴力解到堆優(yōu)化關(guān)鍵在于識別出“每次找最小值”這個操作是性能瓶頸。如果你在草稿紙上列一下這個操作需要做什么會發(fā)現(xiàn)它本質(zhì)上就是“從集合中重復(fù)取最小元素”這就是優(yōu)先隊列的經(jīng)典使用場景。用Python的heapq實現(xiàn)import heapq def simulate_fast(ops): heap [] removed set() next_id 1 for op in ops: if op[0] add: priority op[2] heapq.heappush(heap, (priority, next_id)) next_id 1 else: # clean while heap: p, idx heapq.heappop(heap) if idx not in removed: removed.add(idx) print(idx) break這個優(yōu)化版本的時間復(fù)雜度降到O(nlogn)肯定能通過全部測試用例。這里有個易錯的細節(jié)heapq在比較元組時會先比較第一個元素如果第一個元素相同就自動比較第二個元素。這正好滿足題目“優(yōu)先級相同時清理編號最小”的要求不需要額外寫比較函數(shù)。但如果題目要求“優(yōu)先級相同時清理編號最大”就得在入堆時把id取負數(shù)或者自定義比較類了。5.4 優(yōu)化思路的通用遷移這類“暴力寫法堆優(yōu)化”的組合幾乎在所有大廠筆試題里都能用上。比如求Top K大元素、合并K個有序數(shù)組、任務(wù)調(diào)度等直接把“找最值”的操作交給自己實現(xiàn)的堆或者語言自帶的優(yōu)先隊列大概率是對的。做完這道題之后我給自己定了一個規(guī)則凡是看到“每次取當前集合中的最大/最小元素”的題型一律先往堆的方向想。這個條件反射在之后的騰訊、百度筆試里幫我省下大量時間。6. 筆試后的復(fù)盤這些事比多刷十道題更管用6.1 錯題整理的核心方法筆試結(jié)束不代表這件事就結(jié)束了。我見過太多人考完試對一下答案然后就丟在一邊下次遇到同類題照樣錯。真正有效的做法是把錯題整理成“考點卡片”每張卡片包含四塊錯誤原因、涉及考點、正確思路、同類變體。比如我當年整理的一道題錯誤原因是題目要求“十進制輸出”但數(shù)據(jù)超出32位整型范圍我當時用了int就以為沒問題結(jié)果在C里溢出。這屬于邊界條件意識不足。整理成卡片之后我會在每次筆試前快速翻一遍這些卡片提醒自己容易在什么地方翻車。錯題整理這件事價值不在于寫了多少張卡片而在于你每次復(fù)盤的時候把自己“重新做一遍題”的思考過程寫下來。這個思考過程才是真正的收獲。6.2 從筆試題看360技術(shù)崗的關(guān)注點整套題刷下來你能明顯感覺到360技術(shù)崗的幾個關(guān)注點基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的熟練度、邊界條件的處理能力、長文本的信息提取能力。它不會考你某個冷門的算法模板但會把非?；A(chǔ)的考點藏在很有迷惑性的題干里。這就給備考方向指了條明路與其花大量時間去啃競賽級別的算法不如把劍指offer和LeetCode熱門100題刷熟。每一道題都問自己三個問題如果數(shù)據(jù)量擴大十倍我的代碼還能跑嗎如果輸入是空值、邊界值、超大值會怎么樣如果我不用庫函數(shù)能不能手寫這個功能把這三個問題想清楚應(yīng)付這類筆試就很有底氣了。我當初刷這套題的時候最大的感受是它不像傳說中那么難但非?？简灮竟ΑＤ阋悄馨炎址?、棧、堆、動態(tài)規(guī)劃這些常規(guī)考點練到“肌肉記憶”的程度這套題對你來說就是送分題合集。反過來你要是刷題只刷難題基礎(chǔ)題反而容易翻車。所以準備360的筆試沉住氣打好基礎(chǔ)比什么技巧都重要。