0%

leetcode Graph 图论

本次题解包括

  • 133 Clone Graph
  • 207 Course Schedule
  • 210 Course Schedule II
  • 547 Number of Provinces
  • 684 冗余连接
  • 803 打砖块
  • 947 移除最多的同行或同列石头
  • 1202. Smallest String With Swaps

133. leetcode Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

题目地址: leetcode Clone Graph

题意:给定一张图,要求进行深拷贝

思路:leetcode之前唯一的图。。

用BFS/DFS对图进行遍历,我使用字典(c++叫Map)建立起旧结点和新结点的映射关系,这样就好复制啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
# @return a undirected graph node
def cloneGraph(self, node):
if not node:return None
head=UndirectedGraphNode(node.label)
q,vis,dic=[],set([node]),{}
dic[node]=head
q.append(node)
while q:
cur = q.pop()
for i in cur.neighbors:
if i not in dic:
dic[i]=UndirectedGraphNode(i.label)
dic[cur].neighbors.append(dic[i])
if i not in vis:
q.append(i)
vis.add(i)
return head

附上我的测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class UndirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []

def printGraph(node):
q ,vis = [],set([node])
q.append(node)
while q:
cur = q.pop(0)
print ' ',cur.label
for i in cur.neighbors:
print i.label
if i not in vis:
q.append(i)
vis.add(i)

s=Solution()
one = UndirectedGraphNode(1)
two = UndirectedGraphNode(2)
three =UndirectedGraphNode(3)
one.neighbors.append(one)
one.neighbors.append(two)
two.neighbors.append(three)
#printGraph(one)
printGraph( s.cloneGraph(one))

 


207. leetcode Course Schedule

 There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

1
2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

1
2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

题目地址: leetcode Course Schedule

题意:给定一些课程,以及他们课程之间先修的关系。如我要修课程1,必须先修完课程0,问是否有可能完成这些课程。

思路:很明显的问题可以转化为求拓扑排序(Topological Sort)

拓扑排序的做法如下:

  1. 每次找入度为0的点,输出该入度为0的点,并删除与之相连接的边
  2. 重复1直到没有入度为0的点。之前输出入度为0的点若小于原图的结点数,那么说明图有环,即拓扑排序不存在,否则即为拓扑排序。

以下面的为例:

Topological Sort
Topological Sort
  1. 在(a)图中v0和v1的入度都为0,选择v0并输出,接着删去顶点v0及出边<0,2>,得到的结果如(b)图所示。

  2. 在(b)图中只有一个入度为0的顶点v1,输出v1,接着删去v1和它的三条出边<1,2>,<1,3>和<1,4>,得到的结果如(c)图所示。

  3. 在(c)图中v2和v4的入度都为0,不妨选择v2并输出之,接着删去v2及两条出边<2,3>和<2,5>,得到的结果如(d)图所示。

  4. 在(d)图上依次输出顶点v3,v4和v5,并在每个顶点输出后删除该顶点及出边。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<vector<int> > g(numCourses);
vector<int> in_degree(numCourses, 0);
for (int i = 0; i < prerequisites.size(); i++){
g[prerequisites[i].second].push_back(prerequisites[i].first);
in_degree[prerequisites[i].first]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) if (in_degree[i] == 0) q.push(i);
while (!q.empty()){
int cur = q.front();
q.pop();
for (auto it = g[cur].begin(); it != g[cur].end(); it++)
if (--in_degree[*it] == 0) q.push(*it);
}

for (int i = 0; i < numCourses; i++) if (in_degree[i] != 0) return false;
return true;
}
};

 


210. leetcode Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

1
2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

1
4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

题目地址: leetcode Course Schedule II

题意:和207那题一样,给定各种课程之间依赖关系,求一个满足条件的顺序。

思路:其实就是输出拓扑排序啦~直接上面那题代码改改即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<vector<int> > g(numCourses);
vector<int> in_degree(numCourses, 0);
vector<int> ans;
for (int i = 0; i < prerequisites.size(); i++){
g[prerequisites[i].second].push_back(prerequisites[i].first);
in_degree[prerequisites[i].first]++;
}
queue<int> q;
int cnt = 0;
for (int i = 0; i < numCourses; i++) if (in_degree[i] == 0) q.push(i);
while (!q.empty()){
int cur = q.front();
ans.push_back(cur);
q.pop();
for (auto it = g[cur].begin(); it != g[cur].end(); it++)
if (--in_degree[*it] == 0) q.push(*it);
}

if (ans.size() == numCourses) return ans;
ans.clear();
return ans;
}
};

547. 省份数量

n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1:

img
img
1
2
>输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]]
>输出:2

示例 2:

img
img
1
2
>输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]]
>输出:3

提示:

  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j]10
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]

方法1:dfs即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
vis = [False] * len(isConnected)
ans = 0
for i in range(len(isConnected)):
if vis[i]:
continue
ans += 1
vis[i] = True
self.dfs(i, isConnected, vis)
return ans

def dfs(self, cur, isConnected, vis):
row = isConnected[cur]
for i in range(len(row)):
if row[i] and not vis[i]:
vis[cur] = True
self.dfs(i, isConnected, vis)

方法2: 并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
fa = list(range(len(isConnected)))
for i in range(len(isConnected)):
for j in range(i):
if isConnected[i][j]:
root_x = self.find(i, fa)
root_y = self.find(j, fa)
if root_x != root_y:
fa[root_y] = root_x

return sum([1 if i == fa[i] else 0 for i in range(len(isConnected))])

def find(self, cur, fa):
if fa[cur] == cur: return cur
fa[cur] = self.find(fa[cur], fa)
return fa[cur]

684. 冗余连接

在本问题中, 树指的是一个连通且无环的无向图。

输入一个图,该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。

结果图是一个以组成的二维数组。每一个的元素是一对[u, v] ,满足 u < v,表示连接顶点uv无向图的边。

返回一条可以删去的边,使得结果图是一个有着N个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v

示例 1:

1
2
3
4
5
6
>输入: [[1,2], [1,3], [2,3]]
>输出: [2,3]
>解释: 给定的无向图为:
1
/ \
>2 - 3

示例 2:

1
2
3
4
5
6
>输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
>输出: [1,4]
>解释: 给定的无向图为:
>5 - 1 - 2
| |
4 - 3

注意:

  • 输入的二维数组大小在 3 到 1000。
  • 二维数组中的整数在1到N之间,其中N是输入数组的大小。

更新(2017-09-26): 我们已经重新检查了问题描述及测试用例,明确图是无向 图。对于有向图详见冗余连接II对于造成任何不便,我们深感歉意。

低配版本的kruskal算法(不像MST要排序),并查集即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
max_n = 0
for edge in edges:
max_n = max(max_n, edge[1])

fa = [i for i in range(max_n + 1)]
for edge in edges:
x, y = edge
root_x = self.find(x, fa)
root_y = self.find(y, fa)
if root_x != root_y:
fa[root_y] = root_x
else:
return edge
return []

def find(self, x, fa):
if x != fa[x]:
fa[x] = self.find(fa[x], fa)
return fa[x]

803. 打砖块

有一个 m x n 的二元网格,其中 1 表示砖块,0 表示空白。砖块 稳定(不会掉落)的前提是:

  • 一块砖直接连接到网格的顶部,或者
  • 至少有一块相邻(4 个方向之一)砖块 稳定 不会掉落时

给你一个数组 hits ,这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时,对应位置的砖块(若存在)会消失,然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落,它会立即从网格中消失(即,它不会落在其他稳定的砖块上)。

返回一个数组 result ,其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

注意,消除可能指向是没有砖块的空白位置,如果发生这种情况,则没有砖块掉落。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
>输入:grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
>输出:[2]
>解释:
>网格开始为:
>[[1,0,0,0],
[1,1,1,0]]
>消除 (1,0) 处加粗的砖块,得到网格:
>[[1,0,0,0]
[0,1,1,0]]
>两个加粗的砖不再稳定,因为它们不再与顶部相连,也不再与另一个稳定的砖相邻,因此它们将掉落。得到网格:
>[[1,0,0,0],
[0,0,0,0]]
>因此,结果为 [2] 。

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
>输入:grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
>输出:[0,0]
>解释:
>网格开始为:
>[[1,0,0,0],
[1,1,0,0]]
>消除 (1,1) 处加粗的砖块,得到网格:
>[[1,0,0,0],
[1,0,0,0]]
>剩下的砖都很稳定,所以不会掉落。网格保持不变:
>[[1,0,0,0],
[1,0,0,0]]
>接下来消除 (1,0) 处加粗的砖块,得到网格:
>[[1,0,0,0],
[0,0,0,0]]
>剩下的砖块仍然是稳定的,所以不会有砖块掉落。
>因此,结果为 [0,0] 。

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • grid[i][j]01
  • 1 <= hits.length <= 4 * 104
  • hits[i].length == 2
  • 0 <= xi <= m - 1
  • 0 <= yi <= n - 1
  • 所有 (xi, yi) 互不相同

并查集+逆向思维法。

首先,一块砖是稳定的仅当与屋顶连接,或者周围4个方块有一个是稳定的。当我们消除一个砖块的时候,可能会破坏这个稳定的结构,导致一堆砖块掉落。

注意到一块砖是稳定的=>说明它直接或间接的和屋顶连接=》其他和该砖头连接的都可以看成是一个稳定的连通子图。因此感觉可以用并查集来做。但是并查集是相当于是对两个连通子图的合并,而这道题消除砖块变成连通分量的分解,因此可以考虑逆向思维。

  1. 消除所有hits的砖块,即将grid中在hits数组对应的位置上都设置为0
  2. 可以首先将与屋顶连接的砖块看成同一个连通分量,因为和任意一个连接都没有什么区别。因此用并查集将他们合并
  3. 初始化其他的砖块,将数值为1的合并起来
  4. 经过2和3,就形成了若干个连通分量
  5. 逆序遍历hits数组,对位置x ,y :
    1. 首先确保这个位置原先是1,否则相当于hit了空的位置,这里不该补上1
    2. 如果x == 0说明这个砖块是和屋顶直接连接的,要先和屋顶合并一下(否则可能这个砖头连接的其他的砖头都不和屋顶连接了)
    3. 合并x, y周围的联通分量
    4. pre_num为合并前屋顶联通分量的儿子的数目,after_num为合并后的数量,则通过补上x,y 连接了after_num - pre_num - 1的数量

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution:
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
origin_grid = copy.deepcopy(grid)
for x, y in hits:
grid[x][y] = 0

self.m, self.n = len(grid), len(grid[0])
roof_key = self.get_key(self.m, self.n) # 屋顶的key
unionfind = UnionFind(roof_key + 1)
for j in range(self.n):
if grid[0][j] == 1:
unionfind.union(self.get_key(0, j), roof_key)

for i in range(1, self.m):
for j in range(self.n):
if grid[i][j] == 0:
continue

if grid[i - 1][j]:
unionfind.union(self.get_key(i, j), self.get_key(i - 1, j))
if j and grid[i][j - 1]:
unionfind.union(self.get_key(i, j), self.get_key(i, j - 1))

ans = []
for x, y in hits[::-1]:
if origin_grid[x][y] == 0:
ans.append(0)
continue

cur_key = self.get_key(x, y)
pre_num = unionfind.get_count(roof_key)
if x == 0:
unionfind.union(cur_key, roof_key)
for i in range(4):
nx, ny = x + self.dx[i], y + self.dy[i]
if nx < 0 or ny < 0 or nx >= len(grid) or ny >= len(grid[0]) or \
not grid[nx][ny]:
continue
unionfind.union(cur_key, self.get_key(nx, ny))

after_num = unionfind.get_count(roof_key)
cur = max(after_num - pre_num - 1, 0)
ans.append(cur)
grid[x][y] = 1
return ans[::-1]

def get_key(self, x, y):
return x * self.n + y

class UnionFind(object):
def __init__(self, n):
self.fa = [i for i in range(n)]
self.counter = [1] * n

def find(self, x):
if x != self.fa[x]:
self.fa[x] = self.find(self.fa[x])
return self.fa[x]

def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
self.fa[root_y] = root_x
self.counter[root_x] += self.counter[root_y]

def get_count(self, x):
root_x = self.find(x)
return self.counter[root_x]

947. 移除最多的同行或同列石头

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在,那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ,其中 stones[i] = [xi, yi] 表示第 i 块石头的位置,返回 可以移除的石子 的最大数量。

示例 1:

1
2
3
4
5
6
7
8
9
>输入:stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
>输出:5
>解释:一种移除 5 块石头的方法如下所示:
>1. 移除石头 [2,2] ,因为它和 [2,1] 同行。
>2. 移除石头 [2,1] ,因为它和 [0,1] 同列。
>3. 移除石头 [1,2] ,因为它和 [1,0] 同行。
>4. 移除石头 [1,0] ,因为它和 [0,0] 同列。
>5. 移除石头 [0,1] ,因为它和 [0,0] 同行。
>石头 [0,0] 不能移除,因为它没有与另一块石头同行/列。

示例 2:

1
2
3
4
5
6
7
>输入:stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
>输出:3
>解释:一种移除 3 块石头的方法如下所示:
>1. 移除石头 [2,2] ,因为它和 [2,0] 同行。
>2. 移除石头 [2,0] ,因为它和 [0,0] 同列。
>3. 移除石头 [0,2] ,因为它和 [0,0] 同行。
>石头 [0,0] 和 [1,1] 不能移除,因为它们没有与另一块石头同行/列。

示例 3:

1
2
3
>输入:stones = [[0,0]]
>输出:0
>解释:[0,0] 是平面上唯一一块石头,所以不可以移除它。

提示:

  • 1 <= stones.length <= 1000
  • 0 <= xi, yi <= 10^4
  • 不会有两块石头放在同一个坐标点上

题目说,如果一块石头的 同行或者同列 上有其他石头存在,那么就可以移除这块石头。

容易想到,可以根据这个规则将同行或者同列的删除得剩下一个石头。比如下面的,由于同行同列可以删除,最优的做法就是删除得剩下一个。

1
2
3
1 0 0 1
0 1 0 0
0 1 0 1

这就又是并查集的思路了:每个连通子图都可以剩下一个,那么答案就是总共的石头数目-连通子图的个数。

所以对于x, y坐标就是把横纵坐标合并为一个子图。由于x, y < 10^4,因此可以将y的坐标加上10001来区分x, y坐标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
fa = {}
for (x, y) in stones:
root_x = self.find(fa, x)
root_y = self.find(fa, y + 10001)
if root_x != root_y:
fa[root_y] = root_x

cnt = 0
for x, root_x in fa.items():
if x == root_x:
cnt += 1
return len(stones) - cnt

def find(self, fa, x):
if x not in fa:
fa[x] = x
return x
if x == fa[x]:
return fa[x]
fa[x] = self.find(fa, fa[x])
return fa[x]

1202. 交换字符串中的元素

给你一个字符串 s,以及该字符串中的一些「索引对」数组 pairs,其中 pairs[i] = [a, b] 表示字符串中的两个索引(编号从 0 开始)。

你可以 任意多次交换pairs 中任意一对索引处的字符。

返回在经过若干次交换后,s 可以变成的按字典序最小的字符串。

示例 1:

1
2
3
4
5
>输入:s = "dcab", pairs = [[0,3],[1,2]]
>输出:"bacd"
>解释:
>交换 s[0] 和 s[3], s = "bcad"
>交换 s[1] 和 s[2], s = "bacd"

示例 2:

1
2
3
4
5
6
>输入:s = "dcab", pairs = [[0,3],[1,2],[0,2]]
>输出:"abcd"
>解释:
>交换 s[0] 和 s[3], s = "bcad"
>交换 s[0] 和 s[2], s = "acbd"
>交换 s[1] 和 s[2], s = "abcd"

示例 3:

1
2
3
4
5
6
>输入:s = "cba", pairs = [[0,1],[1,2]]
>输出:"abc"
>解释:
>交换 s[0] 和 s[1], s = "bca"
>交换 s[1] 和 s[2], s = "bac"
>交换 s[0] 和 s[1], s = "abc"

提示:

  • 1 <= s.length <= 10^5
  • 0 <= pairs.length <= 10^5
  • 0 <= pairs[i][0], pairs[i][1] < s.length
  • s 中只含有小写英文字母

这题有一个pairs数组,可以任意多次交换,容易想到的是,[0, 3]能交换,[3, 6]能交换,那么[0, 6]也能交换(具有传递性)。

因此可以用一个并查集,来找到所有的连通分量,对于同一组连通分量的,进行排序,然后按大小输出即可。

注意这里由于只有小写字母,因此可以用计数排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
vector<int> fa(s.size(), 0);
for (std::size_t i = 0; i < s.size(); ++i) {
fa[i] = i;
}

for (auto& pair : pairs) {
int root_x = find(pair[0], fa);
int root_y = find(pair[1], fa);
fa[root_y] = root_x;
}

unordered_map<int, vector<int>> counter;
for (std::size_t i = 0; i < s.size(); ++i) {
int root = find(i, fa);
if (counter.find(root) == counter.end()) {
counter[root] = vector(26, 0);
}
++counter[root][s[i] - 'a'];
}

stringstream ss;
for (std::size_t i = 0; i < s.size(); ++i) {
int root = find(i, fa);
vector<int>& cnt = counter[root];
for (std::size_t j = 0; j < 26; ++j) {
if (cnt[j] > 0) {
--cnt[j];
ss << char('a' + j);
break;
}
}
}
return ss.str();
}

int find(int cur, vector<int>& fa) {
return cur == fa[cur]? cur : fa[cur] = find(fa[cur], fa);
}
};
请我喝杯咖啡吧~