{"id":466,"date":"2025-10-29T15:28:01","date_gmt":"2025-10-29T07:28:01","guid":{"rendered":"https:\/\/heyingnian.com\/?p=466"},"modified":"2025-10-29T15:28:35","modified_gmt":"2025-10-29T07:28:35","slug":"leetcode-200","status":"publish","type":"post","link":"https:\/\/heyingnian.com\/index.php\/2025\/10\/29\/leetcode-200\/","title":{"rendered":"\u5c9b\u5c7f\u6570\u91cf"},"content":{"rendered":"\n<h1 class=\"wp-block-heading\">\ud83d\udd17 \u5c9b\u5c7f\u6570\u91cf<\/h1>\n\n\n\n<p><strong>\u9898\u76ee\u6765\u6e90<\/strong>\uff1a<a target=\"_blank\" rel=\"noreferrer noopener\"><a href=\"https:\/\/leetcode.cn\/problems\/number-of-islands\/description\/?envType=study-plan-v2&amp;envId=top-100-liked\" target=\"_blank\" rel=\"noopener\">200. \u5c9b\u5c7f\u6570\u91cf &#8211; \u529b\u6263\uff08LeetCode\uff09<\/a><\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\ud83d\udccc \u9898\u76ee\u63cf\u8ff0<\/h2>\n\n\n\n<p>\u7ed9\u4f60\u4e00\u4e2a\u7531 <code>'1'<\/code>\uff08\u9646\u5730\uff09\u548c <code>'0'<\/code>\uff08\u6c34\uff09\u7ec4\u6210\u7684\u4e8c\u7ef4\u7f51\u683c\uff0c\u8bf7\u4f60\u8ba1\u7b97\u5176\u4e2d<strong>\u5c9b\u5c7f\u7684\u6570\u91cf<\/strong>\u3002<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>\u5c9b\u5c7f<\/strong>\u662f\u7531\u6c34\u5e73\u6216\u7ad6\u76f4\u65b9\u5411\u4e0a\u76f8\u90bb\u7684\u9646\u5730\uff08<code>'1'<\/code>\uff09\u8fde\u63a5\u5f62\u6210\u7684\uff1b<\/li>\n\n\n\n<li>\u5c9b\u5c7f\u88ab\u6c34\uff08<code>'0'<\/code>\uff09\u5305\u56f4\uff1b<\/li>\n\n\n\n<li>\u7f51\u683c\u7684\u56db\u6761\u8fb9\u5916\u5747\u89c6\u4e3a\u6c34\u3002<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u2705 \u793a\u4f8b\u89e3\u6790<\/h2>\n\n\n\n<p><strong>\u793a\u4f8b 1\uff1a<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><code>\u8f93\u5165\uff1agrid = [<br>  ['1','1','1','1','0'],<br>  ['1','1','0','1','0'],<br>  ['1','1','0','0','0'],<br>  ['0','0','0','0','0']<br>]<br>\u8f93\u51fa\uff1a1<\/code><\/pre>\n\n\n\n<p>\u89e3\u91ca\uff1a\u6240\u6709\u9646\u5730\u8fde\u6210\u4e00\u7247\uff0c\u6784\u6210\u4e00\u4e2a\u5c9b\u5c7f\u3002<\/p>\n\n\n\n<p><strong>\u793a\u4f8b 2\uff1a<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><code>\u8f93\u5165\uff1agrid = [<br>  ['1','1','0','0','0'],<br>  ['1','1','0','0','0'],<br>  ['0','0','1','0','0'],<br>  ['0','0','0','1','1']<br>]<br>\u8f93\u51fa\uff1a3<\/code><\/pre>\n\n\n\n<p>\u89e3\u91ca\uff1a\u5b58\u5728\u4e09\u4e2a\u4e92\u4e0d\u76f8\u8fde\u7684\u9646\u5730\u533a\u57df\u3002<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u26a0\ufe0f \u63d0\u793a<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>m == grid.length<\/code>\uff0c<code>n == grid[i].length<\/code><\/li>\n\n\n\n<li><code>1 &lt;= m, n &lt;= 300<\/code><\/li>\n\n\n\n<li><code>grid[i][j]<\/code>\u00a0\u7684\u503c\u4e3a\u00a0<code>'0'<\/code>\u00a0\u6216\u00a0<code>'1'<\/code><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\ud83d\udca1 \u89e3\u6cd5\uff1a\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\uff08DFS\uff09\u2014\u2014 O(mn) \u65f6\u95f4\uff0cO(mn) \u7a7a\u95f4\uff08\u6700\u574f\uff09<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\n    public int numIslands(char&#91;]&#91;] grid) {\n        int count = 0;\n        \/\/ \u904d\u5386\u6574\u4e2a\u7f51\u683c\n        for (int i = 0; i &lt; grid.length; i++) {\n            for (int j = 0; j &lt; grid&#91;i].length; j++) {\n                \/\/ \u53d1\u73b0\u9646\u5730\uff0c\u8bf4\u660e\u627e\u5230\u4e00\u4e2a\u65b0\u5c9b\u5c7f\n                if (grid&#91;i]&#91;j] == '1') {\n                    count++;\n                    \/\/ \u7528 DFS \u5c06\u8be5\u5c9b\u5c7f\u6240\u6709\u9646\u5730\u201c\u6df9\u6ca1\u201d\uff08\u6807\u8bb0\u4e3a '0'\uff09\n                    dfs(grid, i, j);\n                }\n            }\n        }\n        return count;\n    }\n\n    private void dfs(char&#91;]&#91;] grid, int i, int j) {\n        \/\/ \u8fb9\u754c\u68c0\u67e5 + \u6c34\u57df\/\u5df2\u8bbf\u95ee\u68c0\u67e5\n        if (i &lt; 0 || i >= grid.length || \n            j &lt; 0 || j >= grid&#91;0].length || \n            grid&#91;i]&#91;j] == '0') {\n            return;\n        }\n\n        \/\/ \u6807\u8bb0\u5f53\u524d\u9646\u5730\u4e3a\u5df2\u8bbf\u95ee\uff08\u201c\u6df9\u6ca1\u201d\uff09\n        grid&#91;i]&#91;j] = '0';\n\n        \/\/ \u5411\u56db\u4e2a\u65b9\u5411\u7ee7\u7eed\u641c\u7d22\n        dfs(grid, i + 1, j); \/\/ \u4e0b\n        dfs(grid, i - 1, j); \/\/ \u4e0a\n        dfs(grid, i, j + 1); \/\/ \u53f3\n        dfs(grid, i, j - 1); \/\/ \u5de6\n    }\n}<\/code><\/pre>\n\n\n\n<p>\u2705 <strong>\u5173\u952e\u70b9<\/strong>\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u6bcf\u6b21\u9047\u5230\u00a0<code>'1'<\/code>\uff0c\u5c31\u8bf4\u660e\u53d1\u73b0\u4e00\u4e2a<strong>\u65b0\u5c9b\u5c7f<\/strong>\uff1b<\/li>\n\n\n\n<li>\u7acb\u5373\u901a\u8fc7\u00a0<strong>DFS \u5c06\u8be5\u5c9b\u5c7f\u6240\u6709\u76f8\u8fde\u9646\u5730\u53d8\u4e3a\u00a0<code>'0'<\/code><\/strong>\uff0c\u907f\u514d\u91cd\u590d\u8ba1\u6570\uff1b<\/li>\n\n\n\n<li>\u672c\u8d28\u662f\u00a0<strong>\u201c\u8fde\u901a\u5206\u91cf\u8ba1\u6570\u201d<\/strong>\u00a0\u95ee\u9898\uff0cDFS\/BFS\/\u5e76\u67e5\u96c6\u5747\u53ef\u89e3\u3002<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\ud83d\udcca \u590d\u6742\u5ea6\u5206\u6790<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>\u65f6\u95f4\u590d\u6742\u5ea6<\/strong>\uff1a<code>O(m \u00d7 n)<\/code><br>\u6bcf\u4e2a\u683c\u5b50\u6700\u591a\u88ab\u8bbf\u95ee\u4e00\u6b21\uff08\u65e0\u8bba\u662f <code>'1'<\/code> \u8fd8\u662f <code>'0'<\/code>\uff09\u3002<\/li>\n\n\n\n<li><strong>\u7a7a\u95f4\u590d\u6742\u5ea6<\/strong>\uff1a<code>O(m \u00d7 n)<\/code>\uff08\u6700\u574f\u60c5\u51b5\uff09\n<ul class=\"wp-block-list\">\n<li>\u9012\u5f52\u6808\u6df1\u5ea6\u5728\u6700\u574f\u60c5\u51b5\u4e0b\uff08\u5168\u4e3a\u00a0<code>'1'<\/code>\u00a0\u4e14\u5448\u86c7\u5f62\uff09\u53ef\u8fbe\u00a0<code>m \u00d7 n<\/code>\uff1b<\/li>\n\n\n\n<li>\u82e5\u4f7f\u7528 BFS\uff08\u961f\u5217\uff09\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\u4e5f\u4e3a\u00a0<code>O(min(m, n))<\/code>\u00a0\u5230\u00a0<code>O(mn)<\/code>\uff1b<\/li>\n\n\n\n<li>\u82e5\u5141\u8bb8\u4fee\u6539\u539f\u6570\u7ec4\uff0c\u5219\u65e0\u9700\u989d\u5916 visited \u6570\u7ec4\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>\ud83d\udca1 \u672c\u89e3\u6cd5<strong>\u76f4\u63a5\u4fee\u6539\u539f\u6570\u7ec4<\/strong>\uff0c\u8282\u7701\u4e86\u989d\u5916\u7a7a\u95f4\u3002<\/p>\n<\/blockquote>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\ud83e\udde9 \u89e3\u9898\u601d\u8def<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u6838\u5fc3\u601d\u60f3\uff1a\u8fde\u901a\u533a\u57df\u67d3\u8272\uff08Flood Fill\uff09<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u5c06\u6bcf\u4e2a\u5c9b\u5c7f\u770b\u4f5c\u4e00\u4e2a<strong>\u56db\u8fde\u901a\u7684\u8fde\u901a\u5206\u91cf<\/strong>\uff1b<\/li>\n\n\n\n<li>\u904d\u5386\u7f51\u683c\uff0c\u4e00\u65e6\u53d1\u73b0\u672a\u8bbf\u95ee\u7684\u9646\u5730\uff08<code>'1'<\/code>\uff09\uff0c\u5c31\u542f\u52a8\u4e00\u6b21\u00a0<strong>\u201c\u6d2a\u6c34\u586b\u5145\u201d<\/strong>\uff08Flood Fill\uff09\uff1a\n<ul class=\"wp-block-list\">\n<li>\u628a\u8be5\u8fde\u901a\u533a\u57df\u6240\u6709\u00a0<code>'1'<\/code>\u00a0\u53d8\u6210\u00a0<code>'0'<\/code>\uff1b<\/li>\n\n\n\n<li>\u540c\u65f6\u8ba1\u6570\u5668\u00a0<code>+1<\/code>\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">\u4e3a\u4ec0\u4e48\u80fd\u907f\u514d\u91cd\u590d\u8ba1\u6570\uff1f<\/h3>\n\n\n\n<p>\u56e0\u4e3a DFS \u4f1a<strong>\u4e00\u6b21\u6027\u6e05\u9664\u6574\u4e2a\u5c9b\u5c7f<\/strong>\u3002\u540e\u7eed\u904d\u5386\u65f6\uff0c\u8be5\u5c9b\u5c7f\u6240\u6709\u4f4d\u7f6e\u90fd\u5df2\u53d8\u4e3a <code>'0'<\/code>\uff0c\u4e0d\u4f1a\u518d\u88ab\u5f53\u4f5c\u65b0\u5c9b\u5c7f\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u8fb9\u754c\u5904\u7406\u6280\u5de7<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u5728 DFS \u5f00\u5934\u7edf\u4e00\u5224\u65ad\uff1a\u8d8a\u754c or \u662f\u6c34 \u2192 \u76f4\u63a5\u8fd4\u56de\uff1b<\/li>\n\n\n\n<li>\u65e0\u9700\u5728\u8c03\u7528\u524d\u5224\u65ad\uff0c\u4ee3\u7801\u66f4\u7b80\u6d01\u3002<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\ud83d\udd17 \u5c9b\u5c7f\u6570\u91cf \u9898\u76ee\u6765\u6e90\uff1a200. \u5c9b\u5c7f\u6570\u91cf &#8211; \u529b\u6263\uff08LeetCode\uff09 \ud83d\udccc \u9898\u76ee\u63cf\u8ff0 \u7ed9\u4f60\u4e00\u4e2a\u7531 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[40,12],"tags":[60,14],"class_list":["post-466","post","type-post","status-publish","format-standard","hentry","category-graph","category-algorithm","tag-graphs","tag-algorithm"],"_links":{"self":[{"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/posts\/466","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/comments?post=466"}],"version-history":[{"count":1,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/posts\/466\/revisions"}],"predecessor-version":[{"id":467,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/posts\/466\/revisions\/467"}],"wp:attachment":[{"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/media?parent=466"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/categories?post=466"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/tags?post=466"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}