春招沖沖沖系列（網(wǎng)易筆試題）
題目來(lái)源：https://www.nowcoder.com/discuss/625915
視頻：
b 站視頻地址：https://www.bilibili.com/video/BV14V411e7MF/
題目一
一組數(shù)據(jù)，判斷能組成三角形最多的數(shù)，如果有多個(gè)，都寫下來(lái)。
力扣原題 611. 有效三角形的個(gè)數(shù)[1]
題目描述
給定一個(gè)包含非負(fù)整數(shù)的數(shù)組，你的任務(wù)是統(tǒng)計(jì)其中可以組成三角形三條邊的三元組個(gè)數(shù)。
示例 1:
輸入: [2,2,3,4]
輸出: 3
解釋:
有效的組合是:
2,3,4 (使用第一個(gè) 2)
2,3,4 (使用第二個(gè) 2)
2,2,3
注意:
數(shù)組長(zhǎng)度不超過(guò)1000。
數(shù)組里整數(shù)的范圍為 [0, 1000]。
前置知識(shí)
排序 雙指針 二分法 三角形邊的關(guān)系
暴力法（超時(shí)）
思路
首先要有一個(gè)數(shù)學(xué)前提：如果三條線段中任意兩條的和都大于第三邊，那么這三條線段可以組成一個(gè)三角形。即給定三個(gè)線段 a，b，c，如果滿足 a + b > c and a + c > b and b + c > a，則線段 a，b，c 可以構(gòu)成三角形，否則不可以。
力扣中有一些題目是需要一些數(shù)學(xué)前提的，不過(guò)這些數(shù)學(xué)前提都比較簡(jiǎn)單，一般不會(huì)超過(guò)高中數(shù)學(xué)知識(shí)，并且也不會(huì)特別復(fù)雜。一般都是小學(xué)初中知識(shí)即可。
?如果你在面試中碰到不知道的數(shù)學(xué)前提，可以尋求面試官提示試試。
?
關(guān)鍵點(diǎn)解析
三角形邊的關(guān)系 三層循環(huán)確定三個(gè)線段
代碼
代碼支持: Python
class Solution:
def is_triangle(self, a, b, c):
if a == 0 or b == 0 or c == 0: return False
if a + b > c and a + c > b and b + c > a: return True
return False
def triangleNumber(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
for i in range(n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
if self.is_triangle(nums[i], nums[j], nums[k]): ans += 1
return ans
「復(fù)雜度分析」
時(shí)間復(fù)雜度：，其中 N 為 數(shù)組長(zhǎng)度。 空間復(fù)雜度：
優(yōu)化的暴力法
思路
暴力法的時(shí)間復(fù)雜度為 ， 其中 最大為 1000。一般來(lái)說(shuō)， 的算法在數(shù)據(jù)量 <= 500 是可以 AC 的。1000 的數(shù)量級(jí)則需要考慮 或者更好的解法。
OK，到這里了。我給大家一個(gè)干貨。應(yīng)該是其他博主不太會(huì)提的。原因可能是他們不知道， 也可能是他們覺(jué)得太小兒科不需要說(shuō)。
由于前面我根據(jù)數(shù)據(jù)規(guī)模推測(cè)到到了解法的復(fù)雜度區(qū)間是 , ，不可能是 （WHY？）。 降低時(shí)間復(fù)雜度的方法主要有： 空間換時(shí)間和排序換時(shí)間（我們一般都是使用基于比較的排序方法）。而排序換時(shí)間僅僅在總體復(fù)雜度大于 才適用（原因不用多說(shuō)了吧？）。
這里由于總體的時(shí)間復(fù)雜度是 ，因此我自然想到了排序換時(shí)間。當(dāng)我們對(duì) nums 進(jìn)行一次排序之后，我發(fā)現(xiàn)：
is_triangle 函數(shù)有一些判斷是無(wú)效的
def is_triangle(self, a, b, c):
if a == 0 or b == 0 or c == 0: return False
# a + c > b 和 b + c > a 是無(wú)效的判斷，因?yàn)楹愠闪?/span>
if a + b > c and a + c > b and b + c > a: return True
return False
因此我們的目標(biāo)變?yōu)檎业?code style="font-size: 14px;word-wrap: break-word;margin: 0 2px;background-color: rgba(27,31,35,.05);font-family: Operator Mono, Consolas, Monaco, Menlo, monospace;word-break: break-all;color: #3594F7;background: RGBA(59, 170, 250, .1);padding: 0 2px;border-radius: 2px;height: 21px;line-height: 22px;">a + b > c即可，因此第三層循環(huán)是可以提前退出的。
for i in range(n - 2):
for j in range(i + 1, n - 1):
k = j + 1
while k < n and num[i] + nums[j] > nums[k]:
k += 1
ans += k - j - 1
這也僅僅是減枝而已，復(fù)雜度沒(méi)有變化。通過(guò)進(jìn)一步觀察，發(fā)現(xiàn) k 沒(méi)有必要每次都從 j + 1 開(kāi)始。而是從上次找到的 k 值開(kāi)始就行。原因很簡(jiǎn)單， 當(dāng) nums[i] + nums[j] > nums[k] 時(shí)，我們想要找到下一個(gè)滿足 nums[i] + nums[j] > nums[k] 的 新的 k 值，由于進(jìn)行了排序，因此這個(gè) k 肯定比之前的大（單調(diào)遞增性），因此上一個(gè) k 值之前的數(shù)都是無(wú)效的，可以跳過(guò)。
for i in range(n - 2):
k = i + 2
for j in range(i + 1, n - 1):
while k < n and nums[i] + nums[j] > nums[k]:
k += 1
ans += k - j - 1
由于 K 不會(huì)后退，因此最內(nèi)層循環(huán)總共最多執(zhí)行 N 次，因此總的時(shí)間復(fù)雜度為 。
?這個(gè)復(fù)雜度分析有點(diǎn)像單調(diào)棧，大家可以結(jié)合起來(lái)理解。
?
關(guān)鍵點(diǎn)分析
排序
代碼
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
nums.sort()
for i in range(n - 2):
if nums[i] == 0: continue
k = i + 2
for j in range(i + 1, n - 1):
while k < n and nums[i] + nums[j] > nums[k]:
k += 1
ans += k - j - 1
return ans
「復(fù)雜度分析」
時(shí)間復(fù)雜度： 空間復(fù)雜度：取決于排序算法
題目二
給你一個(gè)二叉樹(shù)，實(shí)現(xiàn)固定值和的路徑，優(yōu)先層數(shù)低的，排在左邊的
思路
DFS 找出所有的滿足和為 target 的，遍歷過(guò)程維護(hù)層數(shù)較低的并返回即可。 函數(shù)簽名為：dfs(node, target, depth)，其中 node 為當(dāng)前的節(jié)點(diǎn)， target 為目標(biāo)和，減到 0 就找到目標(biāo)路徑了，depth 是深度，用于「維護(hù)層數(shù)較低」。
也可以使用 BFS 從左到右將 (node, target) 入隊(duì)即可。
如果還不懂， 建議參考我的樹(shù)專題[2]
題目三
一組數(shù)據(jù)，找出能組成和被6整除的最大值對(duì)應(yīng)的集合
題目描述
給你一個(gè)整數(shù)數(shù)組 nums，請(qǐng)你找出并返回能被六整除的元素最大和。
示例 1：
輸入：nums = [3,6,5,1,8]
輸出：18
解釋：選出數(shù)字 3, 6, 1 和 8，它們的和是 18（可被 6 整除的最大和）。
示例 2：
輸入：nums = [4]
輸出：0
解釋：4 不能被 6 整除，所以無(wú)法選出數(shù)字，返回 0。
示例 3：
輸入：nums = [1,2,3,4,4]
輸出：12
解釋：選出數(shù)字 1, 3, 4 以及 4，它們的和是 12（可被 6 整除的最大和）。
提示：
1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4
前置知識(shí)
數(shù)組 回溯法 排序
公司
字節(jié) 網(wǎng)易有道
暴力法
思路
力扣類似題 1262. 可被三整除的最大和[3]
這道題是 6 的倍數(shù)，而上面的是 3 的倍數(shù)。實(shí)際上， 6 的倍數(shù)就是在滿足三的倍數(shù)的條件下，再加上「是偶數(shù)的條件即可」。
這里以 3 的倍數(shù)為例，講一下這道題。
一種方式是找出所有的能夠被 3 整除的子集，然后挑選出和最大的。由于我們選出了所有的子集，那么時(shí)間復(fù)雜度就是 ， 毫無(wú)疑問(wèn)會(huì)超時(shí)。這里我們使用回溯法找子集，如果不清楚回溯法，可以參考我之前的題解，很多題目都用到了，比如78.subsets。
更多回溯題目，可以訪問(wèn)上方鏈接查看（可以使用一套模板搞定）：
代碼
class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
self.res = 0
def backtrack(temp, start):
total = sum(temp)
if total % 3 == 0:
self.res = max(self.res, total)
for i in range(start, len(nums)):
temp.append(nums[i])
backtrack(temp, i + 1)
temp.pop(-1)
backtrack([], 0)
return self.res
減法 + 排序
減法的核心思想是，我們求出總和。如果總和不滿足題意，我們嘗試減去最小的數(shù)，使之滿足題意。
思路
這種算法的思想，具體來(lái)說(shuō)就是：
我們將所有的數(shù)字加起來(lái)，我們不妨設(shè)為 total total 除以 3，得到一個(gè)余數(shù) mod， mod 可能值有 0，1，2. 同時(shí)我們建立兩個(gè)數(shù)組，一個(gè)是余數(shù)為 1 的數(shù)組 one，一個(gè)是余數(shù)為 2 的數(shù)組 two 如果 mod 為 0，我們直接返回即可。 如果 mod 為 1，我們可以減去 one 數(shù)組中最小的一個(gè)（如果有的話），或者減去兩個(gè) two 數(shù)組中最小的（如果有的話），究竟減去誰(shuí)取決誰(shuí)更小。 如果 mod 為 2，我們可以減去 two 數(shù)組中最小的一個(gè)（如果有的話），或者減去兩個(gè) one 數(shù)組中最小的（如果有的話），究竟減去誰(shuí)取決誰(shuí)更小。
由于我們需要取 one 和 two 中最小的一個(gè)或者兩個(gè)，因此對(duì)數(shù)組 one 和 two 進(jìn)行排序是可行的，如果基于排序的話，時(shí)間復(fù)雜度大致為 ，這種算法可以通過(guò)。
以題目中的例 1 為例：
以題目中的例 2 為例：
代碼
class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
one = []
two = []
total = 0
for num in nums:
total += num
if num % 3 == 1:
one.append(num)
if num % 3 == 2:
two.append(num)
one.sort()
two.sort()
if total % 3 == 0:
return total
elif total % 3 == 1 and one:
if len(two) >= 2 and one[0] > two[0] + two[1]:
return total - two[0] - two[1]
return total - one[0]
elif total % 3 == 2 and two:
if len(one) >= 2 and two[0] > one[0] + one[1]:
return total - one[0] - one[1]
return total - two[0]
return 0
減法 + 非排序
思路
上面的解法使用到了排序。我們其實(shí)觀察發(fā)現(xiàn)，我們只是用到了 one 和 two 的最小的兩個(gè)數(shù)。因此我們完全可以在線形的時(shí)間和常數(shù)的空間完成這個(gè)算法。我們只需要分別記錄 one 和 two 的最小值和次小值即可，在這里，我使用了兩個(gè)長(zhǎng)度為 2 的數(shù)組來(lái)表示，第一項(xiàng)是最小值，第二項(xiàng)是次小值。
代碼
class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
one = [float('inf')] * 2
two = [float('inf')] * 2
total = 0
for num in nums:
total += num
if num % 3 == 1:
if num < one[0]:
t = one[0]
one[0] = num
one[1] = t
elif num < one[1]:
one[1] = num
if num % 3 == 2:
if num < two[0]:
t = two[0]
two[0] = num
two[1] = t
elif num < two[1]:
two[1] = num
if total % 3 == 0:
return total
elif total % 3 == 1 and one:
if len(two) >= 2 and one[0] > two[0] + two[1]:
return total - two[0] - two[1]
return total - one[0]
elif total % 3 == 2 and two:
if len(one) >= 2 and two[0] > one[0] + one[1]:
return total - one[0] - one[1]
return total - two[0]
return 0
有限狀態(tài)機(jī)
思路
我在數(shù)據(jù)結(jié)構(gòu)與算法在前端領(lǐng)域的應(yīng)用 - 第二篇 中講到了有限狀態(tài)機(jī)。
狀態(tài)機(jī)表示若干個(gè)狀態(tài)以及在這些狀態(tài)之間的轉(zhuǎn)移和動(dòng)作等行為的數(shù)學(xué)模型。通俗的描述狀態(tài)機(jī)就是定義了一套狀態(tài)変更的流程：狀態(tài)機(jī)包含一個(gè)狀態(tài)集合，定義當(dāng)狀態(tài)機(jī)處于某一個(gè)狀態(tài)的時(shí)候它所能接收的事件以及可執(zhí)行的行為，執(zhí)行完成后，狀態(tài)機(jī)所處的狀態(tài)。
狀態(tài)機(jī)使用非常廣泛，比如正則表達(dá)式的引擎，編譯器的詞法和語(yǔ)法分析，網(wǎng)絡(luò)協(xié)議，企業(yè)應(yīng)用等很多領(lǐng)域都會(huì)用到。
拿本題中來(lái)說(shuō)，我們從左到右掃描數(shù)組的過(guò)程，將會(huì)不斷改變狀態(tài)機(jī)的狀態(tài)。
我們使用 state 數(shù)組來(lái)表示本題的狀態(tài)：
state[0] 表示 mod 為 0 的 最大和 state[1] 表示 mod 為 1 的 最大和 state[2] 表示 mod 為 1 的 最大和
我們的狀態(tài)轉(zhuǎn)移方程就會(huì)很容易。說(shuō)到狀態(tài)轉(zhuǎn)移方程，你可能會(huì)想到動(dòng)態(tài)規(guī)劃。沒(méi)錯(cuò)！這種思路可以直接翻譯成動(dòng)態(tài)規(guī)劃，算法完全一樣。如果你看過(guò)我上面提到的文章，那么狀態(tài)轉(zhuǎn)移方程對(duì)你來(lái)說(shuō)就會(huì)很容易。如果你不清楚，那么請(qǐng)往下看：
我們從左往右不斷讀取數(shù)字，我們不妨設(shè)這個(gè)數(shù)字為 num。 如果 num % 3 為 0。那么我們的 state[0], state[1], state[2] 可以直接加上 num（題目限定了 num 為非負(fù)）， 因?yàn)槿魏螖?shù)字加上 3 的倍數(shù)之后，mod 3 的值是不變的。 如果 num % 3 為 1。我們知道 state[2] + num 會(huì)變成一個(gè)能被三整除的數(shù)，但是這個(gè)數(shù)字不一定比當(dāng)前的 state[0]大。代碼表示就是 max(state[2] + num, state[0])。同理 state[1] 和 state[2] 的轉(zhuǎn)移邏輯類似。同理 num % 3 為 2 也是類似的邏輯。 最后我們返回 state[0]即可。
代碼
class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
state = [0, float('-inf'), float('-inf')]
for num in nums:
if num % 3 == 0:
state = [state[0] + num, state[1] + num, state[2] + num]
if num % 3 == 1:
a = max(state[2] + num, state[0])
b = max(state[0] + num, state[1])
c = max(state[1] + num, state[2])
state = [a, b, c]
if num % 3 == 2:
a = max(state[1] + num, state[0])
b = max(state[2] + num, state[1])
c = max(state[0] + num, state[2])
state = [a, b, c]
return state[0]
當(dāng)然這個(gè)代碼還可以簡(jiǎn)化：
class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
state = [0, float('-inf'), float('-inf')]
for num in nums:
temp = [0] * 3
for i in range(3):
temp[(i + num) % 3] = max(state[(i + num) % 3], state[i] + num)
state = temp
return state[0]
「復(fù)雜度分析」
時(shí)間復(fù)雜度： 空間復(fù)雜度：
關(guān)鍵點(diǎn)解析
貪婪法 狀態(tài)機(jī) 數(shù)學(xué)分析
擴(kuò)展
實(shí)際上，我們可以采取加法（貪婪策略），感興趣的可以試一下。
另外如果題目改成了請(qǐng)你找出并返回能被x整除的元素最大和，你只需要將我的解法中的 3 改成 x 即可。
題目四
題目描述
編輯距離變種，定義了編輯距離和兩組字符串長(zhǎng)度的比值，參考 https://leetcode-cn.com/problems/edit-distance/ ,只不過(guò)增刪距離為1，改距離為2
思路
力扣原題變種 72. 編輯距離
這道題我太熟悉了，這道題用不同的語(yǔ)言我寫了不下十次，提供了大概四五種寫法（基本思路類似，寫法不同）。然而筆試推薦大家「記憶化遞歸」來(lái)寫，畢竟大多數(shù)筆試題解題速度比代碼運(yùn)行速度更重要。
代碼
代碼支持：Python3
Python3 Code:
class Solution:
@lru_cache(None)
def helper(self, word1: str, s1: int, e1: int, word2: str, s2: int, e2: int) -> int:
if s1 > e1:
return e2 - s2 + 1
elif s2 > e2:
return e1 - s1 + 1
c1 = word1[s1]
c2 = word2[s2]
if c1 == c2:
return self.helper(word1, s1 + 1, e1, word2, s2 + 1, e2)
else:
return (
min(
self.helper(word1, s1 + 1, e1, word2, s2, e2) + 1, # delete or add
self.helper(word1, s1, e1, word2, s2 + 1, e2) + 1, # delete or add
self.helper(word1, s1 + 1, e1, word2, s2 + 1, e2) + 2, # replace
)
)
def minDistance(self, word1: str, word2: str) -> int:
return self.helper(word1, 0, len(word1) - 1, word2, 0, len(word2) - 1)
「復(fù)雜度分析」
令 m 和 n 分別為兩個(gè)字符串的長(zhǎng)度。
時(shí)間復(fù)雜度： 空間復(fù)雜度：
Reference
611. 有效三角形的個(gè)數(shù): https://leetcode-cn.com/problems/valid-triangle-number/solution/chao-xiang-xi-pai-xu-shuang-zhi-zhen-611-you-xiao-/
[2]樹(shù)專題: https://lucifer.ren/blog/2020/11/23/tree/
[3]1262. 可被三整除的最大和: https://github.com/azl397985856/leetcode/blob/master/problems/1262.greatest-sum-divisible-by-three.md
愛(ài)心三連擊
1.看到這里了就點(diǎn)個(gè)在看支持下吧，你的在看是我創(chuàng)作的動(dòng)力。
2.關(guān)注公眾號(hào)力扣加加，帶你啃下算法這塊硬骨頭！加個(gè)星標(biāo)，不錯(cuò)過(guò)每一條成長(zhǎng)的機(jī)會(huì)。
3.如果你覺(jué)得本文的內(nèi)容對(duì)你有幫助，就幫我轉(zhuǎn)發(fā)一下吧。