iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 30
3
Software Development

使用JavaScript學習資料結構與演算法系列 第 30

Day30-解題-Subsets

終於來到最後一天的挑戰!!時間真的過很快呢~今天我們要解決 Subsets 問題。該問題內容如下:

給定一個陣列,裡面包含多個不重複的數字元素,然後要求出陣列中元素所有的集合,例如給定 [1,2,3]這個陣列,則它的所有集合為[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

思考:

  1. 我們可以將所有可能的子集合做成樹狀結構
  2. 接著使用深度優先搜尋搭配遞迴將每個子集合都找出來

自己一開始也不知道如何解決問題,因此參考了以下連結的程式碼並研究了一番:
https://qiuyuntao.github.io/leetcode/solution/78.html

那麼就來說說這題是怎麼解出來的吧!我們需要兩個函式,一個用於將目標陣列當參數傳入,最後輸出所有子集合,為 subsets() 函式,另一個用於遞迴找出所有子集合,為 combine() 函式。在此我們的目標陣列為 [1, 2, 3]

  1. 由於任何陣列元素的子集合都包括了空集合,因此 result (儲存所有子集合的陣列)先預設加上一個空集合[],接著呼叫 combine() 找出所有子集合。
function subsets(arr) {
  let result = [
    []
  ];
  combine([], arr, result);
  return result;
}

function combine(tempArr, arr, result) {

}

console.log(subsets([1, 2, 3]));
  1. 在combine() 函式的部分,data 取出目標陣列的最前面一個元素,接著我們需要一個新的陣列 tempArr_1 儲存 data,並將 tempArr_1 加到 result 裡,最後移除一個最前面目標陣列的元素,因為已經加到 tempArr_1過。

在此補充使用 slice(0) 是充分利用 slice() 會回傳新陣列的特性,用0當參數可以直接複製一個新的陣列出來。
參考:
https://stackoverflow.com/questions/5024085/whats-the-point-of-slice0-here

然後 slice() 和 slice(0) 使用結果都相同:
https://stackoverflow.com/questions/43208336/javascript-array-slice-vs-array-slice0

function combine(tempArr, arr, result) {
  while (arr.length) {
    let data = arr[0];
    let tempArr_1 = tempArr.slice(0); // 用 slice的目的在於建立一個新陣列
    tempArr_1.push(data);
    result.push(tempArr_1);
    arr.shift();
    
    console.log('data:',data, 'tempArr_1:',tempArr_1, 'result:',result);
    console.log('-------------------');
    
    combine(tempArr_1, arr.slice(0), result);
  }
}

實際運行過程如下:
要注意很重要的一點是因為 combine() 裡 arr 後加了 .slice(0),因此每次呼叫的 arr 都是複製出來的新陣列。


自己用紙筆推演出來的,不過只有用 [1, 2] 兩個元素的陣列。最主要是要表達 combine() 內的 arr 都是複製出來的,讓遞迴可以進行下去。

這次的程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day30-subsets.js

最後來分享一下鐵人賽小小心得哈哈哈

這次是我第一次參加鐵人賽,透過這次鐵人賽複習了以前學過的資料結構和演算法,覺得完成30天連續發文的挑戰後確實有所成長,只是每天寫寫到後面幾天會不知道要寫什麼,因此最後7天就找了一些題目來練習並寫成文章。明年如果還有參加鐵人賽的話,我會把30天的內容規劃好再來行動的哈哈~

接著由於我是前端技術的愛好者,因此我選擇了 JavaScript 作為實作此系列文章的程式語言,目的除了讓自己的 JS 更熟練外,也希望能幫助到一些大學非科系又加入學習前端行列的人認識資料結構與演算法,而以前學過資料結構與演算法者可以作為複習。

最後如果你看到我的文章有哪裡有寫錯的話,非常希望你可以告訴我,讓我可以做出一些修正,感謝看完我這篇文章的你,也歡迎留言跟我交流討論~


上一篇
Day29-解題-Two Sum
系列文
使用JavaScript學習資料結構與演算法30

1 則留言

1
阿展展展
iT邦好手 1 級 ‧ 2019-12-29 09:17:15

好豐富的 JS
後半的解題非常的有趣 我...我再仔細鑽研鑽研/images/emoticon/emoticon06.gif
恭喜完賽 /images/emoticon/emoticon64.gif

harry xie iT邦新手 3 級 ‧ 2019-12-29 09:32:00 檢舉

恩恩謝謝~
也謝謝你看完我文章還幫我按 like 啊/images/emoticon/emoticon07.gif

/images/emoticon/emoticon12.gif

我要留言

立即登入留言