{"id":2257,"date":"2025-02-21T11:05:41","date_gmt":"2025-02-21T03:05:41","guid":{"rendered":"https:\/\/guapicoding.com\/?p=2257"},"modified":"2025-03-03T22:17:48","modified_gmt":"2025-03-03T14:17:48","slug":"leetcode-hot100%e8%b4%aa%e5%bf%83","status":"publish","type":"post","link":"https:\/\/guapicoding.com\/?p=2257","title":{"rendered":"LeetCode hot100@\u8d2a\u5fc3"},"content":{"rendered":"\n

More content<\/strong><\/em>\uff1a<\/em><\/strong><\/a><\/a>\u529b\u6263\u9898\u8bb0\u4e4b\u8d2a\u5fc3<\/a><\/p>\n\n\n\n

121. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a<\/a>\u2705<\/h2>\n\n\n\n

\u7b80\u5355\u8d2a\u5fc3 \u4e5f\u53efDP<\/em><\/strong><\/p>\n\n\n\n

class Solution {\npublic:\n    int maxProfit(vector<int>& prices) {\n        int res = 0;\n        int mny = 0;\n        for(int i = 1; i < prices.size(); i++) {\n            mny += prices[i] - prices[i-1];\n            if(mny < 0)  mny = 0; \/\/\u4e00\u65e6\u4e8f\u94b1\u5c31\u91cd\u65b0\u5f00\u59cb\uff0c\u96f6\u603b\u6bd4\u8d1f\u6570\u5927\u5427\n            else res = max(res, mny);\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
55. \u8df3\u8dc3\u6e38\u620f<\/a>\u274c<\/h2>\n\n\n\n
\u4e00\u5f00\u59cb\u60f3\u7684\u662f\u8df3\u5411\u6700\u5927\u957f\u5ea6\u4e4b\u95f4\u4e2d\u4e0b\u6807\u6700\u5927\u7684\uff0c\u53d1\u73b0\u4e0d\u884c<\/strong><\/em><\/p>\n\n\n\n
\u4e0d\u8981\u62d8\u6ce5\u4e8e\u8df3\u5230\u54ea\uff0c\u800c\u662f\u80fd\u8df3\u5230\u54ea\uff0c\u5373\u5173\u6ce8\u80fd\u8df3\u5230\u7684\u8303\u56f4<\/strong><\/em><\/p>\n\n\n\n
\u8d2a\u5fc3\u7b97\u6cd5\u5c40\u90e8\u6700\u4f18\u89e3\uff1a\u6bcf\u6b21\u53d6\u6700\u5927\u8df3\u8dc3\u6b65\u6570\uff08\u53d6\u6700\u5927\u8986\u76d6\u8303\u56f4\uff09<\/strong><\/p>\n\n\n\n
\u6574\u4f53\u6700\u4f18\u89e3\uff1a\u6700\u540e\u5f97\u5230\u6574\u4f53\u6700\u5927\u8986\u76d6\u8303\u56f4\uff0c\u770b\u662f\u5426\u80fd\u5230\u7ec8\u70b9<\/strong> <\/p>\n\n\n\n
class Solution {\npublic:\n    bool canJump(vector<int>& nums) {\n        int dest = nums.size() - 1;\n        \/\/\u770b\u8df3\u8dc3\u8986\u76d6\u8303\u56f4\u53ef\u4e0d\u53ef\u4ee5\u8986\u76d6\u5230\u7ec8\u70b9\n        int cover = 0;\n        for(int i = 0; i <= dest; i++) {\n            if(cover < i) return false; \/\/\u9047\u52300\u8df3\u4e0d\u5230\uff0c\u4e2d\u65ad\u4e86\n            for(int j = 1; j <= nums[i] && j + i <= dest; j++) {\n                cover = max(cover, i + j + nums[i+j]);\n            }\n            if(cover >= dest) return true;\n        }\n        return false;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
45. \u8df3\u8dc3\u6e38\u620f II<\/a>\u274c<\/h2>\n\n\n\n
\u4e0a\u4e00\u9898\u662f\u80fd\u4e0d\u80fd\u8df3\u5230\u7ec8\u70b9\uff0c\u8fd9\u9898\u662f\u6c42\u8df3\u5230\u7ec8\u70b9\u7684\u6700\u5c0f\u6b65\u6570<\/strong><\/em><\/p>\n\n\n\n
class Solution {\npublic:\n    int jump(vector<int>& nums) {\n        if(nums.size() == 1) return 0;\n        int dest = nums.size() - 1;\n        int res = 0;\n        int curDis = 0;\n        int nextDis = 0;\n          \n        for(int i = 0; i <= dest; i++) {\n            nextDis = max(nums[i] + i, nextDis); \/\/ \u66f4\u65b0\u4e0b\u4e00\u6b65\u8986\u76d6\u6700\u8fdc\u8ddd\u79bb\u4e0b\u6807\n            if(i == curDis) {                    \/\/ \u9047\u5230\u5f53\u524d\u8986\u76d6\u6700\u8fdc\u8ddd\u79bb\u4e0b\u6807\n                if(curDis != dest) {             \/\/ \u5982\u679c\u5f53\u524d\u8986\u76d6\u6700\u8fdc\u8ddd\u79bb\u4e0b\u6807\u4e0d\u662f\u7ec8\u70b9\n                    res++;                       \/\/ \u9700\u8981\u8d70\u4e0b\u4e00\u6b65\n                    curDis = nextDis;            \/\/ \u66f4\u65b0\u5f53\u524d\u8986\u76d6\u6700\u8fdc\u8ddd\u79bb\u4e0b\u6807\uff08\u76f8\u5f53\u4e8e\u52a0\u6cb9\u4e86\uff09\n                    if(nextDis >= dest) break;   \/\/ \u4e0b\u4e00\u6b65\u7684\u8986\u76d6\u8303\u56f4\u5df2\u7ecf\u53ef\u4ee5\u8fbe\u5230\u7ec8\u70b9\uff0c\u7ed3\u675f\u5faa\u73af\n                } else break;                    \/\/ \u5f53\u524d\u8986\u76d6\u6700\u8fdc\u8ddd\u79bb\u4e0b\u6807\u662f\u96c6\u5408\u7ec8\u70b9\uff0c\u4e0d\u7528\u505aans++\u64cd\u4f5c\u4e86\uff0c\u76f4\u63a5\u7ed3\u675f\n            }\n        }\n\n        return res;\n    }\n};\n<\/code><\/pre>\n\n\n\n
\n\n\n\n
763. \u5212\u5206\u5b57\u6bcd\u533a\u95f4<\/a>\u2705<\/h2>\n\n\n\n
\u904d\u5386\u627e\u5230\u5207\u5272\u70b9\uff0c\u5373\u91cd\u590d\u5b57\u6bcd\u6700\u540e\u51fa\u73b0\u7684\u4f4d\u7f6e\uff0c\u7528map\u8bb0\u5f55\u9632\u6b62\u91cd\u590d\u641c\u7d22<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    vector<int> partitionLabels(string s) {\n        vector<int> map(100, -1); \/\/\u6807\u8bc6\u5b57\u6bcd\u51fa\u73b0\u7684\u6700\u540e\u4f4d\u7f6e\n        vector<int> res; \/\/\u4e0d\u4f1a\u591a\u4e8e26\u4e2a\u7247\u6bb5\uff0c\u56e0\u4e3a\u4e00\u517126\u4e2a\u82f1\u6587\u5b57\u6bcd\n\n        int cutpoint = 0;\n        int start = 0;\n        for(int i = 0; i < s.size(); i++) {\n            if(map[s[i] - '0'] == -1) { \/\/\u4e4b\u524d\u6ca1\u641c\u8fc7\n                for(int j = s.size() - 1; j >= i; j--) {\n                    if(s[j] == s[i]) {\n                        cutpoint = max(j, cutpoint);\n                        map[s[i] - '0'] = j;\n                        break;\n                    }\n                }\n                \/\/ cout << \"i = \" << i << \", cutpoint = \" << cutpoint << endl;\n            } \n            \n            if(i == cutpoint) {\n                \/\/ cout << \"\u5207i = \" << i << endl;\n                res.push_back(cutpoint - start + 1);\n                start = cutpoint + 1; \n            }\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
More content\uff1a\u529b\u6263\u9898\u8bb0\u4e4b\u8d2a\u5fc3 121. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a\u2705 \u7b80\u5355\u8d2a\u5fc3 \u4e5f\u53efDP 55. \u8df3\u8dc3\u6e38\u620f […]<\/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,78],"class_list":["post-2257","post","type-post","status-publish","format-standard","hentry","category-suanfa","tag-leetcode","tag-19","tag-78"],"_links":{"self":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2257","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=2257"}],"version-history":[{"count":8,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2257\/revisions"}],"predecessor-version":[{"id":2327,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2257\/revisions\/2327"}],"wp:attachment":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2257"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2257"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2257"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}