摘要：一集合是什么與它相關(guān)數(shù)學(xué)概念有哪些解題集合定義集合是一種包含不同元素的數(shù)據(jù)結(jié)構(gòu)。集合中的元素稱為成員，集合最重要的兩個(gè)特點(diǎn)集合中的成員是無序集合中不存在相同成員即無序且唯一。

這是第四周的練習(xí)題，五一放假結(jié)束，該收拾好狀態(tài)啦。

下面是之前分享的鏈接：

1.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法（Stack）

2.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法（LinkedList）

3.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法（Queue）

歡迎關(guān)注我的 個(gè)人主頁 &&  個(gè)人博客 && 個(gè)人知識(shí)庫 && 微信公眾號(hào)“前端自習(xí)課”

本周練習(xí)內(nèi)容：數(shù)據(jù)結(jié)構(gòu)與算法 —— Set

這些都是數(shù)據(jù)結(jié)構(gòu)與算法，一部分方法是團(tuán)隊(duì)其他成員實(shí)現(xiàn)的，一部分我自己做的，有什么其他實(shí)現(xiàn)方法或錯(cuò)誤，歡迎各位大佬指點(diǎn)，感謝。

解題：
1.集合定義：
集合（Set）是一種包含不同元素的數(shù)據(jù)結(jié)構(gòu)。集合中的元素稱為成員，集合最重要的兩個(gè)特點(diǎn)：

集合中的成員是無序；

集合中不存在相同成員；

即：無序且唯一。

2.集合相關(guān)的數(shù)學(xué)概念：
集合的概念，如數(shù)學(xué)中一個(gè)由大于或等于0的整數(shù)組成的自然數(shù)集合， N = { 0, 1, 2, ...}。
還有如空集，表示不包含任何元素的集合。
并且也有并集，交集，差集等操作。

add(value)：向集合添加一個(gè)新的項(xiàng)。
delete(value)：從集合移除一個(gè)值。
has(value)：如果值在集合中，返回 true，否則返回 false。
clear()：移除集合中的所有項(xiàng)。
size()：返回集合所包含元素的數(shù)量。與數(shù)組的 length 屬性類似。
values()：返回一個(gè)包含集合中所有值的數(shù)組。

解題：

class Sets {
    constructor(){
        this.items = {}
    }
    has(value){
        // return value in this.items
        return this.items.hasOwnProperty(value)
    }
    add(value){
        if(!this.has(value)) {
            this.items[value] = value
            return true
        }
        return false
    }
    delete(value){
        if(!this.has(value)){
            delete this.items[value]
            return true
        }
        return false
    }
    clear(){
        this.items = {}
    }
    size(){
        const values = this.values()
        return values.length
    }
    values(){
        return Object.keys(this.items)
    }
}

并集（union）：對于給定的兩個(gè)集合，返回一個(gè)包含兩個(gè)集合中所有元素的新集合。

交集（intersection）：對于給定的兩個(gè)集合，返回一個(gè)包含兩個(gè)集合中共用元素的新集合。

差集（difference）：對于給定的兩個(gè)集合，返回一個(gè)包含所有存在于第一個(gè)集合且不存在于第二個(gè)集合的元素的新集合。

子集（subset）：驗(yàn)證一個(gè)給定集合是否是另一個(gè)集合的子集。

解題：

/**
 * union 并集
 * @param {Object} otherSet 其他集合
 */
Sets.prototype.union = function(otherSet){
    let result = new Sets(),
        current = this.values(),
        other = otherSet.values()
    for(let i = 0; i < current.length; i++){
        result.add(current[i])
    }
    for(let i = 0; i < other.length; i++){
        result.add(other[i])
    }
    return result
}


/**
 * intersection 交集
 * @param {Object} otherSet 其他集合
 */
Sets.prototype.intersection = function(otherSet){
    let result = new Sets(),
        current = this.values()
    for(let i = 0; i < current.length; i++){
        if(otherSet.has(current[i])){
            result.add(current[i])
        }
    }
    return result
}


/**
 * difference 差集
 * @param {Object} otherSet 其他集合
 */
Sets.prototype.difference = function(otherSet){
    let result = new Sets(),
        current = this.values()
    for(let i = 0; i < current.length; i++){
        if(!otherSet.has(current[i])){
            result.add(current[i])
        }
    }
    return result
}



/**
 * subset 子集
 * @param {Object} otherSet 其他集合
 */
Sets.prototype.subset = function(otherSet){
    let result = new Sets(),
        current = this.values()

    if(this.size() > otherSet.size()) return false
    for(let i = 0; i < current.length; i++){
        if(!otherSet.has(current[i])){
            return false
        }
    }
    return true
}

使用示例如下：

const nums1 = [1, 2, 2, 1];
const nums2 = [2, 2];
const nums3 = [4, 9, 5];
const nums4 = [9, 4, 9, 8, 4];

intersection(nums1, nums2); // [2]
intersection(nums3, nums4); // [9, 4]

提示：輸出結(jié)果中的每個(gè)元素是唯一的，可以不考慮輸出結(jié)果的順序。

解題：

function intersection(arr1, arr2){
    if(!Array.isArray(arr1) || !Array.isArray(arr2)) return []
    let create = function(arr){
        let sets = new Sets()
        arr.map(item => sets.add(item))
        return sets
    }
    let Sets1 = create(arr1)
    let Sets2 = create(arr2)
    let result = Sets1.intersection(Sets2)
    return  result.values()
}

使用示例如下：

const nums = [1, 2, 3];
subsets(nums);
// 輸出以下結(jié)果：
[
  [3],
  [1],
  [2],
  [1, 2, 3],
  [1, 3],
  [2, 3],
  [1, 2],
  []
]

來源：leetcode 78.集合

解題：

目前網(wǎng)絡(luò)上的最優(yōu)解：

function subsets(nums){
    if(!nums || !Array.isArray(nums)) return []
    
    function diff (num, vec) {
        let tmp = vec.slice(0)
        result.push(tmp)
        for (let i = num; i < len; i++) {
            vec.push(nums[i])
            diff(i + 1, vec)
            vec.splice(-1)
        }
    }

    const len = nums.length
    let arr = [], result = []
    diff(0, arr)
    return result
}

窮舉法：

function subsets(nums){
    if(!nums || !Array.isArray(nums)) return []

    let result = [[]],
        len = nums.length
    if(len === 0) return result 
    for(let i = 0; i < len; i++){
        let l = result.length
        let num = nums[i]
        let array = [num]
        for(let j = 0; j < l; j++){
            let tmparray = result[j].concat(array)
            result.push(tmparray)
        }
    }
    return result
}

下周將練習(xí)Dictionary 和 HashTable 的題目。