楼主: wisdompeak2
跳转到指定楼层
上一主题 下一主题
收起左侧

发个十月初的狗家面经

🔗
leetcod_ 2019-1-4 10:57:19 | 只看该作者
全局:
我感觉楼主最后一轮的算法应该挺慢的呀~ 有分析时间复杂度吗?
回复

使用道具 举报

全局:
楼主能说下第二轮的第二题递归式是什么吗
回复

使用道具 举报

全局:
tsl665 发表于 2019-1-4 10:32
噗,是这个意思。。你说没写代码我以为是证明题。。

另外最后一题感觉可以用线段树做

能说下这一题怎么做的吗,没想出来怎么写
回复

使用道具 举报

全局:
楼主,我看了你在另外一个帖子里面的第三题的代码,有个问题是如果test case是 abcdefghijklmnopqrstuvwx 和badcfehgjilknmpoeqtsvuxw,这种没有包括所有26个字母,但也不能实现吧,它包括了12个环,需要12个额外的字母来做中间值

补充内容 (2019-1-5 12:16):
不好意思想错了,你的是对的
回复

使用道具 举报

🔗
14417335 2019-1-5 22:41:46 | 只看该作者
全局:
wisdompeak2 发表于 2019-1-4 10:25
不需要证明或计算,写出递归关系,让计算机去跑就行了。

您好!
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies


回复

使用道具 举报

🔗
 楼主| wisdompeak2 2019-1-6 04:01:39 | 只看该作者
全局:
14417335 发表于 2019-1-5 22:41
**** 本内容被作者隐藏 ****

你想得太复杂了吧。
难道不是简单地根据左右两分支的数量,然后不断往下递归吗?
回复

使用道具 举报

🔗
14417335 2019-1-6 06:23:24 | 只看该作者
全局:
wisdompeak2 发表于 2019-1-6 04:01
你想得太复杂了吧。
难道不是简单地根据左右两分支的数量,然后不断往下递归吗?

可能是。
期望是把所有可能的结果x其概率并求和。所以我的思路是把可能的层数的概率求出来。
仅仅根据左右两分支的数量不知道怎么分布。
你是不是下面这个意思?
  1. f(0)=1
  2. f(1)=1
  3. f(2)=average { 1+f(0)*f(1) }
  4. f(3)=average { 1+f(0)*f(2), 1+f(1)*f(1) }
  5. f(4)=average { 1+f(0)*f(3), 1+f(1)*f(2) }
  6. f(5)=average { 1+f(0)*f(4), 1+f(1)*f(3), 1+f(2)*f(2) }
  7. ...
复制代码




补充内容 (2019-1-7 06:21):
上面公式修改三点下:不是乘积的关系,而是MAX的关系。f(0)=0。另外可能还是要考虑每个树的分布。比如n=3时,有80%得到3,20%是2. 不能简单的average。
回复

使用道具 举报

全局:
wisdompeak2 发表于 2019-1-6 04:01
你想得太复杂了吧。
难道不是简单地根据左右两分支的数量,然后不断往下递归吗?

楼主,你这样做是得到一个卡特兰数,这个表示的不是n个nodes构成的树的种类吗,你怎么用他来表示树的高度和啊
回复

使用道具 举报

🔗
 楼主| wisdompeak2 2019-1-6 14:36:05 | 只看该作者
全局:
穿袈裟的流氓 发表于 2019-1-6 13:47
楼主,你这样做是得到一个卡特兰数,这个表示的不是n个nodes构成的树的种类吗,你怎么用他来表示树的高度 ...

数的形状一旦确定了,数的高度难道不就确定了吗?
回复

使用道具 举报

🔗
Amber25 2019-1-6 16:10:34 | 只看该作者
全局:
能请楼主讲讲第三题的思路吗? 另外恭喜楼主!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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