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