📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3116| 回复: 10
跳转到指定楼层
上一主题 下一主题
收起左侧

Google : 计算a[0]*a[1]*...*a[n-1]/a[i]

全局:

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

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

x
//Given an array a[n], build another array b[n], b[i] = a[0]*a[1]*...*a[n-1]/a[i]
//no division can be used, O(n) time complexity

上一篇:Microsoft : 不用额外空间,链接二叉树同一层的每个node
下一篇:Microsoft : Implement a special stack
🔗
danielgao 2011-5-2 00:19:13 | 只看该作者
全局:
本帖最后由 wwwyhx 于 2011-5-2 01:40 编辑

回复 1# wwwyhx

取巧的话可以求lg以后用加减来代替。。。

不取巧的话伪代码大致如下


  1. for int i = 1, c[0] = 1;  i  < n; ++i
  2.     c[i] = c[i - 1] * a[i - 1]
  3. for int i = n-2, d[n-1] = 1;  i  >=0;  --i
  4.     d[i] = d[i + 1] * a[i + 1]
  5. for int i = 0; i <= n -1; ++i
  6.    b[i] = c[i] * d[i]
复制代码
[i][i][i][i][i][i][i][i][i]

[/i][/i][/i][/i][/i][/i][/i][/i][/i]
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-2 01:39:54 | 只看该作者
全局:
回复  wwwyhx

取巧的话可以求lg以后用加减来代替。。。

不取巧的话伪代码大致如下
danielgao 发表于 2011-5-2 00:19


很聪明啊
回复

使用道具 举报

🔗
darksteel 2011-5-2 04:13:04 | 只看该作者
全局:
面试的时候就被问到这题。。
回复

使用道具 举报

🔗
darksteel 2011-5-2 08:54:52 | 只看该作者
全局:
我面试的时候说的也是和上面类似的方法,但其实有个O(1)额外空间的方法,请参考下面链接。
http://www.ihas1337code.com/2010 ... ion-of-numbers.html
回复

使用道具 举报

🔗
Imbalism 2011-5-2 09:35:58 | 只看该作者
全局:
我面试的时候说的也是和上面类似的方法,但其实有个O(1)额外空间的方法,请参考下面链接。
darksteel 发表于 2011-5-2 08:54


很巧妙, 受教了!
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-2 10:38:04 | 只看该作者
全局:
我面试的时候说的也是和上面类似的方法,但其实有个O(1)额外空间的方法,请参考下面链接。
darksteel 发表于 2011-5-2 08:54



    对啊,用两个变量存储左右并同步更新
    DP问题很多都可以把直观的空间复杂度降低一个数量级,谢了
回复

使用道具 举报

🔗
danielgao 2011-5-2 12:18:12 | 只看该作者
全局:
我面试的时候说的也是和上面类似的方法,但其实有个O(1)额外空间的方法,请参考下面链接。
darksteel 发表于 2011-5-2 08:54



  Good idea!
回复

使用道具 举报

🔗
法兰天蝎 2011-5-3 20:50:22 | 只看该作者
全局:
回复 6# darksteel


    哥们哪个网站不错嘛,还能实时运行写的程序,就是不知道它给出的运行时间准不准确哦
回复

使用道具 举报

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

本版积分规则

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