--

--

js

class Heap { constructor(data, type, compartor) { this.data = data || [] // less // type this.compartor = compartor || function(a, b) { if (type == 'less') return a - b else return b - a } this.heapify() } size() { return this.data.length } // heapify() { if (this.size() < 2) { return } for (let i = 1; i < this.size(); i++) { this.bubbleUp(i) } } // top() { if (!this.size()) return null return this.data[0] } // push(val) { this.data.push(val) this.bubbleUp(this.size() - 1) } // pop() { if (!this.size()) return null if (this.size() == 1) return this.data.pop() let res = this.data[0] this.data[0] = this.data.pop() if (this.size()) { this.bubbleDown(0) } return res } // swap(i, j) { if (i === j) return [this.data[i], this.data[j]] = [this.data[j], this.data[i]] } // 0 bubbleUp(index) { while (index) { // const parenIndex = (index - 1) >> 1; //const parenIndex = Math.floor((index - 1)/2); //const parenIndex = (index - 1)/2 | 0; // if (this.compartor(this.data[index], this.data[parenIndex]) > 0) { // this.swap(index, parenIndex); // index = parenIndex; } else { // break; } } } // bubbleDown(index) { let lastIndex = this.size() - 1; while (index < lastIndex) { // let leftIndex = index * 2 + 1; let rightIndex = index * 2 + 2; // let findIndex = index; if (leftIndex <= lastIndex && this.compartor(this.data[leftIndex], this.data[findIndex]) > 0) { findIndex = leftIndex; } if (rightIndex <= lastIndex && this.compartor(this.data[rightIndex], this.data[findIndex]) > 0) { findIndex = rightIndex; } if (index !== findIndex) { this.swap(index, findIndex); index = findIndex; } else { break; } } } }

LeetCode

  1. Offer 40. k
// k k var getLeastNumbers = function(arr, k) { if (k == 0) return [] let h = new Heap(arr, 'less') while(h.size() > k) h.pop() return h.data; };
// 0 var lastStoneWeight = function(stones) { let h = new Heap(stones, 'less') while(h.size() > 1) { let big = h.pop(), small = h.pop() if (big - small) h.push(big - small) } return h.top() };
    1. K
// k k var KthLargest = function(k, nums) { this.h = new Heap(nums, 'greator') this.k = k }; KthLargest.prototype.add = function(val) { this.h.push(val) while(this.h.size() > this.k) this.h.pop() return this.h.top() };
    1. K
// a b var compartor = function(a, b) { return a[0] + a[1] - b[0] - b[1] } var kSmallestPairs = function(nums1, nums2, k) { let h = new Heap([], 'less', compartor) for(let i in nums1) { for(let j in nums2) { // k h.push([nums1[i], nums2[j]]) if(h.size() > k) h.pop() } } return h.data };
    1. K
// k k var findKthLargest = function(nums, k) { let h = new Heap(nums, 'greator') while(h.size() > k) h.pop() return h.top() };
    1. K
// var topKFrequent = function(words, k) { let obj = {} // for(let item of words) { obj[item] = obj[item] + 1 || 1 } // // // sort a>b let compartor = function(a, b) { if(obj[a] == obj[b]) return a > b ? 1:-1 return obj[b] - obj[a] } let h = new Heap(Object.keys(obj), 'greator', compartor) while(h.size() > k) h.pop() h.data.sort(compartor) return h.data };
// // ///2 var MedianFinder = function() { this.lessH = new Heap([], 'less') this.greatorH = new Heap([], 'greator') }; /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function(num) { if (this.lessH.size() == 0 || num <= this.lessH.top()) { this.lessH.push(num) } else { this.greatorH.push(num) } if(this.lessH.size() < this.greatorH.size()) { this.lessH.push(this.greatorH.pop()) } if (this.lessH.size() - this.greatorH.size() > 1) { this.greatorH.push(this.lessH.pop()) } }; /** * @return {number} */ MedianFinder.prototype.findMedian = function() { if (this.lessH.size() == this.greatorH.size()) { return (this.lessH.top() + this.greatorH.top())/2 } return this.lessH.top() };
    1. II
// var nthUglyNumber = function(n) { let h = new Heap([1], 'greator') while(--n) { // top let top = h.pop() // 5 push top*5 if (top % 5 === 0) { h.push(top * 5) // 3 push top*5 top*3 } else if (top % 3 === 0) { h.push(top * 5) h.push(top * 3) } else {// push h.push(top * 5) h.push(top * 3) h.push(top * 2) } } return h.top() };
// p data var nthSuperUglyNumber = function(n, primes) { let p = new Array(primes.length).fill(0) let data = [1], ans = 1 while(data.length < n) { ans = primes[0] * data[p[0]] // ans for(let i = 1; i< primes.length; i++) { ans = Math.min(ans, primes[i] * data[p[i]]) } // ans +1 for(let i = 0; i< primes.length; i++) { if(primes[i] * data[p[i]] === ans) p[i]++ } data.push(ans) } return ans };
// a c var maximumScore = function(a, b, c) { let ans = 0 if (a > b) [a, b] = [b, a] if (a > c) [a, c] = [c, a] if (b > c) [b, c] = [c, b] if (c - b > a) { // b c a b+c ans = b + a } else { // bc a a b c b c ans = c - b a -= ans let i = a >> 1 b -= i ans += i * 2 ans += b } return ans };
// // key id value // var cmp = function(a, b) { return a[2] - b[2] } var Twitter = function() { this.user = {} this.twitter = new Heap([], 'less', cmp) this.time = 0 }; // Twitter.prototype.postTweet = function(userId, tweetId) { this.twitter.push([userId, tweetId, this.time++]) }; // push id Twitter.prototype.follow = function(followerId, followeeId) { this.user[followerId] ? this.user[followerId].push(followeeId) : this.user[followerId] = [followeeId] }; // id Twitter.prototype.unfollow = function(followerId, followeeId) { if (!this.user[followerId]) return this.user[followerId].splice(this.user[followerId].findIndex(item => item == followeeId), 1) }; // Set id Set push ans ans Twitter.prototype.getNewsFeed = function(userId) { if(this.twitter.size() == 0) return [] let list = [...(this.user[userId]||[]), userId], ans = [], n = 10, data = JSON.parse(JSON.stringify(this.twitter.data)) let userSet = new Set(list) while(n && this.twitter.size()) { let top = this.twitter.pop() if (userSet.has(top[0])) { ans.push(top[1]) n-- } } this.twitter = new Heap(data, 'less', cmp) return ans };
// 0 1 // // // var compartor1 = function(a, b) { return a[0] - b[0] } var compartor2 = function(a, b) { return b[0] - a[0] } var getNumberOfBacklogOrders = function(orders) { let buy = new Heap([], 'less', compartor1), sell = new Heap([], 'greator', compartor2) for(let x of orders) { if (x[2] == 0) { while (x[1] != 0 && sell.size() && sell.data[0][0] <= x[0]) { let cnt = Math.min(x[1], sell.data[0][1]) x[1] -= cnt sell.data[0][1] -= cnt if (sell.data[0][1] == 0) sell.pop() } if (x[1] != 0) buy.push(x) } else { while (x[1] != 0 && buy.size() && buy.data[0][0] >= x[0]) { let cnt = Math.min(x[1], buy.data[0][1]) x[1] -= cnt buy.data[0][1] -= cnt if (buy.data[0][1] == 0) buy.pop() } if (x[1] != 0) sell.push(x) } } let mod = 1000000007, sum = 0 for(let item of buy.data) { sum = (sum + item[1]) % mod } for(let item of sell.data) { sum = (sum + item[1]) % mod } return sum };