LeetCode题解(1042):不邻接种花/地图染色(Python)
发布日期:2021-06-29 19:55:19
浏览次数:4
分类:技术文章
本文共 1519 字,大约阅读时间需要 5 分钟。
题目:(简单)
解法 | 时间复杂度 | 空间复杂度 | 执行用时 |
---|---|---|---|
Ans 1 (Python) | O ( P + N ) O(P+N) O(P+N) | O ( P ) O(P) O(P) | 532ms (64.19%) |
Ans 2 (Python) | O ( P + N ) O(P+N) O(P+N) | O ( P ) O(P) O(P) | 476ms (98.90%) |
Ans 3 (Python) |
LeetCode的Python执行用时随缘,只要时间复杂度没有明显差异,执行用时一般都在同一个量级,仅作参考意义。
解法一(情景模拟+哈希表):
def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]: hashmap = { } for path in paths: if path[0] not in hashmap: hashmap[path[0]] = [path[1]] else: hashmap[path[0]].append(path[1]) if path[1] not in hashmap: hashmap[path[1]] = [path[0]] else: hashmap[path[1]].append(path[0]) color = [0 for _ in range(N + 1)] for i in range(1, N + 1): if i not in hashmap: color[i] = 1 else: apt = [1, 2, 3, 4] for near in hashmap[i]: if color[near] != 0 and color[near] in apt: apt.remove(color[near]) color[i] = apt[0] return color[1:]
解法二(将哈希表改为数组):
def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]: hashmap = [[] for _ in range(N + 1)] for path in paths: if path[0] > path[1]: hashmap[path[0]].append(path[1]) else: hashmap[path[1]].append(path[0]) color = [0 for _ in range(N + 1)] for i in range(1, N + 1): apt = [1, 2, 3, 4] for near in hashmap[i]: if color[near] != 0 and color[near] in apt: apt.remove(color[near]) color[i] = apt[0] return color[1:]
转载地址:https://dataartist.blog.csdn.net/article/details/107102642 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年05月03日 06时56分47秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Java查找Map中的日期时间里当前时间最远
2019-04-30
安装openfire教程
2019-04-30
Android support v7 ActionBarActivity 过时
2019-04-30
Android Studio 导入第三方库
2019-04-30
Sql Server 查询一段日期内的所有礼拜天
2019-04-30
golang testing
2019-04-30
阅读protobuf-go代码
2019-04-30
golang反射基本准则
2019-04-30
2020-11-30-golang并发模式context
2019-04-30
知名定律摘要-持续更新
2019-04-30
golang value part
2019-04-30
golang-reflect-method-callback
2019-04-30
系统性能和TCP/UDP网络优化-学习大杂烩
2019-04-30
shader入门精要2
2019-04-30
shader入门精要3
2019-04-30
刷一下leetcode算法题,寻找两个正序数组的中位数
2019-04-30
2021-03-12
2019-04-30
戴森球计划这个游戏牛逼
2019-04-30
Redis 学习part one
2019-04-30
Bitcoin比特币源码解读——网络协议
2019-04-30