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

开一贴刷题打卡

🔗
 楼主| tall_cool_13 2018-12-22 16:41:33 | 只看该作者
全局:
Leetcode 928和924, 928稍微复杂一点点


  1. class Solution(object):
  2.         def minMalwareSpread(self, graph, initial):

  3.                 def dfs(node, vis):
  4.                         for v in range(len(graph)):
  5.                                 if graph[node][v] == 1 and v not in vis:  
  6.                                         vis.add(v)
  7.                                         dfs(v, vis)

  8.                 s_initial, t_vis = set(initial), set()
  9.                 del_node, sub_len = min(initial), 0
  10.                 for node in range(len(graph)):
  11.                         if node not in t_vis:
  12.                                 vis = set([node])
  13.                                 dfs(node, vis)
  14.                                 infect = vis & s_initial
  15.                                 if len(infect) == 1:
  16.                                         if len(vis) > sub_len or (len(vis) == sub_len and min(list(infect)) < del_node):
  17.                                                 del_node, sub_len = min(list(infect)), len(vis)
  18.                                 t_vis |= vis
  19.                                
  20.                 return del_node
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-12-22 16:42:03 | 只看该作者
全局:
Code for 928
  1. import collections
  2. class Solution(object):
  3.     def minMalwareSpread(self, graph, initial):
  4.         """
  5.         :type graph: List[List[int]]
  6.         :type initial: List[int]
  7.         :rtype: int
  8.         """
  9.         def dfs(node, vis):
  10.             for n in range(len(graph)):
  11.                 if graph[node][n] == 1  and n not in initial and n not in vis:
  12.                     vis.append(n)
  13.                     dfs(n, vis)

  14.         # using bfs instead of dfs
  15.         inf = collections.defaultdict(list)
  16.         del_node = min(initial)
  17.         for node in initial:
  18.             vis = [node]
  19.             dfs(node, vis)
  20.             for n in vis:
  21.                 inf[n].append(node)

  22.         max_len = 0
  23.         ans = collections.defaultdict(int)
  24.         for k, v in inf.items():
  25.             if len(v) == 1:
  26.                 ans[v[0]] += 1
  27.                 if ans[v[0]] > max_len or (ans[v[0]] == max_len and v[0] < del_node):
  28.                     del_node, max_len = v[0], ans[v[0]]
  29.         
  30.         return del_node
复制代码
回复

使用道具 举报

🔗
Gerhut 2018-12-22 22:29:54 | 只看该作者
全局:
我也来打个卡
回复

使用道具 举报

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

本版积分规则

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