要不要加入一亩三分地团队,和我们一起开发app和网站?
一亩三分地招summer intern

一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


码农求职神器Triplebyte
不用海投
内推多家公司面试

瞄准秋招
跟Shawn一起刷算法题

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code: 20%off 打八折

深入浅出AB Test
从入门到精通
coupon code: 20%off 打八折
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 977|回复: 3
收起左侧

[树/链表/图] Atlassian oa题, 做不来求帮助。。

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
sanesean12 发表于 2018-10-28 07:30:20 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 👍  94% (17)
 
 
5% (1)  👎

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

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

x
帮同学问的,在地里找到的oa题。没有头绪,求大佬指点
3.png

评分

参与人数 1大米 +5 收起 理由
14417335 + 5 很有用的信息!

查看全部评分


上一篇:回馈地里, 提供mock interview.
下一篇:找工作刷题贴~Java
我的人缘0
gamesover 发表于 2019-4-6 02:57:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 👍  96% (53)
 
 
3% (2)  👎
搜一下吧,有人贴过答案,比较难理解的是u和v两个数据,意思是一个路径从u走到v,同一个index
比如
u = [2,4]
v = [1,0]
表示2条路径,从2<=>1和4<=>0,注意路径是双向的

[Python] 纯文本查看 复制代码
require 'set'

def find_best_path(n, m, max_t, beauty, u, v, t) 
  $max_beauty = 0

  paths = {}
  times = {}
  u.each_with_index do |from, i|
    current = v[i]
    times[i+1] = t[i]

    if paths.key? from 
      paths[from] << current
    else
      paths[from] = [current] 
    end

    if paths.key? current 
      paths[current] << from
    else
      paths[current] = [from] 
    end 
  end

  dfs(paths, {0 => 1}, [].to_set, 0, beauty[0], max_t, times, beauty)
  $max_beauty
end

def dfs(paths, visited_cities, visited_paths, city, current_beauties, time_left, times, beauties)
  if time_left < 0
    return 
  end

  if city == 0
    $max_beauty = [$max_beauty, current_beauties].max 
  end

  paths[city].each do |next_city|
    path = "#{city}|#{next_city}"
    
    if visited_paths.include?(path)
      next 
    else
      visited_paths << path
    end

    city_beauties = current_beauties
    if visited_cities.key?(next_city)
      visited_cities[next_city] += 1
    else
      visited_cities[next_city] = 1
      city_beauties += beauties[next_city]  
    end

    spend_time = times[[city, next_city].max]

    dfs(paths, visited_cities, visited_paths, next_city, city_beauties, time_left - spend_time, times, beauties)
    visited_paths.delete(path)
    visited_cities[next_city] -= 1
    if visited_cities[next_city] == 0
      visited_cities.delete(next_city)
    end
  end
end

u = [0,1,0]
v = [1,2,3]
t = [6,7,10]
beauty = [5,10,15,20]

p find_best_path(4, 3, 30, beauty, u, v, t) #30


u = [0,2,0]
v = [1,0,3]
t = [10,13,17]
beauty = [0,32,10,43]

p find_best_path(4, 3, 49, beauty, u, v, t) #43
回复

使用道具 举报

我的人缘0
14417335 发表于 2019-4-6 03:52:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 👍  99% (377)
 
 
0% (3)  👎
这题有说是树,DAG或者是图吗?如果是树(猜的),那么还有个combinational sum的问题。比如时间充裕,我回到旅馆后还可以再选择一条线路。
回复

使用道具 举报

我的人缘0
gamesover 发表于 2019-4-6 05:34:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 👍  96% (53)
 
 
3% (2)  👎
14417335 发表于 2019-4-6 03:52
这题有说是树,DAG或者是图吗?如果是树(猜的),那么还有个combinational sum的问题。比如时间充裕,我回 ...

更像无向图吧,你说的办法的确可以
回复

使用道具 举报

游客
请先登录
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地

GMT+8, 2019-5-26 14:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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