June LeetCoding Challenge

求组队，欢迎加群~~可以加我微信 a1a1a11a

我咋感觉最近的June Challenge 越来越难了……

a_ryerson 发表于 2020-6-21 06:15
我咋感觉最近的June Challenge 越来越难了……

是的哎，这两天稍微好一点

AAAlllen 发表于 2020-6-21 01:43
求组队，欢迎加群~~可以加我微信 a1a1a11a

哈哈一起刷呀~~ 你有群吗？

6/21 https://leetcode.com/problems/dungeon-game/
1) Greedy
lz辛辛苦苦实现了最大堆（JS啥时候才可以实现堆自由？），从左上角开始使用贪心算法找到所需hp最少的路径并记录最低hp，最后如果hp为负则取绝对值再加一，如果是正则直接返回1。虽然workable但是时间复杂度惨不忍睹：

1. class MaxHeap {
   
2.     constructor() {
   
3.         this.list = [];
   
4.         this.size = 0;
   
5.     }
   
6.    
   
7.     push(ele) {
   
8.         this.siftUp(ele, this.size);
   
9.         this.size++;
   
10.     }
    
11.    
    
12.     siftUp(ele, pos) {
    
13.         let parent = Math.floor((pos-1)/2);
    
14.         while(parent >=0 && this.list[parent][0] < ele[0]) {
    
15.             this.list[pos] = this.list[parent];
    
16.             pos = parent;
    
17.             parent = Math.floor((pos-1)/2);
    
18.         }
    
19.         this.list[pos] = ele;
    
20.     }
    
21.    
    
22.     pop() {
    
23.         const res = this.list[0];
    
24.         this.list[0] = this.list[--this.size];
    
25.         this.list.pop();
    
26.         if(this.size) this.siftDown(this.list[0], 0);
    
27.         return res;
    
28.     }
    
29.    
    
30.     siftDown(ele, pos) {
    
31.         let child = 2*pos+2 < this.size && this.list[2*pos+2][0] > this.list[2*pos+1][0]
    
32.             ? 2*pos+2
    
33.             : 2*pos+1;
    
34.         while(child < this.size && this.list[child][0] > ele[0]) {
    
35.             this.list[pos] = this.list[child];
    
36.             pos = child;
    
37.             child = 2*pos+2 < this.size && this.list[2*pos+2][0] > this.list[2*pos+1][0]
    
38.                 ? 2*pos+2
    
39.                 : 2*pos+1;
    
40.         }
    
41.         this.list[pos] = ele;
    
42.     }
    
43. }
    
44. 
    
45. /**
    
46. * @param {number[][]} dungeon
    
47. * [url=home.php?mod=space&uid=160137]@return[/url] {number}
    
48. */
    
49. var calculateMinimumHP = function(dungeon) {
    
50.     if(!dungeon || !dungeon.length) return 0;
    
51.     const mh = new MaxHeap(), HEIGHT = dungeon.length, WIDTH = dungeon[0].length;
    
52.     const flag = [...Array(HEIGHT).keys()].map(key => new Array(WIDTH));
    
53.     let min = Number.MAX_SAFE_INTEGER;
    
54.     flag[0][0] = dungeon[0][0];
    
55.     mh.push([dungeon[0][0], 0, 0]);
    
56.     while(mh.size) {
    
57.         const [hp, row, col] = mh.pop();
    
58.         min = Math.min(min, hp);
    
59.         if(row === HEIGHT-1 && col === WIDTH-1) return min < 0 ? min*-1 + 1 : 1;
    
60.         if(row < HEIGHT-1 && (!flag[row+1][col] || hp+dungeon[row+1][col] > flag[row+1][col])) {
    
61.             flag[row+1][col] = hp+dungeon[row+1][col];
    
62.             mh.push([hp+dungeon[row+1][col], row+1, col]);
    
63.         }
    
64.         if(col < WIDTH-1 && (!flag[row][col+1] || flag[row][col+1] < hp+dungeon[row][col+1])) {
    
65.             flag[row][col+1] = hp+dungeon[row][col+1];
    
66.             mh.push([hp+dungeon[row][col+1], row, col+1]);
    
67.         }
    
68.     }
    
69. };

复制代码

T: O(m * n * log(m*n)) (由于有些cell会多次处理(从另一个角度出发需要hp更小时)有可能会更差，但大致是这个scale
S: O(m * n) (flag matrix + max heap)

2) Dynamic Programming
从最后一格开始往回倒，求在每个位置想要到达终点所需的最小hp。除了最后一行/列需要特殊处理之外，在每个格子通过选取下方和右方的最小值作为离开当前格子需要的hp，再参照当前格子的值（如果大于离开时需要的，则进入时只需要最少hp 1，如果小于离开时需要的，则需要补上差值）：

1. var calculateMinimumHP = function(dungeon) {
   
2.     if(!dungeon || !dungeon.length) return 0;
   
3.     const HEIGHT = dungeon.length, WIDTH = dungeon[0].length;
   
4.     const hp = new Array(WIDTH);
   
5.     for(let i=HEIGHT-1; i>=0; i--) {
   
6.         for(let j=WIDTH-1; j>=0; j--) {
   
7.             let bottom = i === HEIGHT-1 ? Number.MAX_SAFE_INTEGER : hp[j];
   
8.             let right = j === WIDTH-1 ? Number.MAX_SAFE_INTEGER : hp[j+1];
   
9.             let next = Math.min(bottom, right) === Number.MAX_SAFE_INTEGER ? 1 : Math.min(bottom, right);
   
10.             hp[j] = Math.max(next - dungeon[i][j], 1);
    
11.         }
    
12.     }
    
13.     return hp[0];
    
14. };

复制代码

T: O(m * n)
S: O(m) (optimized with the circular queue)
相比之下不管是代码还是复杂度都简化了不要太多，但是真的不太能想通为什么一定要倒着往回算，而用同样的思路从起点开始的话就是各种坑，lz尝试调了几次最终还是放弃了。遇到这种题除了死记硬背之外还有别的可以找到最佳解法的切入点吗？

6/22 https://leetcode.com/problems/single-number-ii/
lz一上来被线性还不让用extra memory吓傻了，直接放弃了哈希开始尝试各种奇技淫巧，但大多不是linear，再回头看才发现线性才是硬性要求，no extra memory只是一个challenge，所以一定要看清楚题目要求，千万不能舍本求末😪

1)HashMap 这个应该是最直接的了：

1. var singleNumber = function(nums) {
   
2.     if(!nums || !nums.length) return 0;
   
3.     let start = 0, map = new Map();
   
4.     while(start < nums.length) {
   
5.         let num = nums[start];
   
6.         if(!map.has(num)) map.set(num, 1);
   
7.         else map.set(num, map.get(map)+1);
   
8.         start++;
   
9.     }
   
10.     let res;
    
11.     map.forEach((val, key) => {
    
12.         if(val === 1) res = key;
    
13.     });
    
14.     return res;
    
15. };

复制代码

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

2) Hash set 用set当中数字之和的三倍减去数组数字之和再除2。虽然乍一看以为会简化，由于JS里面没有很简单可以直接求数组/集合当中所有数字之和的算法，但是代码量并没有太大区别：

1. var singleNumber = function(nums) {
   
2.     if(!nums || !nums.length) return 0;
   
3.     let start = sum1 = sum2 = 0, set = new Set();
   
4.     while(start < nums.length) {
   
5.         let num = nums[start];
   
6.         if(!set.has(num)) {
   
7.             sum1 += num;
   
8.             set.add(num)
   
9.         }
   
10.         sum2 += num;
    
11.         start++;
    
12.     }
    
13.     return (sum1 * 3 - sum2) / 2;
    
14. };

复制代码

T: O(n) 与hashmap相比这个只需要过一次，但是scale是一样的
S: O(n)

3) Quick select
由于每次选取pivot之后可以排除掉一半的选项（左右两边是3的倍数的那一边），所有avg复杂度可以降到O(n)，但是要注意pivot一定要随机选取，lz一开始默认取当前区间的第一个值，结果悲剧的陷入了死循环。。。

1. var singleNumber = function(nums) {
   
2.     if(!nums || !nums.length) return 0;
   
3.     return singleNumberHelper(nums, 0, nums.length-1);
   
4. };
   
5. 
   
6. var singleNumberHelper = function(nums, start, end) {
   
7.     if(start === end) return nums[start];
   
8.     const random = start + Math.floor(Math.random() * (end-start));
   
9.     const pivot = nums[random];
   
10.     let s = start, e = end;
    
11.     while(s <= e) {
    
12.         if(nums <= pivot) s++;        else if(nums[e] > pivot) e--;
    
13.         else [nums[s++], nums[e--]] = [nums[e], nums];
    
14.     }
    
15.     let pos = nums <= pivot ? s+1 : s;
    
16.     if(!((pos - start) % 3)) start = pos;
    
17.     else end = pos-1;
    
18.     return singleNumberHelper(nums, start, end);
    
19. }

复制代码

T: O(n) (Worst case O(n^2))
S: O(1)

4) Bit Manipulation
吊是吊，但是面试当中真的想得出来吗。。。

1. var singleNumber = function(nums) {
   
2.     if(!nums || !nums.length) return 0;
   
3.     let once = twice = start = 0;
   
4.     while(start < nums.length) {
   
5.         once = ~twice & (once ^ nums[start]);
   
6.         twice = ~once & (twice ^ nums[start++]);
   
7.     }
   
8.     return once;
   
9. };
   

复制代码

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

每天都在刷哦！大家加油呀！