{"id":129,"date":"2022-12-25T13:48:39","date_gmt":"2022-12-25T05:48:39","guid":{"rendered":"https:\/\/www.vcoco.top\/?p=129"},"modified":"2022-12-28T14:18:27","modified_gmt":"2022-12-28T06:18:27","slug":"leetcode-%e7%ac%ac-325-%e5%9c%ba%e5%91%a8%e8%b5%9b","status":"publish","type":"post","link":"https:\/\/www.vcoco.top\/index.php\/2022\/12\/25\/leetcode-%e7%ac%ac-325-%e5%9c%ba%e5%91%a8%e8%b5%9b\/","title":{"rendered":"Leetcode \u7b2c 325 \u573a\u5468\u8d5b"},"content":{"rendered":"\n<p>\u9898\u76ee\u94fe\u63a5\uff1a<a href=\"https:\/\/leetcode.cn\/contest\/weekly-contest-325\">\u7b2c 325 \u573a\u5468\u8d5b &#8211; \u529b\u6263\uff08LeetCode\uff09<\/a><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u6700\u540e\u4e00\u9898\u6ca1\u8003\u8651\u5168\u75db\u5931AK<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">\u5230\u76ee\u6807\u5b57\u7b26\u4e32\u7684\u6700\u77ed\u8ddd\u79bb<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int closetTarget(vector&lt;string&gt;&amp; words, string target, int startIndex) \n    {\n        int res=INT_MAX;\n        int n=words.size();\n        for(int i=0;i&lt;n;i++)\n        {\n            if(words&#91;i]==target)\n            {\n                res=min(res, (i-startIndex+n)%n);\n                res=min(res, (startIndex-i+n)%n);\n            }\n        }\n        return res==INT_MAX?-1:res;\n    }\n};<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u6bcf\u79cd\u5b57\u7b26\u81f3\u5c11\u53d6K\u4e2a<\/h3>\n\n\n\n<p>\u4ece\u5934\u6216\u5c3e\u4efb\u53d6\u4e00\u4e9b\u6570\u5b57\uff0c\u8ba9abc\u90fd\u81f3\u5c11\u51fa\u73b0k\u6b21\u3002<\/p>\n\n\n\n<p>\u505a\u6cd5\uff1a\u4e8c\u5206\u6b65\u6570\uff08PS\uff1a\u80af\u5b9a\u6709\u5176\u4ed6\u505a\u6cd5\uff0c\u6ca1\u591a\u60f3\uff09<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int s1&#91;100010]&#91;4], s2&#91;100010]&#91;4];\n    int k;\n    bool check(int len, int n)\n    {\n        for(int l=0, r=len-l;l&lt;=len;l++, r--)\n        {\n            int a=(l-1&gt;=0?s1&#91;l-1]&#91;0]:0)+s2&#91;n-r]&#91;0];\n            int b=(l-1&gt;=0?s1&#91;l-1]&#91;1]:0)+s2&#91;n-r]&#91;1];\n            int c=(l-1&gt;=0?s1&#91;l-1]&#91;2]:0)+s2&#91;n-r]&#91;2];\n            if(a&gt;=k &amp;&amp; b&gt;=k &amp;&amp; c&gt;=k) return true;\n        }\n        return false;\n    }\n    int takeCharacters(string s, int k) {\n        if(k==0) return 0;\n        this-&gt;k=k;\n        for(int i=0;i&lt;s.size();i++){\n            if(i) for(int j=0;j&lt;3;j++) s1&#91;i]&#91;j]=s1&#91;i-1]&#91;j];\n            s1&#91;i]&#91;s&#91;i]-'a']++;\n        }\n        for(int i=s.size()-1;i&gt;=0;i--){\n            for(int j=0;j&lt;3;j++) s2&#91;i]&#91;j]=s2&#91;i+1]&#91;j];\n            s2&#91;i]&#91;s&#91;i]-'a']++;\n        }\n        \n        int l=1, r=s.size();\n        while(l&lt;r)\n        {\n            int mid=l+r&gt;&gt;1;\n            if(check(mid, s.size())) r=mid;\n            else l=mid+1;\n        }\n        if(check(r, s.size())) return r;\n        return -1;\n    }\n};<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u793c\u76d2\u7684\u6700\u5927\u751c\u871c\u5ea6<\/h3>\n\n\n\n<p>\u4efb\u9009k\u4e2a\u5143\u7d20\u6c42\u5176\u4e4b\u95f4\u5dee\u6700\u5c0f\u503c\uff0c\u4f7f\u8fd9\u4e2a\u6700\u5c0f\u503c\u6700\u5927\u3002<\/p>\n\n\n\n<p>\u505a\u6cd5\uff1a\u76f4\u63a5\u4e8c\u5206\u751c\u871c\u5ea6<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    \n    int n, k;\n    vector&lt;int&gt; price;\n    bool check(int m)\n    {\n        int r=n-1, l=0;\n        if(price&#91;r]-price&#91;l]&lt;m) return false;\n        int cnt=2, d=0;\n        for(int i=1;i&lt;n-1;i++)\n        {\n            if(price&#91;i]-price&#91;l]&lt;m) continue;\n            if(price&#91;r]-price&#91;i]&lt;m) break;\n            cnt++;\n            l=i;\n        }\n        \n        return cnt&gt;=k;\n    }\n    \n    int maximumTastiness(vector&lt;int&gt;&amp; price, int k) {\n        n=price.size();\n        sort(price.begin(), price.end());\n        this-&gt;price=price;\n        this-&gt;k=k;\n        \n        int l=0, r=1e9;\n        while(l&lt;r)\n        {\n            int mid=l+r+1&gt;&gt;1;\n            if(check(mid)) l=mid;\n            else r=mid-1;\n        }\n        \n        return r;\n    }\n};<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u597d\u5206\u533a\u7684\u6570\u76ee<\/h3>\n\n\n\n<p>\u597d\u5206\u533a\u65b9\u6848\u6570=\u603b\u65b9\u6848\u6570-\u574f\u5206\u533a\u65b9\u6848\u6570<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u60c5\u51b51\uff1a$sum&gt;=k\\times2$\uff0c\u8fd9\u79cd\u662f\u6b63\u5e38\u60c5\u51b5\uff0c\u7edf\u8ba1\u4e00\u4fa7\u5206\u533a\u7684\u65b9\u6848\u6570\u518d\u4e58\u4ee52\uff0c\u5c31\u662f\u574f\u5206\u533a\u65b9\u6848\u6570<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u60c5\u51b52\uff1a$sum&lt;k\\times2$\uff0c\u6b64\u65f6\u7edf\u8ba1\u4e00\u4fa7\u5206\u533a\u7684\u65b9\u6848\u4f1a\u91cd\u590d\u7edf\u8ba1\uff08\u5982[1,2,3], k=5\u3002\u6b64\u65f6sum=6, \u7edf\u8ba1\u4e00\u4fa7\u65b9\u6848\u6570\u65f6\u4f1a\u6709\uff1a(0, 6), (1, 5), (2, 4), (3, 3), (4, 2)\u3002(3, 3)\u548c(4, 2)\u90fd\u5305\u542b\u91cd\u590d\uff09\u4f46\u8fd9\u79cd\u60c5\u51b5\u4e0d\u4f1a\u6709\u597d\u5206\u533a\uff0c\u7279\u5224\u6389\u5373\u53ef<\/li>\n<\/ul>\n\n\n\n<p>\u505a\u6cd5\uff1a\u52a8\u6001\u89c4\u5212-01\u80cc\u5305<\/p>\n\n\n\n<p><strong>\u72b6\u6001\u8868\u793a<\/strong>\uff1a$dp[i][j]$ \u8868\u793a\u8003\u8651\u524d$i$\u4e2a\u6570\u5b57\u4e14\u603b\u548c\u4e3a$j$\u7684\u65b9\u6848\u6570<\/p>\n\n\n\n<p><strong>\u72b6\u6001\u8ba1\u7b97<\/strong>\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u4e0d\u8003\u8651\u7b2c$i$\u4e2a\u6570\u5b57\uff1a$dp[i][j]=dp[i-1][j]$<\/li>\n\n\n\n<li>\u8003\u8651\u7b2c$i$\u4e2a\u6570\u5b57\uff1a$dp[i][j]+=dp[i][j-nums[i]], j&gt;=nums[i]$<\/li>\n<\/ol>\n\n\n\n<p><strong>\u7ed3\u679c\u8868\u793a<\/strong>\uff1a$res=2\\times\\sum\\limits_{i=0}^{k-1}{dp[n][i]}$<\/p>\n\n\n\n<p><strong>\u7b54\u6848\u8868\u793a<\/strong>\uff1a$ans=2^n-res$<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int MOD=1e9+7;\n    int dp&#91;1010]&#91;1010];\n    \n    int qmi(int a, int b)\n    {\n        long long res=1;\n        while(b)\n        {\n            if(b&amp;1) res=res*a%MOD;\n            a=1ll*a*a%MOD;\n            b&gt;&gt;=1;\n        }\n        return res;\n    }\n    \n    int countPartitions(vector&lt;int&gt;&amp; nums, int k) {\n        dp&#91;0]&#91;0]=1;\n        int n=nums.size();\n        long long sum=0;\n        for(auto x: nums) sum+=x;\n        if(sum&lt;k*2) return 0;\n            \n        for(int ii=0;ii&lt;n;ii++){\n            int i=ii+1;\n            for(int j=0;j&lt;k;j++){\n                dp&#91;i]&#91;j]=dp&#91;i-1]&#91;j];\/\/\u4e0d\u9009\n                if(j-nums&#91;ii]&gt;=0) dp&#91;i]&#91;j]=(dp&#91;i]&#91;j]+dp&#91;i-1]&#91;j-nums&#91;ii]])%MOD;\n            }\n        }\n        \n        long long res=0;\n        for(int i=0;i&lt;k;i++) {\n            res=(res+dp&#91;n]&#91;i])%MOD;\n        }\n\n        res=res*2%MOD;\n        \n        return (qmi(2, n)-res+MOD)%MOD;\n    }\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u94fe\u63a5\uff1a\u7b2c 325 \u573a\u5468\u8d5b &#8211; \u529b\u6263\uff08LeetCode\uff09 \u5230\u76ee\u6807\u5b57\u7b26\u4e32\u7684\u6700\u77ed\u8ddd\u79bb \u6bcf\u79cd\u5b57\u7b26\u81f3\u5c11\u53d6 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":172,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[76,26,79,75,78,77],"class_list":["post-129","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-leetcode","tag-76","tag-dp","tag-leetcode","tag-75","tag-78","tag-77"],"_links":{"self":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts\/129","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/comments?post=129"}],"version-history":[{"count":12,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts\/129\/revisions"}],"predecessor-version":[{"id":159,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts\/129\/revisions\/159"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/media\/172"}],"wp:attachment":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/media?parent=129"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/categories?post=129"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/tags?post=129"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}