{"id":1274,"date":"2024-04-15T09:24:56","date_gmt":"2024-04-15T09:24:56","guid":{"rendered":"https:\/\/www.gislxz.com\/?p=1274"},"modified":"2024-04-15T09:24:57","modified_gmt":"2024-04-15T09:24:57","slug":"leetcode-%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92","status":"publish","type":"post","link":"https:\/\/www.gislxz.com\/index.php\/2024\/04\/15\/leetcode-%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92\/","title":{"rendered":"Leetcode \u52a8\u6001\u89c4\u5212"},"content":{"rendered":"\n<p><a href=\"https:\/\/leetcode.cn\/problems\/word-break\/description\/\" target=\"_blank\"  rel=\"nofollow\" >139. \u5355\u8bcd\u62c6\u5206 - \u529b\u6263\uff08LeetCode\uff09<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/leetcode.cn\/problems\/coin-change\/description\/\" target=\"_blank\"  rel=\"nofollow\" >322. \u96f6\u94b1\u5151\u6362 - \u529b\u6263\uff08LeetCode\uff09<\/a><\/p>\n\n\n\n<p>\u641c\u4e86\u4e00\u4e0b\uff0c\u53d1\u73b0\u6211\u4e4b\u524d\u5c45\u7136\u8bb0\u5f55\u8fc7\u96f6\u94b1\u5151\u6362\uff0c\u4fe9\u5e74\u540e\u53c8\u6709\u70b9\u751f\u758f\u4e86\uff0c\u4e0d\u8fc7\u8fd9\u6b21\u81f3\u5c11\u5199\u51fa\u6765\u4e86\u3002<\/p>\n\n\n\n<p>\u4e00\u5f00\u59cb\u60f3\u7684\u662fDFS\uff0c\u4e0d\u8fc7\u4e00\u5f00\u59cb\u601d\u8def\u6709\u95ee\u9898\uff0c\u4ee5\u4e3a\u4f18\u5148\u4f7f\u7528\u5927\u989d\u786c\u5e01\u5c31\u4e00\u5b9a\u662f\u6700\u4f18\u89e3\uff0c\u4f46\u662f\u8fd9\u9898\u4e0d\u80fd\u7528\u8d2a\u5fc3\u7b97\u6cd5\uff0c\u6bd4\u5982\u8981\u51d110\u5757\u94b1\uff0c\u53ef\u7528\u786c\u5e01\u662f1\u5757\uff0c5\u5757\uff0c6\u5757\uff0c\u90a3\u4e48\u4f18\u5148\u7528\u5927\u989d\u786c\u5e01\u662f6+4\u00d71\uff0c\u4e0d\u59822\u00d75\u3002<\/p>\n\n\n\n<p>\u6240\u4ee5\u7528BFS\u642d\u914dDP\u526a\u679d\uff0c\u81ea\u5df1\u5199\u7684\u4ee3\u7801\u6709\u70b9\u81c3\u80bf<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\r\npublic:\r\n    int coinChange(vector&lt;int>&amp; coins, int amount) {\r\n        if(amount == 0)\r\n            return 0;\r\n        vector&lt;int> dp(amount+1,0);\r\n        queue&lt;int> now_arrived;\r\n        int nums = 1;\r\n        for(auto coin:coins){\r\n            if(coin == amount)\r\n                return nums;\r\n            if(coin&lt;amount){\r\n                now_arrived.push(coin);\r\n                dp&#91;coin] = 1;                   \r\n            }       \r\n        }\r\n        while(now_arrived.size()>0){\r\n            nums++;\r\n            int arrived_num = now_arrived.size();\r\n            for(int i = 0;i&lt;arrived_num;i++){\r\n                int temp = now_arrived.front();\r\n                now_arrived.pop();\r\n                for(auto coin:coins){\r\n                    if(temp>amount-coin)\r\n                        continue;\r\n                    int temp_sum = temp + coin;\r\n                    if(temp_sum == amount)\r\n                        return nums;\r\n                    if(temp_sum&lt;amount&amp;&amp;dp&#91;temp_sum]==0){\r\n                        dp&#91;temp_sum] = nums;\r\n                        now_arrived.push(temp_sum);\r\n                    }\r\n                }\r\n            }\r\n        }\r\n        return -1;\r\n    }\r\n};<\/code><\/pre>\n\n\n\n<p>\u53e6\u4e00\u79cd\u601d\u8def\u662f\u53cd\u8fc7\u6765\u81ea\u4e0b\u800c\u4e0a\u7684\u65b9\u5f0f\u8fdb\u884c\u601d\u8003\u3002\u8be6\u89c1\u9898\u89e3<a href=\"https:\/\/leetcode.cn\/problems\/coin-change\/solutions\/132979\/322-ling-qian-dui-huan-by-leetcode-solution\/\" target=\"_blank\"  rel=\"nofollow\" >322. \u96f6\u94b1\u5151\u6362 - \u529b\u6263\uff08LeetCode\uff09<\/a><\/p>\n\n\n\n<p>\u7b2c\u4e8c\u9898\u662f\u5355\u8bcd\u62c6\u5206\uff0c\u8dcc\u8dcc\u649e\u649e\u4e5f\u662f\u7528DFS\u5199\u51fa\u6765\u4e86<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\r\npublic:\r\n    \/\/\u8ba1\u7b97\u6bcf\u4e2a\u5355\u8bcd\u5728\u5b57\u7b26\u4e32\u4e2d\u5bf9\u5e94\u7684\u8d77\u59cb\u4f4d\u7f6e\r\n    void begin_end(string s,string word,unordered_map&lt;int,vector&lt;int>>&amp; word_begin_end){\r\n        for(int i=0;i+word.size()&lt;s.size()+1;i++){\r\n            int j = 0;\r\n            for(;j&lt;word.size();j++)\r\n                if(s&#91;i+j] != word&#91;j])\r\n                    break;\r\n            if(j == word.size()){\r\n                if(word_begin_end.count(i)==0)\r\n                    word_begin_end.insert({i,{i+j}});\r\n                else\r\n                    word_begin_end&#91;i].emplace_back(i+j);\r\n            }\r\n        }\r\n    }\r\n    \/\/\u9012\u5f52\u641c\u7d22\r\n    bool search(unordered_map&lt;int,vector&lt;int>>&amp; word_begin_end,const int&amp; s_size,int index,vector&lt;int>&amp; has_arrived){\r\n        if(index == s_size)\r\n            return true;\r\n        if(has_arrived&#91;index] == 1)\r\n            return false;\r\n        if(word_begin_end.count(index)==0)\r\n            return false;\r\n        for(auto end:word_begin_end&#91;index]){\r\n            if(search(word_begin_end,s_size,end,has_arrived))\r\n                return true;\r\n        }\r\n        has_arrived&#91;index] = 1;\r\n        return false;\r\n    }\r\n    bool wordBreak(string s, vector&lt;string>&amp; wordDict) {\r\n        unordered_map&lt;int,vector&lt;int>> word_begin_end;\r\n        vector&lt;int> has_arrived(s.size(),0);\r\n        for(auto word:wordDict){\r\n            begin_end(s,word,word_begin_end);\r\n        }\r\n        return search(word_begin_end,s.size(),0,has_arrived);\r\n    }\r\n};<\/code><\/pre>\n\n\n\n<p>\u8fd9\u9898DFS\uff0cBFS\uff0cDP\u90fd\u53ef\u4ee5\u89e3\uff0c\u8be6\u89c1<a href=\"https:\/\/leetcode.cn\/problems\/word-break\/solutions\/302779\/shou-hui-tu-jie-san-chong-fang-fa-dfs-bfs-dong-tai\/\" target=\"_blank\"  rel=\"nofollow\" >139. \u5355\u8bcd\u62c6\u5206 - \u529b\u6263\uff08LeetCode\uff09<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>139. \u5355\u8bcd\u62c6\u5206 &#8211; \u529b\u6263\uff08LeetCode\uff09 322. \u96f6\u94b1\u5151\u6362 &#8211; \u529b\u6263\uff08LeetCode\uff09 \u641c\u4e86\u4e00\u4e0b\uff0c\u53d1\u73b0\u6211\u4e4b\u524d\u5c45\u7136\u8bb0\u5f55\u8fc7","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1274","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/1274","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/comments?post=1274"}],"version-history":[{"count":2,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/1274\/revisions"}],"predecessor-version":[{"id":1278,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/1274\/revisions\/1278"}],"wp:attachment":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/media?parent=1274"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/categories?post=1274"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/tags?post=1274"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}