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