June LeetCoding Challenge

好不容易又看到一个Js刷题的，mark一下！！！我之前Java刷了550道左右，因为工作是偏前端，想到日后发展，现在正在痛苦的转Js中，加油lz！

6/10 https://leetcode.com/problems/search-insert-position/
二分搜索经典题目

1. var searchInsert = function(nums, target) {
   
2.     if(!nums || !nums.length) return 0;
   
3.     let i=0, j=nums.length;
   
4.     while(i<j) {
   
5.         const mid = parseInt(i + (j-i)/2);
   
6.         if(nums[mid] === target) return mid;
   
7.         if(nums[mid] > target) j = mid;
   
8.         else i = mid+1;
   
9.     }
   
10.     return i;
    
11. };

复制代码

搞笑的是lz在提交记录里面翻出了5年前用Java刷过的记录，原本觉得代码写很蠢结果跑完avg 0ms然后faster than 100%的Java用户，而且连跑三次都是😂  以为LC出bug了结果一跑JS又被打回现实。。 百思不得其解ing...
  

6/11 https://leetcode.com/problems/sort-colors/
双指针题目，一开始忘记了在交换之后j需要重新检查，后来又忽略了其实跟i交换过后其实也是可以直接j++的因为i指向的只能是1（i一定<=j，而所有被j处理过的0都会被换到i之前，所有的2都会放到k之后），而对于nums[j] = 1的情况我们会直接j++，所以在跟i交换后直接j++可以skip掉接下来的那轮。

1. var sortColors = function(nums) {
   
2.     if(!nums || nums.length < 2) return;
   
3.     let i = j = 0, k = nums.length-1;
   
4.     while(j <= k) {
   
5.         if(!nums[j]) {
   
6.             [nums[i++], nums[j++]] = [nums[j], nums[i]];
   
7.         } else if(nums[j] === 2) {
   
8.             [nums[j], nums[k--]] = [nums[k], nums[j]];
   
9.         } else j++;
   
10.     }
    
11. };

复制代码

T: O(n)
S: O(1)

6/12 https://leetcode.com/problems/insert-delete-getrandom-o1/
一开始写了Doubly LinkedList:

1. var ListNode = function(val) {
   
2.     this.val = val;
   
3.     this.prev = this.next = null;
   
4. }
   
5. 
   
6. /**
   
7. * Initialize your data structure here.
   
8. */
   
9. var RandomizedSet = function() {
   
10.     this.map = new Map();
    
11.     this.head = new ListNode(-1);
    
12.     this.tail = new ListNode(-1);
    
13.     this.head.next = this.tail;
    
14.     this.tail.prev = this.head;
    
15. };
    
16. 
    
17. /**
    
18. * Inserts a value to the set. Returns true if the set did not already contain the specified element.
    
19. * @param {number} val
    
20. * [url=home.php?mod=space&uid=160137]@return[/url] {boolean}
    
21. */
    
22. RandomizedSet.prototype.insert = function(val) {
    
23.     if(this.map.has(val)) return false;
    
24.     const node = new ListNode(val);
    
25.     node.prev = this.tail.prev;
    
26.     this.tail.prev.next = node;
    
27.     this.tail.prev = node;
    
28.     node.next = this.tail;
    
29.     this.map.set(val, node);
    
30.     return true;
    
31. };
    
32. 
    
33. /**
    
34. * Removes a value from the set. Returns true if the set contained the specified element.
    
35. * @param {number} val
    
36. * @return {boolean}
    
37. */
    
38. RandomizedSet.prototype.remove = function(val) {
    
39.     if(!this.map.has(val)) return false;
    
40.     const node = this.map.get(val);
    
41.     node.prev.next = node.next;
    
42.     node.next.prev = node.prev;
    
43.     this.map.delete(val);
    
44.     return true;
    
45. };
    
46. 
    
47. /**
    
48. * Get a random element from the set.
    
49. * @return {number}
    
50. */
    
51. RandomizedSet.prototype.getRandom = function() {
    
52.     if(this.map.size) {
    
53.         const random = parseInt(Math.random() * this.map.size);
    
54.         return [...this.map.keys()][random];
    
55.     }
    
56.     return -1;
    
57. };
    

复制代码

后来发现其实没必要，只需要HashMap + Array即可：

1. /**
   
2. * Initialize your data structure here.
   
3. */
   
4. var RandomizedSet = function() {
   
5.     this.arr = [];
   
6.     this.map = new Map();
   
7. };
   
8. 
   
9. /**
   
10. * Inserts a value to the set. Returns true if the set did not already contain the specified element.
    
11. * @param {number} val
    
12. * @return {boolean}
    
13. */
    
14. RandomizedSet.prototype.insert = function(val) {
    
15.     if(this.map.has(val)) return false;
    
16.     this.map.set(val, this.arr.length);
    
17.     this.arr.push(val);
    
18.     return true;
    
19. };
    
20. 
    
21. /**
    
22. * Removes a value from the set. Returns true if the set contained the specified element.
    
23. * @param {number} val
    
24. * @return {boolean}
    
25. */
    
26. RandomizedSet.prototype.remove = function(val) {
    
27.     if(!this.map.has(val)) return false;
    
28.     let idx = this.map.get(val);
    
29.     this.arr[idx] = this.arr[this.arr.length-1];
    
30.     this.arr.pop();
    
31.     this.map.set(this.arr[idx], idx);
    
32.     this.map.delete(val);
    
33.     return true;
    
34. };
    
35. 
    
36. /**
    
37. * Get a random element from the set.
    
38. * @return {number}
    
39. */
    
40. RandomizedSet.prototype.getRandom = function() {
    
41.     const r = parseInt(Math.random() * this.arr.length)
    
42.     return this.arr[r];
    
43. };

复制代码

虽然可以通过test, 但是当数组里只剩最后一个时remove会有不必要的arr[0] = arr[0]; arr.pop()，而且会造成Map当中存入不必要的`{ undefined => 0 }`，于是lz重新写了：

1. RandomizedSet.prototype.remove = function(val) {
   
2.     if(!this.map.has(val)) return false;  
   
3.     let last = this.arr.pop();
   
4.     if(this.arr.length) {
   
5.         let idx = this.map.get(val);
   
6.         this.arr[idx] = last;
   
7.         this.map.set(last, idx);
   
8.     }
   
9.     this.map.delete(val);
   
10.     return true;
    
11. };

复制代码

可是不知道为什么就是跑不过倒数第二个test case怎么都跑不过，而且由于数据量过大所以无法debug，求走过路过的大神帮忙看看问题究竟出在哪里🙏

我建了个群，里面有几个人在刷，我们都是从二月就开始刷的，一起吗？

zmcddn 发表于 2020/06/13 16:09:32
我建了个群，里面有几个人在刷，我们都是从二月就开始刷的，一起吗？

求二维码 zszs

zmcddn 发表于 2020-6-13 00:09
我建了个群，里面有几个人在刷，我们都是从二月就开始刷的，一起吗？

求加群~~~ zszszs

6/13 https://leetcode.com/problems/largest-divisible-subset/

1. var largestDivisibleSubset = function(nums) {
   
2.     if(!nums || nums.length < 2) return nums;
   
3.     nums.sort((a,b) => a-b);
   
4.     let cache = [[nums[0]]], res = [];
   
5.    
   
6.     var getLargestDivisibleSubset = function(i) {
   
7.         if(cache[i]) return cache[i];
   
8.         let temp = [];
   
9.         for(let j=0; j<i; j++) {
   
10.             if(nums[i] % nums[j] === 0) {
    
11.                 let prev = getLargestDivisibleSubset(j);
    
12.                 if(prev.length > temp.length) temp = [...prev];
    
13.             }
    
14.         }
    
15.         temp.push(nums[i]);
    
16.         if(temp.length > res.length) res = temp;
    
17.         cache[i] = temp;
    
18.     }
    
19.    
    
20.     for(let i=1; i<nums.length; i++) {
    
21.         getLargestDivisibleSubset(i);
    
22.     }
    
23.     return res;
    
24. };

复制代码

T: O(n^2);
S: O(n^2);

动态规划问题，lz一直在找O(n)的解法，后来发现想多了= = 一个重点是要先排序，不然各种情况考虑起来很复杂。而且O(n^2)的话排序本身也不会成为bottleneck。还有一种省空间的算法，相对更负责：

1. var largestDivisibleSubset = function(nums) {
   
2.     if(!nums || nums.length < 2) return nums;
   
3.     nums.sort((a,b) => a-b);
   
4.     let arr = [1], longest = 1, longestIdx = 0;
   
5.     for(let i=1; i<nums.length; i++) {
   
6.         arr[i] = 1;
   
7.         for(let j=i-1; j>=0; j--) {
   
8.             if(nums[i] % nums[j] === 0) {
   
9.                 arr[i] = Math.max(arr[i], arr[j]+1);
   
10.             }
    
11.         }
    
12.         if(arr[i] > longest) {
    
13.             longest = arr[i];
    
14.             longestIdx = i;
    
15.         }
    
16.     }
    
17.     let res = [], dividend = nums[longestIdx];
    
18.     while(longest >= 0 && longestIdx >= 0) {
    
19.         if(dividend % nums[longestIdx] === 0 && arr[longestIdx] === longest){
    
20.             res.push(nums[longestIdx]);
    
21.             longest--;
    
22.         }
    
23.         longestIdx--;
    
24.     }
    
25.     return res;
    
26. };

复制代码

T: O(n^2);
S; O(n);

6/14 https://leetcode.com/problems/cheapest-flights-within-k-stops/
又是动规 果然周末的题都比较难吗。。。

1) DFS w/ Memorization 注意要存进cache的是src + k而不是src+dst，lz在这里浪费了好多时间 ==

1. var findCheapestPrice = function(n, flights, src, dst, K) {
   
2.     if(!n || !flights || !flights.length) return 0;
   
3.     const flightsArr = [...Array(n).keys()].map(key => new Array(n));
   
4.     for(let i=0; i<flights.length; i++) {
   
5.         const [s, d, p] = flights[i];
   
6.         flightsArr[s][d] = p;
   
7.     }
   
8.     let cache = [...Array(n).keys()].map(key => new Array(K));
   
9.     var findCheapestPriceHelper = function(s, d, k) {
   
10.         if(s === d) return 0;
    
11.         if(!k) return flightsArr[s][d] || Number.MAX_SAFE_INTEGER;
    
12.         if(cache[s][k]) return cache[s][k];
    
13.         let min = Number.MAX_SAFE_INTEGER;
    
14.         for(let j=0; j<n; j++) {
    
15.             if(flightsArr[s][j]) {
    
16.                 min = Math.min(min, flightsArr[s][j] + findCheapestPriceHelper(j, d, k-1));
    
17.             }
    
18.         }
    
19.         cache[s][k] = min;
    
20.         return min;
    
21.     }
    
22.     let res = findCheapestPriceHelper(src, dst, K);
    
23.     return res === Number.MAX_SAFE_INTEGER ? -1 : res;
    
24. };

复制代码

Time: O(|F| + n^2*k);
Space: O(n^2 + n * k);

2) Dijkstra Algorithm
JS没有内置的堆伤不起，每次都要辛辛苦苦自己写。这里跟普通Dijkstra不太一样的是不仅需要比较price，如果某个城市的stop比之前遍历过的要少的话也要重新加进堆里，而且注意在更新visited数组时，只更新stop/price到更小的值，不要两个一起更新不然会把一些不不要的组合加入堆里导致超时（别问我为什么知道==)

1. var findCheapestPrice = function(n, flights, src, dst, K) {
   
2.     if(!n || !flights || !flights.length) return 0;
   
3.     const flightsArr = new Array(n);
   
4.     for(let i=0; i<flights.length; i++) {
   
5.         const [s, d, p] = flights[i];
   
6.         if(!flightsArr[s]) flightsArr[s] = {};
   
7.         flightsArr[s][d] = p;
   
8.     }
   
9.     let visited = new Array(n), stop=0, res = Number.MAX_SAFE_INTEGER;
   
10.     visited[src] = [0, 0]; // [stop, price]
    
11.     let mh = new minHeap();
    
12.     mh.push([0, -1, src]);
    
13.     while(mh.size >0) {
    
14.         const [price, stop, city] = mh.pop();
    
15.         if(city == dst) res = Math.min(res, price);
    
16.         else if(stop<K && flightsArr[city]) {
    
17.             Object.entries(flightsArr[city]).forEach(([d, p]) => {
    
18.                 if(visited[d] && visited[d][0] <= stop+1 && visited[d][1] <= price+p) return;
    
19.                 if(!visited[d]) visited[d] = [stop+1, price+p];
    
20.                 else {
    
21.                     visited[d][1] = Math.min(price+p, visited[d][1]);
    
22.                     visited[d][0] = Math.min(stop+1, visited[d][0]);
    
23.                 }   
    
24.                 mh.push([price+p, stop+1, d]);
    
25.             })
    
26.         }
    
27.     }
    
28.     return res === Number.MAX_SAFE_INTEGER ? -1 : res;
    
29. };
    
30. 
    
31. class minHeap {
    
32.     constructor() {
    
33.         this.list = [];
    
34.         this.size = 0;
    
35.     }
    
36.    
    
37.     push(val) {
    
38.         this.list.push(val);
    
39.         this.siftUp(val, this.size);
    
40.         this.size++;
    
41.     }
    
42.    
    
43.     siftUp(val, pos) {
    
44.         let parent = Math.floor((pos-1)/2);
    
45.         while(parent >= 0 && val[0] < this.list[parent][0]) {
    
46.             this.list[pos] = this.list[parent];
    
47.             pos = parent;
    
48.             parent = Math.floor((pos-1)/2);
    
49.         }
    
50.         this.list[pos] = val;
    
51.     }
    
52.    
    
53.     pop() {
    
54.         let res = this.list[0];
    
55.         this.size--;
    
56.         this.list[0] = this.list[this.size];
    
57.         this.list.pop();
    
58.         if(this.size > 1) this.siftDown(this.list[0], 0);
    
59.         return res;
    
60.     }
    
61.    
    
62.     siftDown(val, pos) {
    
63.         let child = 2 * pos + 2 < this.size && this.list[2*pos+2][0] < this.list[2*pos+1][0] ? 2*pos+2 : 2*pos+1;
    
64.         while(child<this.size && this.list[child]<this.list[pos]) {
    
65.             this.list[pos] = this.list[child];
    
66.             pos = child;
    
67.             child = 2 * pos + 2 < this.size && this.list[2*pos+2][0] < this.list[2*pos+1][0] ? 2*pos+2 : 2*pos+1;
    
68.         }
    
69.         this.list[pos] = val;
    
70.     }
    
71. }

复制代码

T: O((|F|+n) * logn);
S: O(n ^ 2);

感觉Graph问题的Complexity还是有点tricky的，不知道大家有什么好的方法吗？

6/15 https://leetcode.com/problems/search-in-a-binary-search-tree/
周一例行easy，一开始没看清是BST，不过修改之后似乎也没有快多少。。

1) Recursion

1. var searchBST = function(root, val) {
   
2.     if(!root || root.val === val) return root;
   
3.     return val < root.val
   
4.         ? searchBST(root.left, val)
   
5.         : searchBST(root.right, val);
   
6. };

复制代码

T: O(H)
S: O(H)

2) Iteration

1. var searchBST = function(root, val) {
   
2.     while(root && root.val !== val) {
   
3.         root = val < root.val ? root.left : root.right, val
   
4.     }
   
5.     return root;
   
6. };

复制代码

T: O(H)
S: O(1)