{"id":918,"date":"2024-10-15T21:54:33","date_gmt":"2024-10-15T13:54:33","guid":{"rendered":"http:\/\/114.55.108.251\/?p=918"},"modified":"2024-10-16T18:27:33","modified_gmt":"2024-10-16T10:27:33","slug":"leetcode-hot100%e7%9f%a9%e9%98%b5","status":"publish","type":"post","link":"https:\/\/guapicoding.com\/?p=918","title":{"rendered":"LeetCode hot100@\u77e9\u9635"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/maximum-subarray\/\">73. \u77e9\u9635\u7f6e\u96f6<\/a>\u2705<\/h2>\n\n\n\n<p><strong><em>Solution1\uff1a\u5148\u628a\u96f6\u7684\u4f4d\u7f6e\u627e\u51fa\u6765\uff0c\u7528\u4e8c\u7ef4\u6570\u7ec4\u5b58\u8d77\u6765\uff0c\u4f46\u8fd9\u6837\u989d\u5916\u7a7a\u95f4\u662f<code>O(mn)<\/code><\/em><\/strong><\/p>\n\n\n\n<p><strong><em>Solution2\u6539\u8fdb\uff1a\u4ec5\u4f7f\u7528\u5e38\u91cf\u7a7a\u95f4\uff0c\u5373O(1)<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution1 {\npublic:\n    void setZeroes(vector&lt;vector&lt;int&gt;&gt;&amp; matrix) {\n        int m = matrix.size();\n        int n = matrix&#91;0].size();\n\n        vector&lt;pair&lt;int, int&gt;&gt; v;\n\n        for(int i = 0; i &lt; m; i++) {\n            for(int j = 0; j &lt; n; j++) {\n                if(!matrix&#91;i]&#91;j]) {\n                    v.push_back(make_pair(i, j));\n                }\n            }\n        }\n\n        for(int i = 0; i &lt; v.size(); i++) {\n            \/\/ cout &lt;&lt; v&#91;i].first &lt;&lt; \" \" &lt;&lt; v&#91;i].second &lt;&lt; endl;\n            for(int k = 0; k &lt; n; k++) matrix&#91;v&#91;i].first]&#91;k] = 0;\n            for(int k = 0; k &lt; m; k++) matrix&#91;k]&#91;v&#91;i].second] = 0;\n        }\n \n    }\n};<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution2 {\npublic:\n    void setZeroes(vector&lt;vector&lt;int&gt;&gt;&amp; matrix) {\n        int m = matrix.size();\n        int n = matrix&#91;0].size();\n\n        bool row_flag = false;\n        bool col_flag = false;\n        \n        \/\/\u5224\u65ad\u7b2c\u4e00\u884c\u662f\u5426\u6709\u96f6\n        for(int j = 0; j &lt; n; j++) {\n            if(!matrix&#91;0]&#91;j]) {\n                row_flag = true;\n                break;\n            }\n        }\n        \/\/\u5224\u65ad\u7b2c\u4e00\u5217\u662f\u5426\u6709\u96f6\n        for(int i = 0; i &lt; m; i++) {\n            if(matrix&#91;i]&#91;0] == 0) {\n                col_flag = true;\n                break;\n            }\n        }\n\n \n        \/\/\u7528\u7b2c\u4e00\u884c\u548c\u7b2c\u4e00\u5217\u4f5c\u4e3a\u6807\u5fd7\u4f4d\uff0c\u8868\u793a\u8be5\u884c\/\u5217\u662f\u5426\u6709\u96f6\n        for(int i = 1; i &lt; m; i++) {\n            for(int j = 1; j &lt; n; j++) {\n                if(!matrix&#91;i]&#91;j]) {\n                    matrix&#91;i]&#91;0] = 0;\n                    matrix&#91;0]&#91;j] = 0;\n                }\n            }\n        }\n\n        \/\/ for(const auto &amp;i : matrix) {\n        \/\/     for(const auto &amp;j : i) {\n        \/\/         cout &lt;&lt; j &lt;&lt; \" \";\n        \/\/     }\n        \/\/     cout &lt;&lt; endl;\n        \/\/ }\n\n        for(int i = 1; i &lt; m; i++) {\n            for(int j = 1; j &lt; n; j++) {\n                if(!matrix&#91;i]&#91;0] || !matrix&#91;0]&#91;j]) {\n                    matrix&#91;i]&#91;j] = 0;\n                }\n            }\n            \n        }\n\n        if(row_flag) {\n            for(int j = 0; j &lt; n; j++) matrix&#91;0]&#91;j] = 0; \n        }\n        \n        if(col_flag) {\n            for(int i = 0; i &lt; m; i++) matrix&#91;i]&#91;0] = 0; \n        }\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\/spiral-matrix\/\">54. \u87ba\u65cb\u77e9\u9635<\/a>\u2705<\/h2>\n\n\n\n<p><strong><em>\u6a21\u62df \u63a7\u5236\u8fb9\u754c<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    vector&lt;int&gt; spiralOrder(vector&lt;vector&lt;int&gt;&gt;&amp; matrix) { \n        vector&lt;int&gt; res;\n \n        int row = matrix.size(), col = matrix&#91;0].size();\n        int pre_row = 0, pre_col = 0;\n        int post_row = row - 1, post_col = col - 1;\n\n        while(res.size() &lt; row * col) {\n            for(int i = pre_col; i &lt;= post_col; i++) res.push_back(matrix&#91;pre_row]&#91;i]); \/\/\u5f80\u53f3\n            pre_row++;\n            if(res.size() &gt;= row * col) break;\n\n            for(int i = pre_row; i &lt;= post_row; i++) res.push_back(matrix&#91;i]&#91;post_col]); \/\/\u5f80\u4e0b\n            post_col--;\n            if(res.size() &gt;= row * col) break;\n\n            for(int i = post_col; i &gt;= pre_col; i--) res.push_back(matrix&#91;post_row]&#91;i]); \/\/\u5f80\u5de6\n            post_row--;\n            if(res.size() &gt;= row * col) break;\n\n            for(int i = post_row; i &gt;= pre_row; i--) res.push_back(matrix&#91;i]&#91;pre_col]); \/\/\u5f80\u4e0a\n            pre_col++;\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\/rotate-image\/\">48. \u65cb\u8f6c\u56fe\u50cf<\/a>\u274c<\/h2>\n\n\n\n<p><strong><em>\u539f\u5730\u4fee\u6539 \u4ee5\u56db\u4e2a\u70b9\u6269\u5c55<\/em><\/strong> <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    void rotate(vector&lt;vector&lt;int&gt;&gt;&amp; matrix) {\n        int n = matrix.size();\n\n        for(int i = 0 ; i &lt; n \/ 2; i++) {\n            for(int j = 0; j &lt; (n+1) \/ 2; j++) {\n                int tmp = matrix&#91;i]&#91;j]; \/\/\u6682\u5b58\u5143\u7d20A\n                \/\/\u65cb\u8f6c\u5143\u7d20 A &lt;- D &lt;- C &lt;- B &lt;- tmp\n                matrix&#91;i]&#91;j] = matrix&#91;n - 1 - j]&#91;i];\n                matrix&#91;n - 1 - j]&#91;i] = matrix&#91;n - 1 - i]&#91;n - 1 - j];\n                matrix&#91;n - 1 - i]&#91;n - 1 - j] = matrix&#91;j]&#91;n - 1 - i];\n                matrix&#91;j]&#91;n - 1 - i] = tmp;\n            }\n        }\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\/search-a-2d-matrix-ii\/\">240. \u641c\u7d22\u4e8c\u7ef4\u77e9\u9635 II<\/a>\u2705<\/h2>\n\n\n\n<p><strong><em>\u65e2\u7136\u90fd\u6709\u5e8f\u4e86<\/em><\/strong> <strong><em>\u76f4\u63a5<\/em><\/strong><em><strong>\u5bf9\u6bcf\u4e00\u884c\u4e8c\u5206<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    bool searchMatrix(vector&lt;vector&lt;int&gt;&gt;&amp; matrix, int target) {\n        int row = matrix.size();\n        int col = matrix&#91;0].size();\n        \n\n        for(int i = 0; i &lt; row; i++) {\n            int left = 0, right = col - 1;\n            while(left &lt;= right) {\n                int mid = (left + right) \/ 2;\n                if(matrix&#91;i]&#91;mid] &gt; target) {\n                    right = mid - 1;\n                } else if(matrix&#91;i]&#91;mid] &lt; target) {\n                    left = mid + 1;\n                } else {\n                    return true;\n                }\n            }\n        }\n\n        return false;\n    }\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>73. \u77e9\u9635\u7f6e\u96f6\u2705 Solution1\uff1a\u5148\u628a\u96f6\u7684\u4f4d\u7f6e\u627e\u51fa\u6765\uff0c\u7528\u4e8c\u7ef4\u6570\u7ec4\u5b58\u8d77\u6765\uff0c\u4f46\u8fd9\u6837\u989d\u5916\u7a7a\u95f4\u662fO(mn) So [&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":[18,19,43],"class_list":["post-918","post","type-post","status-publish","format-standard","hentry","category-suanfa","tag-leetcode","tag-19","tag-43"],"_links":{"self":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/918","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=918"}],"version-history":[{"count":6,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/918\/revisions"}],"predecessor-version":[{"id":957,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/918\/revisions\/957"}],"wp:attachment":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=918"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=918"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=918"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}