June LeetCoding Challenge

前两个月的challenge都是差一两天就全勤了，六月再努力一把吧（可是LC这奖品也太不吸引人了）

megrez 发表于 2020-6-4 20:24
前两个月的challenge都是差一两天就全勤了，六月再努力一把吧（可是LC这奖品也太不吸引人了）

lz前俩月都是一开始刷的很勤快，一般刚过12点就会把第二天的刷掉，然后月中某天一旦开始掉链子就放弃治疗了😂

Random Pick with Weight

这题目的input output是什么意思...不明白为什么专门选这种奇怪的题目 600+赞 1600踩
=======================================
我好像看懂了，solution是初始化，然后后面几个pickindex就是sample了几次；
第二行第一个就是weight vector，后面的都不用管
output和第一行对应，第一个对应初始化不用管，后面的是每次sample出来的数字（被sample的数字应该就是index）

鸡籽就是大王 发表于 2020-6-5 07:10
Random Pick with Weight

这题目的input output是什么意思...不明白为什么专门选这种奇怪的题目 600+赞  ...

题目真的写得很不清楚，看懂了input output，但是想了半天没明白啥叫` in proportion to its weight`。神奇的是在解析里面看完一大段废话之后第一句就秒懂了，真的无语

btw现在已经2000+ down votes了🙃

Reborn2beCoder 发表于 2020/06/06 14:03:19
题目真的写得很不清楚，看懂了input output，但是想了半天没明白啥叫` in proportion to its...

我也down vote了，相当沙币的一道题

6/5 https://leetcode.com/problems/random-pick-with-weight/
跟楼上的几位同学一样，花了些工夫理解题目究竟想问啥。最后使用了二分搜索，值得注意的是这里如果`this.weights[m] === r`的情况下，应该返回的是m+1而不是m，因为第一个Index对应的区间应该是[0, this.weights[0])，注意右边是开区间，然后以此类推。lz因为这个原因在第54个test case卡了好久（差点错过ddl），手动测试了前100次
pickIndex也都能通过，一度以为test case有bug。最后想通了发现也是make sense，感叹一下leetcode的test还是非常严苛的。

1. /**
   
2. * @param {number[]} w
   
3. */
   
4. var Solution = function(w) {
   
5.     this.weights = [], sum = 0;
   
6.     for(let i=0; i<w.length; i++) {
   
7.         sum += w[i];
   
8.         this.weights[i] = sum;
   
9.     }
   
10.     this.total = sum;
    
11. };
    
12. 
    
13. /**
    
14. * [url=home.php?mod=space&uid=160137]@return[/url] {number}
    
15. */
    
16. Solution.prototype.pickIndex = function() {
    
17.     const r = parseInt(Math.random() * this.total);
    
18.     let s = 0, e = this.weights.length-1;
    
19.     while(s<e) {
    
20.         const m = parseInt((s+e)/2);
    
21.         if(this.weights[m] > r) e = m;
    
22.         else s = m + 1
    
23.     }
    
24.     return s;
    
25. };

复制代码

6/6 星期六 (非常6的一个日子）https://leetcode.com/problems/queue-reconstruction-by-height/

感觉题目还是有点tricky的，一开始不看hint完全没思路，看完之后先是写出了如下解法：

1. vvar reconstructQueue = function(people) {
   
2.     if(!people || people.length < 2) return people;
   
3.     people.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
   
4.     let remaining = [...Array(people.length).keys()], res = new Array(people.length);
   
5.     while(people.length) {
   
6.         let ppl = people.shift();
   
7.         let idx = remaining[ppl[1]];
   
8.         remaining.splice(ppl[1], 1);
   
9.         res[idx] = ppl;
   
10.     }
    
11.     return res;

复制代码

再看答案的时候才发现hint似乎具有误导性，因为如果从shortest开始排的话就需要类似如上remaining的一个array来记录已经填充的位置，而如果从tallest开始的话则会更简单，这里的关键是 `The smaller persons are "invisible" for the taller ones`（哎，矮个子的忧桑）：

1. var reconstructQueue = function(people) {
   
2.     if(!people || people.length < 2) return people;
   
3.     people.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]);
   
4.     const res = [];
   
5.     people.forEach(ppl => {
   
6.         res.splice(ppl[1], 0, ppl);
   
7.     })
   
8.     return res;
   
9. };

复制代码

最后的空间复杂度为O(n)，时间复杂度则取决于JS当中Array.splice()的实现，如果使用Linkedlist的话应当为O(1)，则整个算法的复杂度为O(nlogn + n) = O(nlogn); 但如果使用普通数组实现的话splice为O(n)，最后的时间复杂度变成O(nlogn + n^2) = O(n^2)

6/7 https://leetcode.com/problems/coin-change-2/ 第一周的最后一天，大家加油呀~~~！
lz先写了coin change再来做这个，结果思路受到了误导，一开始写了个backtrack（因为按照I的思路只用DP已经无法解决了），结果amount太大的时候会超时。后来无奈偷偷查看了答案，发现这两题的本质区别在于，虽然同是动态规划，但是如果以amount序列为横坐标的话，I的纵坐标为coin count，而II的纵坐标为combinations（一定要看清问题当中的落脚点在哪里），而且要把各种coin一层一层依次叠加上去，这里因为需要去重，并不适合I当中一开始就各种coin大乱炖的解法。

1. var change = function(amount, coins) {
   
2.     let count = Array(amount+1).fill(0);
   
3.     count[0] = 1;
   
4.     coins.forEach(coin => {
   
5.         for(let i=coin; i<amount+1; i++) {
   
6.             count[i] += count[i-coin];
   
7.         }
   
8.     })
   
9.     return count[amount];
   
10. };

复制代码

T: O(amount * coins.length)
S: O(amount)
由衷的感慨一下DP真的太强大了，可以用如此精简的代码解决这么复杂的问题，希望有朝一日可以充分掌握它，写题的时候不用再偷偷看答案 😅[/i]

6/8 https://leetcode.com/problems/power-of-two/
周一例行Easy
1) recursion O(logn)

1. var isPowerOfTwo = function(n) {
   
2.     if(n <= 0) return false;
   
3.     if(n <= 2) return true;
   
4.     if(n % 2) return false;
   
5.     return isPowerOfTwo(n/2);
   
6. };

复制代码

2) Iteration O(logn)

1. var isPowerOfTwo = function(n) {
   
2.     if(n <= 0) return false;
   
3.     while(n%2 === 0) {
   
4.         n = n/2;
   
5.     }
   
6.     return n === 1;
   
7. };

复制代码

3) Bit manipulation O(1)

1. var isPowerOfTwo = function(n) {
   
2.     return n>0 && (n & (n-1)) == 0;
   
3. };

复制代码

不知道是不是所有的算法都很快的缘故，感觉Runtime Distribution很不make sense...

6/9 https://leetcode.com/problems/is-subsequence/
双指针经典题目

1. var isSubsequence = function(s, t) {
   
2.     if(s.length > t.length) return false;
   
3.     let i = j = 0;
   
4.     while(i<s.length && j<t.length) {
   
5.         if(s[i] === t[j]) i++;
   
6.         j++;
   
7.     }
   
8.     return i === s.length;
   
9. };

复制代码

T: O(t.length)
S: O(1)