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

11月水卢狗昂赛

🔗
novasu 2019-11-19 06:57:39 | 只看该作者
全局:
匿名者 发表于 2019-11-19 06:38
应该是对的。。。bellman-ford求的是一个点到其他所有点的值时间复杂度是比dfs高的。。

我感觉dfs的复杂度是O(4^mn) 然而bellman ford是O(m^2 * n^2) 感觉还是BF好一点。。。
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-NYFU9  2019-11-19 08:25:52
novasu 发表于 2019-11-19 06:57
我感觉dfs的复杂度是O(4^mn) 然而bellman ford是O(m^2 * n^2) 感觉还是BF好一点。。。

DFS时间复杂度应该是O(m*n)吧
回复

使用道具 举报

🔗
novasu 2019-11-19 08:44:26 | 只看该作者
全局:
匿名者 发表于 2019-11-19 08:25
DFS时间复杂度应该是O(m*n)吧

我觉得每一个点有四个方向,一共有mn个点然后也不好做记忆化搜索所以我觉得复杂度是O(4^mn), 但是最主要的是面试官是满意这个做法的吗,感觉写完这个dfs应该时间还剩不少,也想不到怎么优化。。。。
回复

使用道具 举报

🔗
zhuanye3 2019-11-21 12:26:51 | 只看该作者
全局:
最后一题应该是从左边和从右边各扫一遍,分别计算距离当前点的左边/右边其他最近设施的距离,然后再取交叉的最大结果就行
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-NYFU9  2019-11-21 13:24:20
zhuanye3 发表于 2019-11-21 12:26
最后一题应该是从左边和从右边各扫一遍,分别计算距离当前点的左边/右边其他最近设施的距离,然后再取交叉 ...

是的。。。当时没想到从右边扫。。555 脑子一根筋了
回复

使用道具 举报

🔗
adayxiang 2019-11-22 04:10:01 | 只看该作者
全局:
求问楼主timeline, 现在到哪一步了
回复

使用道具 举报

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

使用道具 举报

🔗
hook5760 2019-11-22 07:00:26 | 只看该作者
全局:
最後一輪:
我的解讀是在2D matrix中,找出一點P(i, j),使得該點距離最遠的設施之距離和最小
P(i, j) is not unique, 可能有複數個點值相等, 不過回傳一個大概就可以了
min( SUM( max( dist( P(i, j) -  facility[f]  )  )  )  )

設施:f = 1, 2, 3, 4,....etc
0: available
1: restaurant
2: Gym
3: ....
4: .....etc
-1: blocked

mat = [
[1,0,0,0,0,0,1,0],
[2,0,0,0,0,0,0,0],
[0,0,0,-1,0,0,2,0],
[0,0,4,-1,0,0,0,0],
[0,0,0,-1,0,0,0,0],
[0,0,0,-1,0,0,0,0],
[0,0,3,-1,0,0,0,0],
[0,0,0,0,0,0,3,0]
]
# output: dist = 20, position = [1 3]
"""
[
[0, 28, 24, 22, 24, 28, 0, 38],
[0, 26, 22, 20, 22, 26, 30, 34],
[30, 26, 24, 0, 24, 28, 0, 36],
[30, 26, 0, 0, 26, 30, 34, 38],
[32, 28, 30, 0, 28, 32, 36, 40],
[34, 30, 32, 0, 30, 34, 38, 42],
[36, 32, 0, 0, 32, 36, 40, 44],
[36, 32, 30, 29, 32, 36, 0, 48]]
"""
import collections
def minMaxDistance(mat):
        m = len(mat)
        n = len(mat[0])
        shift = [-1, 0, 1, 0, -1]
        buildingNum = 0
        buildingFind = False
        dist = [[0 for _ in range(n)] for _ in range(m)]
        reach = [[0 for _ in range(n)] for _ in range(m)]
        d = collections.defaultdict(list)
        for i in range(m):
                for j in range(n):
                        if mat[i][j] != 0 and mat[i][j] != -1:
                                d[mat[i][j]].append([i, j])

        for key, val in d.items():
                maxDist = [[0 for _ in range(n)] for _ in range(m)]
                for i, j in val:
                        queue = collections.deque()
                        queue.append((i, j))
                        visited = [[0 for _ in range(n)] for _ in range(m)]
                        level = 1
                        while queue:
                                size = len(queue)
                                for _ in range(size):
                                        r, c = queue.popleft()
                                        for k in range(len(shift) - 1):
                                                nr = r + shift[k]
                                                nc = c + shift[k + 1]
                                                if 0 <= nr < m and 0 <= nc < n and mat[nr][nc] == 0 and not visited[nr][nc]:
                                                        queue.append((nr, nc))                                                       
                                                        maxDist[nr][nc] = max(maxDist[nr][nc], level)
                                                        reach[nr][nc] += key
                                                        visited[nr][nc] = 1
                                level += 1
                dist = [[dist[i][j] + maxDist[i][j] for j in range(n)] for i in range(m)]

        reachBuildingSum = 0
        for key, val in d.items():
                for i, j in val:
                        reachBuildingSum += key

        shortestDist = float("inf")
        pos = [0, 0]
        for i in range(m):
                for j in range(n):
                        if mat[i][j] == 0 and reach[i][j] == reachBuildingSum:
                                if dist[i][j] <= shortestDist:
                                        shortestDist = dist[i][j]
                                        pos = [i, j]

        return [shortestDist, pos]

print(minMaxDistance(mat))

补充内容 (2019-11-22 08:03):
time complexity: O(f * (traverse all elements in 2D) * (BFS)) = O(f * mn * mn) = O(f * m^2*n^2)
where f: category set of facilities
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-NYFU9  2019-11-22 07:20:21
adayxiang 发表于 2019-11-22 04:10
求问楼主timeline, 现在到哪一步了

在等hc review结果
回复

使用道具 举报

🔗
ctcs 2019-11-22 14:04:00 | 只看该作者
全局:
"给一排街区,可以想象成是数组" 这是sliding window
https://leetcode.com/discuss/int ... -the-farthest-point
回复

使用道具 举报

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

本版积分规则

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