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

🐶店 电面挂经

全局:
neverlate 发表于 2022-07-09 18:48:10
1. 不用前缀和,后缀和2个数组,一个变量总和即可
2. 不用全部过一遍,bs搜索valley即可
能请大大给个示范吗?我试了一下不排序,没得出正确答案
回复

使用道具 举报

🔗
deidaraho 2022-7-11 00:58:11 | 只看该作者
全局:
看描述感觉可以把问题转化成找max(h[i]*(n-i)),h是输入的sorted的高度,n是h的长度。
原因:减去最少的floor相当于留下最多的层数,sorted了h之后,那么i之前的没法留,i之后的最多留到h[i]的高度。

然后用binary search找这个peak就行,找到了之后,返回sum(h)-peak。
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-GGUTA  2022-7-11 01:48:54 来自APP
0,3,3高度不一样啊,这是正确答案?
回复

使用道具 举报

🔗
acheirs 2022-7-11 07:01:38 | 只看该作者
全局:
请问谷歌电面具体是怎么个东西?就是打电话(非视频),然后在 share 的 google doc 上面code么?不用compile出来吧?
回复

使用道具 举报

🔗
 楼主| rpg99699016 2022-7-11 07:21:14 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-HBKQQ  2022-7-11 19:21:01
deidaraho 发表于 2022-7-10 12:58
看描述感觉可以把问题转化成找max(h*(n-i)),h是输入的sorted的高度,n是h的长度。
原因:减去最少的floo ...

sorted了,peak就在最后,为啥要BS?
回复

使用道具 举报

全局:
匿名用户 发表于 2022-07-11 04:21:01
sorted了,peak就在最后,为啥要BS?
sort是高度h,找peak找的是h[i]*(n-i)
回复

使用道具 举报

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

使用道具 举报

全局:
sudoAPT-GET 发表于 2022-07-08 18:57:10
直接排序然后指针iterate?不过那样就nlogn了 不知道有没有更好的办法
给定的h就已经是sorted过的嚒?如果是的话直接二分找h*(n-i)最快。 o(logn)
回复

使用道具 举报

🔗
xinyulrsm 2022-7-13 09:55:01 | 只看该作者
全局:
本帖最后由 xinyulrsm 于 2022-7-12 22:00 编辑


先sort, 然后scan, 计算推到以前的 和 把后面平成 一样的, O(n logn) for sorting. Hope this makes sense.  真心求指教
  1. a = [5, 3, 1]

  2. def cal_floors(a):
  3.    
  4.     a.sort()
  5.    
  6.     temp_sum, min_v  = 0, float('inf')
  7.    
  8.     for i, h in enumerate(a):
  9.         
  10.         ans = temp_sum + h * (len(a) - i)
  11.         
  12.         min_v = min(min_v, ans)
  13.         
  14.        temp_sum += x
  15.         
  16.    return min_v

  17. cal_floors(a)
复制代码

本帖子中包含更多资源

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

x
回复

使用道具 举报

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

本版积分规则

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