Enumeration — 列舉法
Published in
Dec 8, 2021
列舉法又稱為窮舉法,簡單來說就是把所有可能發生的狀況都列出來,再根據問題提供的條件,從中找出符合條件的解答,也就是所謂的暴力破解法,優點是簡單直觀,缺點就是當問題的範圍很廣,執行時間會等比上升,因此不適合拿來解範圍過於廣泛的題目。
舉一項生活中的實例,小學的時候都會玩的交換日記,上面會有一個金屬扣搭配一個密碼鎖的鎖頭(如果不知道這是甚麼東西的人,代表我們之間有世代的隔閡😢),防止有人想偷看裡面的內容,只有交換日記的當事人才知道密碼是多少,但一定會有那種調皮的同學會想偷看裡面寫甚麼,趁沒人注意的時候把所有的密碼都嘗試過一遍,想在這些密碼的排列組合中找出正確的密碼,這就是列舉法的一種。
雞兔同籠
這是中國古代經典的數學題目,也可以用列舉法來推算答案,假設有數隻雞和兔子被關在同一個籠子裡,從上面數有35顆頭,從下面數有94隻腳,試問籠子裡有幾隻兔子和幾隻雞?
用js實作:
大致理解列舉法的思維之後,我們就用Enumeration的標籤從leetcode中挑一題1534. Count Good Triplets 來說明列舉法吧,題目會給予一個陣列以及三個整數a、 b、 c ,要你從陣列當中找出有幾組符合條件的三胞胎(這邊的三胞胎指的是三個一組) ,每組三胞胎 (arr[i], arr[j], arr[k])
會具備以下的條件:
0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
|x|
代表是取x的絕對值
.
leetcode提供的example如下:
Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output: 4
Explanation: There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].
用js實作: