June LeetCoding Challenge

6/16 https://leetcode.com/problems/validate-ip-address/
每次看到RegEx就头疼，这次也不例外
1) Divide and conquer

1. var validIPAddress = function(IP) {
   
2.     if(IP.split('.').length === 4 && isValidIPv4Address(IP.split('.'))) return 'IPv4';
   
3.     else if(IP.split(':').length === 8 && isValidIPv6Address(IP.split(':'))) return 'IPv6';
   
4.     return 'Neither';
   
5. };
   
6. 
   
7. var isValidIPv4Address = function(IPArr) {
   
8.     for(let i=0; i<IPArr.length; i++){
   
9.         let Adr = IPArr[i];
   
10.         if(Adr === '') return false;
    
11.         if(Adr<0 || Adr>255) return false;
    
12.         if(Adr.length > 1 && Adr[0] == '0') return false;
    
13.         if(/[^0-9]/.test(Adr)) return false;
    
14.     }
    
15.     return true;
    
16. }
    
17. 
    
18. var isValidIPv6Address = function(IPArr) {
    
19.     for(let i=0; i<IPArr.length; i++) {
    
20.         let Adr = IPArr[i];
    
21.         if(Adr === '') return false;
    
22.         if(Adr.length > 4) return false;
    
23.         if(/[^0-9A-Fa-f]/.test(Adr)) return false;
    
24.     }
    
25.     return true;
    
26. }

复制代码

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

2) RegEx 看着LC上的答案纠结了好久重复的部分要怎么处理，因为JS不支持regex variable，直到看到了了一个惊为天人的解法

1. var validIPAddress = function(IP) {
   
2.     if(/^((\d|[1-9]\d|1\d\d|2([0-4]\d|5[0-5])).){4}$/.test(IP+'.')) return 'IPv4';
   
3.     if(/^(([\dA-F]{1,4}):){8}$/i.test(IP+':')) return 'IPv6';
   
4.     return 'Neither';
   
5. };

复制代码

T: O(1);
S: O(1);

希望有朝一日lz写起regex也可以有如信手拈来🙏

楼主不更新了吗？今天这道hash还挺难的

megrez 发表于 2020/06/20 11:31:21
楼主不更新了吗？今天这道hash还挺难的

目前我看到三种方法，
第一种二分法加Robin carp，
第二种suffix array+lcp 我按Coursera UCSD的倍增算法做的，Lcp用的kasai
第三种Trie，应该和suffix array差不多，讨论中有看到。
不管怎么说，这道hard题挺值的(ง •̀_•́)ง

zyshmie 发表于 2020/06/20 20:58:30
目前我看到三种方法，
第一种二分法加Robin carp，
第二种suffix array+lcp 我按Coursera...

同意 哪种解法都不简单

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

你好，想加群， 谢谢

6/17 https://leetcode.com/problems/surrounded-regions/

1) BFS + flag matrix 老老实实找需要被翻牌的:

1. var solve = function(board) {
   
2.     if(!board || !board.length) return;
   
3.     const HEIGHT = board.length, WIDTH = board[0].length;
   
4.     const flag = [...Array(HEIGHT).keys()].map(key => Array(WIDTH).fill(0));
   
5.     for(let i=0; i<HEIGHT; i++) {
   
6.         for(let j=0; j<WIDTH; j++) {
   
7.             if(flag[i][j]) continue;
   
8.             if(board[i][j] === 'X') {
   
9.                 flag[i][j] = 1;
   
10.                 continue;
    
11.             }
    
12.             let queue = [], neighbors = [], surrounded = true;
    
13.             flag[i][j] = 1;
    
14.             queue.push([i, j]);
    
15.             while(queue.length) {
    
16.                 let temp = [];
    
17.                 neighbors = [...neighbors, ...queue];
    
18.                 for(let k=0; k<queue.length; k++) {
    
19.                     const [row, col] = queue[k];
    
20.                     if(!row) surrounded = false;
    
21.                     else if(!flag[row-1][col] && board[row-1][col] === 'O') {
    
22.                         flag[row-1][col] = 1;
    
23.                         temp.push([row-1, col]);
    
24.                     }
    
25.                     if(row === HEIGHT-1) surrounded = false;
    
26.                     else if(!flag[row+1][col] && board[row+1][col] === 'O') {
    
27.                         flag[row+1][col] = 1;
    
28.                         temp.push([row+1, col]);
    
29.                     }
    
30.                     if(!col) surrounded = false;
    
31.                     else if(!flag[row][col-1] && board[row][col-1] === 'O') {
    
32.                         flag[row][col-1] = 1;
    
33.                         temp.push([row, col-1]);
    
34.                     }
    
35.                     if(col === WIDTH-1) surrounded = false;
    
36.                     else if(!flag[row][col+1] && board[row][col+1] === 'O') {
    
37.                         flag[row][col+1] = 1;
    
38.                         temp.push([row, col+1]);
    
39.                     }
    
40.                 }
    
41.                 queue = temp;
    
42.             }
    
43.             if(surrounded) neighbors.forEach(([r, c]) => board[r][c] = 'X');
    
44.         }
    
45.     }
    
46. };

复制代码

T: O(m * n)
S: O(m * n)

2) DFS w/ Optiomization 重点是要从边缘开始做dfs, 先mark出不应该被翻的再进行二次处理：

1. var solve = function(board) {
   
2.     if(!board || !board.length) return;
   
3.     const HEIGHT = board.length, WIDTH = board[0].length;
   
4.     if(HEIGHT < 3 || WIDTH < 3) return;
   
5.     const queue = [];
   
6.     for(let i=0; i<HEIGHT; i++) {
   
7.         if(board[i][0] === 'O') dfs(board, i, 0);
   
8.         if(board[i][WIDTH-1] === 'O') dfs(board, i, WIDTH-1);
   
9.     }
   
10.     for(let j=1; j<WIDTH-1; j++) {
    
11.         if(board[0][j] === 'O') dfs(board, 0, j);
    
12.         if(board[HEIGHT-1][j] === 'O') dfs(board, HEIGHT-1, j);
    
13.     }
    
14.     for(let i=0; i<HEIGHT; i++) {
    
15.         for(let j=0; j<WIDTH; j++) {
    
16.             if(board[i][j] === 'A') board[i][j] = 'O';
    
17.             else if(board[i][j] === 'O') board[i][j] = 'X';
    
18.         }
    
19.     }
    
20. };
    
21. 
    
22. var dfs = function(board, row, col) {
    
23.     if(board[row][col] !== 'O') return;
    
24.     board[row][col] = 'A';
    
25.     if(row) dfs(board, row-1, col);
    
26.     if(row !== board.length-1) dfs(board, row+1, col);
    
27.     if(col) dfs(board, row, col-1);
    
28.     if(col !== board[0].length-1) dfs(board, row, col+1);
    
29. }

复制代码

T: O(m * n)
S: worst-case O(m * n)

megrez 发表于 2020-6-19 19:31
楼主不更新了吗？今天这道hash还挺难的

以为没人看最近更的有点慢。。看来要继续加油了Lol

6/18 https://leetcode.com/problems/h-index-ii/

有点Tricky的二分搜索，lz写出的第一版非常之messy，在该return value还是index之间举棋不定（可能是因为给出的例子刚好value = index，所有有点混，一直在想[0,1,3,5,6]和[0,1,3,5,6,7]的情况下都应该return 3要怎么做到），还被各种比如[0], [100], [0, 0]之类的corner case弄得晕头转向。一看答案才发现原来solution可以如此elegent，看来自己还是没有掌握到二分查找的精髓。。

1. var hIndex = function(citations) {
   
2.     if(!citations || !citations.length) return 0;
   
3.     const LEN = citations.length;
   
4.     let start = 0, end = LEN-1;
   
5.     while(start<=end) {
   
6.         let mid = parseInt((start+end)/2);
   
7.         let rank = LEN-mid;
   
8.         if(citations[mid] == rank) return rank;
   
9.         else if(citations[mid] < rank) start = mid+1;
   
10.         else end = mid-1;
    
11.     }
    
12.     return LEN-start;
    
13. };

复制代码

T: O(logn)
S: O(1)

6/19 https://leetcode.com/problems/longest-duplicate-substring/

Hard得心服口服，第一次学习Rabin-Karp 's algorithm。一开始自己写了个非常naive的方法是先比较每个subStr的charCode之和，如果相同的话再进行深入比较。然后不出意外的在字符串超级长的时候timeout了。

然后放弃挣扎开始看答案，答案里面各种变量名取得一点都不好，花了些工夫才弄清究竟啥是啥（于是将心比心，以后也要认真写变量名），一开始还存着侥幸心理想说不用modulus行不行，跑了几个test case之后发现真的是低估了这个字符串可以长到什么程度。

最后没办法，老老实实看着答案一行一行把python翻译成js，然后居然，还是通不过？！👀都快看瞎了也找不出哪里有问题，然后看了一眼Java version才发现有个非常恶心的overflow(详情可以参照这里)，感觉不看答案永远做不出来的那种。。

不过话又说回来，还是学到了不少东西，比如可以通过二分搜索找满足特定条件的最长子数组（这里的重点：如果长度n满足的话，n-1一定也成立），比如如何写出一个旋转哈希（重点：可以提前求出a的L次方然后反复使用），比如处理“大数据”的时候一定要取模，而且只对结果取还不够，每一个小的step都有可能overflow（在这种情况下连Math.pow都不能直接用，必须每一步lPow = (lPow * base) % modulus）

总之一句话，妥妥的被被这个数量级的字符串降维打击到(╥╯^╰╥)

1. var longestDupSubstring = function(S) {
   
2.     if(!S || S.length < 2) return "";
   
3.     const LEN = S.length, AChar = 'a'.charCodeAt(0), charCodes = [], modulus = Math.pow(2, 32);
   
4.    
   
5.     var findDupSubstringOfLength = function(l) {
   
6.         let charCodeSum = [0], hash = 0, lPow = 1, base = 26;
   
7.         for(let i=0; i<l; i++) {
   
8.             hash = (hash * base + charCodes[i]) % modulus;
   
9.             lPow = (lPow * base) % modulus;
   
10.         }
    
11.         const seen = new Set();
    
12.         seen.add(hash);
    
13.         for(let j=1; j<=LEN-l; j++) {
    
14.             hash = (hash * base - charCodes[j-1] * lPow + base*modulus) % modulus;
    
15.             hash = (hash + charCodes[j+l-1]) % modulus;
    
16.             if(seen.has(hash)) return S.slice(j, j+l);
    
17.             seen.add(hash);
    
18.         }
    
19.         return '';
    
20.     }
    
21.    
    
22.     for(let i=0; i<LEN; i++) {
    
23.         charCodes.push(S.charCodeAt(i)-AChar);
    
24.     }
    
25.    
    
26.     let start = 1; end = S.length, res = "";
    
27.     while(start <= end) {
    
28.         const mid = start + Math.floor((end-start)/2);
    
29.         const subStr = findDupSubstringOfLength(mid);
    
30.         if(subStr.length) {
    
31.             res = subStr;
    
32.             start = mid+1;
    
33.         } else end = mid-1;
    
34.     }
    
35.     return res;
    
36. };

复制代码

T: O(|S| * log|S|)
S: O(|S|)
[/i]

6/20 https://leetcode.com/problems/permutation-sequence/
这周被连续打击了许多天，终于有一题仅凭一己之力写出来了😂

1. var getPermutation = function(n, k) {
   
2.     if(!n || !k) return "";
   
3.     let res = [], i=1, arr = [...Array(n).keys()].map(key => key+1);
   
4.     const permNumCache = [1];
   
5.    
   
6.     while(i < n) {
   
7.         permNumCache[i] = i*permNumCache[i-1];
   
8.         i++;
   
9.     }
   
10.    
    
11.     var getPermutationHelper = function(arr, k, res) {
    
12.         if(!arr.length) return;
    
13.         let segment = permNumCache[arr.length-1];
    
14.         let idx = parseInt((k-1)/segment);
    
15.         res.push(arr[idx]);
    
16.         arr.splice(idx, 1)
    
17.         getPermutationHelper(arr, k-idx*segment, res);
    
18.     }
    
19.    
    
20.     getPermutationHelper(arr, k, res);
    
21.     return res.join('');
    
22. };

复制代码

T: O(n^2) 而不是 O(n)，因为用到了splice
S: O(n)