一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 2288|回复: 56
收起左侧

[Leetcode] June LeetCoding Challenge

[复制链接] |试试Instant~ |leetcode, 刷题
我的人缘0

分享帖子到朋友圈
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (99)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
有没有小伙伴想组队一起刷?

评分

参与人数 2大米 +2 收起 理由
炸鸡博主张二狗 + 1 赞一个
machecazzo + 1 给你点个赞!

查看全部评分


上一篇:Leetcode账号转让[已关闭]
下一篇:Cracking The Code Interview: 这句话是不是不对?
我的人缘0
 楼主| Reborn2beCoder 2020-6-5 12:28:02 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   100% (99)
 
 
0% (0)    👎
megrez 发表于 2020-6-4 20:24
前两个月的challenge都是差一两天就全勤了,六月再努力一把吧(可是LC这奖品也太不吸引人了)

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

使用道具 举报

我的人缘0
 楼主| Reborn2beCoder 2020-6-17 14:37:27 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (99)
 
 
0% (0)    👎
6/16 https://leetcode.com/problems/validate-ip-address/
每次看到RegEx就头疼,这次也不例外
1) Divide and conquer
[JavaScript] 纯文本查看 复制代码
var validIPAddress = function(IP) {
    if(IP.split('.').length === 4 && isValidIPv4Address(IP.split('.'))) return 'IPv4';
    else if(IP.split(':').length === 8 && isValidIPv6Address(IP.split(':'))) return 'IPv6';
    return 'Neither';
};

var isValidIPv4Address = function(IPArr) {
    for(let i=0; i<IPArr.length; i++){
        let Adr = IPArr[i];
        if(Adr === '') return false;
        if(Adr<0 || Adr>255) return false;
        if(Adr.length > 1 && Adr[0] == '0') return false;
        if(/[^0-9]/.test(Adr)) return false;
    }
    return true;
}

var isValidIPv6Address = function(IPArr) {
    for(let i=0; i<IPArr.length; i++) {
        let Adr = IPArr[i];
        if(Adr === '') return false;
        if(Adr.length > 4) return false;
        if(/[^0-9A-Fa-f]/.test(Adr)) return false;
    }
    return true;
}


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

2) RegEx 看着LC上的答案纠结了好久重复的部分要怎么处理,因为JS不支持regex variable,直到看到了了一个惊为天人的解法
[JavaScript] 纯文本查看 复制代码
var validIPAddress = function(IP) {
    if(/^((\d|[1-9]\d|1\d\d|2([0-4]\d|5[0-5])).){4}$/.test(IP+'.')) return 'IPv4';
    if(/^(([\dA-F]{1,4}):){8}$/i.test(IP+':')) return 'IPv6';
    return 'Neither';
};


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

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

使用道具 举报

我的人缘0
 楼主| Reborn2beCoder 2020-6-8 14:11:34 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (99)
 
 
0% (0)    👎
本帖最后由 Reborn2beCoder 于 2020-6-7 22:14 编辑

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大乱炖的解法。

[JavaScript] 纯文本查看 复制代码
var change = function(amount, coins) {
    let count = Array(amount+1).fill(0);
    count[0] = 1;
    coins.forEach(coin => {
        for(let i=coin; i<amount+1; i++) {
            count[i] += count[i-coin];
        }
    })
    return count[amount];
};


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

评分

参与人数 1大米 +1 收起 理由
zyshmie + 1 赞一个

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| Reborn2beCoder 2020-6-6 14:03:19 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (99)
 
 
0% (0)    👎
鸡籽就是大王 发表于 2020-6-5 07:10
Random Pick with Weight

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

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

btw现在已经2000+ down votes了🙃
回复

使用道具 举报

我的人缘0
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   97% (158)
 
 
2% (4)    👎
本帖最后由 鸡籽就是大王 于 2020-6-5 23:26 编辑

Random Pick with Weight

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

评分

参与人数 1大米 +1 收起 理由
Reborn2beCoder + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| Reborn2beCoder 2020-6-2 14:44:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (99)
 
 
0% (0)    👎
本帖最后由 Reborn2beCoder 于 2020-6-2 14:49 编辑

6/1 [儿童节快乐] 刷鲨鱼一时爽,刷题火葬场,直到11点才开动,还好题不难。

1) Recursion. Time: O(n); Space: stack cost, O(logn) for best(full binary tree) & O(n) for worst (single chain)
[JavaScript] 纯文本查看 复制代码
var invertTree = function(root) {
    if(!root || !root.left && !root.right) return root;
    [node.left, node.right] = [node.right, node.left];
    invertTree(root.left);
    invertTree(root.right);
    return root;
};


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)
[JavaScript] 纯文本查看 复制代码
var invertTree = function(root) {
    if(!root || !root.left && !root.right) return root;
    let queue = [root];
    while(queue.length) {
        let node = queue.shift();
        [node.left, node.right] = [node.right, node.left];
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
    }
    return root;
};

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




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

使用道具 举报

我的人缘0
machecazzo 2020-6-2 17:55:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
[Python] 纯文本查看 复制代码
class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val=node.next.val
        node.next=node.next.next


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

评分

参与人数 1大米 +1 收起 理由
Reborn2beCoder + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
shawn_lyu 2020-6-3 06:00:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (38)
 
 
0% (0)    👎
machecazzo 发表于 2020-6-2 17:55
[mw_shl_code=python,true]class Solution:
    def deleteNode(self, node):
        """

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

评分

参与人数 2大米 +3 收起 理由
Emol + 2 给你点个赞!
Reborn2beCoder + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
machecazzo 2020-6-3 10:52:48 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
shawn_lyu 发表于 2020-6-3 06:00
力口怎么选题的。。。这题downvotes有六千多

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

评分

参与人数 1大米 +1 收起 理由
Reborn2beCoder + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| Reborn2beCoder 2020-6-3 11:47:33 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (99)
 
 
0% (0)    👎

来来来!
回复

使用道具 举报

我的人缘0
 楼主| Reborn2beCoder 2020-6-3 11:48:01 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (99)
 
 
0% (0)    👎
machecazzo 发表于 2020-6-3 10:52
每次Daily challenge感觉前几天的题都挺水的,标准很迷的Easy题……

不能更同意
回复

使用道具 举报

我的人缘0
 楼主| Reborn2beCoder 2020-6-3 11:48:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (99)
 
 
0% (0)    👎
欢迎大家互相加分互相鼓励~~~
回复

使用道具 举报

我的人缘0
 楼主| Reborn2beCoder 2020-6-3 11:51:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (99)
 
 
0% (0)    👎
machecazzo 发表于 2020-6-2 17:55
[mw_shl_code=python,true]class Solution:
    def deleteNode(self, node):
        """

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-7-12 11:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表