June LeetCoding Challenge

有没有小伙伴想组队一起刷？

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

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

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也可以有如信手拈来🙏

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/1 [儿童节快乐] 刷鲨鱼一时爽，刷题火葬场，直到11点才开动，还好题不难。

1) Recursion. Time: O(n); Space: stack cost, O(logn) for best(full binary tree) & O(n) for worst (single chain)

1. var invertTree = function(root) {
   
2.     if(!root || !root.left && !root.right) return root;
   
3.     [node.left, node.right] = [node.right, node.left];
   
4.     invertTree(root.left);
   
5.     invertTree(root.right);
   
6.     return root;
   
7. };

复制代码

2) Iteration. Time: O(n); Space: storage cost, O(n) for worst(full binary tree, which actually would be O(n/2) & O(1) for best(single chain)

1. var invertTree = function(root) {
   
2.     if(!root || !root.left && !root.right) return root;
   
3.     let queue = [root];
   
4.     while(queue.length) {
   
5.         let node = queue.shift();
   
6.         [node.left, node.right] = [node.right, node.left];
   
7.         if(node.left) queue.push(node.left);
   
8.         if(node.right) queue.push(node.right);
   
9.     }
   
10.     return root;
    
11. };

复制代码

然鹅只跑赢了28.96%的JS玩家，不知道有什么更好的解法吗？




补充内容 (2020-6-3 12:21):
题目链接：https://leetcode.com/problems/invert-binary-tree/

1. class Solution:
   
2.     def deleteNode(self, node):
   
3.         """
   
4.         :type node: ListNode
   
5.         :rtype: void Do not return anything, modify node in-place instead.
   
6.         """
   
7.         node.val=node.next.val
   
8.         node.next=node.next.next

复制代码

最开始写了个循环到底，结果发现两次操作就可以了。。。

我我我我！

machecazzo 发表于 2020-6-2 17:55
[mw_shl_code=python,true]class Solution:
    def deleteNode(self, node):
        """

力口怎么选题的。。。这题downvotes有六千多

shawn_lyu 发表于 2020-6-3 06:00
力口怎么选题的。。。这题downvotes有六千多

每次Daily challenge感觉前几天的题都挺水的，标准很迷的Easy题……

ichwaredu 发表于 2020-6-3 02:44
我我我我！

来来来！

machecazzo 发表于 2020-6-3 10:52
每次Daily challenge感觉前几天的题都挺水的，标准很迷的Easy题……

不能更同意

欢迎大家互相加分互相鼓励~~~

machecazzo 发表于 2020-6-2 17:55
[mw_shl_code=python,true]class Solution:
    def deleteNode(self, node):
        """

一开始看到这个解法还是惊艳了一下的，不过真的太简单了，连删除最后一个node的corner case都给排除掉了