{"id":801,"date":"2024-10-12T16:12:52","date_gmt":"2024-10-12T08:12:52","guid":{"rendered":"http:\/\/114.55.108.251\/?p=801"},"modified":"2024-10-15T20:38:13","modified_gmt":"2024-10-15T12:38:13","slug":"leetcode-hot100%e6%95%b0%e7%bb%84","status":"publish","type":"post","link":"https:\/\/guapicoding.com\/?p=801","title":{"rendered":"LeetCode hot100@\u6570\u7ec4"},"content":{"rendered":"\n

53. \u6700\u5927\u5b50\u6570\u7ec4\u548c<\/a>\u274c<\/h2>\n\n\n\n

\u8d2a\u5fc3\uff1a<\/strong><\/em>\u4e0d\u80fd\u8ba9\u201c\u8fde\u7eed\u548c\u201d\u4e3a\u8d1f\u6570\u7684\u65f6\u5019\u52a0\u4e0a\u4e0b\u4e00\u4e2a\u5143\u7d20\uff08\u56e0\u4e3a\u76f4\u63a5\u628a\u524d\u9762\u8fd9\u4e00\u5806\u548c\u4e3a\u8d1f\u6570\u7684\u5b50\u4e32\u629b\u5f03\u5c31\u56de\u6765\uff0c\u540e\u9762\u600e\u4e48\u4e5f\u4f1a\u6bd4\u52a0\u4e0a\u4e2a\u8d1f\u6570\u66f4\u5927\uff09\uff0c\u800c\u4e0d\u662f\u4e0d\u8ba9\u201c\u8fde\u7eed\u548c\u201d\u52a0\u4e0a\u4e00\u4e2a\u8d1f\u6570<\/strong>\uff08\u52a0\u4e0a\u8d1f\u6570\u4e5f\u6ca1\u4e8b\uff0c\u53ea\u8981\u6574\u4f53\u8fd8\u7b97\u5927\uff09<\/em><\/strong><\/p>\n\n\n\n

<\/p>\n\n\n\n

class Solution {\npublic:\n    int maxSubArray(vector<int>& nums) {\n        int sum = 0;\n        int res = INT32_MIN;\n        for(int i = 0; i < nums.size(); i++) {\n            sum += nums[i];\n            if(sum > res) res = sum;\n            if(sum <= 0) sum = 0;\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
ps\uff1a\u56de\u5934\u770b\u4e00\u4e0bdp\u7684\u89e3\u6cd5<\/em><\/strong>\uff08https:\/\/leetcode.cn\/problems\/maximum-subarray\/solutions\/9058\/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai\/?envType=study-plan-v2&envId=top-100-liked<\/a>\uff09<\/p>\n\n\n\n
\n\n\n\n
56. \u5408\u5e76\u533a\u95f4<\/a>\u2705<\/h2>\n\n\n\n
\u7b80\u5355\u6a21\u62df<\/strong><\/em> \u6ce8\u610f\u53f3\u8fb9\u754c\u5982\u4f55\u66f4\u65b0<\/strong><\/em><\/p>\n\n\n\n
class Solution {\npublic:\n    vector<vector<int>> merge(vector<vector<int>>& intervals) {\n        vector<vector<int>> res;\n        ranges::sort(intervals);\n\n        \/\/ for(const auto &interval : intervals) {\n        \/\/     for(const auto &num : interval) {\n        \/\/         cout << num << \" \";\n        \/\/     }\n        \/\/     cout << endl;\n        \/\/ }\n\n        int left = intervals[0][0];\n        int right = intervals[0][1];\n        for(int i = 1; i < intervals.size(); i++) {\n            if(intervals[i][0] <= right) { \/\/\u5982\u679c\u8fde\u7eed\n                right = max(right, intervals[i][1]);\n            } else {\n                res.push_back({left, right});   \n                left = intervals[i][0];       \n                right = intervals[i][1];\n            }\n        }\n        res.push_back({left, right});\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
189. \u8f6e\u8f6c\u6570\u7ec4<\/a>\u2705<\/h2>\n\n\n\n
\u7b80\u5355\u6a21\u62df \u7a0d\u5fae\u7b97\u4e00\u4e0b<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    void rotate(vector<int>& nums, int k) {\n        k %= nums.size();\n        vector<int> v(nums);\n\n        for(int i = 0; i < nums.size(); i++) {\n            \/\/\u7531\u5316\u7b80\u5f97\u5230\uff1anums.size() + i - k  < nums.size()\n            if(i < k) {\n                nums[i] = v[nums.size() + i - k];\n            } else {\n                nums[i] = v[i - k];\n            }\n        }\n\n        return ;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
238. \u9664\u81ea\u8eab\u4ee5\u5916\u6570\u7ec4\u7684\u4e58\u79ef<\/a>\u2705<\/h2>\n\n\n\n
\u672c\u6765\u5f88\u7b80\u5355 \u53ef\u60dc\u9898\u76ee\u4e0d\u8ba9\u7528\u9664\u6cd5<\/em><\/strong><\/p>\n\n\n\n
\u7c7b\u6bd4\u524d\u7f00\u548c<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    vector<int> productExceptSelf(vector<int>& nums) {\n        vector<int> pre_prod(nums), post_prod(nums), res(nums);\n        for(int i = 1; i < nums.size(); i++) { \/\/\u524d\u7f00\u79ef\n            pre_prod[i] *= pre_prod[i-1];\n        }\n        for(int i = nums.size() - 2; i >= 0; i--) { \/\/\u540e\u7f00\u79ef\n            post_prod[i] *= post_prod[i+1];\n        }\n        \/\/ for(const auto &i : pre_prod) {\n        \/\/     cout << i << \" \";\n        \/\/ }\n        \/\/ cout << endl;\n        \/\/ for(const auto &i : post_prod) {\n        \/\/     cout << i << \" \";\n        \/\/ }\n        \/\/ cout << endl;\n        res[0] = post_prod[1];\n        res[nums.size() - 1] = pre_prod[nums.size() - 2];\n        for(int i = 1; i < nums.size() - 1; i++) {\n            res[i] = pre_prod[i-1] * post_prod[i+1];\n        }\n        \/\/ for(const auto &i : res) {\n        \/\/     cout << i << \" \";\n        \/\/ }\n\n        return res;\n    }\n};\n<\/code><\/pre>\n\n\n\n
\n\n\n\n
41. \u7f3a\u5931\u7684\u7b2c\u4e00\u4e2a\u6b63\u6570<\/a>\u2705<\/h2>\n\n\n\n
\u4e0d\u5408\u7406Solution1<\/em><\/strong>\uff1a<\/em><\/strong>\u4e8c\u5206 + \u7ec6\u8282\uff08\u4e0d\u8fc7\u9898\u610f\u5e94\u8be5\u662f\u4e0d\u8ba9\u76f4\u63a5\u8c03\u7528\u6392\u5e8f\u51fd\u6570\u7684\uff09<\/strong><\/em><\/p>\n\n\n\n
\u5408\u7406Solution2\uff1a<\/em><\/strong>\u98de\u673a\u5bf9\u53f7\u5165\u5ea7\u95ee\u9898 \u539f\u5730\u54c8\u5e0c\u6876\u6392\u5e8f\uff08<\/b><\/span>https:\/\/leetcode.cn\/problems\/first-missing-positive\/solutions\/304894\/zhao-zuo-wei-de-gu-shi-onyuan-di-jie-fa-by-java_le\/?envType=study-plan-v2&envId=top-100-liked\uff09<\/strong><\/em><\/p>\n\n\n\n
class Solution1 {\npublic:\n    int firstMissingPositive(vector<int>& nums) {\n        ranges::sort(nums);\n\n        int left = 0, right = nums.size() - 1;\n        int mid = 0;\n        while(left <= right) { \/\/\u4e8c\u5206\u67e5\u627e\u7b2c\u4e00\u4e2a\u6b63\u6570\u7d22\u5f15\n            mid = (left + right) \/ 2;\n            if(nums[mid] > 0) {\n                right = mid - 1;\n            }\n            else if(nums[mid] < 0) {\n                left = mid + 1;\n            }\n            else {\n                break;\n            }\n        }\n\n        int p = mid;\n        while(nums[p] <= 0 && p < nums.size() - 1) p++;\n\n        if(nums[p] != 1) return 1;\n        for(int i = p; i < nums.size() - 1; i++) {\n            if(nums[i] == nums[i+1]) continue;\n            if(nums[i] + 1 != nums[i+1]) return nums[i] + 1;\n        }\n        return nums[nums.size() - 1] + 1;\n    }\n};<\/code><\/pre>\n\n\n\n
class Solution2 {\npublic:\n    int firstMissingPositive(vector<int>& nums) {\n        for(int i = 0; i < nums.size(); i++) {\n            if(nums[i] < 0 || nums[i] > nums.size()) nums[i] = 0;\n        }\n\n        for(int i = 0; i < nums.size(); i++) {\n            if(nums[i] && nums[i] != i + 1) { \/\/\u5982\u679c\u5750\u9519\u4e86\u4f4d\u7f6e\n                int tmp = nums[i]; \/\/\u5750\u9519\u7684\u4eba\u5148\u7ad9\u4e00\u8fb9\u53bb\n                nums[i] = 0; \/\/\u90a3\u4e48\u4f4d\u7f6e\u5c31\u7a7a\u4e86\n                while(nums[tmp - 1] != tmp) { \/\/\u53bb\u627e\u5c5e\u4e8e\u81ea\u5df1\u7684\u4f4d\u7f6e\n                    if(!nums[tmp - 1]) {\n                        nums[tmp - 1] = tmp; \/\/\u6b63\u786e\u7684\u4f4d\u7f6e\u662f\u7a7a\u7684 \u76f4\u63a5\u5750\u4e0b\n                    } else { \/\/\u5df2\u7ecf\u6709\u4eba\u4e86\n                        int ta = nums[tmp - 1]; \/\/\u8ba9\u4ed6\u79bb\u5f00\n                        nums[tmp - 1] = tmp; \/\/tmp\u5750\u4e0b\n                        tmp = ta; \/\/ta\u53d8\u6210\u65b0\u7684tmp \u53bb\u627e\u6b63\u786e\u7684\u5ea7\u4f4d\n                    }\n                }\n            }\n        }\n        int i = 0;\n        for(i = 0; i < nums.size() && nums[i]; i++);  \n        \/\/i\u53f7\u4f4d\u7f6e\u662f\u7a7a\u7684 \u8bf4\u660ei+1\u53f7\u4e58\u5ba2\u4e0d\u5728\n        \/\/\u5982\u679c\u6bcf\u4e2a\u4eba\u90fd\u5750\u5bf9\u4e86 \u90a3\u4e48\u8fd4\u56denums.size()+1 \u7b26\u5408\u9898\u610f\n        return i + 1;\n    }\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
53. \u6700\u5927\u5b50\u6570\u7ec4\u548c\u274c \u8d2a\u5fc3\uff1a\u4e0d\u80fd\u8ba9\u201c\u8fde\u7eed\u548c\u201d\u4e3a\u8d1f\u6570\u7684\u65f6\u5019\u52a0\u4e0a\u4e0b\u4e00\u4e2a\u5143\u7d20\uff08\u56e0\u4e3a\u76f4\u63a5\u628a\u524d\u9762\u8fd9\u4e00\u5806\u548c\u4e3a\u8d1f\u6570\u7684\u5b50\u4e32\u629b […]<\/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,35],"class_list":["post-801","post","type-post","status-publish","format-standard","hentry","category-suanfa","tag-leetcode","tag-19","tag-35"],"_links":{"self":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/801","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=801"}],"version-history":[{"count":15,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/801\/revisions"}],"predecessor-version":[{"id":894,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/801\/revisions\/894"}],"wp:attachment":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=801"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=801"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=801"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}