Comments (2)
Leetcode
102. Binary Tree Level Order Traversal
类型:BFS
Time Complexity O(n)
Space Complexity O(n)
BFS的题解思路。
这里
new_q
也可以命名成next_level
,同样q
可以命名为cur_level
,但因为太长,我选择放弃。
通过一个temp的数组new_q
来存储下一层的node,
每次迭代完成后,把temp数组的node更新到q
里面用于下一次迭代,并存储至res
class Solution(object):
def levelOrder(self, root):
res = []
if not root:
return res
q = [root]
while q :
res.append([node.val for node in q])
new_q = []
for node in q:
if node.left:
new_q.append(node.left)
if node.right:
new_q.append(node.right)
q = new_q
return res
133. Clone Graph
类型:BFS
Time Complexity O(n)
Space Complexity O(n)
思路:
- 找到所有的Nodes,并且储存到字典
- 找到每个Node的Neighbor,并储存到字典
有了思路以后,写个Helper用来BFS遍历寻找所有的Node,具体参考getNodes()
然后要做的就是把所有的Nodes存储以及他们的Neighbor,参考以下
# Definition for a undirected graph node
# class UndirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors = []
class Solution:
def cloneGraph(self, node):
if not node: return node
root = node
# Store Nodes
nodes = self.getNodes(node)
dic = {}
for node in nodes:
dic[node] = UndirectedGraphNode(node.label)
# Store Node's Neighbors
for node in nodes:
clone_node = dic[node]
for neighbor in node.neighbors:
clone_neighbor = dic[neighbor]
clone_node.neighbors.append(clone_neighbor)
return dic[root]
def getNodes(self, node):
q = collections.deque([node])
res = set([node])
while q:
head = q.popleft()
for neighbor in head.neighbors:
if neighbor not in res:
res.add(neighbor)
q.append(neighbor)
return res
127. Word Ladder
类型:BFS
Time Complexity O(n26^len) -> O(n26^len/2)
Space Complexity O(n)
每次只要对word里面任意字母进行更改以后,就将其放回queue里面。
对于是否访问这个问题,我的写法是写一个visted的set来统计,LC里面有一种直接删除wordList里面访问过的词,想法雷同。
至于记录深度,可以利用python里面tuple
的小技巧,每次迭代的时候对tuple里面的计量单位增值即可:
q.append((new_word, length + 1))
最后一点就是开头的arr = set(arr)
用来解决TLE,LC里面有些特别大的重复List很尴尬。
class Solution(object):
def ladderLength(self, start, end, arr):
arr = set(arr) #avoid TLE
q = collections.deque([(start, 1)])
visted = set()
alpha = string.ascii_lowercase #'abcd...z'
while q:
word, length = q.popleft()
if word == end:
return length
for i in range(len(word)):
for ch in alpha:
new_word = word[:i] + ch + word[i+1:]
if new_word in arr and new_word not in visted:
q.append((new_word, length + 1))
visted.add(new_word)
return 0
白板
写白板的时候忘记写 new_word not in visted
207. Course Schedule
类型:BFS
Time Complexity O(n)
Space Complexity O(n)
Topological Sorting题
首先构建一个图,因为题目没有提供。
然后创建一个入度数组。
把入度数组里面为0的课丢进Queue,表示这门课无需Pre-req,然后对这门课的所有邻居的入度减1。更新完邻居的入度后,如果发现邻居里面有入度为0,则将其丢进Queue继续迭代。
class Solution(object):
def canFinish(self, n, edges):
from collections import deque
in_degrees = [0 for i in range(n)] #入度记录一门课需要上几个pre_req
graph = {i: set() for i in range(n)} #画一幅图
# 构建图以及入度
for i, j in edges:
in_degrees[i] += 1
graph[j].add(i)
# 如果课没有pre_req,扔到Queue里
q = deque()
for i, pre_req in enumerate(in_degrees):
if not pre_req:
q.append(i)
# 进行BFS操作
visited = 0
while q:
node = q.popleft()
visited += 1
for neigh in graph[node]:
in_degrees[neigh] -= 1
if in_degrees[neigh] == 0:
q.append(neigh)
return visited == n
210. Course Schedule II
类型:BFS
Time Complexity O(n)
Space Complexity O(n)
这种Follow up简直就是送分啊。就把每次pop出来的数存到一个数组返回即可。
class Solution(object):
def findOrder(self, n , edges):
from collections import deque
in_degrees = [0 for i in range(n)] #入度记录一门课需要上几个pre_req
graph = {i: set() for i in range(n)} #画一幅图
# 构建图以及入度
for i, j in edges:
in_degrees[i] += 1
graph[j].add(i)
# 如果课没有pre_req,扔到Queue里
q = deque()
for i, pre_req in enumerate(in_degrees):
if not pre_req:
q.append(i)
# 进行BFS操作
visited = 0
res = []
while q:
node = q.popleft()
visited += 1
res.append(node)
for neigh in graph[node]:
in_degrees[neigh] -= 1
if in_degrees[neigh] == 0:
q.append(neigh)
return res if visited == n else []
from leetcode.
Lintcode
127. Topological Sorting
类型:BFS
Time Complexity O(n)
Space Complexity O(n)
def topSortBFS(self, graph):
indegree = {}
ans = []
for g in graph:
for n in g.neighbors:
if n not in indegree:
indegree[n] = 1
else:
indegree[n] += 1
q = []
for g in graph:
if g not in indegree:
q.append(g)
while q:
temp = q.pop(0)
ans.append(temp)
for n in temp.neighbors:
indegree[n] -= 1
if indegree[n] == 0:
q.append(n)
return ans
from leetcode.
Related Issues (20)
- Day 7 | 3/20/20 HOT 1
- 76. Minimum Window Substring
- 215 -> 研究下Quick Select算法
- Day 3. 02/10/20 HOT 3
- 973. K Closest Points to Origin
- 67. Add Binary HOT 2
- 491. Increasing Subsequences
- 1027
- Day 4. 02/11/20 HOT 5
- 350 Intersection of Two Arrays II
- 297. Serialize and Deserialize Binary Tree
- Day 5. 02/12/20
- Day 5. 02/15/20 HOT 3
- [Weekly Plan] Day 7 - 12. (New Start) | 2/18 - 2/22 HOT 6
- Day 5 | 2/20/20 HOT 6
- 560. Subarray Sum Equals K HOT 1
- Sliding Windows HOT 2
- Day 6 HOT 2
- Week 3
- 116. Populating Next Right Pointers in Each Node
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from leetcode.