Enumeration — 列舉法

發表於 更新於 分類於
列舉法又稱為窮舉法，簡單來說就是把所有可能發生的狀況都列出來，再根據問題提供的條件，從中找出符合條件的解答，也就是所謂的暴力破解法，優點是簡單直觀，缺點就是當問題的範圍很廣，執行時間會等比上升，因此不適合拿來解範圍過於廣泛的題目。

列舉法又稱為窮舉法，簡單來說就是把所有可能發生的狀況都列出來，再根據問題提供的條件，從中找出符合條件的解答，也就是所謂的暴力破解法，優點是簡單直觀，缺點就是當問題的範圍很廣，執行時間會等比上升，因此不適合拿來解範圍過於廣泛的題目。

舉一項生活中的實例，小學的時候都會玩的交換日記，上面會有一個金屬扣搭配一個密碼鎖的鎖頭(如果不知道這是甚麼東西的人，代表我們之間有世代的隔閡 😢)，防止有人想偷看裡面的內容，只有交換日記的當事人才知道密碼是多少，但一定會有那種調皮的同學會想偷看裡面寫甚麼，趁沒人注意的時候把所有的密碼都嘗試過一遍，想在這些密碼的排列組合中找出正確的密碼，這就是列舉法的一種。

雞兔同籠

這是中國古代經典的數學題目，也可以用列舉法來推算答案，假設有數隻雞和兔子被關在同一個籠子裡，從上面數有 35 顆頭，從下面數有 94 隻腳，試問籠子裡有幾隻兔子和幾隻雞?

用 js 實作:

1
2
3
4
5
6
7
8
9
10
11
const solution = (head, foot) => {
  let rabbit = 1;
  let chicken = head - rabbit; //雞的數量必定是總數減掉兔子的數量
  while (chicken * 2 + rabbit * 4 !== foot) {
    rabbit++;
    chicken = head - rabbit;
  }
  return [rabbit, chicken];
};

solution(35, 94); //12隻兔子 23隻雞

大致理解列舉法的思維之後，我們就用 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 實作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} arr
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var countGoodTriplets = function (arr, a, b, c) {
  let count = 0;
  //三迴圈列出所有可能的組合
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      for (let k = j + 1; k < arr.length; k++) {
        //依據條件篩選出答案
        let condition1 = Math.abs(arr[i] - arr[j]) <= a;
        let condition2 = Math.abs(arr[j] - arr[k]) <= b;
        let condition3 = Math.abs(arr[i] - arr[k]) <= c;
        if (condition1 && condition2 && condition3) {
          count++;
        }
      }
    }
  }
  return count;
};