Bloomberg面试题分析

greenmoon55

wxl3691 发表于 2017-9-19 02:51
能解释下吗，我遇到递归， DFS就无法分析了，为什么是2啊？

set里每个string都有选和不选两种情况，一共n个，所以2^n

seannaes

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

wxl3691

seannaes 发表于 2017-9-19 03:02
对不起，其实我只是猜测的。
我不确定你是不是这么做的：
每次把target string 分成， 0 到 i, 和 i 到 ...

我就是这个思路，应该是对的。谢谢你

westcoastboy

wxl3691 发表于 2017-9-19 02:36
我没用什么DP，就DFS，时间复杂度答 O(N^2), 烙印当场说我是错的，说比O(N^2) 高

DFS的复杂度不可能是N^2。。。我觉得是2^N吧

wxl3691

westcoastboy 发表于 2017-9-19 03:29
DFS的复杂度不可能是N^2。。。我觉得是2^N吧

是的，当时口误，说错了，尴尬

susan57susan

谢谢分享~

cxw111 · 2017-10-10 00:55:21

求问lz啥时投的啊。。。一点消息都没有

wxl3691 · 2017-10-10 00:56:49

cxw111 发表于 2017-10-10 00:55
求问lz啥时投的啊。。。一点消息都没有

投的早，赶的第一波，今年坑少，大家都是地狱模式

cxw111 · 2017-10-10 00:58:10

wxl3691 发表于 2017-10-10 00:56
投的早，赶的第一波，今年坑少，大家都是地狱模式

估计我没戏了
今年怎么感觉好难啊。。。

wxl3691 · 2017-10-10 01:02:08

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Bloomberg面试题 分析