這類題目最值得先看的不是它有多少種解法而是它到底在考什么。力扣第1037題“有效的回旋鏢”名字聽起來有點(diǎn)怪但核心就是一個初中數(shù)學(xué)問題給你三個點(diǎn)的坐標(biāo)判斷它們是否在一條直線上。如果不在一條直線上就能構(gòu)成一個“回旋鏢”或者說一個三角形返回True如果在一條直線上就返回False。對于正在刷題、尤其是準(zhǔn)備面試的朋友來說這道題的價值在于它考察的是對基礎(chǔ)數(shù)學(xué)知識的代碼實(shí)現(xiàn)能力以及對浮點(diǎn)數(shù)精度問題的處理意識。很多人在第一次做的時候會直接想到用斜率公式(y2-y1)/(x2-x1) (y3-y1)/(x3-x1)然后就被“除零”和“浮點(diǎn)數(shù)相等比較”這兩個坑給卡住了。我建議先從理解題意和避開常見誤區(qū)開始再去看代碼實(shí)現(xiàn)。下面我會按實(shí)際解題和思考的順序把這道題拆解清楚。1. 先拆題意什么是“有效的回旋鏢”題目描述很簡單給定一個數(shù)組points里面包含三個子數(shù)組每個子數(shù)組[x, y]代表一個點(diǎn)的坐標(biāo)。你需要判斷這三個點(diǎn)是否不在同一條直線上。1.1 問題轉(zhuǎn)化這本質(zhì)上是一個幾何問題。三個點(diǎn)(x1, y1),(x2, y2),(x3, y3)共線的充要條件是它們構(gòu)成的向量是共線的。更具體地說向量(x2-x1, y2-y1)和向量(x3-x1, y3-y1)是平行的。在數(shù)學(xué)上判斷兩個向量是否平行共線可以用它們的叉積對于二維向量叉積是一個標(biāo)量是否為零來判斷。叉積公式為(x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)如果這個值等于0說明兩個向量平行三點(diǎn)共線不是有效的回旋鏢返回False。 如果這個值不等于0說明三點(diǎn)不共線是有效的回旋鏢返回True。1.2 為什么不用斜率很多人第一反應(yīng)是用斜率相等來判斷共線(y2 - y1) / (x2 - x1) (y3 - y1) / (x3 - x1)這個方法有兩個大問題除零問題當(dāng)x2 - x1或x3 - x1等于0時分母為零程序會報(bào)錯。雖然可以加if判斷但會讓代碼變得冗長。浮點(diǎn)數(shù)精度問題除法會產(chǎn)生浮點(diǎn)數(shù)。在計(jì)算機(jī)中浮點(diǎn)數(shù)的存儲和計(jì)算有精度誤差直接使用比較兩個浮點(diǎn)數(shù)是否相等是非常不可靠的。例如1.0 / 3.0的結(jié)果并不是一個精確的值。因此在編程競賽和面試中凡是涉及幾何、判斷共線或平行優(yōu)先考慮使用叉積或更一般的使用整數(shù)運(yùn)算來避免精度問題。這是本題第一個要記住的經(jīng)驗(yàn)點(diǎn)。2. 核心解法叉積公式的實(shí)現(xiàn)與解釋理解了叉積是正道代碼就非常簡單了。我們直接實(shí)現(xiàn)叉積公式。2.1 代碼實(shí)現(xiàn)def isBoomerang(points): :type points: List[List[int]] :rtype: bool # 解包三個點(diǎn) (x1, y1), (x2, y2), (x3, y3) points # 計(jì)算向量 (x2-x1, y2-y1) 和 (x3-x1, y3-y1) 的叉積 # 叉積公式 (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) cross_product (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) # 如果叉積為0則三點(diǎn)共線不是回旋鏢 # 如果叉積不為0則三點(diǎn)不共線是有效的回旋鏢 return cross_product ! 02.2 關(guān)鍵點(diǎn)解析解包賦值(x1, y1), (x2, y2), (x3, y3) points這行代碼直接、清晰地將輸入列表中的三個坐標(biāo)點(diǎn)賦值給六個變量。這比反復(fù)使用points[0][0]這樣的索引更易讀。叉積計(jì)算整個算法的核心就這一行。它完全使用整數(shù)運(yùn)算因?yàn)轭}目給的坐標(biāo)是整數(shù)徹底避免了浮點(diǎn)數(shù)精度問題。返回值直接返回cross_product ! 0的結(jié)果。True代表叉積非零有效回旋鏢False代表叉積為零三點(diǎn)共線。2.3 復(fù)雜度分析時間復(fù)雜度O(1)。只有固定次數(shù)的加減乘除運(yùn)算。空間復(fù)雜度O(1)。只使用了常數(shù)個額外變量。這個效率對于任何輸入都是最優(yōu)的。3. 測試與邊界條件代碼寫完了不要急著提交。先自己構(gòu)造幾個測試用例跑一遍尤其是邊界情況。這是養(yǎng)成好習(xí)慣的關(guān)鍵一步。3.1 常規(guī)測試用例# 測試代碼 print(isBoomerang([[1,1],[2,3],[3,2]])) # True三點(diǎn)構(gòu)成三角形 print(isBoomerang([[1,1],[2,2],[3,3]])) # False三點(diǎn)在直線 yx 上 print(isBoomerang([[0,0],[1,1],[2,2]])) # False同樣是 yx 直線 print(isBoomerang([[0,0],[0,1],[0,2]])) # False三點(diǎn)在垂直直線 x0 上 print(isBoomerang([[0,0],[1,0],[2,0]])) # False三點(diǎn)在水平直線 y0 上3.2 需要特別注意的邊界情況重復(fù)點(diǎn)題目描述中“回旋鏢”的定義是三個互不相同的點(diǎn)。但我們的叉積公式能處理重復(fù)點(diǎn)嗎如果兩個點(diǎn)重合例如points [[0,0], [0,0], [1,1]]那么向量(0,0)和(1,1)的叉積0*1 - 0*1 0會返回False。這符合邏輯因?yàn)閮蓚€點(diǎn)重合本質(zhì)上它們和第三個點(diǎn)必然“共線”退化情況構(gòu)不成一個面積不為零的三角形。但是題目明確說了點(diǎn)是互不相同的。不過我們的算法對于重復(fù)點(diǎn)也能給出合理的False輸出這體現(xiàn)了算法的魯棒性。在實(shí)際面試中你可以提一句“根據(jù)題意點(diǎn)應(yīng)該是互異的但即使有重復(fù)點(diǎn)這個算法也能正確返回False?！贝笳麛?shù)運(yùn)算題目坐標(biāo)是整數(shù)但叉積計(jì)算中涉及乘法。Python 的整數(shù)int是任意精度的所以不用擔(dān)心溢出問題。這在其他語言如 C、Java中可能需要考慮使用long long類型。浮點(diǎn)數(shù)陷阱再次強(qiáng)調(diào)如果你一開始寫的是斜率版本用這些測試用例可能會發(fā)現(xiàn)一些問題。例如對于點(diǎn)[[0,0], [1,2], [2,4]]斜率都是2浮點(diǎn)數(shù)比較可能沒問題。但對于某些會產(chǎn)生無限循環(huán)小數(shù)的斜率比如點(diǎn)[[0,0], [1,3], [2,6]]斜率是3浮點(diǎn)數(shù)表示是精確的。但點(diǎn)[[0,0], [1,7], [2,14]]呢似乎也沒問題。問題的關(guān)鍵在于你不能依賴運(yùn)氣。使用整數(shù)叉積是絕對安全的做法。4. 深入理解叉積的幾何意義知道怎么用還不夠最好能理解為什么叉積能判斷共線。這對于舉一反三解決其他幾何問題很有幫助。4.1 叉積的幾何含義對于二維向量u (a, b)和v (c, d)它們的叉積標(biāo)量a*d - b*c的絕對值等于以這兩個向量為鄰邊構(gòu)成的平行四邊形的面積。如果面積為0說明兩個向量共線平行它們無法“張開”成一個有面積的平行四邊形。如果面積不為0說明兩個向量不共線可以構(gòu)成一個平行四邊形其面積就是叉積的絕對值。在我們的問題中向量u (x2-x1, y2-y1)和v (x3-x1, y3-y1)是以點(diǎn)1為起點(diǎn)的兩個向量。它們的叉積為零意味著點(diǎn)1、2、3共線。叉積不為零意味著點(diǎn)1、2、3能構(gòu)成一個三角形該三角形面積是平行四邊形面積的一半即abs(cross_product)/2。4.2 與其他方法的聯(lián)系理解了面積你就能明白為什么這道題有時也被歸類為“計(jì)算三角形面積不為零”。判斷三角形面積是否為零公式之一就是使用叉積。這也解釋了為什么重復(fù)點(diǎn)會導(dǎo)致面積為零當(dāng)兩個點(diǎn)重合時其中一個向量是零向量它和任何向量的叉積都是零面積為零。5. 舉一反三類似題型與變種刷題不能只刷一道要能識別題型和套路。這道題屬于“計(jì)算幾何”的基礎(chǔ)題。掌握叉積后你可以解決一系列類似問題。5.1 力扣中的類似題目LeetCode 1232. 綴點(diǎn)成線這是幾乎一模一樣的問題給你一系列點(diǎn)超過三個判斷它們是否都在同一條直線上。解題思路完全一樣遍歷點(diǎn)依次判斷相鄰三個點(diǎn)是否共線即叉積是否為零即可。LeetCode 812. 最大三角形面積給定一組點(diǎn)找出能構(gòu)成最大面積三角形的三個點(diǎn)。核心就是遍歷所有三元組用叉積公式計(jì)算面積abs(cross_product)/2.0并記錄最大值。LeetCode 939. 最小面積矩形這道題更難一些但判斷平行、垂直等關(guān)系時向量點(diǎn)積、叉積的知識是基礎(chǔ)。5.2 面試可能問到的變種面試官可能會基于這道題進(jìn)行擴(kuò)展問題1“如果點(diǎn)不是整數(shù)而是浮點(diǎn)數(shù)坐標(biāo)你的方法還適用嗎”回答叉積公式依然適用但會出現(xiàn)浮點(diǎn)數(shù)精度問題。這時不能直接判斷cross_product 0而應(yīng)該判斷abs(cross_product) epsilon其中epsilon是一個極小的正數(shù)如1e-10用來容忍計(jì)算誤差。問題2“如果不允許使用乘法你能判斷三點(diǎn)共線嗎”回答這是一個有挑戰(zhàn)性的問題。一種思路是比較斜率但要用分?jǐn)?shù)形式(y2-y1)/(x2-x1)和(y3-y1)/(x3-x1)進(jìn)行交叉相乘比較即判斷(y2-y1)*(x3-x1) (y3-y1)*(x2-x1)。看這又回到了我們叉積公式的變形本質(zhì)上還是乘法。如果完全不允許乘法在整數(shù)坐標(biāo)下幾乎無法精確判斷。問題3“如何判斷四個點(diǎn)是否構(gòu)成一個平行四邊形”回答判斷兩組對邊分別平行且相等。利用向量知識對于點(diǎn)A,B,C,D需要滿足向量AB 向量DC且向量AD 向量BC。這可以通過比較坐標(biāo)差來實(shí)現(xiàn)。6. 從解題到刷題策略的思考通過這道簡單的題目我們可以提煉出一些通用的力扣刷題策略。6.1 讀題與轉(zhuǎn)化很多力扣題目的描述都包裹著一個簡單的核心。像“回旋鏢”這種名詞不要被它嚇到仔細(xì)讀題把它轉(zhuǎn)化為基本的數(shù)學(xué)或計(jì)算機(jī)科學(xué)問題。這道題的核心就是“三點(diǎn)是否共線”。6.2 選擇穩(wěn)健的解法當(dāng)一個問題有多個解法時如斜率法 vs 叉積法要選擇穩(wěn)健、坑少的解法。斜率法有除零和精度兩個坑叉積法只有整數(shù)運(yùn)算明顯更穩(wěn)健。在面試中選擇穩(wěn)健的解法并解釋清楚原因比炫技更重要。6.3 測試驅(qū)動寫完代碼一定要用不同的用例測試包括常規(guī)用例肯定為True肯定為False。邊界用例坐標(biāo)值很大、很小點(diǎn)重復(fù)斜率為零或無窮大。 自己先測試一遍能大大減少提交出錯的概率也向面試官展示了嚴(yán)謹(jǐn)性。6.4 理解背后的原理知道“怎么做”之后多問一句“為什么”。為什么叉積能判斷共線它的幾何意義是什么理解原理后你就能解決一類問題而不是一道題。6.5 整理與歸類做完題把它放到你的知識框架里。這道題可以歸類到“計(jì)算幾何-基礎(chǔ)-叉積應(yīng)用”。以后遇到幾何問題先想想向量、點(diǎn)積、叉積這些工具。7. 完整的、帶注釋的參考代碼最后給出一份包含詳細(xì)注釋和測試的完整代碼方便你理解和運(yùn)行。class Solution(object): def isBoomerang(self, points): 判斷三點(diǎn)是否構(gòu)成有效的回旋鏢即不共線。 使用向量叉積法避免浮點(diǎn)數(shù)精度問題。 參數(shù) points: List[List[int]]包含三個點(diǎn)的坐標(biāo)例如 [[1,1],[2,3],[3,2]] 返回 bool: 如果三點(diǎn)不共線返回 True否則返回 False。 # 1. 解包三個點(diǎn)的坐標(biāo)使代碼更清晰 point1, point2, point3 points x1, y1 point1 x2, y2 point2 x3, y3 point3 # 2. 計(jì)算向量 (x2-x1, y2-y1) 和 (x3-x1, y3-y1) 的叉積 # 叉積公式 (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) # 幾何意義叉積的絕對值等于以這兩個向量為鄰邊的平行四邊形面積 # 面積為零 向量共線 三點(diǎn)共線 cross_product (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) # 3. 判斷叉積是否為0 # 在整數(shù)運(yùn)算中直接比較即可 # 如果考慮浮點(diǎn)數(shù)應(yīng)使用 abs(cross_product) epsilon return cross_product ! 0 # 測試代碼 if __name__ __main__: sol Solution() test_cases [ ([[1,1],[2,3],[3,2]], True), # 不共線三角形 ([[1,1],[2,2],[3,3]], False), # 共線斜率為1 ([[0,0],[0,1],[0,2]], False), # 共線垂直直線 ([[0,0],[1,0],[2,0]], False), # 共線水平直線 ([[0,0],[1,1],[2,3]], True), # 不共線 ([[0,0],[0,0],[1,1]], False), # 重復(fù)點(diǎn)退化共線 ] print(測試結(jié)果) for i, (points, expected) in enumerate(test_cases): result sol.isBoomerang(points) status 通過 if result expected else 失敗 print(f測試用例 {i1}: 輸入{points}, 期望{expected}, 輸出{result}, {status})運(yùn)行這段代碼你會看到所有測試用例都通過。這驗(yàn)證了我們算法的正確性。8. 總結(jié)與下一步建議“有效的回旋鏢”這道題本身不難但它是一個非常好的起點(diǎn)讓你熟悉力扣中幾何類題目的常見套路——使用向量運(yùn)算代替浮點(diǎn)數(shù)計(jì)算。我個人的刷題建議是吃透基礎(chǔ)像叉積這樣的基礎(chǔ)工具一定要理解其原理和代碼實(shí)現(xiàn)。它會在很多題目里反復(fù)出現(xiàn)。一題多解雖然叉積法最好但你也可以嘗試實(shí)現(xiàn)一下斜率法親自踩一踩除零和精度那兩個坑印象會更深刻。建立連接做完這道題立刻去刷我前面提到的1232. 綴點(diǎn)成線你會發(fā)現(xiàn)幾乎不用思考就能寫出來這就是知識遷移的效果。整理筆記在你的刷題筆記里為“計(jì)算幾何”開一個分區(qū)把叉積公式、點(diǎn)積公式以及這道題、1232題、812題都放進(jìn)去。定期回顧。最后不要只追求刷題數(shù)量。把這種一道題背后的數(shù)學(xué)原理、代碼實(shí)現(xiàn)、測試方法、關(guān)聯(lián)題目都搞明白刷一道頂十道。當(dāng)你再遇到“判斷點(diǎn)線關(guān)系”、“計(jì)算多邊形面積”、“判斷圖形形狀”這類問題時你的第一反應(yīng)就會是向量和叉積這就是扎實(shí)的進(jìn)步。