{"id":598,"date":"2024-09-29T10:05:52","date_gmt":"2024-09-29T02:05:52","guid":{"rendered":"http:\/\/114.55.108.251\/?p=598"},"modified":"2025-03-04T20:14:16","modified_gmt":"2025-03-04T12:14:16","slug":"leetcode-hot100%e5%8f%8c%e6%8c%87%e9%92%88","status":"publish","type":"post","link":"https:\/\/guapicoding.com\/?p=598","title":{"rendered":"LeetCode hot100@\u53cc\u6307\u9488"},"content":{"rendered":"\n

\u53cc\u6307\u9488\u6cd5<\/strong>\uff1a\u901a\u8fc7\u4e24\u4e2a\u6307\u9488\u5728\u4e00\u4e2afor\u5faa\u73af\u4e0b\u5b8c\u6210\u4e24\u4e2afor\u5faa\u73af\u7684\u5de5\u4f5c<\/strong>\uff0c\u4e00\u822c\u662f\u5c06O(n^2)\u7684\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u964d\u4e3aO(n)<\/p>\n\n\n\n

283. \u79fb\u52a8\u96f6<\/a>\u2705<\/h2>\n\n\n\n

\u7b80\u5355\u6a21\u62df \u4e0d\u6539\u53d8\u6570\u7ec4\u5185\u5143\u7d20\u7684\u76f8\u5bf9\u4f4d\u7f6e \u590d\u6742\u5ea6O(n)<\/em><\/strong><\/p>\n\n\n\n

class Solution {\npublic:\n    void moveZeroes(vector<int>& nums) {\n        int slow = 0;\n        for(int fast = 0; fast < nums.size(); fast++) {\n            if(nums[fast]) {\n                nums[slow] = nums[fast];\n                slow++;\n            }\n        }\n        for(int i = slow; i < nums.size(); i++) {\n            nums[i] = 0;\n        }\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
11. \u76db\u6700\u591a\u6c34\u7684\u5bb9\u5668<\/a> \u274c<\/h2>\n\n\n\n
\u5982\u4f55\u505a\u5230\u6307\u9488\u7684\u6bcf\u4e00\u6b21\u79fb\u52a8\u90fd\u80fd\u6392\u9664\u6389\u4e00\u6839\u67f1\u5b50<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    int maxArea(vector<int>& height) {\n        int res = 0;\n        int front = 0;\n        int back = height.size() - 1;\n        while(front < back) {\n            int area = ((back-front)*(min(height[back], height[front])));\n            res = max(res, area);\n            if(height[front] <= height[back]) { \/\/\u601d\u8003\u4e3a\u4ec0\u4e48\u53ef\u4ee5\u6dd8\u6c70\n                front++;\n            } else {\n                back--;\n            }\n        }\n         \n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
\u9898\u89e3<\/strong>\uff1ahttps:\/\/leetcode.cn\/problems\/container-with-most-water\/solutions\/94102\/on-shuang-zhi-zhen-jie-fa-li-jie-zheng-que-xing-tu<\/a><\/p>\n\n\n\n
\n\n\n\n
15. \u4e09\u6570\u4e4b\u548c<\/a>\u274c<\/h2>\n\n\n\n
\u54c8\u5e0cor\u53cc\u6307\u9488\uff1f<\/em><\/strong><\/p>\n\n\n\n
\u53bb\u91cd\u5669\u68a6<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    vector<vector<int>> threeSum(vector<int>& nums) {\n        vector<vector<int>> res;\n        ranges::sort(nums);\n        \/\/\u5047\u5b9aa = nums[i], b = nums[left], c = nums[right]\n        for(int i = 0; i < nums.size() - 2; i++) {\n            if(nums[i] > 0) return res; \/\/\u5982\u679ca\u5c31\u5df2\u7ecf\u5927\u4e8e0\u4e86\uff0c\u90a3\u4e48\u4e0d\u7ba1\u662f\u8fd9\u4e2a\u5c0f\u5faa\u73af\n            \/\/\u8fd8\u662f\u4e4b\u540e\u7684\u6240\u6709\u5faa\u73af\u90fd\u4e0d\u53ef\u80fd\u518d\u6709\u6ee1\u8db3\u6761\u4ef6\u7684\u7ec4\u5408\u4e86\n            if(i > 0 && nums[i-1] == nums[i]) continue; \/\/\u5bf9a\u53bb\u91cd\n            int left = i + 1;\n            int right = nums.size() - 1;\n            while(left < right) {\n                if(nums[i] + nums[left] + nums[right] > 0) right--;\n                else if(nums[i] + nums[left] + nums[right] < 0) left++;\n                else {\n                    res.push_back({nums[i], nums[left], nums[right]});\n                    while(left < right && nums[left] == nums[left+1]) left++; \/\/\u5bf9b\u53bb\u91cd\n                    while(left < right && nums[right] == nums[right-1]) right--; \/\/\u5bf9c\u53bb\u91cd \n                    left++;\n                    right--;\n                }\n            }\n\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
ps\uff1a\u4e3a\u4ec0\u4e481. \u4e24\u6570\u4e4b\u548c<\/a>\u4e0d\u80fd\u4f7f\u7528\u53cc\u6307\u9488\u6cd5\uff1f<\/strong><\/p>\n\n\n\n
\u56e0\u4e3a\u4e24\u6570\u4e4b\u548c\u8981\u6c42\u8fd4\u56de\u7684\u662f\u7d22\u5f15\u4e0b\u6807\uff0c \u800c\u53cc\u6307\u9488\u6cd5\u4e00\u5b9a\u8981\u6392\u5e8f\uff0c\u4e00\u65e6\u6392\u5e8f\u4e4b\u540e\u539f\u6570\u7ec4\u7684\u7d22\u5f15\u5c31\u88ab\u6539\u53d8\u4e86<\/p>\n\n\n\n
\n\n\n\n
42. \u63a5\u96e8\u6c34<\/a>\u274c<\/h2>\n\n\n\n
Solution1\uff1a<\/strong><\/em>\u53cc\u6307\u9488 (\u6309\u5217\u8ba1\u7b97)<\/em><\/strong><\/p>\n\n\n\n
\u6bcf\u4e00\u5217\u96e8\u6c34\u7684\u9ad8\u5ea6\u53d6\u51b3\u4e8e\uff0c\u8be5\u5217\u5de6\u4fa7\u6700\u9ad8\u7684\u67f1\u5b50\u548c\u53f3\u4fa7\u6700\u9ad8\u7684\u67f1\u5b50\u4e2d\u8f83\u77ee\u7684\u90a3\u4e2a\u67f1\u5b50\u7684\u9ad8\u5ea6 – \u81ea\u8eab\u9ad8\u5ea6<\/em><\/strong><\/p>\n\n\n\n
Solution2\uff1a\u5355\u8c03\u6808<\/strong><\/em> (\u6309\u884c\u8ba1\u7b97)<\/strong><\/em><\/p>\n\n\n\n
\u6808\u5e95\u5230\u6808\u5934\u5143\u7d20\u9012\u51cf\uff0c\u56e0\u4e3a\u4e00\u65e6\u8981\u6dfb\u52a0\u7684\u67f1\u5b50\u9ad8\u5ea6\u5927\u4e8e\u6808\u5934\u5143\u7d20\uff0c\u8bf4\u660e\u51fa\u73b0\u51f9\u69fd\u4e86<\/em><\/strong><\/p>\n\n\n\n
\u6b64\u65f6\uff0c\u6808\u5934\u5143\u7d20\u5c31\u662f\u51f9\u69fd\u5e95\u90e8\u7684\u67f1\u5b50\uff0c\u6808\u5934\u7b2c\u4e8c\u4e2a\u5143\u7d20\u5c31\u662f\u51f9\u69fd\u5de6\u8fb9\u7684\u67f1\u5b50\uff0c\u800c\u6dfb\u52a0\u7684\u5143\u7d20\u5c31\u662f\u51f9\u69fd\u53f3\u8fb9\u7684\u67f1\u5b50 <\/strong><\/em><\/p>\n\n\n\n
class Solution1 {\npublic:\n    int trap(vector<int>& height) {\n        int res = 0;\n        int len = height.size();\n        \/\/\u8bb0\u5f55\u5f53\u524d\u5217\u7684\u5de6\u53f3\u4e24\u8fb9\u7684\u6700\u9ad8\u5217\n        vector<int> lmax(len);\n        vector<int> rmax(len);\n        \n        lmax[0] = height[0];\n        for(int i = 1; i < len; i++) {\n            lmax[i] = max(lmax[i-1], height[i]);\n        }\n\n        rmax[len - 1] = height[len - 1];\n        for(int i = len - 2; i >= 0; i--) {\n            rmax[i] = max(rmax[i+1], height[i]);\n        }\n\n        for(int i = 0; i < height.size(); i++) {\n            int x = min(lmax[i], rmax[i]) - height[i]; \/\/\u7b2c\u4e00\u5217\u548c\u6700\u540e\u4e00\u5217\u7684x\u7b97\u51fa\u6765\u662f0           \n            if(x > 0) res += x; \/\/\u662f\u6b63\u6570\u624d\u8bf4\u660e\u80fd\u63a5\u4f4f\u96e8\u6c34\uff0c\u8d1f\u6570\u7684\u60c5\u51b5\u6bd4\u5982\u6700\u9ad8\u5217\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
class Solution2 {\npublic:\n    int trap(vector<int>& height) {\n        stack<int> sk; \/\/\u5b58\u4e0b\u6807\n        int res = 0;\n        sk.push(0);\n\n        for(int i = 1; i < height.size(); i++) {\n            while(!sk.empty() && height[i] > height[sk.top()]) { \/\/\u51fa\u73b0\u51f9\u69fd\n                int mid = height[sk.top()]; \/\/\u51f9\u69fd\u4e2d\u95f4\u67f1\u5b50\u9ad8\u5ea6\n                sk.pop();\n                if(!sk.empty()) {\n                    int left = height[sk.top()]; \/\/\u51f9\u69fd\u5de6\u8fb9\u67f1\u5b50\u9ad8\u5ea6\n                    int right = height[i]; \/\/\u51f9\u69fd\u53f3\u8fb9\u67f1\u5b50\u9ad8\u5ea6\n                    int h = min(left, right) - mid;\n                    int w = i - sk.top() - 1;\n                    res += h * w; \/\/\u9ad8\u00d7\u5bbd\n                }\n            }\n            sk.push(i);\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u53cc\u6307\u9488\u6cd5\uff1a\u901a\u8fc7\u4e24\u4e2a\u6307\u9488\u5728\u4e00\u4e2afor\u5faa\u73af\u4e0b\u5b8c\u6210\u4e24\u4e2afor\u5faa\u73af\u7684\u5de5\u4f5c\uff0c\u4e00\u822c\u662f\u5c06O(n^2)\u7684\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u964d\u4e3aO(n […]<\/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,29],"class_list":["post-598","post","type-post","status-publish","format-standard","hentry","category-suanfa","tag-leetcode","tag-19","tag-29"],"_links":{"self":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/598","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=598"}],"version-history":[{"count":22,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/598\/revisions"}],"predecessor-version":[{"id":2656,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/598\/revisions\/2656"}],"wp:attachment":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=598"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=598"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=598"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}