Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
http://www.lintcode.com/en/problem/graph-valid-tree/
https://leetcode.com/problems/graph-valid-tree/#/description
In [2]:
class Solution:
# @param {int} n an integer
# @param {int[][]} edges a list of undirected edges
# @return {boolean} true if it's a valid tree, or false
def validTree(self, n, edges):
# Write your code here
dic = {i: [] for i in range(n)}
for i, j in edges:
dic[i].append(j)
dic[j].append(i)
visited = [0 for i in range(n)]
layer, visited[0] = [0], 1
while layer:
next_layer = []
for node in layer:
for next_node in dic[node]:
if visited[next_node]:
return False
dic[next_node].remove(node)
next_layer.append(next_node)
visited[next_node] = 1
layer = next_layer
return True if sum(visited) == n else False
In [3]:
# Definition for a undirected graph node
# class UndirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors = []
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
def __init__(self):
self.dict = {}
def cloneGraph(self, node):
# write your code here
if node is None:
return
nodeCopy = UndirectedGraphNode(node.label)
self.dict[node] = nodeCopy
queue = [node]
while queue:
node = queue.pop(0)
for n in node.neighbors:
if n not in self.dict:
nc = UndirectedGraphNode(n.label)
self.dict[n] = nc
self.dict[node].neighbors.append(nc)
queue.append(n)
else:
self.dict[node].neighbors.append(self.dict[n])
return nodeCopy
Given a undirected graph, a node and a target, return the nearest node to given node which value of it is target, return NULL if you can't find.
There is a mapping store the nodes' values in the given parameters.
Notice
It's guaranteed there is only one available solution
In [8]:
# Definition for a undirected graph node
# class UndirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors = []
class Solution:
# @param {UndirectedGraphNode[]} graph a list of undirected graph node
# @param {dict} values a dict, <UndirectedGraphNode, (int)value>
# @param {UndirectedGraphNode} node an Undirected graph node
# @param {int} target an integer
# @return {UndirectedGraphNode} a node
def searchNode(self, graph, values, node, target):
# Write your code here
if not node:
return None
if values[node] == target:
return node
queue = [node]
visited = set([node])
while queue:
node = queue.pop(0)
for n in node.neighbors:
if values[n] == target:
return n
if n not in visited:
visited.add(n)
queue.append(n)
return None
Given an directed graph, a topological order of the graph nodes is defined as follow:
For each directed edge A -> B in graph, A must before B in the order list. The first node in the order can be any node in the graph with no nodes direct to it. Find any topological order for the given graph.
In [18]:
# Definition for a Directed graph node
# class DirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors = []
class Solution:
"""
@param graph: A list of Directed graph node
@return: A list of graph nodes in topological order.
"""
def topSort(self, graph):
# write your code here
dic = {}
for node in graph:
dic[node] = 0
for node in graph:
for n in node.neighbors:
dic[n] += 1
order = []
for node in graph:
if dic[node] == 0:
order.append(node)
queue = order[:] ## right way to copy a list!!!
while queue:
node = queue.pop(0)
for n in node.neighbors:
dic[n] -= 1
if dic[n] == 0:
order.append(n)
queue.append(n)
return order if len(order) == len(dic) else None
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110 11010 11000 00000 Answer: 1
Example 2:
11000 11000 00100 00011 Answer: 3
https://leetcode.com/problems/number-of-islands/#/description
In [20]:
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if grid is None or len(grid) == 0 or len(grid[0]) == 0:
return 0
m, n = len(grid), len(grid[0])
visited = [[False for i in range(n)] for j in range(m)]
count = 0
def bfs(grid, m, n, x, y):
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
queue = [[x, y]]
visited[x][y] = True
while queue:
x, y = queue.pop(0)
for i in range(4):
xx, yy = x + dx[i], y + dy[i]
if 0 <= xx < m and 0 <= yy < n:
if not visited[xx][yy] and grid[xx][yy] == '1':
queue.append([xx, yy])
visited[xx][yy] = True
for x in range(m):
for y in range(n):
if not visited[x][y] and grid[x][y] == '1':
count += 1
bfs(grid, m, n, x, y)
return count
In [21]:
class Solution:
# @param {boolean[][]} grid a boolean 2D matrix
# @return {int} an integer
def numIslands(self, grid):
# Write your code here
if grid is None or len(grid) == 0 or len(grid[0]) == 0:
return 0
m, n = len(grid), len(grid[0])
visited = [[False for y in range(n)] for x in range(m)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
count = 0
def bfs(x, y):
queue = [[x, y]]
while queue:
x, y = queue.pop(0)
visited[x][y] = True
for i in range(4):
xx, yy = x + dx[i], y + dy[i]
if 0 <= xx < m and 0 <= yy < n:
if not visited[xx][yy] and grid[xx][yy] == 1:
queue.append([xx, yy])
visited[xx][yy] = True
for x in range(m):
for y in range(n):
if not visited[x][y] and grid[x][y] == 1:
count += 1
bfs(x, y)
return count
Given a 2D grid, each cell is either a wall 2, a zombie 1 or people 0 (the number zero, one, two).Zombies can turn the nearest people(up/down/left/right) into zombies every day, but can not through wall. How long will it take to turn all people into zombies? Return -1 if can not turn all people into zombies.
Example Given a matrix:
0 1 2 0 0 1 0 0 2 1 0 1 0 0 0 return 2
In [22]:
class Solution:
# @param {int[][]} grid a 2D integer grid
# @return {int} an integer
def zombie(self, grid):
# Write your code here
if grid is None or len(grid) == 0 or len(grid[0]) == 0:
return -1
m, n = len(grid), len(grid[0])
day, people, zombies = -1, 0, []
di = [0, 0, 1, -1]
dj = [1, -1, 0, 0]
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
people += 1
elif grid[i][j] == 1:
zombies.append([i, j])
while zombies:
new_zombies = []
for i, j in zombies:
for k in range(4):
zi, zj = i + di[k], j + dj[k]
if 0 <= zi < m and 0 <= zj < n and grid[zi][zj] == 0:
new_zombies.append([zi, zj])
grid[zi][zj] = 1
people -= 1
day += 1
zombies = new_zombies
# print day, zombies
return -1 if people > 0 else day
In [23]:
# Definition for a point.
# class Point:
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b
class Solution:
# @param {boolean[][]} grid a chessboard included 0 (False) and 1 (True)
# @param {Point} source a point
# @param {Point} destination a point
# @return {int} the shortest path
def shortestPath(self, grid, source, destination):
# Write your code here
if grid is None or len(grid) == 0 or len(grid[0]) == 0:
return -1
m, n = len(grid), len(grid[0])
d = [(1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1), (-2,1), (-2,-1)]
path, step = [[source.x, source.y]], -1
while path:
step += 1
new_path = []
for x, y in path:
if [x, y] == [destination.x, destination.y]:
return step
for dx, dy in d:
xx, yy = x + dx, y + dy
if 0 <= xx < m and 0 <= yy < n and grid[xx][yy] != 1:
new_path.append([xx, yy])
grid[xx][yy] = 1
path = new_path
return -1
In [ ]: