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

[高频题] 计算车流平均速度

全局:
高频题
公司名称: google

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

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

x
在地里和leetcode面经版都看到这个题了,不知道能不能发到高频板块
您好!
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Popular Interview Questions from Top Companies



评分

参与人数 4大米 +12 收起 理由
dlwlrma + 2 给你点个赞!
14417335 + 6
duracell + 1 给你点个赞!
dobbin + 3 很有用的信息!

查看全部评分


上一篇:分享一个帮助Leetcode笔记本拍照上传的安卓app
下一篇:到什么级别之后面试不用刷题了?
推荐
dlwlrma 2019-5-25 07:28:46 | 只看该作者
全局:
大概写了下,不确定有没有漏掉edge case。
  1. #!/usr/bin/python
  2. # -*- coding: utf-8 -*-

  3. import collections

  4. def carstreamspeed(arr):
  5.     nums = []
  6.     for s, e, v in arr:
  7.         nums.append([s, 1, v])
  8.         nums.append([e, -1, v])

  9.     nums.sort()
  10.     cnt = 0
  11.     cum_v = 0
  12.     i = 0
  13.     n = len(nums)
  14.     res = []
  15.     while i < n:
  16.         j = i
  17.         while j < n and nums[i][0] == nums[j][0]:
  18.             if nums[j][1] == 1:
  19.                 cum_v += nums[j][2]
  20.                 cnt += 1
  21.             else:
  22.                 cum_v -= nums[j][2]
  23.                 cnt -= 1
  24.             j += 1
  25.         if j == n:
  26.             break
  27.         tmp = [nums[i][0], nums[j][0], cum_v / float(cnt)]
  28.         res.append(tmp)
  29.         i = j
  30.     return res

  31. arr = [[0, 14, 90],
  32.        [13, 15, 80],
  33.        [13, 16, 70]]

  34. print carstreamspeed(arr)

  35. arr = [[0, 14, 90],
  36.        [3, 15, 80]]

  37. print carstreamspeed(arr)

  38. arr = [[0, 14, 90],
  39.        [13, 15, 80],
  40.        [13, 16, 70],
  41.        [15, 17, 100]]

  42. print carstreamspeed(arr)


复制代码

评分

参与人数 1大米 +20 收起 理由
admin + 20

查看全部评分

回复

使用道具 举报

推荐
djmiss 2019-5-23 08:06:15 | 只看该作者
全局:
应该是和meeting room2类似
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
mc2 2019-5-24 08:42:09 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
dlwlrma 2019-5-25 07:41:41 | 只看该作者
全局:
dlwlrma 发表于 2019-5-25 07:28
大概写了下,不确定有没有漏掉edge case。
[mw_shl_code=python,true]#!/usr/bin/python
# -*- coding: u ...

思路就是扫描线, 然后从头到尾扫一遍,碰到起点,cum_v加上速度v, 碰到终点,cum_v减去v. O(nlogn)
回复

使用道具 举报

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

本版积分规则

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