文章目錄
- 785. 判斷二分圖（圖 DFS，染色）
- 207. 課程表（拓撲排序，有向無環圖）
- 684. 冗余連接（并查集）
- 695. 島嶼的最大面積（DFS）
- 200. 島嶼數量（DFS）
- 463. 島嶼的周長
785. 判斷二分圖（圖 DFS，染色）
給定一個無向圖graph，當這個圖為二分圖時返回true。
如果我們能將一個圖的節點集合分割成兩個獨立的子集A和B，并使圖中的每一條邊的兩個節點一個來自A集合，一個來自B集合，我們就將這個圖稱為二分圖。
graph將會以鄰接表方式給出，graph[i]表示圖中與節點i相連的所有節點。每個節點都是一個在0到graph.length-1之間的整數。這圖中沒有自環和平行邊： graph[i] 中不存在i，并且graph[i]中沒有重復的值。
示例 1:
輸入: [[1,3], [0,2], [1,3], [0,2]]
輸出: true
解釋:
無向圖如下:
0----1
| |
| |
3----2
我們可以將節點分成兩組: {0, 2} 和 {1, 3}。
思路：這個本質上可以理解為染色問題，相鄰兩個點的染色不一致就是二分圖了
class
Solution
(
object
)
:
def
isBipartite
(
self
,
graph
)
:
"""
:type graph: List[List[int]]
:rtype: bool
"""
# 初始化顏色 -1，0 和 1 兩種染色
colors
=
[
-
1
]
*
len
(
graph
)
for
i
in
range
(
len
(
graph
)
)
:
# 遍歷每一個結點
if
colors
[
i
]
==
-
1
and
not
self
.
dfs
(
i
,
0
,
colors
,
graph
)
:
# 如果都沒有染色且dfs返回False
return
False
return
True
def
dfs
(
self
,
cur_node
,
cur_color
,
colors
,
graph
)
:
if
colors
[
cur_node
]
!=
-
1
:
# 如果當前結點已經涂了顏色
return
colors
[
cur_node
]
==
cur_color
#當前結點的顏色和該點應該的顏色相等(承接下面if條件的)
# 給結點涂顏色
colors
[
cur_node
]
=
cur_color
for
next_node
in
graph
[
cur_node
]
:
#遍歷相鄰的結點，1-cur_color 表示涂相反的顏色
if
not
self
.
dfs
(
next_node
,
1
-
cur_color
,
colors
,
graph
)
:
# 該結點0，那結點就涂1，反之亦然
return
False
return
True
207. 課程表（拓撲排序，有向無環圖）
現在你總共有 n 門課需要選，記為 0 到 n-1。
在選修某些課程之前需要一些先修課程。 例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示他們: [0,1]
給定課程總量以及它們的先決條件，判斷是否可能完成所有課程的學習？
-
示例 1:
輸入: 2, [[1,0]]
輸出: true
解釋: 總共有 2 門課程。學習課程 1 之前，你需要完成課程 0。所以這是可能的。 -
示例 2:
輸入: 2, [[1,0],[0,1]]
輸出: false
解釋: 總共有 2 門課程。學習課程 1 之前，你需要先完成?課程 0；并且學習課程 0 之前，你還應先完成課程 1。這是不可能的。
思路1：BFS，統計每個結點的入度和鄰接表，將所有入度為 0 的結點存在隊列中，隊列不為空時，一個一個出隊列，出隊列的結點的所有后繼結點入度 -1（相當于刪除了該出隊列的結點），如果后繼結點的入度 -1 后入度為 0（只有出隊列的結點為前繼結點），則繼續添加到隊列中！統計所有出隊列的結點的數量，如果和原結點相同，則無環！
參考： https://leetcode-cn.com/problems/course-schedule/solution/tuo-bu-pai-xu-by-liweiwei1419/
class
Solution
(
object
)
:
def
canFinish
(
self
,
numCourses
,
prerequisites
)
:
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
# 課程的長度
clen
=
len
(
prerequisites
)
if
clen
==
0
:
# 沒有課程，當然可以完成課程的學習
return
True
# 步驟1：統計每個頂點的入度，搭建鄰接矩陣
# 入度數組，記錄了指向它的結點的個數，一開始全部為 0
in_degrees
=
[
0
for
_
in
range
(
numCourses
)
]
# 鄰接表，使用set是為了去重
adj
=
[
set
(
)
for
_
in
range
(
numCourses
)
]
# 這里[set()]*numCourses 這樣的話每個set都一樣
# [0, 1] 表示 1 在先，0 在后，注意：鄰接表存放的是后繼 successor 結點的集合
for
second
,
first
in
prerequisites
:
in_degrees
[
second
]
+=
1
# 統計每個點的入度
adj
[
first
]
.
add
(
second
)
# 搭建鄰接表
# 步驟2：拓撲排序開始之前，先把所有入度為 0 的結點加入到一個隊列中
# 首先遍歷一遍，把所有入度為 0 的結點都加入隊列
queue
=
[
]
for
i
in
range
(
numCourses
)
:
if
in_degrees
[
i
]
==
0
:
queue
.
append
(
i
)
counter
=
0
while
queue
:
top
=
queue
.
pop
(
0
)
counter
+=
1
# 步驟3：把這個結點的所有后繼結點的入度減去 1（刪掉這個結點），如果發現入度為 0（后繼結點只有這一個結點的前繼） ，就馬上添加到隊列中
for
successor
in
adj
[
top
]
:
in_degrees
[
successor
]
-=
1
if
in_degrees
[
successor
]
==
0
:
queue
.
append
(
successor
)
return
counter
==
numCourses
思路二：DFS
bryant
684. 冗余連接（并查集）
在本問題中, 樹指的是一個連通且無環的無向圖。
輸入一個圖，該圖由一個有著N個節點 (節點值不重復1, 2, …, N) 的樹及一條附加的邊構成。附加的邊的兩個頂點包含在1到N中間，這條附加的邊不屬于樹中已存在的邊。
結果圖是一個以邊組成的二維數組。每一個邊的元素是一對[u, v] ，滿足 u < v，表示連接頂點u 和v的無向圖的邊。
返回一條可以刪去的邊，使得結果圖是一個有著N個節點的樹。如果有多個答案，則返回二維數組中最后出現的邊。答案邊 [u, v] 應滿足相同的格式 u < v。
-
示例 1：
輸入: [[1,2], [1,3], [2,3]]
輸出: [2,3]
解釋: 給定的無向圖為:
-
示例 2：
輸入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
輸出: [1,4]
解釋: 給定的無向圖為:
思路：
大致可以這么理解，每個結點表示每位俠客，初始化的時候，每個俠客都是單獨的門派，邊表示兩人狹路相逢要打架了，首先自報家門，
- 如果來自不同門派，就一決雌雄（誰贏由你代碼決定），然后把決斗的兩者的門派歸并成勝利一方的門派
- 如果來自同一門派，表示形成回路了，返回這兩位大俠
（參考 并查集詳解（超級簡單有趣~~就學會了））
也可以這么理解：
有點像貪吃蛇，點就是每條蛇，邊表示兩蛇之間的游動遭遇了，遍歷每條邊，就表示遍歷每次遭遇戰，
- 如果兩條蛇不是一個隊伍的，就一方吃掉另一方（壯大自己）
- 如果兩條蛇是一個隊伍的，自己吃自己……死了
class
UnionFind
:
def
__init__
(
self
,
n
)
:
# n 為邊的數量
self
.
ids
=
[
i
for
i
in
range
(
n
+
1
)
]
# 創建了邊+1個門派，初始化門派名為結點（大俠）名
def
find
(
self
,
p
)
:
# 找門派
return
self
.
ids
[
p
]
def
connect
(
self
,
u
,
v
)
:
# 是否來自同一門派
return
self
.
find
(
u
)
==
self
.
find
(
v
)
def
union
(
self
,
u
,
v
)
:
# 把大俠 u 所在的門派合并到大俠 v 門派
u_id
=
self
.
find
(
u
)
# 報門派
v_id
=
self
.
find
(
v
)
# 報門派
if
u_id
==
v_id
:
# 同一個門派，就不用合并了
return
for
i
in
range
(
len
(
self
.
ids
)
)
:
#遍歷每位大俠
if
self
.
ids
[
i
]
==
u_id
:
self
.
ids
[
i
]
=
v_id
# 把 u 門派的大俠，合并到 v 的門派
class
Solution
(
object
)
:
def
findRedundantConnection
(
self
,
edges
)
:
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
uf
=
UnionFind
(
len
(
edges
)
)
# 初始化門派
for
u
,
v
in
edges
:
if
uf
.
connect
(
u
,
v
)
:
# 如果兩位大俠來自同一門派
return
u
,
v
uf
.
union
(
u
,
v
)
# 把 u 所在門派的大俠們合并到 v 所在的門派
return
695. 島嶼的最大面積（DFS）
給定一個包含了一些 0 和 1的非空二維數組 grid , 一個 島嶼 是由四個方向 (水平或垂直) 的 1 (代表土地) 構成的組合。你可以假設二維矩陣的四個邊緣都被水包圍著。
找到給定的二維數組中最大的島嶼面積。(如果沒有島嶼，則返回面積為0。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
對于上面這個給定矩陣應返回 6。注意答案不應該是11，因為島嶼只能包含水平或垂直的四個方向的‘1’。
思路：遍歷 grid，對每個島嶼（=1的點）進行一次 dfs，遍歷過的島嶼變成陸地，輸出最大的 dfs 結果即可！
class
Solution
(
object
)
:
def
maxAreaOfIsland
(
self
,
grid
)
:
"""
:type grid: List[List[int]]
:rtype: int
"""
r
,
c
=
len
(
grid
)
,
len
(
grid
[
0
]
)
def
dfs
(
i
,
j
)
:
# 計算每一個點的四個方向的深度遍歷
if
0
<=
i
<
r
and
0
<=
j
<
c
and
grid
[
i
]
[
j
]
:
#只遍歷大陸
grid
[
i
]
[
j
]
=
0
# 遍歷過的點不參與面積的計算（變成海洋）
return
1
+
dfs
(
i
-
1
,
j
)
+
dfs
(
i
+
1
,
j
)
+
dfs
(
i
,
j
-
1
)
+
dfs
(
i
,
j
+
1
)
else
:
return
0
# 越界的話返回 0
result
=
0
for
i
in
range
(
r
)
:
for
j
in
range
(
c
)
:
if
grid
[
i
]
[
j
]
:
# 只遍歷有島嶼的點
result
=
max
(
result
,
dfs
(
i
,
j
)
)
#輸出最大的結果
return
result
200. 島嶼數量（DFS）
給定一個由 ‘1’（陸地）和 ‘0’（水）組成的的二維網格，計算島嶼的數量。一個島被水包圍，并且它是通過水平方向或垂直方向上相鄰的陸地連接而成的。你可以假設網格的四個邊均被水包圍。
-
示例 1:
輸入:
11110
11010
11000
00000
輸出: 1 -
示例 2:
輸入:
11000
11000
00100
00011
輸出: 3
思路：斜著的不算，4 鄰域不是 8 鄰域，同
695. 島嶼的最大面積
一樣，要注意的是數據類型，這里是 str，695 是 int，我們在695的基礎上，把每次的 dfs 結果存起來，計算長度即可！
class
Solution
(
object
)
:
def
numIslands
(
self
,
grid
)
:
"""
:type grid: List[List[str]]
:rtype: int
"""
if
grid
==
[
]
:
# 極端情況
return
0
row
,
col
=
len
(
grid
)
,
len
(
grid
[
0
]
)
def
dfs
(
i
,
j
)
:
# dfs 遍歷每個島嶼的大小
if
0
<=
i
<
row
and
0
<=
j
<
col
and
grid
[
i
]
[
j
]
==
"1"
:
grid
[
i
]
[
j
]
=
"0"
# 計算過的島就讓他變成海洋（這句最重要了），訪問過的就不再訪問了
return
1
+
dfs
(
i
-
1
,
j
)
+
dfs
(
i
+
1
,
j
)
+
dfs
(
i
,
j
-
1
)
+
dfs
(
i
,
j
+
1
)
else
:
return
0
list1
=
[
]
for
r
in
range
(
row
)
:
for
c
in
range
(
col
)
:
if
grid
[
r
]
[
c
]
==
"1"
:
# 遍歷整個地圖，只在有島的地方用 dfs
list1
.
append
(
dfs
(
r
,
c
)
)
# 把結果存在列表中
return
len
(
list1
)
# 返回列表的長度
463. 島嶼的周長
給定一個包含 0 和 1 的二維網格地圖，其中 1 表示陸地 0 表示水域。
網格中的格子水平和垂直方向相連（對角線方向不相連）。整個網格被水完全包圍，但其中恰好有一個島嶼（或者說，一個或多個表示陸地的格子相連組成的島嶼）。
島嶼中沒有“湖”（“湖” 指水域在島嶼內部且不和島嶼周圍的水相連）。格子是邊長為 1 的正方形。網格為長方形，且寬度和高度均不超過 100 。計算這個島嶼的周長。
-
示例 :
輸入:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
輸出: 16
解釋: 它的周長是下面圖片中的 16 個黃色的邊：
思路：比較直接（笨）的方法是，統計每個有島的地方，遍歷四領域，有島嶼的話，邊長被覆蓋 -1
class
Solution
(
object
)
:
def
islandPerimeter
(
self
,
grid
)
:
"""
:type grid: List[List[int]]
:rtype: int
"""
r
,
c
=
len
(
grid
)
,
len
(
grid
[
0
]
)
total_num
=
0
for
i
in
range
(
r
)
:
for
j
in
range
(
c
)
:
if
grid
[
i
]
[
j
]
==
1
:
num
=
0
if
0
<=
i
-
1
<
r
and
0
<=
j
<
c
and
grid
[
i
-
1
]
[
j
]
==
1
:
num
+=
1
if
0
<=
i
+
1
<
r
and
0
<=
j
<
c
and
grid
[
i
+
1
]
[
j
]
==
1
:
num
+=
1
if
0
<=
i
<
r
and
0
<=
j
-
1
<
c
and
grid
[
i
]
[
j
-
1
]
==
1
:
num
+=
1
if
0
<=
i
<
r
and
0
<=
j
+
1
<
c
and
grid
[
i
]
[
j
+
1
]
==
1
:
num
+=
1
total_num
+=
(
4
-
num
)
return
total_num
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
