{"id":529,"date":"2021-10-16T01:15:08","date_gmt":"2021-10-15T17:15:08","guid":{"rendered":"https:\/\/blog.cauchyschwarz.com\/?p=529"},"modified":"2021-12-05T19:11:12","modified_gmt":"2021-12-05T11:11:12","slug":"hackerrank-interview-preparation-kit","status":"publish","type":"post","link":"https:\/\/blog.cauchyschwarz.com\/?p=529","title":{"rendered":"Hackerrank Interview Preparation Kit"},"content":{"rendered":"\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 ez-toc-wrap-right counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69e0c3b5c3d2c\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69e0c3b5c3d2c\" checked aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Warm-up_Challenges\" >Warm-up Challenges<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Counting_Valleys\" >Counting Valleys<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Sales_by_Match\" >Sales by Match<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Jumping_on_the_Clouds\" >Jumping on the Clouds<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E6%95%B0%E7%BB%84\" >\u6570\u7ec4<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Minimal_Swaps_2\" >Minimal Swaps 2<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E6%8E%92%E5%BA%8F\" >\u6392\u5e8f<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E8%AE%A1%E7%AE%97%E4%B8%AD%E4%BD%8D%E6%95%B0\" >\u6ed1\u52a8\u7a97\u53e3\u8ba1\u7b97\u4e2d\u4f4d\u6570<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E7%BB%9F%E8%AE%A1%E6%95%B0%E7%BB%84%E4%B8%AD%E6%9C%89%E5%BA%8F%E4%B8%89%E5%85%83%E7%BB%84kkrkrr%E7%9A%84%E4%B8%AA%E6%95%B0\" >\u7edf\u8ba1\u6570\u7ec4\u4e2d\u6709\u5e8f\u4e09\u5143\u7ec4k,k*r,k*r*r\u7684\u4e2a\u6570<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E5%AD%97%E7%AC%A6%E4%B8%B2\" >\u5b57\u7b26\u4e32<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E6%9C%80%E5%A4%9A%E5%88%A0%E9%99%A4%E4%B8%80%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%BD%BF%E5%BE%97%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E5%AD%97%E7%AC%A6%E5%87%BA%E7%8E%B0%E9%A2%91%E7%8E%87%E7%9B%B8%E7%AD%89\" >\u6700\u591a\u5220\u9664\u4e00\u4e2a\u5b57\u7b26\u4f7f\u5f97\u5b57\u7b26\u4e32\u4e2d\u5b57\u7b26\u51fa\u73b0\u9891\u7387\u76f8\u7b49<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E6%B1%82%E9%99%A4%E4%B8%AD%E5%BF%83%E5%AD%97%E7%AC%A6%E5%8F%AF%E4%BB%A5%E4%B8%8D%E5%90%8C%E5%A4%96%E5%85%B6%E4%BB%96%E5%AD%97%E7%AC%A6%E9%83%BD%E5%BF%85%E9%A1%BB%E7%9B%B8%E5%90%8C%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E4%B8%AA%E6%95%B0\" >\u6c42\u9664\u4e2d\u5fc3\u5b57\u7b26\u53ef\u4ee5\u4e0d\u540c\u5916\u5176\u4ed6\u5b57\u7b26\u90fd\u5fc5\u987b\u76f8\u540c\u7684\u5b50\u5b57\u7b26\u4e32\u7684\u4e2a\u6570<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E9%93%BE%E8%A1%A8\" >\u94fe\u8868<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-14\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E5%8F%8D%E8%BD%AC%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8\" >\u53cd\u8f6c\u53cc\u5411\u94fe\u8868<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-15\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E6%8F%92%E5%85%A5%E8%8A%82%E7%82%B9%E5%88%B0%E6%9C%89%E5%BA%8F%E9%93%BE%E8%A1%A8\" >\u63d2\u5165\u8282\u70b9\u5230\u6709\u5e8f\u94fe\u8868<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-16\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E6%89%BE%E5%88%B0%E4%B8%A4%E4%B8%AA%E9%93%BE%E8%A1%A8%E7%9A%84%E5%85%AC%E5%85%B1%E8%8A%82%E7%82%B9\" >\u627e\u5230\u4e24\u4e2a\u94fe\u8868\u7684\u516c\u5171\u8282\u70b9<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-17\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E5%88%A4%E6%96%AD%E9%93%BE%E8%A1%A8%E6%98%AF%E5%90%A6%E6%9C%89%E7%8E%AF\" >\u5224\u65ad\u94fe\u8868\u662f\u5426\u6709\u73af<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-18\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E9%80%92%E5%BD%92%E4%B8%8E%E5%9B%9E%E6%BA%AF\" >\u9012\u5f52\u4e0e\u56de\u6eaf<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-19\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E5%8D%81%E5%AD%97%E5%A1%AB%E5%AD%97%E6%B8%B8%E6%88%8F\" >\u5341\u5b57\u586b\u5b57\u6e38\u620f<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-20\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E6%A0%91\" >\u6811<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-21\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E5%88%A4%E6%96%AD%E6%98%AF%E5%90%A6%E6%98%AF%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91\" >\u5224\u65ad\u662f\u5426\u662f\u4e8c\u53c9\u641c\u7d22\u6811<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-22\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92\" >\u52a8\u6001\u89c4\u5212<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-23\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Abbreviation\" >Abbreviation<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-24\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Candies\" >Candies<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-25\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E8%B4%AA%E5%BF%83\" >\u8d2a\u5fc3<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-26\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Reverse_Shuffle_Merge\" >Reverse Shuffle Merge<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-27\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97\" >\u6808\u4e0e\u961f\u5217<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-28\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Min_Max_Riddle\" >Min Max Riddle<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-29\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E7%94%A8%E6%A0%88%E6%A8%A1%E6%8B%9F%E9%98%9F%E5%88%97\" >\u7528\u6808\u6a21\u62df\u961f\u5217<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-30\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E6%90%9C%E7%B4%A2\" >\u641c\u7d22<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-31\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Maximum_Subarray_Sum\" >Maximum Subarray Sum<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-32\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Making_Candies\" >Making Candies<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-33\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E5%9B%BE%E8%AE%BA\" >\u56fe\u8bba<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-34\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E5%AF%BB%E6%89%BE%E7%9B%B8%E5%90%8C%E9%A2%9C%E8%89%B2%E8%8A%82%E7%82%B9%E4%B9%8B%E9%97%B4%E7%9A%84%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84\" >\u5bfb\u627e\u76f8\u540c\u989c\u8272\u8282\u70b9\u4e4b\u95f4\u7684\u6700\u77ed\u8def\u5f84<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-35\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E4%BF%AE%E5%BB%BA%E9%81%93%E8%B7%AF%E5%92%8C%E5%9B%BE%E4%B9%A6%E9%A6%86%E7%9A%84%E6%9C%80%E5%B0%8F%E8%B4%B9%E7%94%A8\" >\u4fee\u5efa\u9053\u8def\u548c\u56fe\u4e66\u9986\u7684\u6700\u5c0f\u8d39\u7528<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-36\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#%E5%85%B6%E4%BB%96\" >\u5176\u4ed6<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-37\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Maximum_Xor\" >Maximum Xor<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-38\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=529\/#Friend_Circle_Queries\" >Friend Circle Queries<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Warm-up_Challenges\"><\/span>Warm-up Challenges<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Counting_Valleys\"><\/span>Counting Valleys<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u6570\u6d77\u62d4\u4ece0\u53d8\u4e3a\u8d1f\u6570\u7684\u6b21\u6570\u5373\u4e3a\u5c71\u8c37\u7684\u4e2a\u6570\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Sales_by_Match\"><\/span>Sales by Match<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u6309\u989c\u8272\u7edf\u8ba1\u889c\u5b50\u7684\u4e2a\u6570\uff0c\u7136\u540e\u7b97\u53cc\u6570\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">int sockMerchant(int n, vector&lt;int&gt; ar) {\n    vector&lt;int&gt; colors(100+1, 0);\n    for (auto &amp;x : ar) {\n        ++colors[x];\n    }\n    int res = 0;\n    for (auto &amp;x : colors) {\n        res += x\/2;\n    }\n    return res;\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Jumping_on_the_Clouds\"><\/span>Jumping on the Clouds<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u56e0\u4e3a\u6bcf\u6b21\u53ea\u80fd\u5f80\u524d\u8d701\u6b65\u6216\u80052\u6b65\uff0c\u56e0\u6b64\u4e0d\u4f1a\u5b58\u57282\u7247\u8fde\u7eed\u7684\u96f7\u96e8\u4e91\u3002\u9047\u5230\u96f7\u96e8\u4e91\u9700\u8981\u5f80\u524d\u8d702\u6b65\u8df3\u8fc7\u96f7\u96e8\u4e91\uff0c\u800c\u5bf9\u4e8e\u4e00\u7247\u8fde\u7eed\u7684\u79ef\u96e8\u4e91\uff0c\u5047\u8bbe\u5176\u957f\u5ea6\u4e3ak\uff0c\u5219\u9700\u8981\u8d70k\/2\u6b65\u4ece\u8fd9\u7247\u79ef\u96e8\u4e91\u7684\u5de6\u7aef\u70b9\u8d70\u5230\u53f3\u7aef\u70b9\uff0c\u56e0\u6b64\u6700\u7ec8\u89e3\u6cd5\u5c31\u662f\u6570\u6570\u7ec4\u4e2d1\u7684\u4e2a\u6570\u548c\u6bcf\u4e2a\u8fde\u7eed0\u533a\u95f4\u7684\u957f\u5ea6\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">int jumpingOnClouds(vector&lt;int&gt; c) {\n    int res = 0;\n    int last_1_pos = -1;\n    int len = c.size();\n    for (int i = 0; i &lt; len; i++) {\n        if (c[i] == 1) {\n            res += 1;\n            res += (i - last_1_pos - 1) \/ 2;\n            last_1_pos = i;\n        }\n    }\n    res += (len - last_1_pos - 1) \/ 2;\n    return res;\n}<\/code><\/pre>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E6%95%B0%E7%BB%84\"><\/span>\u6570\u7ec4<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Minimal_Swaps_2\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/minimum-swaps-2\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=arrays\">Minimal Swaps 2<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u601d\u8def\uff1a\u627e\u51fa\u8f93\u5165\u6392\u5217\u4e2d\u7684\u5faa\u73af\uff0c\u5bf9\u4e00\u4e2a\u6709k\u4e2a\u5143\u7d20\u7684\u5faa\u73af\u9700\u8981\u6700\u5c11k &#8211; 1\u6b21swap\u6765\u4f7f\u5f97\u5faa\u73af\u91cc\u7684\u5404\u4e2a\u5143\u7d20\u56de\u5230\u5176\u672c\u6765\u7684\u4f4d\u7f6e\u4e0a\uff0e<\/p>\n\n\n\n<p>\u6570\u5b66\u8bc1\u660e\uff1a\u5982\u4f55\u8bc1\u660e\u6709k\u4e2a\u5143\u7d20\u7684\u5faa\u73af\u9700\u8981\u6700\u5c11k &#8211; 1\u6b21swap\u53ef\u4ee5\u56de\u5230\u5176\u672c\u6765\u7684\u4f4d\u7f6e\u4e0a\uff1f<\/p>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E6%8E%92%E5%BA%8F\"><\/span>\u6392\u5e8f<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E8%AE%A1%E7%AE%97%E4%B8%AD%E4%BD%8D%E6%95%B0\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/fraudulent-activity-notifications\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=sorting\">\u6ed1\u52a8\u7a97\u53e3\u8ba1\u7b97\u4e2d\u4f4d\u6570<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u957f\u5ea6\u4e3an\u7684\u6570\u7ec4\uff0c\u4e00\u4e2a\u957f\u5ea6\u4e3ak\u7684\u6ed1\u52a8\u7a97\u53e3\u5728\u8fd9\u4e2a\u6570\u7ec4\u4e0a\u6ed1\u52a8\uff0c\u6c42\u6ed1\u52a8\u7a97\u53e3\u7684\u4e2d\u4f4d\u6570\uff0e<\/p>\n\n\n\n<p>\u601d\u8def\uff11\uff1a\u7a97\u53e3\u5f00\u59cb\u6ed1\u52a8\u65f6\uff0c\u5bf9\u7a97\u53e3\u5185\u7684\u6570\u7ec4\u6392\u4e00\u6b21\u5e8f\uff0c\u4e4b\u540e\u6bcf\u6b21\u5f80\u524d\u6ed1\u52a8\u4e00\u4e2a\u5143\u7d20\u65f6\uff0c\u7528\u4e8c\u5206\u67e5\u627e\u627e\u5230\u8981\u5220\u9664\u7684\u5143\u7d20\uff0c\u5c06\u5176\u66ff\u6362\u4e3a\u8981\u52a0\u5165\u6ed1\u52a8\u7a97\u53e3\u7684\u5143\u7d20\uff0c\u6b64\u65f6\u9664\u4e86\u8fd9\u4e2a\u65b0\u52a0\u5165\u7684\u5143\u7d20\uff0c\u5176\u4ed6\u5143\u7d20\u90fd\u662f\u6709\u5e8f\u7684\uff0c\u65b0\u52a0\u5165\u5143\u7d20\u53ea\u8981\u6309\u7167\u5192\u6ce1\u6392\u5e8f\u7684\u65b9\u5f0f\uff0c\u4e0d\u505c\u5411\u5de6\u6216\u8005\u5411\u53f3\u4ea4\u6362\uff0c\u5373\u53ef\u5230\u8fbe\u4f7f\u6574\u4e2a\u7a97\u53e3\u6709\u5e8f\u7684\u4f4d\u7f6e\uff0e<\/p>\n\n\n\n<p>\u4e0d\u8fc7\u8fd9\u79cd\u601d\u8def\u5728\u6d4b\u8bd5\u65f6\u9047\u5230\u4e86\u8d85\u65f6\u7684\u95ee\u9898\uff0c\u539f\u56e0\u5728\u4e8e\u6d4b\u8bd5case\u4e2dk\u5f88\u5927\uff0c\u548cn\u76f8\u5f53\uff0c\u90a3\u4e48\u8fd9\u5c31\u9000\u5316\u6210\u4e3a\u4e00\u4e2an*n\u7ea7\u522b\u7684\u7b97\u6cd5\uff0e<\/p>\n\n\n\n<p>\u601d\u8def\uff12\uff1a\u7531\u4e8e\u9898\u76ee\u9650\u5236\u4e86\u5143\u7d20\u5927\u5c0f\u8303\u56f4\u4e3a0-200\uff0c\u56e0\u6b64\u53ef\u4ee5\u7528\u8ba1\u6570\u6392\u5e8f\u7684\u65b9\u5f0f\u7edf\u8ba1\u6ed1\u52a8\u7a97\u53e3\u5185\u7684\u6570\uff0c\u6bcf\u6b21\u6ed1\u52a8\u65f6\uff0c\u53ea\u9700\u8981\u5c06\u5bf9\u5e94\u5143\u7d20\u7684\u9891\u7387\u7edf\u8ba1\u503c\u51cf\uff11\u548c\u52a0\uff11\u5373\u53ef\uff0c\u7136\u540e\u904d\u5386\u9891\u7387\u7edf\u8ba1\u7684\u6570\u7ec4\u6c42\u6ed1\u52a8\u7a97\u53e3\u7684\u4e2d\u4f4d\u6570\u5373\u53ef\uff0e\u8fd9\u662f\u4e00\u4e2a200*n\u7ea7\u522b\u7684\u7b97\u6cd5\uff0e<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E7%BB%9F%E8%AE%A1%E6%95%B0%E7%BB%84%E4%B8%AD%E6%9C%89%E5%BA%8F%E4%B8%89%E5%85%83%E7%BB%84kkrkrr%E7%9A%84%E4%B8%AA%E6%95%B0\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/count-triplets-1\/problem?h_r=profile\" data-type=\"URL\" data-id=\"https:\/\/www.hackerrank.com\/challenges\/count-triplets-1\/problem?h_r=profile\">\u7edf\u8ba1\u6570\u7ec4\u4e2d\u6709\u5e8f\u4e09\u5143\u7ec4k,k*r,k*r*r\u7684\u4e2a\u6570<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u76f4\u63a5\u679a\u4e3e\u6240\u6709\u7684\u4e09\u5143\u7ec4\uff0c\u6765\u5224\u65ad\u5176\u662f\u5426\u6ee1\u8db3r\u500d\u6570\u5173\u7cfb\u7684\u8bdd\uff0c\u6709\u591a\u5c11\u4e2a\u4e09\u5143\u7ec4\u5c31\u9700\u8981\u679a\u4e3e\u591a\u5c11\u6b21\uff0c\u5373\u4f7f\u662f\u6ee1\u8db3\u6761\u4ef6\u7684\u4e09\u5143\u7ec4\u4e2a\u6570\uff0c\u4e5f\u90fd\u662f\u67091\u4e2a\u6ee1\u8db3\u6761\u4ef6\u7684\u4e09\u5143\u7ec4\u5c31\u679a\u4e3e\u4e86\u4e00\u6b21\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u5f88\u9ad8\uff0e<\/p>\n\n\n\n<p>\u53ef\u4ee5\u4f9d\u6b21\u679a\u4e3e\u6570\u7ec4\u4e2d\u7684\u5143\u7d20a[i]\uff0c\u5e76\u4e14\u7528\u4e00\u4e2a\u54c8\u7cfb\u8868\u8bb0\u5f55\u5230\u76ee\u524d\u4e3a\u6b62a[i]\u4f5c\u4e3ak*r*r\u51fa\u73b0\u4e86\u591a\u5c11\u6b21\uff0ca[i]\u4f5c\u4e3ak*r\u51fa\u73b0\u4e86\u591a\u5c11\u6b21\uff0c\u6700\u540e\u66f4\u65b0a[i]\u4f5c\u4e3ak\u51fa\u73b0\u4e86\u591a\u5c11\u6b21\uff0e\u90a3\u4e48\u9898\u76ee\u8981\u6c42\u7684\u6709\u5e8f\u4e09\u5143\u7ec4\u4e2a\u6570\u5c31\u662f\u6240\u6709a[i]\u4f5c\u4e3ak*r*r\u51fa\u73b0\u6b21\u6570\u4e4b\u548c\uff0e\u8fd9\u679a\u4e3e\u548c\u66f4\u65b0\u7684\u987a\u5e8f\u9690\u5f0f\u5730\u4fdd\u8bc1\u4e86k,k*r,k*r*r\u4e09\u4e2a\u6570\u7684\u7d22\u5f15\u4e5f\u662f\u9012\u589e\u7684\uff0e<\/p>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E5%AD%97%E7%AC%A6%E4%B8%B2\"><\/span>\u5b57\u7b26\u4e32<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E6%9C%80%E5%A4%9A%E5%88%A0%E9%99%A4%E4%B8%80%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%BD%BF%E5%BE%97%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E5%AD%97%E7%AC%A6%E5%87%BA%E7%8E%B0%E9%A2%91%E7%8E%87%E7%9B%B8%E7%AD%89\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/sherlock-and-valid-string\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=strings\">\u6700\u591a\u5220\u9664\u4e00\u4e2a\u5b57\u7b26\u4f7f\u5f97\u5b57\u7b26\u4e32\u4e2d\u5b57\u7b26\u51fa\u73b0\u9891\u7387\u76f8\u7b49<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>3\u79cd\u60c5\u51b5\u662f\u6709\u6548\u7684\u5b57\u7b26\u4e32\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>\u5b57\u7b26\u4e32\u4e2d\u6240\u6709\u5b57\u7b26\u9891\u7387\u76f8\u7b49\uff1b<\/li><li>\u5b57\u7b26\u4e32\u4e2d\u67091\u4e2a\u5b57\u7b26\u51fa\u73b0\u7684\u9891\u7387\u4e3a1\u6b21\uff0c\u5176\u4ed6\u5b57\u7b26\u90fd\u51fa\u73b0\u4e86k(k &gt; 1)\u6b21\uff1b<\/li><li>\u5b57\u7b26\u4e32\u4e2d\u6709\u9664\u4e86\u4e00\u4e2a\u5b57\u7b26\u51fa\u73b0\u4e86k+1\u6b21\uff0c\u5176\u4ed6\u5b57\u7b26\u90fd\u51fa\u73b0\u4e86k\u6b21\uff1b<\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E6%B1%82%E9%99%A4%E4%B8%AD%E5%BF%83%E5%AD%97%E7%AC%A6%E5%8F%AF%E4%BB%A5%E4%B8%8D%E5%90%8C%E5%A4%96%E5%85%B6%E4%BB%96%E5%AD%97%E7%AC%A6%E9%83%BD%E5%BF%85%E9%A1%BB%E7%9B%B8%E5%90%8C%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E4%B8%AA%E6%95%B0\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/special-palindrome-again\/problem?h_r=profile\">\u6c42\u9664\u4e2d\u5fc3\u5b57\u7b26\u53ef\u4ee5\u4e0d\u540c\u5916\u5176\u4ed6\u5b57\u7b26\u90fd\u5fc5\u987b\u76f8\u540c\u7684\u5b50\u5b57\u7b26\u4e32\u7684\u4e2a\u6570<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u601d\u8def\u5c31\u662f\u7edf\u8ba1\u8fde\u7eed\u76f8\u540c\u5b57\u7b26\u4e32\u6784\u6210\u7684\u533a\u95f4\uff0c\u518d\u5206\u522b\u6c42\u6240\u6709\u5b57\u7b26\u90fd\u76f8\u540c\u7684\u5b50\u4e32\u7684\u4e2a\u6570\u548c\u4e2d\u5fc3\u5b57\u7b26\u4e0d\u540c\u4f46\u662f\u5176\u4ed6\u5b57\u7b26\u90fd\u76f8\u540c\u7684\u5b50\u4e32\u7684\u4e2a\u6570\uff0e<\/p>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E9%93%BE%E8%A1%A8\"><\/span>\u94fe\u8868<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E5%8F%8D%E8%BD%AC%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/reverse-a-doubly-linked-list\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=linked-lists\" data-type=\"URL\" data-id=\"https:\/\/www.hackerrank.com\/challenges\/reverse-a-doubly-linked-list\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=linked-lists\">\u53cd\u8f6c\u53cc\u5411\u94fe\u8868<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u601d\u8def\u4e00\uff1a\u4f9d\u6b21\u79fb\u9664head\u540e\u9762\u7684\u8282\u70b9\u5e76\u5c06\u5176\u653e\u5230\u94fe\u8868\u5934\uff1b<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">DoublyLinkedListNode* reverse(DoublyLinkedListNode* llist) {\n    if (!llist) {\n        return llist;\n    }\n    \n    DoublyLinkedListNode *head = llist;\n    while (llist-&gt;next) {\n        DoublyLinkedListNode *tmp = llist-&gt;next;\n        llist-&gt;next = llist-&gt;next-&gt;next;\n        if (llist-&gt;next) {\n            llist-&gt;next-&gt;prev = llist;\n        }\n        tmp-&gt;prev = nullptr;\n        tmp-&gt;next = head;\n        head = tmp;\n    }\n    \n    return head;\n}\n<\/code><\/pre>\n\n\n\n<p>\u601d\u8def\u4e8c\uff1a\u7531\u4e8e\u662f\u53cc\u5411\u94fe\u8868\uff0c\u56e0\u6b64\u53ea\u8981\u5c06\u6bcf\u4e2a\u8282\u70b9\u7684next\u548cprev\u4ea4\u6362\u5373\u53ef\uff1b<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">Node* Reverse(Node* head)\n{\n     Node *temp = NULL;  \n     Node *current = head;\n\n\n     while (current !=  NULL)\n     {\n       temp = current-&gt;prev;\n       current-&gt;prev = current-&gt;next;\n       current-&gt;next = temp;              \n       current = current-&gt;prev;\n     }      \n    if(temp != NULL )\n        head = temp-&gt;prev;\n\n    return head;\n\n}<\/code><\/pre>\n\n\n\n<p>\u601d\u8def\u4e09\uff1a\u9012\u5f52\uff1b<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E6%8F%92%E5%85%A5%E8%8A%82%E7%82%B9%E5%88%B0%E6%9C%89%E5%BA%8F%E9%93%BE%E8%A1%A8\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/insert-a-node-into-a-sorted-doubly-linked-list\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=linked-lists\" data-type=\"URL\" data-id=\"https:\/\/www.hackerrank.com\/challenges\/insert-a-node-into-a-sorted-doubly-linked-list\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=linked-lists\">\u63d2\u5165\u8282\u70b9\u5230\u6709\u5e8f\u94fe\u8868<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u601d\u8def\uff1a\u627e\u5230\u6700\u540e\u4e00\u4e2a\u5c0f\u4e8e\u63d2\u5165\u8282\u70b9\u6570\u636e\u7684\u8282\u70b9\uff0c\u7136\u540e\u5206\u60c5\u51b5\u5904\u7406\uff1b<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* llist, int data) {\n    DoublyLinkedListNode *inserted = new DoublyLinkedListNode(data);\n    DoublyLinkedListNode *tmp = llist;\n    while (tmp != nullptr &amp;&amp; tmp-&gt;data &lt; data &amp;&amp; tmp-&gt;next != nullptr) {\n        tmp = tmp-&gt;next;\n    }\n    if (tmp == nullptr) {\n        llist = inserted;\n    } else if (tmp-&gt;data &lt; data) {\n        inserted-&gt;next = tmp-&gt;next;\n        inserted-&gt;prev = tmp;\n        tmp-&gt;next = inserted;\n        if (inserted-&gt;next) {\n            inserted-&gt;next-&gt;prev = inserted;\n        }\n    } else {\n        if (tmp == llist) {\n            llist = inserted;\n        }\n        inserted-&gt;next = tmp;\n        inserted-&gt;prev = tmp-&gt;prev;\n        tmp-&gt;prev = inserted;\n        if (inserted-&gt;prev) {\n            inserted-&gt;prev-&gt;next = inserted;\n        }\n    }\n    return llist;\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E6%89%BE%E5%88%B0%E4%B8%A4%E4%B8%AA%E9%93%BE%E8%A1%A8%E7%9A%84%E5%85%AC%E5%85%B1%E8%8A%82%E7%82%B9\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/find-the-merge-point-of-two-joined-linked-lists\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=linked-lists\" data-type=\"URL\" data-id=\"https:\/\/www.hackerrank.com\/challenges\/find-the-merge-point-of-two-joined-linked-lists\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=linked-lists\">\u627e\u5230\u4e24\u4e2a\u94fe\u8868\u7684\u516c\u5171\u8282\u70b9<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u601d\u8def\u4e00\uff1a\u5148\u786e\u5b9a\u4e24\u4e2a\u94fe\u8868\u7684\u957f\u5ea6\uff0c\u5982\u679c\u4e24\u4e2a\u94fe\u8868\u5b58\u5728\u516c\u5171\u8282\u70b9\uff0c\u90a3\u4e48\u4ed6\u4eec\u7684\u6700\u540e\u4e00\u6bb5\u662f\u76f8\u540c\u7684\uff0c\u56e0\u6b64\u4ece\u4e24\u4e2a\u94fe\u8868\u7684\u5934\u8282\u70b9\u5f00\u59cb\u904d\u5386\uff0c\u5e76\u4e14\u8ba9\u957f\u5ea6\u66f4\u957f\u7684\u94fe\u8868\u5148\u5f80\u524d\u8d70k\u6b65(k\u4e3a\u957f\u5ea6\u66f4\u957f\u7684\u94fe\u8868\u591a\u51fa\u6765\u7684\u8282\u70b9\u4e2a\u6570)\uff0c\u7136\u540e\u4e24\u4e2a\u94fe\u8868\u4f9d\u6b21\u6bd4\u8f83\u8282\u70b9\u662f\u5426\u76f8\u540c\uff0c\u76f4\u5230\u627e\u5230\u76f8\u540c\u7684\u8282\u70b9\u6216\u8005\u5230\u8fbe\u94fe\u8868\u672b\u5c3e\uff0e<\/p>\n\n\n\n<p>\u601d\u8def\u4e8c\uff1a\u5bf9\u4e8e\u5df2\u77e5\u7684\u4e24\u4e2a\u94fe\u8868A\u548cB\uff0c\u53ef\u4ee5\u628aA\u5206\u89e3\u4e3alistX+listC\uff0cB\u5206\u89e3\u4e3alistY+listC\uff0clistC\u4e3a\u4e24\u4e2a\u94fe\u8868\u516c\u5171\u7684\u90e8\u5206(listC\u53ef\u80fd\u662f\u7a7a\u7684)\uff0e\u90a3\u4e48\u540c\u65f6\u7528\u4e24\u4e2a\u6307\u9488\u6765\u904d\u5386listX+listC+listY\u548clistY+listC+listX\uff0c<\/p>\n\n\n\n<p>\u5982\u679c\u4e24\u4e2a\u94fe\u8868A,B\u957f\u5ea6\u76f8\u540c\uff1a\u5982\u679clistC\u975e\u7a7a\uff0c\u90a3\u4e48\u8fd9\u4e24\u4e2a\u6307\u9488\u4f1a\u540c\u65f6\u904d\u5386\u5230\u540c\u4e00\u4e2a\u8282\u70b9\uff1b\u5982\u679clistC\u4e3a\u7a7a\uff0c\u90a3\u4e48\u8fd9\u4e24\u4e2a\u6307\u9488\u4f1a\u540c\u65f6\u53d8\u4e3a\u7a7a\uff1b<\/p>\n\n\n\n<p>\u5982\u679c\u4e24\u4e2a\u94fe\u8868A,B\u957f\u5ea6\u4e0d\u76f8\u540c\uff1a\u5982\u679clistC\u975e\u7a7a\uff0c\u90a3\u4e48\u4e24\u4e2a\u6307\u9488\u4f1a\u5404\u81ea\u5728\u904d\u5386\u5b8c\u4e00\u904dlistX+listC+listY\u548clistY+listC+listX\u540e\uff0c\u5f00\u59cb\u63a5\u7740\u904d\u5386listC\uff0c\u8fd9\u4e2a\u65f6\u5019\u4e24\u4e2a\u6307\u9488\u5c31\u904d\u5386\u5230\u4e86\u540c\u4e00\u4e2a\u8282\u70b9\uff1b\u5982\u679clistC\u4e3a\u7a7a\uff0c\u90a3\u4e48\u4e24\u4e2a\u6307\u9488\u4f1a\u5404\u81ea\u5728\u904d\u5386\u5b8c\u4e00\u904dlistX+listC+listY\u548clistY+listC+listX\u540e\u540c\u65f6\u53d8\u4e3a\u7a7a\uff1b<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E5%88%A4%E6%96%AD%E9%93%BE%E8%A1%A8%E6%98%AF%E5%90%A6%E6%9C%89%E7%8E%AF\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/ctci-linked-list-cycle\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=linked-lists\" data-type=\"URL\" data-id=\"https:\/\/www.hackerrank.com\/challenges\/ctci-linked-list-cycle\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=linked-lists\">\u5224\u65ad\u94fe\u8868\u662f\u5426\u6709\u73af<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u7528\u4e24\u4e2a\u6307\u9488\u4ece\u5934\u5f00\u59cb\u904d\u5386\uff0c\u4e00\u4e2a\u6bcf\u6b21\u524d\u8fdb\uff11\u6b65\uff0c\u4e00\u4e2a\u6bcf\u6b21\u524d\u8fdb\uff12\u6b65\uff0c\u5982\u679c\u4e24\u4e2a\u6307\u9488\u8d70\u5230\u540c\u4e00\u4e2a\u8282\u70b9\u5219\u6709\u73af\uff0c\u5426\u5219\u8d70\uff12\u6b65\u7684\u4f1a\u5148\u8d70\u5230\u94fe\u8868\u7684\u672b\u5c3e\uff0e<\/p>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E9%80%92%E5%BD%92%E4%B8%8E%E5%9B%9E%E6%BA%AF\"><\/span>\u9012\u5f52\u4e0e\u56de\u6eaf<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E5%8D%81%E5%AD%97%E5%A1%AB%E5%AD%97%E6%B8%B8%E6%88%8F\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/crossword-puzzle\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=recursion-backtracking\">\u5341\u5b57\u586b\u5b57\u6e38\u620f<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u601d\u8def\uff1a\u9012\u5f52\u627e\u5230\u7b2c\u4e00\u4e2a&#8217;-&#8216;\u7684\u683c\u5b50\uff0c\u4f9d\u6b21\u5c1d\u8bd5\u7528\u6bcf\u4e00\u4e2a\u5355\u8bcd\u53bb\u586b\u8fd9\u4e2a\u683c\u5b50\uff0c\u5e76\u4e14\u586b\u7684\u65b9\u5f0f\u4e5f\u9700\u8981\u679a\u4e3e\uff0c\u4e00\u662f\u679a\u4e3e\u6a2a\u7740\u586b\u8fd8\u662f\u7ad6\u7740\u586b\uff0c\u4e8c\u662f\u8fd9\u4e2a\u683c\u5b50\u53ef\u80fd\u9700\u8981\u7528\u8fd9\u4e2a\u5355\u8bcd\u7684\u7b2c\u51e0\u4e2a\u5b57\u6bcd\u6765\u586b\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">multiset&lt;string&gt; split(string words, char sep) {\n    vector&lt;int&gt; seps;\n    seps.push_back(-1);\n    for (int i = 0; i &lt; words.size(); i++) {\n        if (words[i] == sep) {\n            seps.push_back(i);\n        }\n    }\n    seps.push_back(words.size());\n    multiset&lt;string&gt; res;\n    for (int i = 1; i &lt; seps.size(); i++) {\n        string word;\n        word.assign(words.substr(seps[i - 1] + 1, seps[i] - seps[i - 1] - 1));\n        res.insert(word);\n    }\n    return res;\n}\nbool match(vector&lt;string&gt; &amp;crossword, vector&lt;vector&lt;int&gt;&gt; &amp;state, string str, int dir, int offset, int x, int y) {\n    if (dir == 0) {\n        if (x - offset &lt; 0 || x - offset + str.size() &gt; crossword.size()) {\n            return false;\n        }\n        for (int i = x - offset; i &lt; x - offset + str.size(); i++) {\n            if (crossword[i][y] == '+' \n                || (crossword[i][y] != '-' &amp;&amp; crossword[i][y] != str[i - (x - offset)])) {\n                return false;\n            }            \n        }\n    } else {\n        if (y - offset &lt; 0 || y - offset + str.size() &gt; crossword[0].size()) {\n            return false;\n        }\n        for (int i = y - offset; i &lt; y - offset + str.size(); i++) {\n            if (crossword[x][i] == '+'\n                || (crossword[x][i] != '-' &amp;&amp; crossword[x][i] != str[i - (y - offset)])) {\n                return false;\n            }\n        }\n    }\n    return true;\n}\n\nvoid apply(vector&lt;string&gt; &amp;crossword, vector&lt;vector&lt;int&gt;&gt; &amp;state, string str, int dir, int offset, int x, int y) {\n    if (dir == 0) {\n        for (int i = x - offset; i &lt; x - offset + str.size(); i++) {\n            crossword[i][y] = str[i - (x - offset)];\n            ++state[i][y];\n        }\n    } else {\n        for (int i = y - offset; i &lt; y - offset + str.size(); i++) {\n            crossword[x][i] = str[i - (y - offset)];\n            ++state[x][i];\n        }\n    }    \n}\nvoid fallback(vector&lt;string&gt; &amp;crossword, vector&lt;vector&lt;int&gt;&gt; &amp;state, string str, int dir, int offset, int x, int y) {\n    if (dir == 0) {\n        for (int i = x - offset; i &lt; x - offset + str.size(); i++) {\n            state[i][y] -= 1;\n            if (state[i][y] == 0) {\n                crossword[i][y] = '-';\n            }\n        }\n    } else {\n        for (int i = y - offset; i &lt; y - offset + str.size(); i++) {\n            state[x][i] -= 1;\n            if (state[x][i] == 0) {\n                crossword[x][i] = '-';\n            }\n        }\n    }\n}\n\nbool solve(vector&lt;string&gt; &amp;crossword, multiset&lt;string&gt; &amp;words, vector&lt;vector&lt;int&gt;&gt; &amp;state) {\n    bool find = false;\n    int i = 0, j = 0;\n    for (i = 0; i &lt; crossword.size(); i++) {\n        for (j = 0; j &lt; crossword.size(); j++) {\n            if (crossword[i][j] == '-') {\n                find = true;\n                break;\n            }\n        }\n        if (find) {\n            break;\n        }\n    }\n    if (!find &amp;&amp; words.empty()) {\n        return true;\n    } else {\n        auto wordSet = words;\n        for (auto &amp;str : wordSet) {\n            for (auto dir = 0; dir &lt; 2; dir++) {\n                for (int k = 0; k &lt; str.size(); k++) {\n                    if (match(crossword, state, str, dir, k, i, j)) {\n                        apply(crossword, state, str, dir, k, i, j);\n                        words.erase(str);\n                        if (solve(crossword, words, state)) {\n                            return true;\n                        } else {\n                            words.insert(str);\n                            fallback(crossword, state, str, dir, k, i, j);\n                        }\n                    }\n                }\n            }\n        }\n    }\n    return false;    \n}\n\/*\n * Complete the 'crosswordPuzzle' function below.\n *\n * The function is expected to return a STRING_ARRAY.\n * The function accepts following parameters:\n *  1. STRING_ARRAY crossword\n *  2. STRING words\n *\/\nvector&lt;string&gt; crosswordPuzzle(vector&lt;string&gt; crossword, string words) {\n    int m = crossword.size();\n    int n = crossword[0].size();\n    vector&lt;vector&lt;int&gt;&gt; state;\n    for (int i = 0; i &lt; m; i++) {\n        state.push_back(vector&lt;int&gt;(n, 0));\n    }\n    multiset&lt;string&gt; wordSet = split(words, ';');\n    solve(crossword, wordSet, state);\n    return crossword;\n}\n<\/code><\/pre>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E6%A0%91\"><\/span>\u6811<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E5%88%A4%E6%96%AD%E6%98%AF%E5%90%A6%E6%98%AF%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/ctci-is-binary-search-tree\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=trees\" data-type=\"URL\" data-id=\"https:\/\/www.hackerrank.com\/challenges\/ctci-is-binary-search-tree\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=trees\">\u5224\u65ad\u662f\u5426\u662f\u4e8c\u53c9\u641c\u7d22\u6811<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u601d\u8def\uff1a\u9012\u5f52\u5224\u65ad\u3002<\/p>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92\"><\/span>\u52a8\u6001\u89c4\u5212<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Abbreviation\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/abbr\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=dynamic-programming\">Abbreviation<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u5bb9\u6613\u5751\u7684\u5730\u65b9\u5c31\u662f\u9012\u63a8\u7684\u65f6\u5019\uff0c\u5f53string a\u7684\u5b57\u4e32\u4e3a\u7a7a\u800cb\u7684\u5b50\u4e32\u4e0d\u4e3a\u7a7a\u7684\u65f6\u5019\uff0c\u8fd9\u4e2a\u4e24\u4e2a\u5b50\u4e32\u662f\u4e0d\u80fd\u7b97\u5339\u914d\u7684\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">string abbreviation(string a, string b) {\n    int lena = a.size();\n    int lenb = b.size();\n    if (lena &lt; lenb) {\n        return \"NO\";\n    }\n    bool res[lena + 1];\n    bool tmp[lena + 1];\n    bool findUpper = false;\n    res[0] = true;\n    for (int i = 0; i &lt; lena; i++) {\n        if (isupper(a[i])) {\n            findUpper = true;\n        }\n        res[i + 1] = !findUpper;\n    }\n    for (int i = 1; i &lt;= lenb; i++) {\n        memcpy(tmp, res, sizeof(bool) * (lena + 1));\n        res[0] = false; \/\/\u8fd9\u53e5\u8bdd\u5f88\u5173\u952e\n        for (int j = 1; j &lt;= lena; j++) {\n            if (isupper(a[j - 1])) {\n                res[j] = (a[j - 1] == b[i - 1]) &amp;&amp; tmp[j - 1];\n            } else {\n                res[j] = res[j - 1] || (tmp[j - 1] &amp;&amp; (toupper(a[j - 1]) == b[i - 1]));\n            }\n        }\n    }\n    if (res[lena]) {\n        return \"YES\";\n    } else {\n        return \"NO\";\n    }\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Candies\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/candies\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=dynamic-programming\">Candies<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u601d\u8def\uff1a\u4ece\u4e24\u4e2a\u65b9\u5411\u5206\u522b\u627e\u4ee5\u6bcf\u4e2a\u5143\u7d20\u7ed3\u5c3e\u7684\u6700\u957f\u8fde\u7eed\u4e0a\u5347\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\uff0c\u53d6\u8f83\u9ad8\u8005\u4f5c\u4e3acandy\u6570\u3002<\/p>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E8%B4%AA%E5%BF%83\"><\/span>\u8d2a\u5fc3<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Reverse_Shuffle_Merge\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/reverse-shuffle-merge\/problem?h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=greedy-algorithms\">Reverse Shuffle Merge<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u6c42\u6700\u5c0f\u7684A\uff0c\u5176\u5b9e\u5c31\u662f\u5c06\u5b57\u7b26\u4e32\u53cd\u8f6c\u540e\uff0c\u6309\u7167\u5b57\u7b26\u4e32\u73b0\u6709\u987a\u5e8f\u53d6\u4e00\u4e2a\u6700\u5c0f\u7684A\u3002\u65b9\u6cd5\u5c31\u662f\u6bcf\u6b21\u8d2a\u5fc3\u5730\u53d6\u4e00\u4e2a\u6700\u5c0f\u7684\u5408\u6cd5\u7684\u5b57\u7b26\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">int getMin(string &amp;s, int index, vector&lt;int&gt; discard_freq, vector&lt;int&gt; target_freq) {\n    int min_index = index;   \n    while (discard_freq[s[index] - 'a'] &gt; 0 &amp;&amp; index + 1 &lt; s.size()) {\n        --discard_freq[s[index] - 'a'];\n        ++index;\n        if (target_freq[s[index] - 'a'] &gt; 0\n            &amp;&amp; (s[index] &lt; s[min_index] || target_freq[s[min_index] - 'a'] &lt;= 0)) {\n            min_index = index;\n        }\n    }\n    return min_index;\n}\n\n\/*\n * Complete the 'reverseShuffleMerge' function below.\n *\n * The function is expected to return a STRING.\n * The function accepts STRING s as parameter.\n *\/\n\nstring reverseShuffleMerge(string s) {\n    vector&lt;int&gt; target_freq(26, 0);\n    for (auto ch : s) {\n        ++target_freq[ch - 'a'];\n    }\n    for (auto &amp;f : target_freq) {\n        f \/= 2;\n    }\n    vector&lt;int&gt; discard_freq = target_freq;\n    std::reverse(s.begin(), s.end());\n    \/\/cout &lt;&lt; \"reversed:\" &lt;&lt; s &lt;&lt; endl;\n    string res;\n    int index = -1;\n    while (res.size() &lt; s.size() \/ 2) {\n        int pick = getMin(s, index + 1, discard_freq, target_freq);\n        \/\/cout &lt;&lt; \"pick: \" &lt;&lt; pick &lt;&lt; \" \" &lt;&lt; s[pick] &lt;&lt; endl;\n        --target_freq[s[pick] - 'a'];\n        res.push_back(s[pick]);\n        for (int i = index + 1; i &lt; pick; i++) {\n            --discard_freq[s[i] - 'a'];\n        }\n        index = pick;\n    }\n    return res;\n}<\/code><\/pre>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97\"><\/span>\u6808\u4e0e\u961f\u5217<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Min_Max_Riddle\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/min-max-riddle\/problem?h_r=profile\">Min Max Riddle<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u601d\u8def\uff1a\u8ba1\u7b97\u51fa\u6bcf\u4e2a\u6570\u4f5c\u4e3a\u6700\u5c0f\u503c\u7684\u533a\u95f4\u957f\u5ea6(\u5206\u522b\u4ece\u987a\u5e8f\u548c\u9006\u5e8f\u4e24\u4e2a\u65b9\u5411\u904d\u5386\u6570\u7ec4\uff0c\u5e76\u7528\u5355\u8c03\u9012\u51cf\u7684\u6808\u7b97\u51fa\u6bcf\u4e2a\u6570\u5de6\u8fb9\u8fde\u7eed\u6bd4\u5b83\u5927\u7684\u6570\u7684\u4e2a\u6570\u548c\u53f3\u8fb9\u8fde\u7eed\u6bd4\u5b83\u5927\u7684\u6570\u7684\u4e2a\u6570)\uff0c\u8fd9\u4e2a\u533a\u95f4\u957f\u5ea6\u4e0d\u5305\u62ec\u81ea\u5df1\uff0c\u56e0\u6b64\u5176\u6700\u5c0f\u503c\u4e3a0\u3002\u5728\u8ba1\u7b97\u6bcf\u4e2a\u6570arr[i]\u4f5c\u4e3a\u6700\u5c0f\u503c\u7684\u533a\u95f4\u957f\u5ea6len[i]\u65f6\uff0c\u6bcf\u7b97\u51fa\u4e00\u4e2alen[i]\uff0c\u9700\u8981\u53bb\u66f4\u65b0\u7ed3\u679c\u6570\u7ec4res[len[i]] = max(res[len[i]], arr[i])\u3002\u9700\u8981\u6ce8\u610f\u4e00\u70b9\uff0c\u5982\u679c\u4e24\u4e2a\u6570arr[i]\uff0carr[j]\u6ee1\u8db3\uff1aarr[i] &gt; arr[j]\uff0clen[i] &gt; len[j]\uff0c\u90a3\u4e48res[len[j]]\u4e5f\u662f\u8981\u8003\u8651arr[i]\u7684\uff0c\u56e0\u4e3aarr[i]\u4f5c\u4e3a\u4e00\u4e2a\u66f4\u957f\u533a\u95f4\u7684\u6700\u5c0f\u503c\uff0c\u4e5f\u662f\u53ef\u4ee5\u4f5c\u4e3alen[j]\u8fd9\u79cd\u957f\u5ea6\u533a\u95f4\u7684\u6700\u5c0f\u503c\u7684\u3002\u6240\u4ee5\u5728\u8ba1\u7b97\u6700\u7ec8\u7684\u7ed3\u679c\u6570\u7ec4\u65f6\u6211\u4eec\u9700\u8981\u5012\u5e8f\u8fdb\u884c\u66f4\u65b0\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">for i = n - 2; i &amp;gt;= 0; i--\n       res[i] = max(res[i], res[i + 1]);<\/code><\/pre>\n\n\n\n<p>Solution\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">vector&lt;long&gt; riddle(vector&lt;long&gt; arr) {\n    vector&lt;long&gt; range(arr.size());\n    stack&lt;long&gt; descend_stack;\n    vector&lt;long&gt; res(arr.size(), 0);\n    \/\/ left side\n    for (int i = 0; i &lt; arr.size(); i++) {\n        while (!descend_stack.empty() &amp;&amp; arr[descend_stack.top()] &gt;= arr[i]) {\n            descend_stack.pop();\n        }\n        if (descend_stack.empty()) {\n            range[i] = i;\n        } else {\n            range[i] = i - descend_stack.top() - 1;\n        }\n        descend_stack.push(i);\n    }\n    while (!descend_stack.empty()) {\n        descend_stack.pop();\n    }\n    \/\/ plus right side\n    for (int i = arr.size() - 1; i &gt;= 0; i--) {\n        while (!descend_stack.empty() &amp;&amp; arr[descend_stack.top()] &gt;= arr[i]) {\n            descend_stack.pop();\n        }\n        if (descend_stack.empty()) {\n            range[i] += arr.size() - 1 - i;\n        } else {\n            range[i] += descend_stack.top() - 1 - i;\n        }\n        res[range[i]] = res[range[i]] &gt; arr[i] ? res[range[i]] : arr[i];\n        descend_stack.push(i);\n    }\n    for (int i = arr.size() - 2; i &gt;= 0; i--) {\n        res[i] = res[i + 1] &gt; res[i] ? res[i + 1] : res[i];\n    }\n    return res;\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E7%94%A8%E6%A0%88%E6%A8%A1%E6%8B%9F%E9%98%9F%E5%88%97\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/ctci-queue-using-two-stacks\/problem?isFullScreen=true&amp;h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=stacks-queues\">\u7528\u6808\u6a21\u62df\u961f\u5217<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u4e00\u4e2a\u6808\u7528\u4e8e\u83b7\u53d6\u961f\u5217\u5934\uff0c\u4e00\u4e2a\u6808\u7528\u4e8e\u83b7\u53d6\u961f\u5217\u5c3e\uff0c\u53ea\u6709\u5728\u5fc5\u8981\u7684\u65f6\u5019\u624d\u79fb\u52a8\u8fd9\u4e24\u4e2a\u6808\u4e2d\u7684\u4e00\u4e2a\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">class MyQueue {\n  \n    public:\n        stack&lt;int&gt; stack_newest_on_top, stack_oldest_on_top;   \n        void push(int x) {\n                   stack_newest_on_top.push(x);\n        }\n\n        void pop() {\n            if (stack_oldest_on_top.empty()) {\n                while (!stack_newest_on_top.empty()) {\n                    stack_oldest_on_top.push(stack_newest_on_top.top());\n                    stack_newest_on_top.pop();\n                }\n            }\n            stack_oldest_on_top.pop();\n        }\n\n        int front() {\n            if (stack_oldest_on_top.empty()) {\n                while (!stack_newest_on_top.empty()) {\n                    stack_oldest_on_top.push(stack_newest_on_top.top());\n                    stack_newest_on_top.pop();\n                }\n            }            \n            return stack_oldest_on_top.top();            \n        }\n};<\/code><\/pre>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E6%90%9C%E7%B4%A2\"><\/span>\u641c\u7d22<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Maximum_Subarray_Sum\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/maximum-subarray-sum\/problem?isFullScreen=true&amp;h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=search\">Maximum Subarray Sum<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u8ba1\u7b97\u8fde\u7eed\u5b50\u6570\u7ec4\u548c\u5bf9\u6307\u5b9a\u6570\u5b57m\u53d6\u6a21\u7684\u6700\u5927\u503c\u3002<\/p>\n\n\n\n<p>\u601d\u8def\u8ba1\u7b97\u4ece\u7d22\u5f150\u5f00\u59cb\u7684\u5e8f\u5217\u548c(\u5bf9m\u53d6\u4e86\u6a21\u7684)prefix[0]\uff0cprefix[1]\uff0cprefix[n-1]\u3002\u5219\u6240\u6709\u7684\u8fde\u7eed\u5b50\u6570\u7ec4\u548c\u90fd\u53ef\u4ee5\u901a\u8fc7prefix[i]\uff0ci = 0\uff0c1\uff0c&#8230;\uff0cn &#8211; 1\u4ee5\u53caprefix[j] &#8211; prefix[i]\uff0cj &gt; i\u8868\u793a\u51fa\u6765\u3002\u5728\u679a\u4e3e(prefix[j] &#8211; prefix[i])%m\u7684\u6700\u5927\u503c\u65f6\uff0c\u53ef\u4ee5\u5148\u679a\u4e3ej\uff0c\u56fa\u5b9a\u4f4fj\uff0c\u5728\u679a\u4e3ei\uff0ci\u53d60\uff0c1\uff0c&#8230;\uff0cj &#8211; 1\u3002\u8fd9\u79cd\u679a\u4e3e\u7684\u590d\u6742\u5ea6\u662fn\u5e73\u65b9\u7684\uff0c\u56e0\u6b64\u9700\u8981\u4f18\u5316\u3002\u4f18\u5316\u7684\u65b9\u5f0f\u5c31\u662f\u907f\u514d\u4e0d\u5fc5\u8981\u7684\u679a\u4e3e\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>\u5bf9\u4e8eprefix[i]\u6bd4prefix[j]\u5c0f\u7684i\uff0c\u6709prefix[j] &#8211; prefix[i] &lt;= prefix[j]\uff0c \u6240\u4ee5\u8fd9\u4e9bprefix[i]\u4e5f\u662f\u4e0d\u5fc5\u679a\u4e3e\u7684\uff1b<\/li><li>\u5bf9\u4e8eprefix[i]\u6bd4prefix[j]\u5927\u7684i\uff0c\u6211\u4eec\u53ea\u9700\u8981\u679a\u4e3e\u8fd9\u4e9bprefix[i]\u4e2d\u6700\u5c0f\u7684\u4e00\u4e2a\uff0c\u56e0\u4e3aprefix[j] &#8211; prefix[i]\u51cf\u51fa\u6765\u662f\u8d1f\u6570\uff0c\u5bf9m\u53d6\u6a21\u9700\u8981\u518d\u52a0\u4e0am\uff0c\u56e0\u6b64\u8d1f\u5f97\u8d8a\u5c11\uff0c\u53d6\u6a21\u7684\u7ed3\u679c\u8d8a\u5927\u3002<\/li><\/ol>\n\n\n\n<p>\u6240\u4ee5\u7ec8\u4e0a\u4e24\u4e2a\u4f18\u5316\u70b9\uff0c\u7b97\u6cd5\u601d\u8def\u5c31\u662f\u4f9d\u6b21\u8ba1\u7b97prefix[j]\uff0c\u5e76\u627e\u5230\u4e4b\u524d\u8ba1\u7b97\u51fa\u7684prefix[0]\uff0cprefix[1]\uff0cprefix[2]\uff0c&#8230;\uff0cprefix[j &#8211; 1]\u4e2d\u5927\u4e8eprefix[j]\u7684\u6700\u5c0f\u90a3\u4e00\u4e2a(\u5047\u8bbe\u7d22\u5f15\u662fk)\uff0c\u7528max(prefix[j]\uff0c(prefix[j] &#8211; prefix[k] + m) % m)\u53bb\u66f4\u65b0\u6211\u4eec\u8981\u6c42\u7684\u6700\u5927\u503c\u5373\u53ef\u3002<\/p>\n\n\n\n<p><a href=\"https:\/\/www.quora.com\/What-is-the-logic-used-in-the-HackerRank-Maximise-Sum-problem\">quora\u7684\u8bb2\u89e3<\/a>\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Making_Candies\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/making-candies\/problem?isFullScreen=true&amp;h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=search\">Making Candies<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u601d\u8def\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>\u5982\u679c\u8981\u589e\u52a0worker\u6216\u8005machine\uff0c\u90a3\u4e48\u5c31\u5e94\u8be5\u5728\u4e00\u5f00\u59cb\u5c31\u589e\u52a0\uff0c\u56e0\u4e3a\u76f8\u540c\u6570\u91cf\u7684worker\u548cmachine\uff0c\u589e\u52a0\u7684\u8d8a\u65e9\u751f\u4ea7\u7684candy\u8d8a\u591a\uff1b<\/li><li>\u589e\u52a0worker\u548cmachine\u65f6\uff0c\u5e94\u8be5\u6309\u7167\u5c3d\u91cf\u8ba9\u4e24\u8005\u6570\u91cf\u4e00\u81f4\u7684\u65b9\u5f0f\u6765\u589e\u52a0\uff0c\u8fd9\u6837\u624d\u53ef\u4ee5\u8ba9machine\u548cworker\u7684\u4e58\u79ef\u5c3d\u91cf\u5927\uff1b<\/li><li>\u6309\u7167\u589e\u52a0\u7684worker\u548cmachine\u7684\u603b\u6570\u6765\u679a\u4e3e\uff0c\u5f53\u53d1\u73b0\u589e\u52a0worker\u548cmachine\u53cd\u800c\u4f7f\u5f97\u751f\u4ea7\u6307\u5b9a\u6570\u91cfcandy\u7684\u65f6\u95f4\u589e\u52a0\u65f6\uff0c\u5c31\u4e0d\u7528\u7ee7\u7eed\u679a\u4e3e\u4e86\uff1b<\/li><li>\u6309\u7167\u7b2c3\u70b9\u5c1d\u8bd5\u4e00\u4e2a\u4e00\u4e2a\u7684\u589e\u52a0worker\u548cmachine\u7684\u603b\u6570\u6765\u679a\u4e3e\u4f1a\u5bfc\u81f4\u9700\u8981\u679a\u4e3e\u7684case\u5f88\u591a\uff0c\u8fd0\u884c\u8d85\u65f6\uff0c\u6240\u4ee5\u9700\u8981\u4f18\u5316\u3002\u4f18\u5316\u7684\u65b9\u5f0f\u662f\uff0c\u5982\u679c\u6bcf\u6b21\u51b3\u5b9a\u8981\u589e\u52a0worker\u548cmachine\u7684\u6570\u91cf\uff0c\u90a3\u5c31\u8981\u628a\u5269\u4f59\u7684candy\u82b1\u5b8c\uff0c\u4e0d\u8981\u8ba9\u5269\u4f59\u7684candy\u8d85\u8fc7p\u3002<\/li><\/ol>\n\n\n\n<p><a href=\"https:\/\/www.hackerrank.com\/challenges\/making-candies\/forum\/comments\/749961\">\u7b2c4\u70b9\u7684\u8bc1\u660e<\/a>\uff1a<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>a proof that we must only buy-all or buy-none, buy-some is not optimal<\/p><cite>At a certain pass, assume that current machine number and worker number is\u00a0<strong>m<\/strong>\u00a0and\u00a0<strong>w<\/strong>, and\u00a0<strong>m &lt;= w<\/strong>, assume\u00a0<strong>r<\/strong>\u00a0for\u00a0<strong>(n-remain)<\/strong>, if buy-one is better than buy-none means that\u00a0<strong>(r\/(m * w))>=((r+p)\/(m * w+w))<\/strong>, this equals to\u00a0<strong><em>r\/p >= m<\/em><\/strong><br>On this basis, prove buying\u00a0<strong>i+1<\/strong>\u00a0is better than buying\u00a0<strong>i<\/strong>\u00a0is to prove that\u00a0<strong>(r + ip)\/(mi * wi ) &#8211; (r+ip+p)\/(mi * wi + wi) >= 0<\/strong>\u00a0where\u00a0<strong>mi, wi<\/strong>\u00a0is machine number and worker number after investing\u00a0<strong>i<\/strong>\u00a0times<br><strong>(r + ip)\/(mi * wi ) &#8211; (r+ip+p)\/(mi * wi + wi) >= 0<\/strong>\u00a0equals\u00a0<strong>r\/p >= mi &#8211; i<\/strong>, because of\u00a0<strong>r\/p >= m<\/strong>, we only need to prove\u00a0<strong>m >= mi &#8211; i<\/strong>, since\u00a0<strong>i<\/strong>\u00a0is split into\u00a0<strong>wi<\/strong>\u00a0and\u00a0<strong>mi<\/strong>,\u00a0<strong>m + i >= mi<\/strong>\u00a0is obvious.<br><\/cite><\/blockquote>\n\n\n\n<p>\u4f18\u5316\u4e4b\u524d\u7684\u4ee3\u7801\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">\/*\n * Complete the 'minimumPasses' function below.\n *\n * The function is expected to return a LONG_INTEGER.\n * The function accepts following parameters:\n *  1. LONG_INTEGER m\n *  2. LONG_INTEGER w\n *  3. LONG_INTEGER p\n *  4. LONG_INTEGER n\n *\/\n\nlong minimumPasses(long m, long w, long p, long n) {\n    if ((double)m * (double)w &gt;= n) {\n        return 1;\n    }\n    long min_passes = ceil((double)n \/ (m * w));\n    long passes = 0;\n    long candies = 0; \/\/ candies remained in the last pass\n    if (p &gt;= n) {\n        return min_passes;\n    }\n    while (true) {\n        if (candies &lt; p) {\n            long added_passes = ceil((double) (p - candies) \/ (m * w));\n            candies += added_passes * (m * w);\n            passes += added_passes;\n        }\n        if (m &lt; w) {\n            ++m;\n        } else {\n            ++w;\n        }\n        candies -= p;\n        long passes_needed = min_passes;\n        if (candies &gt;= n) {\n            passes_needed = passes;\n        } else {\n            passes_needed = passes + ceil((double) (n - candies) \/ (m * w));\n        }\n        if (passes_needed &gt; min_passes || passes &gt;= min_passes) {\n            break;\n        } else if (passes_needed &lt; min_passes) {\n            min_passes = passes_needed;\n        }\n    }\n    return min_passes;\n}<\/code><\/pre>\n\n\n\n<p>\u4f18\u5316\u4e4b\u540e\u7684\u4ee3\u7801\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">\/*\n * Complete the 'minimumPasses' function below.\n *\n * The function is expected to return a LONG_INTEGER.\n * The function accepts following parameters:\n *  1. LONG_INTEGER m\n *  2. LONG_INTEGER w\n *  3. LONG_INTEGER p\n *  4. LONG_INTEGER n\n *\/\n\nlong minimumPasses(long m, long w, long p, long n) {\n    long min_passes = ceil((double)n \/ ((double)m * w));\n    long passes = 0;\n    long candies = 0; \/\/ candies remained in the last pass\n    if (p &gt;= n || min_passes == 1) {\n        return min_passes;\n    }\n    int index = 0;\n    while (true) {\n        if (candies &lt; p) {\n            long added_passes = ceil((double) (p - candies) \/ ((double)m * w));\n            candies += added_passes * (m * w);\n            passes += added_passes;\n        }\n        long added_m_or_w = candies \/ p;\n        if (m + added_m_or_w &lt;= w) {\n            m += added_m_or_w;\n        } else if (w + added_m_or_w &lt;= m) {\n            w += added_m_or_w;\n        } else {\n            long sum = m + w + added_m_or_w;\n            m = sum \/ 2;\n            w = sum - m;\n        }\n        candies = candies % p;\n        long passes_needed = passes + ceil((double) (n - candies) \/ ((double)m * w));\n        if (passes_needed &gt; min_passes || passes &gt;= min_passes) {\n            break;\n        } else if (passes_needed &lt;= min_passes) {\n            min_passes = passes_needed;\n            cout &lt;&lt; \"min_passes:\" &lt;&lt; passes_needed \n                 &lt;&lt; \" m:\" &lt;&lt; m\n                 &lt;&lt; \" w:\" &lt;&lt; w\n                 &lt;&lt; \" passes:\" &lt;&lt; passes\n                 &lt;&lt; \" candies:\" &lt;&lt; candies\n                 &lt;&lt; \" index:\" &lt;&lt; index++\n                 &lt;&lt; endl;\n        }\n    }\n    return min_passes;\n}\n<\/code><\/pre>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E5%9B%BE%E8%AE%BA\"><\/span>\u56fe\u8bba<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E5%AF%BB%E6%89%BE%E7%9B%B8%E5%90%8C%E9%A2%9C%E8%89%B2%E8%8A%82%E7%82%B9%E4%B9%8B%E9%97%B4%E7%9A%84%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/find-the-nearest-clone\/problem?isFullScreen=true&amp;h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=graphs\">\u5bfb\u627e\u76f8\u540c\u989c\u8272\u8282\u70b9\u4e4b\u95f4\u7684\u6700\u77ed\u8def\u5f84<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u5bf9\u6307\u5b9a\u989c\u8272\u7684\u8282\u70b9\u540c\u65f6\u8fdb\u884c\u5bbd\u5ea6\u4f18\u5148\u641c\u7d22\u5373\u53ef\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E4%BF%AE%E5%BB%BA%E9%81%93%E8%B7%AF%E5%92%8C%E5%9B%BE%E4%B9%A6%E9%A6%86%E7%9A%84%E6%9C%80%E5%B0%8F%E8%B4%B9%E7%94%A8\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/torque-and-development\/problem?isFullScreen=true&amp;h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=graphs\" data-type=\"URL\" data-id=\"https:\/\/www.hackerrank.com\/challenges\/torque-and-development\/problem?isFullScreen=true&amp;h_l=interview&amp;playlist_slugs%5B%5D=interview-preparation-kit&amp;playlist_slugs%5B%5D=graphs\">\u4fee\u5efa\u9053\u8def\u548c\u56fe\u4e66\u9986\u7684\u6700\u5c0f\u8d39\u7528<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u56fe\u4e66\u9986\u7684\u8d39\u7528\u4f4e\u4e8e\u9053\u8def\u8d39\u7528\u65f6\u5c31\u76f4\u63a5\u6bcf\u4e2a\u57ce\u5e02\u4fee\u5efa\u4e00\u5ea7\u56fe\u4e66\u9986\uff0c\u5426\u5219\u6709\u591a\u5c11\u4e2a\u8054\u901a\u5206\u91cf\u5c31\u4fee\u5efa\u591a\u5c11\u4e2a\u56fe\u4e66\u9986\u3002<\/p>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"%E5%85%B6%E4%BB%96\"><\/span>\u5176\u4ed6<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Maximum_Xor\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/maximum-xor\/problem?h_r=profile\">Maximum Xor<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u5bf9\u4e8e\u7ed9\u5b9a\u7684\u4e00\u4e2a\u6570\u548c\u4e00\u4e2a\u96c6\u5408\uff0c\u5224\u65ad\u8fd9\u4e2a\u6570\u548c\u96c6\u5408\u4e2d\u7684\u54ea\u4e2a\u6570\u505a\u5f02\u6216\u8fd0\u7b97\u5f97\u5230\u7684\u7ed3\u679c\u6700\u5927\u3002<\/p>\n\n\n\n<p>\u601d\u8def\uff1a\u5c06\u8fd9\u4e2a\u96c6\u5408\u91cc\u7684\u6570\u7ec4\u7ec7\u6210trie\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Friend_Circle_Queries\"><\/span><a href=\"https:\/\/www.hackerrank.com\/challenges\/friend-circle-queries\/problem?h_r=profile\">Friend Circle Queries<\/a><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u670b\u53cb\u7684\u670b\u53cb\u8fd8\u662f\u670b\u53cb\uff0c\u95ee\u6bcf\u5f53\u5f97\u77e5\u4e24\u4e2a\u4eba\u662f\u670b\u53cb\uff0c\u6240\u6709\u4eba\u4e2d\u6700\u5927\u7684\u670b\u53cb\u5708\u7684\u4eba\u6570\u662f\u591a\u5c11\uff1f<\/p>\n\n\n\n<p>\u601d\u8def\uff1a\u5e76\u67e5\u96c6\uff0c\u6bcf\u5f53\u5f97\u77e5\u4e24\u4eba\u662f\u670b\u53cb\u5173\u7cfb\u540e\uff0c\u5c06\u4eba\u6570\u8f83\u5c0f\u7684\u5708\u5b50\u91cc\u7684\u4eba\u52a0\u5165\u5230\u4eba\u6570\u6559\u5927\u7684\u5708\u5b50\u91cc\u53bb\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Warm-up Challenges Counting Valleys \u6570\u6d77\u62d4\u4ece0\u53d8\u4e3a\u8d1f\u6570\u7684\u6b21\u6570\u5373\u4e3a\u5c71\u8c37\u7684\u4e2a\u6570\u3002 Sales by Match \u6309\u989c\u8272\u7edf\u8ba1\u889c\u5b50\u7684\u4e2a\u6570\uff0c\u7136\u540e\u7b97\u53cc\u6570\u3002 Jumping on&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[32],"class_list":["post-529","post","type-post","status-publish","format-standard","hentry","category-10","tag-hackerrank"],"_links":{"self":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/529","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=529"}],"version-history":[{"count":23,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/529\/revisions"}],"predecessor-version":[{"id":686,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/529\/revisions\/686"}],"wp:attachment":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=529"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=529"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=529"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}