{"id":273,"date":"2015-11-29T16:13:50","date_gmt":"2015-11-29T08:13:50","guid":{"rendered":"http:\/\/www.codeeel.com\/?p=273"},"modified":"2015-11-29T16:13:50","modified_gmt":"2015-11-29T08:13:50","slug":"%e5%b8%b8%e7%94%a8%e7%9a%84%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84","status":"publish","type":"post","link":"https:\/\/www.codeeel.com\/?p=273","title":{"rendered":"\u5e38\u7528\u7684\u6570\u636e\u7ed3\u6784"},"content":{"rendered":"<p>\u6700\u8fd1\u7684\u7814\u7a76\u8868\u660e\uff0c\u6570\u636e\u7ed3\u6784\u4e0d\u80fd\u4e22\uff0c\u5927\u5b66\u65f6\u7684\u6570\u636e\u7ed3\u6784\u8bfe\u7a0b\u5c31\u662f\u4e2a\u5f62\u5f0f\uff0c\u73b0\u5728\u540e\u6094\u6ca1\u6709\u597d\u597d\u7684\u5438\u53d6\u8425\u517b\u3002<\/p>\n<p>\u4e00\u3001\u6808\uff1a<\/p>\n<p>1\u3001\u540e\u7f00\u8868\u8fbe\u5f0f\u7684\u6c42\u503c\uff1b<br \/>\n2\u3001\u4e2d\u7f00\u5230\u540e\u7f00\u8868\u8fbe\u5f0f\u7684\u8f6c\u6362\uff1b<br \/>\n3\u3001\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u7684\u975e\u9012\u5f52\u5b9e\u73b0\uff1b<br \/>\n4\u3001\u52a8\u6001\u89c4\u5212\u7684\u4f18\u5316\uff1a\u7528\u4e8e\u7ef4\u62a4\u4e00\u4e2a\u51f8\u5e8f\u5217\uff0c\u4fbf\u4e8e\u4e8c\u5206\u67e5\u627e\uff0c\u5982LIS\u95ee\u9898\u7684O(nlgn)\u7b97\u6cd5\u3002<\/p>\n<p>\u4e8c\u3001\u961f\u5217\uff1a<br \/>\n1\u3001\u6811\u7684\u5c42\u5e8f\u904d\u5386\uff1b<br \/>\n2\u3001\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\uff1b<br \/>\n3\u3001Bellman-Ford\u7b97\u6cd5\u7684SPFA\u5b9e\u73b0\uff1b<br \/>\n4\u3001\u7f51\u7edc\u6d41\u4e2dFF\u7b97\u6cd5\u7684Edmonds-Karp\u5b9e\u73b0\uff0c\u4ee5\u53caPreflow\u7b97\u6cd5\u7684\u961f\u5217\u4f18\u5316\u5b9e\u73b0\u3002<\/p>\n<p>\u4e09\u3001\u4e8c\u53c9\u641c\u7d22\u6811\uff1a<\/p>\n<p>1\u3001\u5bf9\u5927\u91cf\u7684\u5173\u952e\u5b57\u7684\u7d22\u5f15\u67e5\u627e\uff1b<br \/>\n2\u3001\u6709\u5f88\u591a\u5e73\u8861\u7b56\u7565\u4ee5\u6539\u5584\u5176\u5e73\u5747\u6027\u80fd\uff1a<br \/>\n\u5e38\u7528\u5e73\u8861\u6811\uff1aAVL\uff0c\u7ea2\u9ed1\u6811\uff0c\u968f\u673a\u5316BST\uff0cSplay Tree\uff0cTreap\uff08\u6216\u53eb\u7b1b\u5361\u513f\u6811\uff09\u3002<\/p>\n<p>\u56db\u3001\u6563\u5217\u8868\uff08hash\u8868\uff09\uff1a<br \/>\n1\u3001\u4e00\u822c\u9488\u5bf9\u503c\u57df\u8f83\u5927\u4f46\u72b6\u6001\u5f88\u7a00\u758f\u7684\u5e94\u7528\uff0c\u6bd4\u5982\u72b6\u6001\u538b\u7f29\u8bb0\u5fc6\u5316\u641c\u7d22\uff1b<br \/>\n2\u3001\u5b9e\u73b0\u6620\u5c04\u529f\u80fd\u3002<\/p>\n<p>\u4e94\u3001\u68c0\u7d22\u6811\uff08Trie\uff09\uff1a<br \/>\n1\u3001\u4e00\u822c\u7528\u4e8e\u5b57\u7b26\u4e32\u7d22\u5f15\u7b97\u6cd5\uff0c\u901f\u5ea6\u5feb\uff0c\u4f46\u5360\u7528\u7a7a\u95f4\u8f83\u5927\uff08\u76f8\u5bf9hash\uff09\uff1b<br \/>\n2\u3001\u5e38\u7528\u7684\u6539\u8fdb\u7ed3\u6784\uff1aPatricia\u7ebf\u7d22\u6811\uff0c\u591a\u53c9\u68c0\u7d22\u6811\uff08TST\uff09\u3002<\/p>\n<p>\u516d\u3001\u4f18\u5148\u961f\u5217\uff1a<\/p>\n<p>1\u3001\u5e38\u7528\u7684\u662f\u4e8c\u53c9\u5806\u7684\u5b9e\u73b0\uff0c\u5177\u4f53\u5e94\u7528\u5982\u5806\u6392\u5e8f\u548cDijkstra\u7b97\u6cd5\uff1b<br \/>\n2\u3001\u5f53\u9700\u8981\u5feb\u901f\u5408\u5e76\u4e24\u4e2a\u4f18\u5148\u961f\u5217\u65f6\uff0c\u5e38\u7528\u4e8c\u9879\u5f0f\u961f\u5217\uff0c\u5b9e\u73b0\u7b80\u5355\u3002<br \/>\n3\u3001\u6ce8\u610f\u6700\u5927\u6700\u5c0f\u5806\u7684\u914d\u5bf9\u4f7f\u7528\u3002<\/p>\n<p>\u4e03\u3001\u7ebf\u6bb5\u6811\u548c\u6811\u72b6\u6570\u7ec4\uff1a<\/p>\n<p>1\u3001\u4e24\u8005\u90fd\u53ef\u4ee5\u7528\u4e8e\u79bb\u6563\u5bf9\u8c61\u7684\u7edf\u8ba1\uff1b<br \/>\n2\u3001\u540e\u8005\u7684\u6b65\u8fdb\u51fd\u6570\u7684\u6027\u8d28\u548c\u5e94\u7528\u503c\u5f97\u6ce8\u610f\uff1b<br \/>\n3\u3001\u524d\u8005\u57fa\u672c\u4e0a\u9002\u7528\u4e8e\u4efb\u4f55\u7684\u533a\u95f4\u64cd\u4f5c\uff0c\u5982\u6c42\u533a\u95f4\u6700\u503c\uff0c\u6539\u53d8\u533a\u95f4\u7684\u503c\u7b49\u3002<br \/>\n4\u3001\u7ebf\u6bb5\u6811\u8fd8\u53ef\u4ee5\u7528\u4e8e\u4f18\u5316\u72b6\u6001\u7684\u679a\u4e3e\uff0c\u7ecf\u5e38\u548c\u52a8\u6001\u89c4\u5212\u7ed3\u5408\u3002<\/p>\n<p>\u516b\u3001\u540e\u7f00\u6811\u4e0e\u540e\u7f00\u6570\u7ec4\uff1a<\/p>\n<p>1\u3001\u603b\u4f53\u89c4\u5f8b\u662f\u4e24\u8005\u7684\u5b9e\u73b0\u90fd\u6bd4\u8f83\u590d\u6742\uff0c\u524d\u8005\u66f4\u751a\uff0c\u4f46\u662f\u524d\u8005\u7684\u529f\u80fd\u4e5f\u66f4\u5f3a\u5927\uff1b<br \/>\n2\u3001\u51e0\u4e4e\u53ef\u4ee5\u89e3\u51b3\u6240\u6709\u5e38\u89c1\u7684\u5173\u4e8e\u5b57\u7b26\u4e32\u7684\u7b97\u6cd5\uff0c\u5982\u6700\u957f\u56de\u6587\u5b50\u4e32\uff0c\u6700\u957f\u91cd\u590d\u5b50\u4e32\uff0c\u4ee5\u53ca\u5f88\u591a\u7684\u6a21\u5f0f\u5339\u914d\u95ee\u9898\u3002<\/p>\n<p>\u4e5d\u3001\u5e76\u67e5\u96c6\uff1a<\/p>\n<p>1\u3001\u89e3\u51b3\u65e0\u5411\u56fe\u7684\u8fde\u901a\u6027\u95ee\u9898\uff0c\u5982\u7528\u4e8eKruskal\u7b97\u6cd5\uff1b<br \/>\n2\u3001\u89e3\u51b3\u7b49\u4ef7\u5173\u7cfb\u7684\u67e5\u8be2\uff08\u8fd9\u662f\u5b83\u7684\u4e3b\u8981\u7528\u6b66\u4e4b\u5730\uff09\uff0c\u598205\u5e74Baidu\u4e4b\u661f\u521d\u8d5b\u7684\u77f3\u5934\u526a\u5b50\u5e03\u6e38\u620f\uff1b<br \/>\n3\u3001\u4f18\u70b9\u662f\u5b9e\u73b0\u5f02\u5e38\u7b80\u5355\uff0c\u7f3a\u70b9\u662f\u5408\u5e76\u540e\u65e0\u6cd5\u5206\u79bb\uff0c\u82e5\u9700\u8981\u53ef\u4ee5\u9009\u62e9\u7528\u52a8\u6001\u6811\u3002<\/p>\n<p>\u5341\u3001\u90bb\u63a5\u8868\u548c\u8fb9\u8868\uff1a<\/p>\n<p>1\u3001\u8868\u793a\u56fe\u7684\u6700\u76f4\u63a5\u7684\u65b9\u6cd5\uff1b<br \/>\n2\u3001\u540e\u8005\u66f4\u7701\u7a7a\u95f4\uff0c\u5e76\u4e14\u5728\u4e00\u5b9a\u7a0b\u5ea6\u4e0a\u66f4\u597d\u7528\uff0c\u6bd4\u5982Bellman-Ford\u7b97\u6cd5\u3002<br \/>\nps:\u6570\u7ec4\u3001\u94fe\u8868\u592a\u57fa\u7840\u4e0d\u5728\u8003\u8651\u4e4b\u5217\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6700\u8fd1\u7684\u7814\u7a76\u8868\u660e\uff0c\u6570\u636e\u7ed3\u6784\u4e0d\u80fd\u4e22\uff0c\u5927\u5b66\u65f6\u7684\u6570\u636e\u7ed3\u6784\u8bfe\u7a0b\u5c31\u662f\u4e2a\u5f62\u5f0f\uff0c\u73b0\u5728\u540e\u6094\u6ca1\u6709\u597d\u597d\u7684\u5438\u53d6\u8425\u517b\u3002 \u4e00\u3001\u6808\uff1a 1\u3001\u540e\u7f00\u8868\u8fbe\u5f0f\u7684\u6c42\u503c\uff1b 2\u3001\u4e2d\u7f00\u5230\u540e\u7f00\u8868\u8fbe\u5f0f\u7684\u8f6c\u6362\uff1b 3\u3001\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u7684\u975e\u9012\u5f52\u5b9e\u73b0\uff1b 4\u3001\u52a8\u6001\u89c4\u5212\u7684\u4f18\u5316\uff1a\u7528\u4e8e\u7ef4\u62a4\u4e00\u4e2a\u51f8\u5e8f\u5217\uff0c\u4fbf\u4e8e\u4e8c\u5206\u67e5\u627e\uff0c\u5982LIS\u95ee\u9898\u7684O(nlgn)\u7b97\u6cd5\u3002 \u4e8c\u3001\u961f\u5217\uff1a 1\u3001\u6811\u7684\u5c42\u5e8f\u904d\u5386\uff1b 2\u3001\u5e7f\u5ea6<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[17],"tags":[151,150,153,152,154],"_links":{"self":[{"href":"https:\/\/www.codeeel.com\/index.php?rest_route=\/wp\/v2\/posts\/273"}],"collection":[{"href":"https:\/\/www.codeeel.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.codeeel.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.codeeel.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.codeeel.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=273"}],"version-history":[{"count":1,"href":"https:\/\/www.codeeel.com\/index.php?rest_route=\/wp\/v2\/posts\/273\/revisions"}],"predecessor-version":[{"id":274,"href":"https:\/\/www.codeeel.com\/index.php?rest_route=\/wp\/v2\/posts\/273\/revisions\/274"}],"wp:attachment":[{"href":"https:\/\/www.codeeel.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=273"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codeeel.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=273"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codeeel.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=273"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}