发个十月初的狗家面经

我感觉楼主最后一轮的算法应该挺慢的呀～ 有分析时间复杂度吗？

楼主能说下第二轮的第二题递归式是什么吗

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

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

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

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

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

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

14417335 发表于 2019-1-5 22:41
**** 本内容被作者隐藏 ****

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

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构成的树的种类吗，你怎么用他来表示树的高度和啊

穿袈裟的流氓 发表于 2019-1-6 13:47
楼主，你这样做是得到一个卡特兰数，这个表示的不是n个nodes构成的树的种类吗，你怎么用他来表示树的高度 ...

数的形状一旦确定了，数的高度难道不就确定了吗？

能请楼主讲讲第三题的思路吗？ 另外恭喜楼主！