[IT技術30篇挑戰] 資料結構和演算法實作 DAY5

章節連結

指令
LeetCode 練習記錄
系列文章

集合是由一組沒有順序且唯一的項目組成的，也可以想成一個沒有重複元素、沒有順序的陣列。不過在這次的實作中，會用物件(Object)來表示集合的各種操作，同時加上數學上常用的聯集、差集、交集、子集。

指令

/*Set 集合*/
function Set(){
	var items = {}
	this.has = value =>{
		return items.hasOwnProperty(value)
	}
	this.add = value =>{
		if(!this.has(value)){
			items[value] = value
			return true
		}
		return false
	}
	this.remove = value =>{
		if(!this.has(value)){
			delete items[value]
			return true
		}
		return false
	}
	this.clear = () =>{
		return items = {}
	}
	this.size = () =>{
		return Object.keys(items).length
	}
	this.values = () =>{
		return Object.keys(items)
	}
	/*Union 聯集*/
	this.union = setB =>{
		let unionSet = new Set()
		let valuesInA = this.values()
		let valuesInB = setB.values()
		for(let i=0;i<valuesInA.length;i++){
			unionSet.add(valuesInA[i])
		}
		for(let i=0;i<valuesInB.length;i++){
			unionSet.add(valuesInB[i])
		}
		return unionSet
	}
	/*Intersection 交集*/
	this.intersection = setB =>{
		let intersectionSet = new Set()
		let valuesInA = this.values()
		for(let i=0;i<valuesInA.length;i++){
			if(setB.has(valuesInA[i])){
				intersectionSet.add(valuesInA[i])
			}
		}
		return intersectionSet
	}
	/*Difference 差集*/
	this.difference = setB =>{
		let differenceSet = new Set()
		let valuesInA = this.values()
		for(let i=0;i<valuesInA.length;i++){
			if(!setB.has(valuesInA[i])){
				differenceSet.add(valuesInA[i])
			}
		}
		return differenceSet
	}
	/*Subset 子集*/
	this.subset = setB =>{
		if(this.size()>setB.size()){
			return false
		}else{
			let valuesInA = this.values()
			for(let i=0;i<valuesInA.length;i++){
				if(!setB.has(valuesInA[i])){
					return false
				}
			}
			return true
		}
	}
}

let setA = new Set()
let setB = new Set()
let setC = new Set()
setA.add(1)
setA.add(2)
setA.add(3)
setB.add(3)
setB.add(4)
setB.add(5)
setB.add(6)
setC.add(5)
setC.add(6)
let unionAB = setA.union(setB)
let intersectionAB = setA.intersection(setB)
let differenceAB = setA.difference(setB)
let differenceBA = setB.difference(setA)
console.log(setA.values()) // [ '1', '2', '3' ]
console.log(setB.values()) // [ '3', '4', '5', '6' ]
console.log(setC.values()) // [ '1', '2', '3', '4', '5', '6' ]
console.log(unionAB.values()) // [ '5', '6' ]
console.log(intersectionAB.values()) // [ '3' ]
console.log(differenceAB.values()) // [ '1', '2' ]
console.log(differenceBA.values()) // [ '4', '5', '6' ]
console.log(setC.subset(setB)) // true
console.log(setC.subset(setA)) // false

100

101

102

103

104

105

/*Set 集合*/

function Set(){

var items = {}

this.has = value =>{

return items.hasOwnProperty(value)

}

this.add = value =>{

if(!this.has(value)){

items[value] = value

return true

}

return false

}

this.remove = value =>{

if(!this.has(value)){

delete items[value]

return true

}

return false

}

this.clear = () =>{

return items = {}

}

this.size = () =>{

return Object.keys(items).length

}

this.values = () =>{

return Object.keys(items)

}

/*Union 聯集*/

this.union = setB =>{

let unionSet = new Set()

let valuesInA = this.values()

let valuesInB = setB.values()

for(let i=0;i<valuesInA.length;i++){

unionSet.add(valuesInA[i])

}

for(let i=0;i<valuesInB.length;i++){

unionSet.add(valuesInB[i])

}

return unionSet

}

/*Intersection 交集*/

this.intersection = setB =>{

let intersectionSet = new Set()

let valuesInA = this.values()

for(let i=0;i<valuesInA.length;i++){

if(setB.has(valuesInA[i])){

intersectionSet.add(valuesInA[i])

}

return intersectionSet

}

/*Difference 差集*/

this.difference = setB =>{

let differenceSet = new Set()

let valuesInA = this.values()

for(let i=0;i<valuesInA.length;i++){

if(!setB.has(valuesInA[i])){

differenceSet.add(valuesInA[i])

}

return differenceSet

}

/*Subset 子集*/

this.subset = setB =>{

if(this.size()>setB.size()){

return false

}else{

let valuesInA = this.values()

for(let i=0;i<valuesInA.length;i++){

if(!setB.has(valuesInA[i])){

return false

}

return true

}

let setA = new Set()

let setB = new Set()

let setC = new Set()

setA.add(1)

setA.add(2)

setA.add(3)

setB.add(3)

setB.add(4)

setB.add(5)

setB.add(6)

setC.add(5)

setC.add(6)

let unionAB = setA.union(setB)

let intersectionAB = setA.intersection(setB)

let differenceAB = setA.difference(setB)

let differenceBA = setB.difference(setA)

console.log(setA.values()) // [ '1', '2', '3' ]

console.log(setB.values()) // [ '3', '4', '5', '6' ]

console.log(setC.values()) // [ '1', '2', '3', '4', '5', '6' ]

console.log(unionAB.values()) // [ '5', '6' ]

console.log(intersectionAB.values()) // [ '3' ]

console.log(differenceAB.values()) // [ '1', '2' ]

console.log(differenceBA.values()) // [ '4', '5', '6' ]

console.log(setC.subset(setB)) // true

console.log(setC.subset(setA)) // false

LeetCode 練習記錄

// 986. Interval List Intersections https://leetcode.com/problems/interval-list-intersections/
/**
 * @param {number[][]} A
 * @param {number[][]} B
 * @return {number[][]}
 */
var intervalIntersection = function(A, B) {
    let answer = []
    let i=0
    let j=0
    while( i<A.length && j<B.length){
        let [al,ar] = A[i]
        let [bl,br] = B[j]
        
        if(ar<bl){
            i++
        }else if(br<al){
            j++
        }else if(ar <= br){
            answer.push([Math.max(al, bl), ar])
            i++
        }else if(br <= ar){
            answer.push([Math.max(al, bl), br])
            j++
        }   
    }
    
    return answer
};