{"id":2315,"date":"2025-01-04T11:18:20","date_gmt":"2025-01-04T03:18:20","guid":{"rendered":"https:\/\/guapicoding.com\/?p=2315"},"modified":"2025-03-03T22:08:29","modified_gmt":"2025-03-03T14:08:29","slug":"leetcode-hot100%e5%9b%be%e8%ae%ba","status":"publish","type":"post","link":"https:\/\/guapicoding.com\/?p=2315","title":{"rendered":"LeetCode hot100@\u56fe\u8bba"},"content":{"rendered":"\n<p class=\"has-text-align-center\"><em><strong>More content<\/strong><\/em><strong><em>\uff1a<\/em><\/strong><a href=\"https:\/\/guapicoding.com\/?p=2314\" data-type=\"post\" data-id=\"1543\">\u529b\u6263\u9898\u8bb0\u4e4b\u56fe\u8bba<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/number-of-islands\/\">200. \u5c9b\u5c7f\u6570\u91cf<\/a>\u2705<\/h2>\n\n\n\n<p><em><strong>\u7b80\u5355\u5c9b\u5c7f\u95ee\u9898 \u6ce8\u610f\u672c\u9898\u7684grid\u6570\u7ec4\u7c7b\u578b\u662fchar \u56e0\u6b64grid[i][j] == &#8216;1&#8217;\u4e0d\u80fd\u7b80\u5199\u4e3agrid[i][j]<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\nprivate:\n    int dir&#91;4]&#91;2] = {0, 1, 0, -1, 1, 0, -1, 0};\n    int n, m;\npublic:\n    void dfs(vector&lt;vector&lt;char&gt;&gt;&amp; grid, vector&lt;vector&lt;bool&gt;&gt;&amp; visited, int row, int col) {\n        int nextx, nexty;\n        for(int i = 0; i &lt; 4; i++) {\n            nextx = row + dir&#91;i]&#91;0];\n            nexty = col + dir&#91;i]&#91;1];\n            if(nextx &lt; 0 || nextx &gt;= n || nexty &lt; 0 || nexty &gt;= m) {\n                continue;\n            } \n            if(!visited&#91;nextx]&#91;nexty] &amp;&amp; grid&#91;nextx]&#91;nexty] == '1') {\n                visited&#91;nextx]&#91;nexty] = true;\n                dfs(grid, visited, nextx, nexty);\n            }\n        }\n\n    }\n    int numIslands(vector&lt;vector&lt;char&gt;&gt;&amp; grid) {\n        int res = 0;\n        n = grid.size();\n        m = grid&#91;0].size();\n        vector&lt;vector&lt;bool&gt;&gt; visited(n, vector&lt;bool&gt;(m, false));\n        for(int i = 0; i &lt; n; i++) {\n            for(int j = 0; j &lt; m; j++) {\n                if(!visited&#91;i]&#91;j] &amp;&amp; grid&#91;i]&#91;j] == '1') {\n                    visited&#91;i]&#91;j] = true;\n                    dfs(grid, visited, i, j);\n                    res++;\n                }\n            }\n        }\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/rotting-oranges\/\">994. \u8150\u70c2\u7684\u6a58\u5b50<\/a>\u274c<\/h2>\n\n\n\n<p>\u4e00\u5f00\u59cb\u89c9\u5f97\u662f\u7b80\u5355\u7684\u67d3\u8272\u95ee\u9898\uff0c\u7edf\u8ba1\u8f6e\u6570\u5373\u53ef<\/p>\n\n\n\n<p>\u540e\u6765\u53d1\u73b0\u7279\u6b8a\u60c5\u51b5\u65e0\u6cd5\u628a\u201c\u662f\u5426\u6709\u65e0\u6cd5\u88ab\u8150\u70c2\u7684\u6a58\u5b50\u201d\u8fd9\u4e00\u60c5\u51b5\u6392\u9664<\/p>\n\n\n\n<p>\u800c\u4e14\u8fd8\u8981\u6ce8\u610f\u5728\u4e00\u8f6e\u4e2d\u8981\u6709\u4e24\u4e2agrid\uff0c\u4e00\u4e2a\u8d1f\u8d23\u8bb0\u5f55\u4e0a\u4e00\u8f6e\u7684\u72b6\u6001\uff0c\u4e00\u4e2a\u7528\u6765\u67d3\u8fd9\u4e00\u8f6e\u7684\u8272\uff0c\u4e0d\u80fd\u4e00\u8fb9\u67d3\u8272\u4e00\u8fb9\u6269\u6563\uff0c\u4f8b\u5982\uff1a[[2,1,1]]\uff0c\u9700\u8981\u4e24\u8f6e\u800c\u4e0d\u662f\u4e00\u8f6e<\/p>\n\n\n\n<p><em><strong>\u56e0\u6b64\u5b8c\u7f8e\u5951\u5408BFS\uff0c\u4e00\u8f6e\u961f\u5217\u64cd\u4f5c\u5c31\u5bf9\u5e94\u4e00\u8f6e\u65f6\u95f4\uff0c\u65e2\u4e0d\u7528\u628a\u4e0a\u8ff0\u7684\u7279\u6b8a\u60c5\u51b5\u5355\u72ec\u62ce\u51fa\u6765\uff08\u56e0\u4e3a\u5f53\u961f\u5217\u4e3a\u7a7a\u4e14\u8fd8\u6709\u65b0\u9c9c\u6a58\u5b50\u65f6\u5c31\u5bf9\u5e94\u8be5\u60c5\u51b5\uff09\uff0c\u4e5f\u4e0d\u7528\u521b\u5efa\u4e00\u4e2agrid\u526f\u672c\u6765\u8bb0\u5f55\u4e0a\u4e00\u8f6e\u72b6\u6001\uff08\u56e0\u4e3a\u4e00\u8f6e\u64cd\u4f5c\u5c31\u53ea\u662f\u5904\u7406\u4e0a\u4e00\u8f6e\u52a0\u5165\u961f\u5217\u7684\u5143\u7d20\uff0c\u4e0d\u4f1a\u4e00\u8fb9\u52a0\u5165\u5143\u7d20\u4e00\u8fb9\u53c8\u628a\u5b83\u5904\u7406\u6389\u4e86\uff09<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\nprivate:\n    int n, m;\n    int dir&#91;4]&#91;2] = {0,1,0,-1,1,0,-1,0};\npublic:\n    int countFresh(vector&lt;vector&lt;int&gt;&gt;&amp; grid) {\n        int cnt = 0;\n        for(auto &amp;v : grid) {\n            for(auto &amp;i : v) {\n                if(i == 1) cnt++;\n            }\n        }\n        return cnt;\n    }\n    int countRot(vector&lt;vector&lt;int&gt;&gt;&amp; grid) {\n        int cnt = 0;\n        for(auto &amp;v : grid) {\n            for(auto &amp;i : v) {\n                if(i == 2) cnt++;\n            }\n        }\n        return cnt;\n    }\n    int orangesRotting(vector&lt;vector&lt;int&gt;&gt;&amp; grid) {\n        n = grid.size();\n        m = grid&#91;0].size();\n        \/\/\u7279\u6b8a\u60c5\u51b5\uff1a\u4e00\u5f00\u59cb\u5c31\u6ca1\u6709\u8150\u70c2\u7684\u6a58\u5b50(\u5176\u4e2d\u8fd8\u5206\u4e3a\u662f\u5426\u6709\u65b0\u9c9c\u6a58\u5b50\u4e24\u79cd\u60c5\u51b5)\n        if(!countRot(grid)) {\n            if(countFresh(grid)) return -1;\n            else return 0;\n        }\n\n        \/\/BFS\n        int round = 0;\n        queue&lt;pair&lt;int, int&gt;&gt; que;\n        \/\/\u628a\u6240\u6709\u8150\u70c2\u6a58\u5b50\u90fd\u52a0\u5165\u961f\u5217\n        for(int i = 0; i &lt; n; i++) {\n            for(int j = 0; j &lt; m; j++) {\n                if(grid&#91;i]&#91;j] == 2) que.push(make_pair(i, j));\n            }\n        }\n        int siz, row, col, nextx, nexty;\n        while(!que.empty()) {\n            siz = que.size();\n            for(int i = 0; i &lt; siz; i++) {\n                row = que.front().first;\n                col = que.front().second;\n                que.pop();\n                for(int j = 0; j &lt; 4; j++) {\n                    nextx = row + dir&#91;j]&#91;0];\n                    nexty = col + dir&#91;j]&#91;1];\n                    if(nextx &lt; 0 || nextx &gt;= n || nexty &lt; 0 || nexty &gt;= m) continue;\n\n                    if(grid&#91;nextx]&#91;nexty] == 1) {\n                        grid&#91;nextx]&#91;nexty] = 2;\n                        que.push(make_pair(nextx, nexty));\n                    }\n                }\n            } \n            \/\/\u961f\u5217\u4e0d\u4e3a\u7a7a\uff0c\u8bf4\u660e\u6709\u65b0\u7684\u8150\u70c2\u6a58\u5b50\u52a0\u5165\u4e86\u961f\u5217\uff0c\u8fd9\u4e00\u8f6e\u624d\u4f5c\u6570\n            if(!que.empty()) round++;\n        }\n        \/\/\u68c0\u67e5\u662f\u5426\u8fd8\u6709\u672a\u8150\u8d25\u7684\u6a58\u5b50(\u5373\u65e0\u8bba\u5982\u4f55\u4e5f\u8150\u8d25\u4e0d\u4e86\u4e86)\n        if(countFresh(grid)) return -1;\n        else return round;    \n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/course-schedule\/\">207. \u8bfe\u7a0b\u8868<\/a>\u2705<\/h2>\n\n\n\n<p><em><strong>\u57fa\u7840\u62d3\u6251\u6392\u5e8f<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    bool canFinish(int numCourses, vector&lt;vector&lt;int>>&amp; prerequisites) {\n        vector&lt;int> inDegree(numCourses, 0);\n        unordered_map&lt;int, vector&lt;int>> ump; \/\/\u8bb0\u5f55\u8bfe\u7a0b\u4f9d\u8d56\u5173\u7cfb\n\n        for(auto &amp;v : prerequisites) {\n            inDegree&#91;v&#91;0]]++;\n            ump&#91;v&#91;1]].push_back(v&#91;0]);\n        }\n\n        queue&lt;int> que;\n        for(int i = 0; i &lt; numCourses; i++) {\n            if(inDegree&#91;i] == 0) que.push(i);\n        }\n\n        while(!que.empty()) {\n            int cur = que.front();\n            que.pop();\n            \/\/\u628a\u8be5\u8bfe\u7a0b\u7684\u540e\u7ee7\u8bfe\u7a0b\u5165\u5ea6\u90fd-1\uff0c\u76f8\u5f53\u4e8e\u5220\u9664\u8be5\u8bfe\u7a0b\n            vector&lt;int> lessons = ump&#91;cur];\n            if(!lessons.empty()) {\n                for(auto &amp;id : lessons) {\n                    inDegree&#91;id]--;\n                    if(inDegree&#91;id] == 0) que.push(id);\n                }\n            }\n        }\n\n        for(auto &amp;degree : inDegree) {\n            if(degree) return false;\n        }\n        return true;\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/implement-trie-prefix-tree\/\">208. \u5b9e\u73b0 Trie (\u524d\u7f00\u6811)<\/a>\u274c<\/h2>\n\n\n\n<p><em><strong>\u65e0\u601d\u8def<\/strong><\/em> <a href=\"https:\/\/leetcode.cn\/problems\/implement-trie-prefix-tree\/solutions\/98390\/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt\/?envType=study-plan-v2&amp;envId=top-100-liked\"><strong><em>\u9898\u89e3<\/em><\/strong><\/a><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Trie {\nprivate:\n    bool isEnd;\n    Trie *next&#91;26];\npublic:\n    Trie() {\n        isEnd = false;\n        memset(next, 0, sizeof(next));\n    }\n    \n    void insert(string word) {\n        Trie *node = this;\n        for(char c : word) {\n            if(node->next&#91;c-'a'] == NULL) {\n                node->next&#91;c-'a'] = new Trie();\n            }\n            node = node->next&#91;c-'a'];\n        }\n        node->isEnd = true;\n    }\n    \n    bool search(string word) {\n        Trie* node = this;\n        for(char c : word) {\n            node = node->next&#91;c-'a'];\n            if(node == NULL) {\n                return false;\n            }\n        }\n        return node->isEnd;\n    }\n \n    \n    bool startsWith(string prefix) {\n        Trie* node = this;\n        for(char c : prefix) {\n            node = node->next&#91;c-'a'];\n            if(node == NULL) {\n                return false;\n            }\n        }\n        return true;\n    }\n\n \n};\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>More content\uff1a\u529b\u6263\u9898\u8bb0\u4e4b\u56fe\u8bba 200. \u5c9b\u5c7f\u6570\u91cf\u2705 \u7b80\u5355\u5c9b\u5c7f\u95ee\u9898 \u6ce8\u610f\u672c\u9898\u7684grid\u6570\u7ec4\u7c7b\u578b\u662fch [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[27,18,19],"class_list":["post-2315","post","type-post","status-publish","format-standard","hentry","category-suanfa","tag-c","tag-leetcode","tag-19"],"_links":{"self":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2315","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2315"}],"version-history":[{"count":8,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2315\/revisions"}],"predecessor-version":[{"id":2485,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2315\/revisions\/2485"}],"wp:attachment":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2315"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2315"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2315"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}