{"id":321,"date":"2022-02-07T15:13:54","date_gmt":"2022-02-07T07:13:54","guid":{"rendered":"https:\/\/www.wennroy.com\/?p=321"},"modified":"2022-02-07T15:14:09","modified_gmt":"2022-02-07T07:14:09","slug":"1405-longest-happy-string","status":"publish","type":"post","link":"https:\/\/wennroy.com\/index.php\/2022\/02\/07\/1405-longest-happy-string\/","title":{"rendered":"1405. \u6700\u957f\u5feb\u4e50\u5b57\u7b26\u4e32"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">\u5982\u679c\u5b57\u7b26\u4e32\u4e2d\u4e0d\u542b\u6709\u4efb\u4f55 <code>'aaa'<\/code>\uff0c<code>'bbb'<\/code> \u6216 <code>'ccc'<\/code> \u8fd9\u6837\u7684\u5b57\u7b26\u4e32\u4f5c\u4e3a\u5b50\u4e32\uff0c\u90a3\u4e48\u8be5\u5b57\u7b26\u4e32\u5c31\u662f\u4e00\u4e2a\u300c\u5feb\u4e50\u5b57\u7b26\u4e32\u300d\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u7ed9\u4f60\u4e09\u4e2a\u6574\u6570 <code>a<\/code>\uff0c<code>b<\/code> \uff0c<code>c<\/code>\uff0c\u8bf7\u4f60\u8fd4\u56de \u4efb\u610f\u4e00\u4e2a \u6ee1\u8db3\u4e0b\u5217\u5168\u90e8\u6761\u4ef6\u7684\u5b57\u7b26\u4e32 <code>s<\/code>\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>s<\/code> \u662f\u4e00\u4e2a\u5c3d\u53ef\u80fd\u957f\u7684\u5feb\u4e50\u5b57\u7b26\u4e32\u3002<\/li><li><code>s<\/code> \u4e2d \u6700\u591a \u6709<code>a<\/code> \u4e2a\u5b57\u6bcd <code>'a'<\/code>\u3001<code>b<\/code>\u00a0\u4e2a\u5b57\u6bcd <code>'b'<\/code>\u3001<code>c<\/code> \u4e2a\u5b57\u6bcd <code>'c'<\/code>\u3002<\/li><li><code>s<\/code> \u4e2d\u53ea\u542b\u6709 <code>'a'<\/code>\u3001<code>'b'<\/code> \u3001<code>'c'<\/code> \u4e09\u79cd\u5b57\u6bcd\u3002<\/li><li>\u5982\u679c\u4e0d\u5b58\u5728\u8fd9\u6837\u7684\u5b57\u7b26\u4e32 <code>s<\/code> \uff0c\u8bf7\u8fd4\u56de\u4e00\u4e2a\u7a7a\u5b57\u7b26\u4e32 <code>\"\"<\/code>\u3002<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u76f4\u63a5\u8d2a\u5a6a\u7b97\u6cd5\uff0c\u6bcf\u6b21\u53ea\u653e\u4e0b\u5269\u4f59\u5b57\u6570\u6700\u591a\u7684\u5b57\u6bcd\uff0c\u5982\u679c\u5df2\u7ecf\u6709\u4e24\u4e2a\u76f8\u540c\u7684\uff0c\u5219\u653e\u4e0b\u7b2c\u4e8c\u591a\u7684\u3002\u82e5\u7b2c\u4e8c\u591a\u7684\u4e3a0\uff0c\u5219\u8bf4\u660e\u65e0\u5b57\u6bcd\u53ef\u653e\uff0c\u7ed3\u675f\u5faa\u73af\u3002<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution:\n    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n        # \u8d2a\u5a6a\n        def findmaxmin(self, vector):\n            if vector[0] > vector[1]:\n                if vector[0]>vector[2]:\n                    if vector[1]>vector[2]:\n                        return [0,1,2]\n                    else:\n                        return [0,2,1]\n                else:\n                    return [2,0,1]\n            else:\n                if vector[0]>vector[2]:\n                    return [1,0,2]\n                else:\n                    if vector[2]>vector[1]:\n                        return [2,1,0]\n                    else:\n                        return [1,2,0]\n        s = ''\n        count = [a,b,c]\n        prev = -1\n        prevv = -1\n\n        def replaceprev(self, a, prev, prevv):\n            prevv = prev\n            prev = a\n            return prev, prevv\n\n        while not sum(count) == 0:\n            index = findmaxmin(self,count)\n            nxt = index[0]\n            if nxt == prev and nxt == prevv:\n                nxt = index[1]\n                if count[nxt] == 0:\n                        break\n\n                if nxt == 0:\n                    s += \"a\"\n                elif nxt == 1:\n                    s += \"b\"\n                else:\n                    s += \"c\"\n            else:\n                if count[nxt] == 0:\n                    nxt = index[1]\n                    if count[nxt] == 0:\n                        break\n                if nxt == 0:\n                    s += \"a\"\n                elif nxt == 1:\n                    s += \"b\"\n                else:\n                    s += \"c\"\n            prev,prevv = replaceprev(self, nxt, prev,prevv)\n            count[nxt] -= 1\n        return s<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e00\u6b21\u8fc7\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u6267\u884c\u7528\u65f6\uff1a<\/strong>40 ms, \u5728\u6240\u6709\u00a0Python3\u00a0\u63d0\u4ea4\u4e2d\u51fb\u8d25\u4e8616.55%\u7684\u7528\u6237<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u5185\u5b58\u6d88\u8017\uff1a<\/strong>15.1 MB, \u5728\u6240\u6709\u00a0Python3\u00a0\u63d0\u4ea4\u4e2d\u51fb\u8d25\u4e8628.27%\u7684\u7528\u6237<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u5b98\u65b9\u6807\u7b54\uff1a<\/strong>\u4e00\u6837\u8d2a\u5fc3\uff0c\u53ea\u662f\u9ad8\u7ea7\u4e86\u5f88\u591a\u3002<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution:\n    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n        ans = []\n        cnt = [[a, 'a'], [b, 'b'], [c, 'c']]\n        while True:\n            cnt.sort(key=lambda x: -x[0])\n            hasNext = False\n            for i, (c, ch) in enumerate(cnt):\n                if c &lt;= 0:\n                    break\n                if len(ans) >= 2 and ans[-2] == ch and ans[-1] == ch:\n                    continue\n                hasNext = True\n                ans.append(ch)\n                cnt[i][0] -= 1\n                break\n            if not hasNext:\n                return ''.join(ans)<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6765\u6e90\uff1a\u529b\u6263\uff08LeetCode\uff09<br>\u94fe\u63a5\uff1a<a href=\"https:\/\/leetcode-cn.com\/problems\/longest-happy-string\">https:\/\/leetcode-cn.com\/problems\/longest-happy-string<\/a><br>\u8457\u4f5c\u6743\u5f52\u9886\u6263\u7f51\u7edc\u6240\u6709\u3002\u5546\u4e1a\u8f6c\u8f7d\u8bf7\u8054\u7cfb\u5b98\u65b9\u6388\u6743\uff0c\u975e\u5546\u4e1a\u8f6c\u8f7d\u8bf7\u6ce8\u660e\u51fa\u5904\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Python\u5c0f\u77e5\u8bc6<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><code>cnt.sort(key=lambda x: -x[0])<\/code> \u6392\u5e8f\uff0c\u5f88\u4e45\u6ca1\u7528\u5fd8\u4e86\u3002<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\u5982\u679c\u5b57\u7b26\u4e32\u4e2d\u4e0d\u542b\u6709\u4efb\u4f55 &#8216;aaa&#8217;\uff0c&#8217;bbb&#8217; \u6216 &hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[6,28],"tags":[25,14,40],"class_list":["post-321","post","type-post","status-publish","format-standard","hentry","category-leetcode","category-greedy-algorithm","tag-leetcode","tag-14","tag-40"],"_links":{"self":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/321","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/comments?post=321"}],"version-history":[{"count":1,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/321\/revisions"}],"predecessor-version":[{"id":322,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/321\/revisions\/322"}],"wp:attachment":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/media?parent=321"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/categories?post=321"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/tags?post=321"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}