-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathleetcode-search.html
296 lines (296 loc) · 172 KB
/
leetcode-search.html
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=2"><meta name="theme-color" content="#222"><meta http-equiv="X-UA-COMPATIBLE" content="IE=edge,chrome=1"><meta name="renderer" content="webkit"><link rel="icon" type="image/ico" sizes="32x32" href="/assets/favicon.ico"><link rel="apple-touch-icon" sizes="180x180" href="/assets/apple-touch-icon.png"><link rel="alternate" href="/rss.xml" title="Jiankychen's Blog" type="application/rss+xml"><link rel="alternate" href="/atom.xml" title="Jiankychen's Blog" type="application/atom+xml"><link rel="alternate" type="application/json" title="Jiankychen's Blog" href="https://jiankychen.github.io/feed.json"><link rel="preconnect" href="https://lf9-cdn-tos.bytecdntp.com"><link rel="preconnect" href="https://at.alicdn.com"><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Mulish:400,400italic,700,700italic%7CFredericka%20the%20Great:400,400italic,700,700italic%7CNoto%20Serif%20JP:400,400italic,700,700italic%7CNoto%20Serif%20SC:400,400italic,700,700italic%7CInconsolata:400,400italic,700,700italic&display=swap&subset=latin,latin-ext" media="none" onload="this.media='all'"><link rel="stylesheet" href="/css/app.css?v=0.4.2"><link rel="modulepreload" href="/js/chunk-7IVLRIQ3.js"><link rel="modulepreload" href="/js/chunk-IXT6LZJL.js"><link rel="modulepreload" href="/js/chunk-PHSEV26P.js"><link rel="modulepreload" href="/js/chunk-XHQGHZCW.js"><link rel="modulepreload" href="/js/comments-TUWNDU5I.js"><link rel="modulepreload" href="/js/post-P6IN2S3Y.js"><link rel="modulepreload" href="/js/quicklink-HAJEHOPK.js"><link rel="modulepreload" href="/js/search-WFXK2K66.js"><link rel="modulepreload" href="/js/siteInit.js"><link rel="stylesheet" href="https://npm.webcache.cn/@waline/[email protected]/dist/waline.css" media="none" onload="this.media='all'"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/42bab566f107b9a16542343e0368fb77.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/YSIlc.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/8fe50780c15461b629c9aeab5a7f2acd.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/488297bfd0233b6c6a444f1860e55d45.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/1135e8eb0ca0a462aa1c2f6ecb6a5ae2.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/Y0hOs.jpg" as="image" fetchpriority="high"><meta name="keywords" content="广度优先搜索,"><link rel="canonical" href="https://jiankychen.github.io/leetcode-search"><title>LeetCode - 搜索专题</title><meta name="generator" content="Hexo 7.0.0"></head><body itemscope="" itemtype="http://schema.org/WebPage"><div id="loading"><div class="cat"><div class="body"></div><div class="head"><div class="face"></div></div><div class="foot"><div class="tummy-end"></div><div class="bottom"></div><div class="legs left"></div><div class="legs right"></div></div><div class="paw"><div class="hands left"></div><div class="hands right"></div></div></div></div><div id="container"><header id="header" itemscope="" itemtype="http://schema.org/WPHeader"><div class="inner"><div id="brand"><div class="pjax"><h1 itemprop="name headline">LeetCode - 搜索专题</h1><div class="meta"><span class="item" title="创建时间：2022-08-16 16:38:30"><span class="icon"><i class="ic i-calendar"></i></span><span class="text">发表于</span><time itemprop="dateCreated datePublished" datetime="2022-08-16T16:38:30+08:00">2022-08-16</time></span><span class="item" title="本文字数"><span class="icon"><i class="ic i-pen"></i></span><span class="text">本文字数</span><span>19k</span><span class="text">字</span></span><span class="item" title="阅读时长"><span class="icon"><i class="ic i-clock"></i></span><span class="text">阅读时长</span><span>17 分钟</span></span></div></div></div><nav id="nav"><div class="inner"><div class="toggle"><div class="lines" aria-label="切换导航栏"><span class="line"></span><span class="line"></span><span class="line"></span></div></div><ul class="menu"><li class="item title"><a href="/" rel="start">Jiankychen</a></li></ul><ul class="right" id="rightNav"><li class="item theme"><i class="ic i-sun"></i></li><li class="item search"><i class="ic i-search"></i></li></ul></div></nav></div><div class="pjax" id="imgs"><ul><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/42bab566f107b9a16542343e0368fb77.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/YSIlc.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/8fe50780c15461b629c9aeab5a7f2acd.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/488297bfd0233b6c6a444f1860e55d45.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/1135e8eb0ca0a462aa1c2f6ecb6a5ae2.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/Y0hOs.jpg");"></li></ul></div></header><div id="waves"><svg class="waves" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 24 150 28" preserveAspectRatio="none" shape-rendering="auto"><defs><path id="gentle-wave" d="M-160 44c30 0 58-18 88-18s 58 18 88 18 58-18 88-18 58 18 88 18 v44h-352z"></path></defs><g class="parallax"><use xlink:href="#gentle-wave" x="48" y="0"></use><use xlink:href="#gentle-wave" x="48" y="3"></use><use xlink:href="#gentle-wave" x="48" y="5"></use><use xlink:href="#gentle-wave" x="48" y="7"></use></g></svg></div><main><div class="inner"><div class="pjax" id="main"><div class="article wrap"><div class="breadcrumb" itemlistelement="" itemscope="" itemtype="https://schema.org/BreadcrumbList"><i class="ic i-home"></i><span><a href="/">首页</a></span><i class="ic i-angle-right"></i><span class="current" itemprop="itemListElement" itemscope="itemscope" itemtype="https://schema.org/ListItem"><a href="/categories/Coding/" itemprop="item" rel="index" title="分类于Coding"><span itemprop="name">Coding<meta itemprop="position" content="0"></span></a></span></div><article class="post block" itemscope="itemscope" itemtype="http://schema.org/Article" lang="zh-CN"><link itemprop="mainEntityOfPage" href="https://jiankychen.github.io/leetcode-search.html"><span hidden="hidden" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><meta itemprop="image" content="/assets/avatar.jpg"><meta itemprop="name" content="Jiankychen"><meta itemprop="description" content="Never put off till tomorrow what you can do today, "></span><span hidden="hidden" itemprop="publisher" itemscope="itemscope" itemtype="http://schema.org/Organization"><meta itemprop="name" content="Jiankychen's Blog"></span><div class="body md" itemprop="articleBody"><h1 id="leetcode-200-岛屿数量"><a class="anchor" href="#leetcode-200-岛屿数量">#</a> LeetCode 200. 岛屿数量</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/number-of-islands/">200. Number of Islands</a></p>
<p>给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。</p>
<p>岛屿总是被水包围，并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。</p>
<p>此外，你可以假设该网格的四条边均被水包围。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><code>m == grid.length</code></li>
<li><code>n == grid[i].length</code></li>
<li><code>1 <= m, n <= 300</code></li>
<li><code>grid[i][j]</code> 的值为 '0' 或 '1'</li>
</ul>
<h2 id="method-1-深度优先搜索"><a class="anchor" href="#method-1-深度优先搜索">#</a> Method 1: 深度优先搜索</h2>
<p>算法思路：</p>
<p>扫描整个二维网格，如果某一个位置为 '1'，则表示查找到一个岛屿，此时需以其为起始位置开始进行深度优先搜索</p>
<p>深度优先搜索的具体操作：</p>
<ul>
<li>将搜索到的 '1' 重新标记为 '0'</li>
<li>从该位置出发，向 4 个方向探索与之相连的位置</li>
</ul>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span> directions <span class="token operator">=</span> <span class="token operator"><</span><span class="token operator">!</span><span class="token operator">--</span>swig<span class="token number">0</span><span class="token operator">--</span><span class="token operator">></span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="2"></td><td><pre></pre></td></tr><tr><td data-num="3"></td><td><pre><span class="token keyword">void</span> <span class="token function">helper</span><span class="token punctuation">(</span>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">char</span><span class="token operator">>></span><span class="token operator">&</span> grid<span class="token punctuation">,</span> <span class="token keyword">int</span> i<span class="token punctuation">,</span> <span class="token keyword">int</span> j<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">int</span> m <span class="token operator">=</span> grid<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">int</span> n <span class="token operator">=</span> grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> grid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token char">'0'</span><span class="token punctuation">;</span> <span class="token comment">// 标记 (i, j) 位置，表示已访问过该位置</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> k <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> k <span class="token operator"><</span> <span class="token number">4</span><span class="token punctuation">;</span> <span class="token operator">++</span>k<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 向四个方向进行搜索</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">int</span> newi <span class="token operator">=</span> i <span class="token operator">+</span> directions<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">int</span> newj <span class="token operator">=</span> j <span class="token operator">+</span> directions<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>newi <span class="token operator">>=</span> <span class="token number">0</span> <span class="token operator">&&</span> newi <span class="token operator"><</span> m <span class="token operator">&&</span> newj <span class="token operator">>=</span> <span class="token number">0</span> <span class="token operator">&&</span> newj <span class="token operator"><</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>grid<span class="token punctuation">[</span>newi<span class="token punctuation">]</span><span class="token punctuation">[</span>newj<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">'1'</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token function">helper</span><span class="token punctuation">(</span>grid<span class="token punctuation">,</span> newi<span class="token punctuation">,</span> newj<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="15"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="16"></td><td><pre></pre></td></tr><tr><td data-num="17"></td><td><pre><span class="token keyword">int</span> <span class="token function">numIslands</span><span class="token punctuation">(</span>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">char</span><span class="token operator">>></span><span class="token operator">&</span> grid<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">int</span> m <span class="token operator">=</span> grid<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token keyword">int</span> n <span class="token operator">=</span> grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> m<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 遍历起点位置</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator"><</span> n<span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>grid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">'1'</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 发现一座岛屿</span></pre></td></tr><tr><td data-num="24"></td><td><pre> <span class="token function">helper</span><span class="token punctuation">(</span>grid<span class="token punctuation">,</span> i<span class="token punctuation">,</span> j<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 扫描整块岛屿</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token operator">++</span>ans<span class="token punctuation">;</span> <span class="token comment">// 岛屿数量加 1</span></pre></td></tr><tr><td data-num="26"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="29"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="30"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>m</mi><mo>×</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(m \times n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">m</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">m</span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 是二维网格的行数和列数</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>m</mi><mo>×</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(m \times n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">m</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，最坏情况下，递归的深度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi><mo>×</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">m \times n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6667em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">m</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span></p>
<h2 id="method-2-广度优先搜索"><a class="anchor" href="#method-2-广度优先搜索">#</a> Method 2: 广度优先搜索</h2>
<p>算法思路：</p>
<p>扫描整个二维网格，每发现一个位置为 '1'，就表示查找到一个岛屿，将该位置加入队列，针对该岛屿开始广度优先搜索，直到队列为空</p>
<ul>
<li>将搜索到的 '1' 重新标记为 '0'</li>
<li>从该位置出发，向 4 个方向探索与之相连的位置</li>
</ul>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">int</span> <span class="token function">numIslands</span><span class="token punctuation">(</span>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">char</span><span class="token operator">>></span><span class="token operator">&</span> grid<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">int</span> m <span class="token operator">=</span> grid<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">int</span> n <span class="token operator">=</span> grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span> directions <span class="token operator">=</span> <span class="token operator"><</span><span class="token operator">!</span><span class="token operator">--</span>swig<span class="token number">1</span><span class="token operator">--</span><span class="token operator">></span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> m<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator"><</span> n<span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>grid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">'1'</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token operator">++</span>ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> grid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token char">'0'</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre> queue<span class="token operator"><</span>pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">>></span> que<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token punctuation">{</span>i<span class="token punctuation">,</span> j<span class="token punctuation">}</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>que<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token keyword">auto</span> neighbor <span class="token operator">=</span> que<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token keyword">int</span> x <span class="token operator">=</span> neighbor<span class="token punctuation">.</span>first<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token keyword">int</span> y <span class="token operator">=</span> neighbor<span class="token punctuation">.</span>second<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> k <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> k <span class="token operator"><</span> <span class="token number">4</span><span class="token punctuation">;</span> <span class="token operator">++</span>k<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token keyword">int</span> newx <span class="token operator">=</span> x <span class="token operator">+</span> directions<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">int</span> newy <span class="token operator">=</span> y <span class="token operator">+</span> directions<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token number">0</span> <span class="token operator"><=</span> newx <span class="token operator">&&</span> newx <span class="token operator"><</span> m <span class="token operator">&&</span> <span class="token number">0</span> <span class="token operator"><=</span> newy <span class="token operator">&&</span> newy <span class="token operator"><</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>grid<span class="token punctuation">[</span>newx<span class="token punctuation">]</span><span class="token punctuation">[</span>newy<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">'1'</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="23"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token punctuation">{</span>newx<span class="token punctuation">,</span> newy<span class="token punctuation">}</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="24"></td><td><pre> grid<span class="token punctuation">[</span>newx<span class="token punctuation">]</span><span class="token punctuation">[</span>newy<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token char">'0'</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="26"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="29"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="30"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="31"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="32"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="33"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>m</mi><mo>×</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(m \times n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">m</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">m</span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 是二维网格的行数和列数</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>min</mi><mo></mo><mo stretchy="false">(</mo><mi>m</mi><mo>×</mo><mi>n</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\min(m \times n))</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mop">min</span><span class="mopen">(</span><span class="mord mathnormal">m</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">n</span><span class="mclose">))</span></span></span></span>，在最坏情况下，整个网格均为陆地，队列的大小为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>min</mi><mo></mo><mo stretchy="false">(</mo><mi>m</mi><mo separator="true">,</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\min(m, n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mop">min</span><span class="mopen">(</span><span class="mord mathnormal">m</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<h1 id="leetcode-207-课程表"><a class="anchor" href="#leetcode-207-课程表">#</a> LeetCode 207. 课程表</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/course-schedule/">207. Course Schedule</a></p>
<p>你这个学期必须选修 <code>numCourses</code> 门课程，记为 <code>0</code> 到 <code>numCourses - 1</code> 。</p>
<p>在选修某些课程之前需要一些先修课程。 先修课程按数组 <code>prerequisites</code> 给出，其中 <code>prerequisites[i] = [ai, bi]</code> ，表示如果要学习课程 <code>ai</code> 则 必须 先学习课程 <code>bi</code> 。</p>
<ul>
<li>例如，先修课程对 <code>[0, 1]</code> 表示：想要学习课程 <code>0</code> ，你需要先完成课程 <code>1</code> 。</li>
</ul>
<p>请你判断是否可能完成所有课程的学习？如果可以，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>numCourses</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>2000</mn></mrow><annotation encoding="application/x-tex">\le 2000</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">2000</span></span></span></span></li>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">0 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">0</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>prerequisites.length</code> \le 5000$</li>
<li><code>prerequisites[i].length</code> == 2</li>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">0 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">0</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>ai</code> , <code>bi</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo><</mo></mrow><annotation encoding="application/x-tex"><</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5782em;vertical-align:-0.0391em;"></span><span class="mrel"><</span></span></span></span> <code>numCourses</code></li>
<li><code>prerequisites[i]</code> 中的所有课程对 互不相同</li>
</ul>
<h2 id="思路"><a class="anchor" href="#思路">#</a> 思路</h2>
<p>给定一个包含 n 个节点的有向图 G，我们给出它的节点编号的一种排列，如果满足：</p>
<ul>
<li>对于图 G 中的任意一条有向边 (u, v)，u 在排列中都出现在 v 的前面</li>
</ul>
<p>那么称该排列是图 G 的 <strong>拓扑排序</strong></p>
<p>根据上述定义，有以下结论：</p>
<ul>
<li>如果图 G 中存在环（即图 G 不是 <strong>有向无环图</strong> ），图 G 不存在拓扑排序</li>
<li>如果图 G 是有向无环图，它的拓扑排序可能不止一种</li>
</ul>
<p>在本题中，我们可以将每一门课看成一个节点，如果学习课程 A 之前必须完成课程 B，则可以连接一条从 B 到 A 的有向边，然后判断该图是否存在拓扑排序（也就是判断该图是否为有向无环图）</p>
<h2 id="method-1-广度优先遍历"><a class="anchor" href="#method-1-广度优先遍历">#</a> Method 1: 广度优先遍历</h2>
<p>算法思路：</p>
<p>我们考虑拓扑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何的先修课程要求。当我们将一个节点加入答案中后，我们就可以移除它的所有出边，代表着它的相邻节点少了一门先修课程的要求。如果某个相邻节点变成了「没有任何入边的节点」，那么就代表着这门课可以开始学习了。按照这样的流程，我们不断地将没有入边的节点加入答案，直到答案中包含所有的节点（得到了一种拓扑排序）或者不存在没有入边的节点（图中包含环）</p>
<p>算法流程：</p>
<p>使用一个队列来进行广度优先搜索：初始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且，它们之间的相对顺序是无关紧要的</p>
<p>在广度优先搜索的每一步中，我们取出队首的节点 u：</p>
<ul>
<li>
<p>将 u 放入答案数组中</p>
</li>
<li>
<p>移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 0，就将 v 放入答案数组中</p>
</li>
</ul>
<p>在广度优先搜索的过程结束后，如果答案数组中包含了这 numCourses 个节点，那就说明我们找到了一种拓扑排序，否则，说明图中存在环，也就不存在拓扑排序了</p>
<blockquote>
<p>特别地，可以只用一个变量来记录入度为 0 的节点个数，而无需将节点实际放入答案数组中。在广度优先搜索结束后，判断该变量的值是否等于课程数，就能知道是否存在一种拓扑排序</p>
</blockquote>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">bool</span> <span class="token function">canFinish</span><span class="token punctuation">(</span><span class="token keyword">int</span> numCourses<span class="token punctuation">,</span> vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span><span class="token operator">&</span> prerequisites<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span> edges<span class="token punctuation">;</span> <span class="token comment">// 有向图的边（邻接表）</span></pre></td></tr><tr><td data-num="3"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> indeg<span class="token punctuation">;</span> <span class="token comment">// 节点的入度</span></pre></td></tr><tr><td data-num="4"></td><td><pre> edges<span class="token punctuation">.</span><span class="token function">resize</span><span class="token punctuation">(</span>numCourses<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> indeg<span class="token punctuation">.</span><span class="token function">resize</span><span class="token punctuation">(</span>numCourses<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">auto</span> info <span class="token operator">:</span> prerequisites<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="7"></td><td><pre> edges<span class="token punctuation">[</span>info<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>info<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 建立一条从 info [1] 到 info [0] 的有向边</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token operator">++</span>indeg<span class="token punctuation">[</span>info<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 更新节点 info [0] 的入度</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="10"></td><td><pre></pre></td></tr><tr><td data-num="11"></td><td><pre> queue<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> que<span class="token punctuation">;</span> <span class="token comment">// 存放入度为 0 的节点</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> numCourses<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>indeg<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> que<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="15"></td><td><pre></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token keyword">int</span> visited <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// 入度为 0 的节点个数（可选修的课程数）</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>que<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token operator">++</span>visited<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token keyword">int</span> u <span class="token operator">=</span> que<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> v <span class="token operator">:</span> edges<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 移除 u 的所有出边</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token operator">--</span>indeg<span class="token punctuation">[</span>v<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>indeg<span class="token punctuation">[</span>v<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> que<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="24"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="26"></td><td><pre> </pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token keyword">return</span> visited <span class="token operator">==</span> numCourses<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="28"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n + m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span>，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 为课程数（即，numCourses），<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">m</span></span></span></span> 为先修课程的要求数（即，prerequisites 中一维数组的数量）</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n + m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span>，其中，邻接表所需空间为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span>，队列所需空间为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<h2 id="method-2-深度优先搜索"><a class="anchor" href="#method-2-深度优先搜索">#</a> Method 2: 深度优先搜索</h2>
<p>算法思路：</p>
<p>借助一个标志列表 flags，用于判断每个节点 i （课程）的状态</p>
<ul>
<li>未被访问：flags [i] == 0</li>
<li>被其他节点启动的深度优先搜索访问过：flags [i] == -1</li>
<li>被当前节点启动的深度优先搜索访问过：flags [i] == 1</li>
</ul>
<p>对 numCourses 个节点依次执行深度优先搜索，判断以每个节点起步的深度优先搜索是否存在环，若存在环直接返回 false</p>
<ul>
<li>终止条件：
<ul>
<li>当 flag [i] == -1，说明当前访问节点已被其他节点启动的深度优先搜索访问过，无需再重复搜索，直接返回 true</li>
<li>当 flag [i] == 1，说明在本轮深度优先搜索中节点 i 被第 2 次访问，即，有环存在，直接返回 false</li>
</ul>
</li>
<li>将当前访问节点 i 对应 flag [i] 置 1</li>
<li>递归访问当前节点 i 的所有邻接节点 j，若发现环则直接返回 false</li>
<li>当前节点所有邻接节点已被遍历，并没有发现环，将当前节点 flag 置为 -1 并返回 true</li>
</ul>
<p>待整个图的深度优先搜索结束，如果未发现环，返回 true</p>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span> edges<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> flags<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre></pre></td></tr><tr><td data-num="4"></td><td><pre><span class="token keyword">bool</span> <span class="token function">DFS</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 判断是否存在以 i 起始的拓扑排序</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>flags<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>flags<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> flags<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">:</span> edges<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">DFS</span><span class="token punctuation">(</span>j<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token boolean">false</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="11"></td><td><pre> flags<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre></pre></td></tr><tr><td data-num="15"></td><td><pre><span class="token keyword">bool</span> <span class="token function">canFinish</span><span class="token punctuation">(</span><span class="token keyword">int</span> numCourses<span class="token punctuation">,</span> vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span><span class="token operator">&</span> prerequisites<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="16"></td><td><pre> edges<span class="token punctuation">.</span><span class="token function">resize</span><span class="token punctuation">(</span>numCourses<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre> flags<span class="token punctuation">.</span><span class="token function">resize</span><span class="token punctuation">(</span>numCourses<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">auto</span> info <span class="token operator">:</span> prerequisites<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="19"></td><td><pre> edges<span class="token punctuation">[</span>info<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>info<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> numCourses<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>flags<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">DFS</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token boolean">false</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="24"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="26"></td><td><pre> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="27"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n + m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span></p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n + m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span></p>
<p>参考：<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/course-schedule/solution/ke-cheng-biao-by-leetcode-solution/">leetcode-solution</a></p>
<h1 id="leetcode-399-除法求值"><a class="anchor" href="#leetcode-399-除法求值">#</a> LeetCode 399. 除法求值</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/evaluate-division/">399. Evaluate Division</a></p>
<p>给你一个变量对数组 <code>equations</code> 和一个实数值数组 <code>values</code> 作为已知条件，其中 <code>equations[i] = [Ai, Bi]</code> 和 <code>values[i]</code> 共同表示等式 <code>Ai / Bi = values[i]</code> 。每个 <code>Ai</code> 或 <code>Bi</code> 是一个表示单个变量的字符串。</p>
<p>另有一些以数组 <code>queries</code> 表示的问题，其中 <code>queries[j] = [Cj, Dj]</code> 表示第 <code>j</code> 个问题，请你根据已知条件找出 <code>Cj / Dj = ?</code> 的结果作为答案。</p>
<p>返回 <strong>所有问题的答案</strong> 。如果存在某个无法确定的答案，则用 <code>-1.0</code> 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 <code>-1.0</code> 替代这个答案。</p>
<p><strong>注意：</strong> 输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]
</code></pre>
<p><strong>示例 3：</strong></p>
<pre><code>输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li>1 <= equations.length <= 20</li>
<li>equations[i].length == 2</li>
<li>1 <= Ai.length, Bi.length <= 5</li>
<li>values.length == equations.length</li>
<li>0.0 < values[i] <= 20.0</li>
<li>1 <= queries.length <= 20</li>
<li>queries[i].length == 2</li>
<li>1 <= Cj.length, Dj.length <= 5</li>
<li>Ai, Bi, Cj, Dj 由小写英文字母与数字组成</li>
</ul>
<h2 id="method-1-广度优先搜索"><a class="anchor" href="#method-1-广度优先搜索">#</a> Method 1: 广度优先搜索</h2>
<h2 id="算法思路"><a class="anchor" href="#算法思路">#</a> 算法思路</h2>
<p>可以将整个问题建模成一个图：将变量字符串视为图的顶点，将两个变量的比值视为两顶点之间边的权值，试对任意两点（两个变量）求其路径长度（两个变量的比值）</p>
<p>首先遍历 <code>equations</code> 数组，将每个不同的变量字符串编号，并通过哈希表建立映射</p>
<p>然后，建立每个顶点的边集并将其存储到数组 <code>vector<vector<pair<int, double>>> edges</code> 中，其中， <code>edges[i]</code> 表示第 i 个顶点的边集， <code>edges[i][j].first</code> 表示顶点 i 的第 j 个邻居节点， <code>edges[i][j].second</code> 表示顶点 i 到其第 j 个邻居节点的路径长度（两个变量的比值）</p>
<p>于是，对于任何一个查询，可以从起点出发，通过广度优先搜索的方式，遍历图中的顶点，并更新起点到当前点的路径长度，直到遍历到终点为止</p>
<blockquote>
<p>由于每次查询都需要遍历图中的所有顶点，当查询数量较大时，效率就会非常低。因此，可以对图进行预处理，先计算出每个顶点到其他顶点的路径长度，然后再依次处理每一个查询</p>
</blockquote>
<h2 id="代码实现"><a class="anchor" href="#代码实现">#</a> 代码实现</h2>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>vector<span class="token operator"><</span><span class="token keyword">double</span><span class="token operator">></span> <span class="token function">calcEquation</span><span class="token punctuation">(</span>vector<span class="token operator"><</span>vector<span class="token operator"><</span>string<span class="token operator">>></span><span class="token operator">&</span> equations<span class="token punctuation">,</span> vector<span class="token operator"><</span><span class="token keyword">double</span><span class="token operator">></span><span class="token operator">&</span> values<span class="token punctuation">,</span> vector<span class="token operator"><</span>vector<span class="token operator"><</span>string<span class="token operator">>></span><span class="token operator">&</span> queries<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token comment">// 给变量字符串编号</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">int</span> varNum <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// 变量字符串的数量</span></pre></td></tr><tr><td data-num="4"></td><td><pre> unordered_map<span class="token operator"><</span>string<span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> vars<span class="token punctuation">;</span> <span class="token comment">// 以变量字符串为 key ，以其编号为 value</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> equations<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>vars<span class="token punctuation">.</span><span class="token function">count</span><span class="token punctuation">(</span>equations<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="7"></td><td><pre> vars<span class="token punctuation">[</span>equations<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">=</span> varNum<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> varNum<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>vars<span class="token punctuation">.</span><span class="token function">count</span><span class="token punctuation">(</span>equations<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="11"></td><td><pre> vars<span class="token punctuation">[</span>equations<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">=</span> varNum<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> varNum<span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="15"></td><td><pre></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token comment">// 将变量视为图的顶点，将两个变量的比值视为两顶点之间边的权值</span></pre></td></tr><tr><td data-num="17"></td><td><pre> vector<span class="token operator"><</span>vector<span class="token operator"><</span>pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">double</span><span class="token operator">>></span><span class="token operator">></span> <span class="token function">edges</span><span class="token punctuation">(</span>varNum<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 存储每个点的邻居及其对应的权值</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> equations<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token keyword">int</span> vertexA <span class="token operator">=</span> vars<span class="token punctuation">[</span>equations<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">int</span> vertexB <span class="token operator">=</span> vars<span class="token punctuation">[</span>equations<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="21"></td><td><pre> edges<span class="token punctuation">[</span>vertexA<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token punctuation">{</span>vertexB<span class="token punctuation">,</span> values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">}</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="22"></td><td><pre> edges<span class="token punctuation">[</span>vertexB<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token punctuation">{</span>vertexA<span class="token punctuation">,</span> <span class="token number">1.0</span> <span class="token operator">/</span> values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">}</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="24"></td><td><pre></pre></td></tr><tr><td data-num="25"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">double</span><span class="token operator">></span> res<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="26"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">auto</span><span class="token operator">&</span> q <span class="token operator">:</span> queries<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 遍历每一个问题</span></pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token comment">// 已知条件中没有出现字符串 q [0] 或 q [1]</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>vars<span class="token punctuation">.</span><span class="token function">count</span><span class="token punctuation">(</span>q<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">||</span> vars<span class="token punctuation">.</span><span class="token function">count</span><span class="token punctuation">(</span>q<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="29"></td><td><pre> res<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">1.0</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 结果为 -1.0</span></pre></td></tr><tr><td data-num="30"></td><td><pre> <span class="token keyword">continue</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="31"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="32"></td><td><pre></pre></td></tr><tr><td data-num="33"></td><td><pre> <span class="token comment">//q [0] 与 q [1] 均出现在已知条件中</span></pre></td></tr><tr><td data-num="34"></td><td><pre> <span class="token comment">// 采用广度优先搜索</span></pre></td></tr><tr><td data-num="35"></td><td><pre> <span class="token keyword">int</span> vertexA <span class="token operator">=</span> vars<span class="token punctuation">[</span>q<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 起点的编号</span></pre></td></tr><tr><td data-num="36"></td><td><pre> <span class="token keyword">int</span> vertexB <span class="token operator">=</span> vars<span class="token punctuation">[</span>q<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 终点的编号</span></pre></td></tr><tr><td data-num="37"></td><td><pre> queue<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> que<span class="token punctuation">;</span> <span class="token comment">// 队列，存放 待访问的顶点</span></pre></td></tr><tr><td data-num="38"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>vertexA<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 将起点入队</span></pre></td></tr><tr><td data-num="39"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">double</span><span class="token operator">></span> <span class="token function">ratios</span><span class="token punctuation">(</span>varNum<span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1.0</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 存放起点 vertexA 到各顶点的路径长度</span></pre></td></tr><tr><td data-num="40"></td><td><pre> ratios<span class="token punctuation">[</span>vertexA<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1.0</span><span class="token punctuation">;</span> <span class="token comment">//vertexA 到其自身的路径长度为 1.0 （自身与自身的比值为 1.0 ）</span></pre></td></tr><tr><td data-num="41"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>que<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&&</span> ratios<span class="token punctuation">[</span>vertexB<span class="token punctuation">]</span> <span class="token operator"><</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 未访问过终点 vertexB</span></pre></td></tr><tr><td data-num="42"></td><td><pre> <span class="token keyword">int</span> u <span class="token operator">=</span> que<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 当前访问的顶点</span></pre></td></tr><tr><td data-num="43"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 将当前顶点出队</span></pre></td></tr><tr><td data-num="44"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">auto</span> <span class="token punctuation">[</span>v<span class="token punctuation">,</span> val<span class="token punctuation">]</span> <span class="token operator">:</span> edges<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 处理顶点 u 的每一条边</span></pre></td></tr><tr><td data-num="45"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>ratios<span class="token punctuation">[</span>v<span class="token punctuation">]</span> <span class="token operator"><</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span><span class="token comment">// 未访问过顶点 v </span></pre></td></tr><tr><td data-num="46"></td><td><pre> ratios<span class="token punctuation">[</span>v<span class="token punctuation">]</span> <span class="token operator">=</span> ratios<span class="token punctuation">[</span>u<span class="token punctuation">]</span> <span class="token operator">*</span> val<span class="token punctuation">;</span> <span class="token comment">// 起点 vertexA 到顶点 v 的路径长度（对应两个变量的比值）</span></pre></td></tr><tr><td data-num="47"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 将顶点 v 入队</span></pre></td></tr><tr><td data-num="48"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="49"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="50"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="51"></td><td><pre> <span class="token comment">// 循环结束时，ratios [vertexB] 即为 vertexA 与 vertexB 对应变量的比值</span></pre></td></tr><tr><td data-num="52"></td><td><pre> <span class="token comment">// 若终点 vertexB 不可达（当队列为空时，仍未访问过 vertexB ），则结果为 -1.0</span></pre></td></tr><tr><td data-num="53"></td><td><pre> res<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>ratios<span class="token punctuation">[</span>vertexB<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="54"></td><td><pre></pre></td></tr><tr><td data-num="55"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="56"></td><td><pre></pre></td></tr><tr><td data-num="57"></td><td><pre> <span class="token keyword">return</span> res<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="58"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>其中， <code>ratios[u]</code> 表示 顶点 <code>vertexA</code> 与顶点 <code>u</code> 对应变量的比值， <code>val</code> 表示 顶点 <code>u</code> 与顶点 <code>v</code> 对应变量的比值，因此，顶点 <code>vertex A</code> 与顶点 <code>v</code> 对应变量的比值为 <code>ratios[u] * val</code> ，即， <code>ratios[v] = ratios[u] * val</code></p>
<h2 id="复杂度分析"><a class="anchor" href="#复杂度分析">#</a> 复杂度分析</h2>
<p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>M</mi><mi>L</mi><mo>+</mo><mi>Q</mi><mo>⋅</mo><mo stretchy="false">(</mo><mi>L</mi><mo>+</mo><mi>M</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(M L + Q \cdot (L + M))</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.10903em;">M</span><span class="mord mathnormal">L</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.8778em;vertical-align:-0.1944em;"></span><span class="mord mathnormal">Q</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">⋅</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">L</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10903em;">M</span><span class="mclose">))</span></span></span></span>，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>M</mi></mrow><annotation encoding="application/x-tex">M</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.10903em;">M</span></span></span></span> 为 数组 <code>equations</code> 的长度（边的数量），<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>L</mi></mrow><annotation encoding="application/x-tex">L</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal">L</span></span></span></span> 为字符串的平均长度，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>Q</mi></mrow><annotation encoding="application/x-tex">Q</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8778em;vertical-align:-0.1944em;"></span><span class="mord mathnormal">Q</span></span></span></span> 为数组 <code>queries</code> 的长度（查询的数量）</p>
<ul>
<li>构建图时，需要处理 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>M</mi></mrow><annotation encoding="application/x-tex">M</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.10903em;">M</span></span></span></span> 条边，每条边都涉及到 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>L</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(L)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">L</span><span class="mclose">)</span></span></span></span> 的字符串比较，时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>M</mi><mi>L</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(M L)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.10903em;">M</span><span class="mord mathnormal">L</span><span class="mclose">)</span></span></span></span></li>
<li>处理每次查询时都要进行一次 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>L</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(L)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">L</span><span class="mclose">)</span></span></span></span> 的字符串比较、遍历 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(M)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.10903em;">M</span><span class="mclose">)</span></span></span></span> 条边（最坏情况下），时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>L</mi><mo>+</mo><mi>M</mi><mo stretchy="false">)</mo><mo>⋅</mo><mi>Q</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O((L + M) \cdot Q)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">((</span><span class="mord mathnormal">L</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10903em;">M</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">⋅</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">Q</span><span class="mclose">)</span></span></span></span></li>
</ul>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>N</mi><mi>L</mi><mo>+</mo><mi>M</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(N L + M)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span><span class="mord mathnormal">L</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10903em;">M</span><span class="mclose">)</span></span></span></span>，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>N</mi></mrow><annotation encoding="application/x-tex">N</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span></span></span></span> 为数组 <code>equations</code> 中的字符串的种类数（图的顶点个数）</p>
<ul>
<li>存储每个变量字符串的编号，需要的空间为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>N</mi><mi>L</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(N L)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span><span class="mord mathnormal">L</span><span class="mclose">)</span></span></span></span></li>
<li>存储图中所有的边及其权重，需要的空间为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(M)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.10903em;">M</span><span class="mclose">)</span></span></span></span></li>
<li>广度优先搜索过程中，存放待访问的顶点，需要的空间为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>N</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(N)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span><span class="mclose">)</span></span></span></span></li>
</ul>
<h2 id="method-2-带权并查集"><a class="anchor" href="#method-2-带权并查集">#</a> Method 2: 带权并查集</h2>
<p>参考：<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/evaluate-division/solution/chu-fa-qiu-zhi-by-leetcode-solution-8nxb/">leetcode-solution</a></p>
<h1 id="leetcode-695-岛屿的最大面积"><a class="anchor" href="#leetcode-695-岛屿的最大面积">#</a> LeetCode 695. 岛屿的最大面积</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/max-area-of-island/">LeetCode 695. Max Area of Island</a></p>
<p>给你一个大小为 <code>m x n</code> 的二进制矩阵 <code>grid</code> 。</p>
<p>岛屿 是由一些相邻的 <code>1</code> (代表土地) 构成的组合，这里的「相邻」要求两个 <code>1</code> 必须在 <strong>水平或者竖直的四个方向上</strong> 相邻。你可以假设 <code>grid</code> 的四个边缘都被 <code>0</code> （代表水）包围着。</p>
<p>岛屿的面积是岛上值为 <code>1</code> 的单元格的数目。</p>
<p>计算并返回 <code>grid</code> 中最大的岛屿面积。如果没有岛屿，则返回面积为 <code>0</code> 。</p>
<p><strong>示例 1：</strong></p>
<p><img loading="lazy" data-src="LeetCode-%E6%90%9C%E7%B4%A2%E4%B8%93%E9%A2%98/LeetCode695_1.webp" alt=""></p>
<pre><code>输入：grid = [[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
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><code>m == grid.length</code></li>
<li><code>n == grid[i].length</code></li>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>m</code> , <code>n</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>50</mn></mrow><annotation encoding="application/x-tex">\le 50</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">50</span></span></span></span></li>
<li><code>grid[i][j]</code> 为 0 或 1</li>
</ul>
<h2 id="method-1-深度优先搜索-2"><a class="anchor" href="#method-1-深度优先搜索-2">#</a> Method 1: 深度优先搜索</h2>
<p>计算网格中每个连通形状的面积，然后取最大值。</p>
<p>在一个土地上，向 4 个方向探索与之相连的每一个土地（以及与这些土地相连的土地），那么探索过的土地总数将是该连通形状的面积</p>
<p><strong>为了确保每个土地访问不超过一次，我们每次经过一块土地时，将这块土地的值置为 <code>0</code> </strong></p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">private</span><span class="token operator">:</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">int</span> <span class="token function">DFS</span><span class="token punctuation">(</span>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span><span class="token operator">&</span> grid<span class="token punctuation">,</span> <span class="token keyword">int</span> cur_i<span class="token punctuation">,</span> <span class="token keyword">int</span> cur_j<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 深度优先搜索</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>cur_i <span class="token operator"><</span> <span class="token number">0</span> <span class="token operator">||</span> cur_i <span class="token operator">==</span> grid<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">||</span> cur_j <span class="token operator"><</span> <span class="token number">0</span> <span class="token operator">||</span> cur_j <span class="token operator">==</span> grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">||</span> grid<span class="token punctuation">[</span>cur_i<span class="token punctuation">]</span><span class="token punctuation">[</span>cur_j<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">//cur_i cur_j 超出边界或 grid [cur_i][cur_j] 为 0 时，返回 0</span></pre></td></tr><tr><td data-num="4"></td><td><pre> grid<span class="token punctuation">[</span>cur_i<span class="token punctuation">]</span><span class="token punctuation">[</span>cur_j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// 已经访问过的位置置 0，以免重复访问</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// 岛屿面积</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">const</span> <span class="token keyword">int</span> di<span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">const</span> <span class="token keyword">int</span> dj<span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> index <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> index <span class="token operator"><</span> <span class="token number">4</span><span class="token punctuation">;</span> index<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">int</span> next_i <span class="token operator">=</span> cur_i <span class="token operator">+</span> di<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">,</span> next_j <span class="token operator">=</span> cur_j <span class="token operator">+</span> dj<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> ans <span class="token operator">+=</span> <span class="token function">DFS</span><span class="token punctuation">(</span>grid<span class="token punctuation">,</span>next_i<span class="token punctuation">,</span>next_j<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre></pre></td></tr><tr><td data-num="15"></td><td><pre><span class="token keyword">public</span><span class="token operator">:</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token keyword">int</span> <span class="token function">maxAreaOfIsland</span><span class="token punctuation">(</span>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span><span class="token operator">&</span> grid<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> grid<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator"><</span> grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="20"></td><td><pre> ans <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> <span class="token function">DFS</span><span class="token punctuation">(</span>grid<span class="token punctuation">,</span>i<span class="token punctuation">,</span>j<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>R</mi><mo>×</mo><mi>C</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(R \times C)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.00773em;">R</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.07153em;">C</span><span class="mclose">)</span></span></span></span>。其中 <code>R</code> 是给定网格中的行数， <code>C</code> 是列数。访问每个网格最多一次</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>R</mi><mo>×</mo><mi>C</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(R \times C)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.00773em;">R</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.07153em;">C</span><span class="mclose">)</span></span></span></span>，递归的深度最大可能是整个网格的大小，因此最大可能使用 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>R</mi><mo>×</mo><mi>C</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(R \times C)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.00773em;">R</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.07153em;">C</span><span class="mclose">)</span></span></span></span> 的栈空间</p>
<h2 id="method-2-深度优先搜索-栈"><a class="anchor" href="#method-2-深度优先搜索-栈">#</a> Method 2: 深度优先搜索 + 栈</h2>
<h2 id="method-3-广度优先搜索"><a class="anchor" href="#method-3-广度优先搜索">#</a> Method 3: 广度优先搜索</h2>
<p>把方法二中的栈改为队列，每次从队首取出土地，并将接下来想要遍历的土地放在队尾，就实现了广度优先搜索算法</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">int</span> <span class="token function">maxAreaOfIsland</span><span class="token punctuation">(</span>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span><span class="token operator">&</span> grid<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">!=</span> grid<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">!=</span> grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">int</span> cur <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> queue<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> queuei<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> queue<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> queuej<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> queuei<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre> queuej<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>j<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>queuei<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">int</span> cur_i <span class="token operator">=</span> queuei<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> cur_j <span class="token operator">=</span> queuej<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> queuei<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> queuej<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>cur_i <span class="token operator"><</span> <span class="token number">0</span> <span class="token operator">||</span> cur_j <span class="token operator"><</span> <span class="token number">0</span> <span class="token operator">||</span> cur_i <span class="token operator">==</span> grid<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">||</span> cur_j <span class="token operator">==</span> grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">||</span> grid<span class="token punctuation">[</span>cur_i<span class="token punctuation">]</span><span class="token punctuation">[</span>cur_j<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token keyword">continue</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token operator">++</span>cur<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> grid<span class="token punctuation">[</span>cur_i<span class="token punctuation">]</span><span class="token punctuation">[</span>cur_j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token keyword">int</span> di<span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">int</span> dj<span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> index <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> index <span class="token operator">!=</span> <span class="token number">4</span><span class="token punctuation">;</span> <span class="token operator">++</span>index<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token keyword">int</span> next_i <span class="token operator">=</span> cur_i <span class="token operator">+</span> di<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">,</span> next_j <span class="token operator">=</span> cur_j <span class="token operator">+</span> dj<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="23"></td><td><pre> queuei<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>next_i<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="24"></td><td><pre> queuej<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>next_j<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="26"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="27"></td><td><pre> ans <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> cur<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="29"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="30"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>R</mi><mo>×</mo><mi>C</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(R \times C)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.00773em;">R</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.07153em;">C</span><span class="mclose">)</span></span></span></span>。其中 <code>R</code> 是给定网格中的行数， <code>C</code> 是列数，访问每个网格最多一次</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>R</mi><mo>×</mo><mi>C</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(R \times C)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.00773em;">R</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.07153em;">C</span><span class="mclose">)</span></span></span></span>，队列中最多会存放所有的土地，土地的数量最多为 <code>R × C</code> 块</p>
<h1 id="leetcode-733-图像渲染"><a class="anchor" href="#leetcode-733-图像渲染">#</a> LeetCode 733. 图像渲染</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/flood-fill/">LeetCode 733. Flood Fill</a></p>
<p>有一幅以 <code>m x n</code> 的二维整数数组表示的图画 <code>image</code> ，其中 <code>image[i][j]</code> 表示该图画的像素值大小（索引 <code>i</code> 和 <code>j</code> 均从 0 开始）。</p>
<p>你也被给予三个整数 <code>sr</code> ， <code>sc</code> 和 <code>newColor</code> 。你应该从像素 <code>image[sr][sc]</code> 开始对图像进行 上色填充 。</p>
<p>为了完成 <strong>上色工作</strong> ，从初始像素开始，记录初始坐标的 <strong>上下左右四个方向上</strong> 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 <strong>四个方向上</strong> 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 <code>newColor</code> 。</p>
<p>最后返回 经过上色渲染后的图像 。</p>
<p></p>
<p><strong>示例 1：</strong></p>
<p><img loading="lazy" data-src="LeetCode-%E6%90%9C%E7%B4%A2%E4%B8%93%E9%A2%98/LeetCode733_1.webp" alt=""></p>
<pre><code>输入：image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
输出：[[2,2,2],[2,2,0],[2,0,1]]
解释：在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
输出：[[2,2,2],[2,2,2]]
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><code>m == image.length</code></li>
<li><code>n == image[i].length</code></li>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>m</code> , <code>n</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>50</mn></mrow><annotation encoding="application/x-tex">\le 50</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">50</span></span></span></span></li>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">0 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">0</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>image[i][j]</code> , <code>newColor</code> < <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mn>16</mn></msup></mrow><annotation encoding="application/x-tex">2^{16}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">16</span></span></span></span></span></span></span></span></span></span></span></span></li>
</ul>
<h2 id="method-1-广度优先搜索-2"><a class="anchor" href="#method-1-广度优先搜索-2">#</a> Method 1: 广度优先搜索</h2>
<p>每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格加入队列，并<strong>将该方格的颜色更新，以防止重复入队</strong>。</p>
<p>注意：因为初始位置的颜色会被修改，所以我们需要保存初始位置的颜色，以便于之后的更新操作。</p>
<p>注意：<strong>当目标颜色和初始颜色相同时，我们无需对原数组进行修改</strong>。</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">const</span> <span class="token keyword">int</span> dx<span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">}</span><span class="token punctuation">;</span> <span class="token comment">// 四个方向</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">const</span> <span class="token keyword">int</span> dy<span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span> <span class="token function">floodFill</span><span class="token punctuation">(</span>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span><span class="token operator">&</span> image<span class="token punctuation">,</span> <span class="token keyword">int</span> sr<span class="token punctuation">,</span> <span class="token keyword">int</span> sc<span class="token punctuation">,</span> <span class="token keyword">int</span> newColor<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">int</span> currColor <span class="token operator">=</span> image<span class="token punctuation">[</span>sr<span class="token punctuation">]</span><span class="token punctuation">[</span>sc<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>currColor <span class="token operator">==</span> newColor<span class="token punctuation">)</span> <span class="token keyword">return</span> image<span class="token punctuation">;</span> <span class="token comment">// 目标颜色和初始颜色相同</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">int</span> n <span class="token operator">=</span> image<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> m <span class="token operator">=</span> image<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> queue<span class="token operator"><</span>pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">>></span> que<span class="token punctuation">;</span> <span class="token comment">// 待搜索位置的队列</span></pre></td></tr><tr><td data-num="8"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">emplace</span><span class="token punctuation">(</span>sr<span class="token punctuation">,</span> sc<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 初始化</span></pre></td></tr><tr><td data-num="9"></td><td><pre> image<span class="token punctuation">[</span>sr<span class="token punctuation">]</span><span class="token punctuation">[</span>sc<span class="token punctuation">]</span> <span class="token operator">=</span> newColor<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>que<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">int</span> x <span class="token operator">=</span> que<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>first<span class="token punctuation">,</span> y <span class="token operator">=</span> que<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>second<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> <span class="token number">4</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token keyword">int</span> mx <span class="token operator">=</span> x <span class="token operator">+</span> dx<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> my <span class="token operator">=</span> y <span class="token operator">+</span> dy<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>mx <span class="token operator">>=</span> <span class="token number">0</span> <span class="token operator">&&</span> mx <span class="token operator"><</span> n <span class="token operator">&&</span> my <span class="token operator">>=</span> <span class="token number">0</span> <span class="token operator">&&</span> my <span class="token operator"><</span> m <span class="token operator">&&</span> image<span class="token punctuation">[</span>mx<span class="token punctuation">]</span><span class="token punctuation">[</span>my<span class="token punctuation">]</span> <span class="token operator">==</span> currColor<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="16"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">emplace</span><span class="token punctuation">(</span>mx<span class="token punctuation">,</span> my<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre> image<span class="token punctuation">[</span>mx<span class="token punctuation">]</span><span class="token punctuation">[</span>my<span class="token punctuation">]</span> <span class="token operator">=</span> newColor<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token keyword">return</span> image<span class="token punctuation">;</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>×</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n \times m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span>，其中 <code>n</code> 和 <code>m</code> 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>×</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n \times m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span>，主要为队列的开销。</p>
<h2 id="method-2-深度优先搜索-2"><a class="anchor" href="#method-2-深度优先搜索-2">#</a> Method 2: 深度优先搜索</h2>
<p>从给定的起点开始，进行深度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格的颜色更新，以防止重复搜索；如果不相同，则进行回溯。</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">const</span> <span class="token keyword">int</span> dx<span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">const</span> <span class="token keyword">int</span> dy<span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre><span class="token keyword">void</span> <span class="token function">dfs</span><span class="token punctuation">(</span>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span><span class="token operator">&</span> image<span class="token punctuation">,</span> <span class="token keyword">int</span> x<span class="token punctuation">,</span> <span class="token keyword">int</span> y<span class="token punctuation">,</span> <span class="token keyword">int</span> color<span class="token punctuation">,</span> <span class="token keyword">int</span> newColor<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>image<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span> <span class="token operator">==</span> color<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="5"></td><td><pre> image<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span> <span class="token operator">=</span> newColor<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> <span class="token number">4</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">int</span> mx <span class="token operator">=</span> x <span class="token operator">+</span> dx<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> my <span class="token operator">=</span> y <span class="token operator">+</span> dy<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>mx <span class="token operator">>=</span> <span class="token number">0</span> <span class="token operator">&&</span> mx <span class="token operator"><</span> image<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&&</span> my <span class="token operator">>=</span> <span class="token number">0</span> <span class="token operator">&&</span> my <span class="token operator"><</span> image<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token function">dfs</span><span class="token punctuation">(</span>image<span class="token punctuation">,</span> mx<span class="token punctuation">,</span> my<span class="token punctuation">,</span> color<span class="token punctuation">,</span> newColor<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 递归，深度优先搜索</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="13"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre></pre></td></tr><tr><td data-num="15"></td><td><pre>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span> <span class="token function">floodFill</span><span class="token punctuation">(</span>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span><span class="token operator">&</span> image<span class="token punctuation">,</span> <span class="token keyword">int</span> sr<span class="token punctuation">,</span> <span class="token keyword">int</span> sc<span class="token punctuation">,</span> <span class="token keyword">int</span> newColor<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token keyword">int</span> currColor <span class="token operator">=</span> image<span class="token punctuation">[</span>sr<span class="token punctuation">]</span><span class="token punctuation">[</span>sc<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>currColor <span class="token operator">!=</span> newColor<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token function">dfs</span><span class="token punctuation">(</span>image<span class="token punctuation">,</span> sr<span class="token punctuation">,</span> sc<span class="token punctuation">,</span> currColor<span class="token punctuation">,</span> newColor<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">return</span> image<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="21"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>×</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n \times m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span>，最坏情况下需要遍历所有的方格一次。</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>×</mo><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n \times m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mclose">)</span></span></span></span>，主要为栈空间的开销。</p>
<div class="tags"><a href="/tags/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2/" rel="tag"><i class="ic i-tag"></i>广度优先搜索</a><a href="/tags/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2/" rel="tag"><i class="ic i-tag"></i>深度优先搜索</a></div></div><footer><div class="meta"><span class="item"><span class="icon"><i class="ic i-calendar-check"></i></span><span class="text">更新于</span><time title="修改时间：2024-06-08 23:08:45" itemprop="dateModified" datetime="2024-06-08T23:08:45+08:00">2024-06-08</time></span></div><div id="copyright"><ul><li class="author"><strong>本文作者：</strong>Jiankychen<i class="ic i-at"><em>@</em></i>Jiankychen's Blog</li><li class="link"><strong>本文链接：</strong><a href="https://jiankychen.github.io/leetcode-search.html" title="LeetCode - 搜索专题">https://jiankychen.github.io/leetcode-search.html</a></li><li class="license"><strong>版权声明：</strong>本站所有文章除特别声明外，均采用 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh"><i class="ic i-creative-commons"><em>(CC)</em></i>BY-NC-SA</a> 许可协议。转载请注明出处！</li></ul></div></footer></article></div><div class="post-nav"><div class="item left"><a href="/leetcode-monotonicstacks.html" rel="prev" itemprop="url" data-background-image="https://i.imgtg.com/2023/03/09/Y0kTl.jpg" title="LeetCode - 单调栈专题"><span class="type">上一篇</span><span class="category"><i class="ic i-flag"></i>Coding</span><h3>LeetCode - 单调栈专题</h3></a></div><div class="item right"><a href="/leetcode-sort.html" rel="next" itemprop="url" data-background-image="https://i.imgtg.com/2023/03/09/Y0iNK.jpg" title="LeetCode - 排序专题"><span class="type">下一篇</span><span class="category"><i class="ic i-flag"></i>Coding</span><h3>LeetCode - 排序专题</h3></a></div></div><div class="wrap" id="comments"></div></div><div id="sidebar"><div class="inner"><div class="panels"><div class="inner"><div class="contents panel pjax" data-title="文章目录"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-200-%E5%B2%9B%E5%B1%BF%E6%95%B0%E9%87%8F"><span class="toc-number">1.</span> <span class="toc-text"> LeetCode 200. 岛屿数量</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2"><span class="toc-number">1.1.</span> <span class="toc-text"> Method 1: 深度优先搜索</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2"><span class="toc-number">1.2.</span> <span class="toc-text"> Method 2: 广度优先搜索</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-207-%E8%AF%BE%E7%A8%8B%E8%A1%A8"><span class="toc-number">2.</span> <span class="toc-text"> LeetCode 207. 课程表</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF"><span class="toc-number">2.1.</span> <span class="toc-text"> 思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86"><span class="toc-number">2.2.</span> <span class="toc-text"> Method 1: 广度优先遍历</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2"><span class="toc-number">2.3.</span> <span class="toc-text"> Method 2: 深度优先搜索</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-399-%E9%99%A4%E6%B3%95%E6%B1%82%E5%80%BC"><span class="toc-number">3.</span> <span class="toc-text"> LeetCode 399. 除法求值</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2"><span class="toc-number">3.1.</span> <span class="toc-text"> Method 1: 广度优先搜索</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E6%80%9D%E8%B7%AF"><span class="toc-number">3.2.</span> <span class="toc-text"> 算法思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="toc-number">3.3.</span> <span class="toc-text"> 代码实现</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="toc-number">3.4.</span> <span class="toc-text"> 复杂度分析</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-%E5%B8%A6%E6%9D%83%E5%B9%B6%E6%9F%A5%E9%9B%86"><span class="toc-number">3.5.</span> <span class="toc-text"> Method 2: 带权并查集</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-695-%E5%B2%9B%E5%B1%BF%E7%9A%84%E6%9C%80%E5%A4%A7%E9%9D%A2%E7%A7%AF"><span class="toc-number">4.</span> <span class="toc-text"> LeetCode 695. 岛屿的最大面积</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2-2"><span class="toc-number">4.1.</span> <span class="toc-text"> Method 1: 深度优先搜索</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2-%E6%A0%88"><span class="toc-number">4.2.</span> <span class="toc-text"> Method 2: 深度优先搜索 + 栈</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-3-%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2"><span class="toc-number">4.3.</span> <span class="toc-text"> Method 3: 广度优先搜索</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-733-%E5%9B%BE%E5%83%8F%E6%B8%B2%E6%9F%93"><span class="toc-number">5.</span> <span class="toc-text"> LeetCode 733. 图像渲染</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2-2"><span class="toc-number">5.1.</span> <span class="toc-text"> Method 1: 广度优先搜索</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2-2"><span class="toc-number">5.2.</span> <span class="toc-text"> Method 2: 深度优先搜索</span></a></li></ol></li></ol></div><div class="related panel pjax" data-title="系列文章"><ul><li><a href="/leetcode-binarysearch.html" rel="bookmark" title="LeetCode - 二分查找专题">LeetCode - 二分查找专题</a></li><li><a href="/leetcode-vectors.html" rel="bookmark" title="LeetCode - 数组专题">LeetCode - 数组专题</a></li><li><a href="/leetcode-list.html" rel="bookmark" title="LeetCode - 链表专题">LeetCode - 链表专题</a></li><li><a href="/leetcode-hashtable.html" rel="bookmark" title="LeetCode - 哈希表专题">LeetCode - 哈希表专题</a></li><li><a href="/leetcode-string.html" rel="bookmark" title="LeetCode - 字符串专题">LeetCode - 字符串专题</a></li><li><a href="/leetcode-stacks&queues.html" rel="bookmark" title="LeetCode - 栈与队列专题">LeetCode - 栈与队列专题</a></li><li><a href="/leetcode-binarytree.html" rel="bookmark" title="LeetCode - 二叉树专题">LeetCode - 二叉树专题</a></li><li><a href="/leetcode-traverse.html" rel="bookmark" title="LeetCode - 回溯专题">LeetCode - 回溯专题</a></li><li><a href="/leetcode-greedy.html" rel="bookmark" title="LeetCode - 贪心专题">LeetCode - 贪心专题</a></li><li><a href="/leetcode-dynamicprogramming.html" rel="bookmark" title="LeetCode - 动态规划专题">LeetCode - 动态规划专题</a></li><li><a href="/leetcode-doublepointer.html" rel="bookmark" title="LeetCode - 双指针专题">LeetCode - 双指针专题</a></li><li><a href="/leetcode-monotonicstacks.html" rel="bookmark" title="LeetCode - 单调栈专题">LeetCode - 单调栈专题</a></li><li class="active"><a href="/leetcode-search.html" rel="bookmark" title="LeetCode - 搜索专题">LeetCode - 搜索专题</a></li><li><a href="/leetcode-sort.html" rel="bookmark" title="LeetCode - 排序专题">LeetCode - 排序专题</a></li><li><a href="/leetcode-input&output.html" rel="bookmark" title="常见输入输出">常见输入输出</a></li><li><a href="/leetcode-analog.html" rel="bookmark" title="LeetCode - 模拟专题">LeetCode - 模拟专题</a></li></ul></div><div class="overview panel" data-title="站点概览"><div class="author" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><img class="image" loading="lazy" decoding="async" itemprop="image" alt="Jiankychen" src="/assets/avatar.webp"><p class="name" itemprop="name">Jiankychen</p><div class="description" itemprop="description"></div></div><nav class="state"><div class="item posts"><a href="/archives/"><span class="count">51</span><span class="name">文章</span></a></div><div class="item categories"><a href="/categories/"><span class="count">8</span><span class="name">分类</span></a></div><div class="item tags"><a href="/tags/"><span class="count">20</span><span class="name">标签</span></a></div></nav><div class="social"><a target="_blank" rel="noopener" href="https://github.com/jiankychen" class="item github" title="https://github.com/jiankychen"><i class="ic i-github"></i></a><a href="mailto:[email protected]" class="item email" title="mailto:[email protected]"><i class="ic i-envelope"></i></a><a target="_blank" rel="noopener" href="https://music.163.com/#/user/home?id=447771275" class="item music" title="https://music.163.com/#/user/home?id=447771275"><i class="ic i-cloud-music"></i></a><a target="_blank" rel="noopener" href="https://www.zhihu.com/people/jiankychen" class="item zhihu" title="https://www.zhihu.com/people/jiankychen"><i class="ic i-zhihu"></i></a></div><div class="menu"><li class="item"><a href="/" rel="section"><i class="ic i-home"></i>首页</a></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>文章</a><ul class="submenu"><li class="item"><a href="/archives/" rel="section"><i class="ic i-list-alt"></i>归档</a></li><li class="item"><a href="/categories/" rel="section"><i class="ic i-th"></i>分类</a></li><li class="item"><a href="/tags/" rel="section"><i class="ic i-tags"></i>标签</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>链接</a><ul class="submenu"><li class="item"><a href="/peers/" rel="section"><i class="ic i-magic"></i>链环</a></li><li class="item"><a href="/friends/" rel="section"><i class="ic i-heart"></i>友链</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-stars"></i>关于</a><ul class="submenu"><li class="item"><a href="/owner/" rel="section"><i class="ic i-user"></i>关于博主</a></li><li class="item"><a href="/site/" rel="section"><i class="ic i-paw"></i>关于本站</a></li><li class="item"><a href="/update/" rel="section"><i class="ic i-cloud"></i>更新日志</a></li></ul></li></div></div></div></div><ul id="quick"><li class="prev pjax"><a href="/leetcode-sort.html" rel="prev" title="上一篇"><i class="ic i-chevron-left"></i></a></li><li class="up"><i class="ic i-arrow-up"></i></li><li class="down"><i class="ic i-arrow-down"></i></li><li class="next pjax"><a href="/leetcode-monotonicstacks.html" rel="next" title="下一篇"><i class="ic i-chevron-right"></i></a></li><li class="percent"></li></ul></div></div><div class="dimmer"></div></div></main><footer id="footer"><div class="inner"><div class="widgets"><div class="rpost pjax"><h2>随机文章</h2><ul><li class="item"><div class="breadcrumb"><a href="/categories/C/" title="分类于C++">C++</a></div><span><a href="/cpp-classes.html">C++ 类</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Tutorial/" title="分类于Tutorial">Tutorial</a></div><span><a href="/vscode-intro.html">vscode 使用</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/binary-search.html">二分查找</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/date-structure.html">数据结构简介</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/KMP.html">KMP 算法</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-string.html">LeetCode - 字符串专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/hash-table.html">哈希表</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-traverse.html">LeetCode - 回溯专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-files.html">Python 文件操作</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/C/" title="分类于C++">C++</a></div><span><a href="/introduce-cpp.html">初识 C++</a></span></li></ul></div><div class="rpost pjax"><h2>最新评论</h2><ul class="leancloud-recent-comment" id="new-comment"></ul></div></div><div class="status"><div class="copyright">© 2021 -<span itemprop="copyrightYear">2024</span><span class="with-love"><i class="ic i-sakura rotate"></i></span><span class="author" itemprop="copyrightHolder">Jiankychen @ Jiankychen</span></div><div class="count"><span class="post-meta-item-icon"><i class="ic i-chart-area"></i></span><span title="站点总字数">955k 字</span><span class="post-meta-divider"> | </span><span class="post-meta-item-icon"><i class="ic i-coffee"></i></span><span title="站点阅读时长">14:28</span></div><div class="powered-by">基于 <a target="_blank" rel="noopener" href="https://hexo.io/">Hexo</a> & Theme.<a target="_blank" rel="noopener" href="https://github.com/theme-shoka-x/hexo-theme-shokaX/">ShokaX</a></div></div><script src="https://unpkg.com/[email protected]/bsz.pure.mini.js"></script><div id="busuanzi-wrap"><span class="ic i-eye"></span><span id="busuanzi_container_site_pv">本站总访问量 <span id="busuanzi_value_site_pv"></span> 次</span> | <span class="ic i-user"></span><span id="busuanzi_container_site_uv">本站总访客量 <span id="busuanzi_value_site_uv"></span> 次</span></div></div></footer></div><script data-config="" type="text/javascript">var LOCAL = {
ispost: true,
path: `/leetcode-search`,
favicon: {
show: `Jiankychen`,
hide: `Jiankychen`
},
search: {
placeholder: "文章搜索",
empty: "关于 「 ${query} 」，什么也没搜到",
stats: "${time} ms 内找到 ${hits} 条结果"
},
copy_tex: true,
katex: true,
mermaid: false,
audio: undefined,
fancybox: true,
nocopy: false,
outime: true,
template: `<div class="note warning"><p><span class="label warning">文章时效性提示</span><br>这是一篇发布于 {{publish}} 天前，最后一次更新在 {{updated}} 天前的文章，部分信息可能已经发生改变，请注意甄别。</p></div>`,
quiz: {
choice: `单选题`,
multiple: `多选题`,
true_false: `判断题`,
essay: `问答题`,
gap_fill: `填空题`,
mistake: `错题备注`
},
ignores: [
(uri) => uri.includes('#'),
(uri) => new RegExp(LOCAL.path + '$').test(uri),
[]
]
};
</script><script src="https://lf9-cdn-tos.bytecdntp.com/cdn/expire-6-M/pace/1.2.4/pace.min.js" async=""></script><script src="https://polyfill.io/v3/polyfill.min.js?features=default,fetch" defer=""></script><script src="/js/siteInit.js?v=0.4.2" type="module" fetchpriority="high" defer=""></script></body></html>