免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12
最近访问板块 发新帖
楼主: hubimaso

[网络] 2013校园招聘腾讯附加题 [复制链接]

论坛徽章:
0
发表于 2012-09-26 10:41 |显示全部楼层
愿听其详 回复 10# crazyhadoop


   

论坛徽章:
0
发表于 2012-09-26 11:04 |显示全部楼层
愿听其详! 回复 10# crazyhadoop


   

论坛徽章:
0
发表于 2012-09-27 14:05 |显示全部楼层
看过下那个 出栈问题的解法, 直接用个 C( )( ) 不是很懂,
我自己后来想了想,把问题归结为 f( n , m ) , f( n , m ) 表示  当前栈里面有n个元素,还有m个元素准备压栈情况下 的所有可能的序列,当然, n+m 个元素应该是不相同的。

所以题目的求有5个元素进栈出栈得到的序列可以表示为  f( 0 , 5 ) == f( 1 , 4 );

f( n , m ) = f( n-1 , m ) + f( n+1 , m -1 );   // <- 得到递推公式,里面有重叠的子问题,这样的递推应该是可以动态规划吧,算法不是很好,以后加强下。

然后画画矩阵: n x m
f( 0 , 0 ) == 0 ;
f( x != 0 , 0 ) == 1 的,
f( 0 , m ) == f( 1 , m-1 ) 的

注意那个递推公式的含义, 头顶的 + 左下 = 自己位置的

   0  1  2    3    4   5  6
0 0  1  2    5    14
1 1  2  5   14   42
2 1  3  9   28
3 1  4  14
4 1  5
5 1  


这样能得到 f( 0 , 5 ) == f( 1 , 4 ) == 14 + 28 = 42;
但是需要空间比较大,而复杂度应该O( m*n ), 挺糟糕的,但是如何将那个函数化简下,得到更低的复杂度,目前还是没能力哎。。

论坛徽章:
0
发表于 2012-09-27 14:10 |显示全部楼层
InMySin 发表于 2012-09-27 14:05
看过下那个 出栈问题的解法, 直接用个 C( )( ) 不是很懂,
我自己后来想了想,把问题归结为 f( n , m ) , ...


哎哟,空间应该不用 mxn 矩阵保存,保存一个数组应该够了,但是也是不少的时空开销;

有没有谁理解那个 C() / () 的,解析...
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP