{"id":137,"date":"2024-09-06T19:11:09","date_gmt":"2024-09-06T11:11:09","guid":{"rendered":"http:\/\/121.40.28.126\/?p=137"},"modified":"2024-09-11T11:27:23","modified_gmt":"2024-09-11T03:27:23","slug":"python-leetcode-3176","status":"publish","type":"post","link":"https:\/\/seandictionary.top\/python-leetcode-3176\/","title":{"rendered":"3176. \u6c42\u51fa\u6700\u957f\u597d\u5b50\u5e8f\u5217 I Python-Leetcode"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">\ud83d\udcd5\u9898\u5e72<\/h2>\n\n\n\n<p style=\"font-size:25px;color:#ffb800\">\u4e2d\u7b49<\/p>\n\n\n\n<p>\u7ed9\u4f60\u4e00\u4e2a\u6574\u6570\u6570\u7ec4&nbsp;<code>nums<\/code>&nbsp;\u548c\u4e00\u4e2a&nbsp;<strong>\u975e\u8d1f<\/strong>&nbsp;\u6574\u6570&nbsp;<code>k<\/code>&nbsp;\u3002\u5982\u679c\u4e00\u4e2a\u6574\u6570\u5e8f\u5217&nbsp;<code>seq<\/code>&nbsp;\u6ee1\u8db3\u5728\u4e0b\u6807\u8303\u56f4&nbsp;<code>[0, seq.length - 2]<\/code>&nbsp;\u4e2d&nbsp;<strong>\u6700\u591a\u53ea\u6709<\/strong>&nbsp;<code>k<\/code>&nbsp;\u4e2a\u4e0b\u6807&nbsp;<code>i<\/code>&nbsp;\u6ee1\u8db3&nbsp;<code>seq[i] != seq[i + 1]<\/code>&nbsp;\uff0c\u90a3\u4e48\u6211\u4eec\u79f0\u8fd9\u4e2a\u6574\u6570\u5e8f\u5217\u4e3a&nbsp;<strong>\u597d<\/strong>&nbsp;\u5e8f\u5217\u3002<\/p>\n\n\n\n<p>\u8bf7\u4f60\u8fd4\u56de&nbsp;<code>nums<\/code>&nbsp;\u4e2d&nbsp;<strong>\u597d<\/strong>&nbsp;<\/p>\n\n\n\n<p>\u5b50\u5e8f\u5217&nbsp;\u7684\u6700\u957f\u957f\u5ea6\u3002<\/p>\n\n\n\n<p><strong>\u793a\u4f8b 1\uff1a<\/strong><\/p>\n\n\n\n<p><strong>\u8f93\u5165\uff1a<\/strong>nums = [1,2,1,1,3], k = 2<\/p>\n\n\n\n<p><strong>\u8f93\u51fa\uff1a<\/strong>4<\/p>\n\n\n\n<p><strong>\u89e3\u91ca\uff1a<\/strong><\/p>\n\n\n\n<p>\u6700\u957f\u597d\u5b50\u5e8f\u5217\u4e3a&nbsp;<code>[<u>1<\/u>,<u>2<\/u>,<u>1<\/u>,<u>1<\/u>,3]<\/code>&nbsp;\u3002<\/p>\n\n\n\n<p><strong>\u793a\u4f8b 2\uff1a<\/strong><\/p>\n\n\n\n<p><strong>\u8f93\u5165\uff1a<\/strong>nums = [1,2,3,4,5,1], k = 0<\/p>\n\n\n\n<p><strong>\u8f93\u51fa\uff1a<\/strong>2<\/p>\n\n\n\n<p><strong>\u89e3\u91ca\uff1a<\/strong><\/p>\n\n\n\n<p>\u6700\u957f\u597d\u5b50\u5e8f\u5217\u4e3a&nbsp;<code>[<u>1<\/u>,2,3,4,5,<u>1<\/u>]<\/code>&nbsp;\u3002<\/p>\n\n\n\n<p><strong>\u63d0\u793a\uff1a<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>1 &lt;= nums.length &lt;= 500<\/code><\/li>\n\n\n\n<li><code>1 &lt;= nums[i] &lt;= 10<sup>9<\/sup><\/code><\/li>\n\n\n\n<li><code>0 &lt;= k &lt;= min(nums.length, 25)<\/code><\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">\ud83d\udcd6\u9898\u89e3<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u8c2c\u8bba<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">\ud83d\udcbb\u4ee3\u7801<\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution:\n    def maximumLength(self, nums: List&#91;int], k: int) -&gt; int:\n        l = 1\n        for i in range(2**len(nums)):\n            result = &#91;]\n            n = 0\n            a = bin(i)&#91;2:]\n            if len(a) &lt; len(nums):\n                a = '0'*(len(nums)-len(a)) + a\n            for m,j in enumerate(a):\n                if j == '0':\n                    result += &#91;nums&#91;m]]\n            for index in range(len(result)-1):\n                if result&#91;index] != result&#91;index+1]:\n                    n += 1\n            if n &lt;= k and len(result) &gt; l:\n                l = len(result)\n        return l<\/code><\/pre>\n\n\n\n<i class=\"fa fa-clock-o\" aria-hidden=\"true\"><\/i> \u6267\u884c\u7528\u65f6\uff1aNaN <i class=\"fa fa-microchip\" aria-hidden=\"true\"><\/i> \u6d88\u8017\u5185\u5b58\uff1aNaN\n\n\n\n<h4 class=\"wp-block-heading\">\ud83e\udd14\u601d\u8def<\/h4>\n\n\n\n<p>\u76f4\u63a5\u66b4\u529b\u6c42\u89e3\uff0c\u7528\u4e8c\u8fdb\u5236\u8868\u793a\u53bb\u4e0e\u820d\uff0c\u8ba1\u7b97\u5168\u90e8\u5b50\u96c6\u3002<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">\u2757 \u540e\u679c<\/h4>\n\n\n\n<p>\u65f6\u95f4\u590d\u6742\u5ea6\u8fbe\u5230\u4e86<em>O(2N\u00d7N)<\/em>\uff0c\u8352\u8c2c\u81f3\u6781\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u6b63\u89e3<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">\ud83d\udcbb\u4ee3\u7801<\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution:\n    def maximumLength(self, nums: List&#91;int], k: int) -&gt; int:\n        n = len(nums)\n        dp = &#91;&#91;1]*(k+1) for _ in range(n)]\n        for i in range (1,n):\n            for j in range(k+1):\n                for m in range(i):\n                    if nums&#91;m] == nums&#91;i]:\n                        dp&#91;i]&#91;j] = max(dp&#91;i]&#91;j],dp&#91;m]&#91;j]+1)\n                    elif j &gt; 0:\n                        dp&#91;i]&#91;j] = max(dp&#91;i]&#91;j],dp&#91;m]&#91;j-1]+1)\n        return max(max(a) for a in dp)<\/code><\/pre>\n\n\n\n<a href=\"https:\/\/leetcode.cn\/problems\/find-the-maximum-length-of-a-good-subsequence-i\/submissions\/562224438\/?envType=daily-question&#038;envId=2024-09-06\" target=\"_blank\" rel=\"noopener\">\n<i class=\"fa fa-clock-o\" aria-hidden=\"true\"><\/i> \u6267\u884c\u7528\u65f6\uff1a6357ms <i class=\"fa fa-microchip\" aria-hidden=\"true\"><\/i> \u6d88\u8017\u5185\u5b58\uff1a16.78MB\n<\/a>\n\n\n\n<h4 class=\"wp-block-heading\">\ud83e\udd14\u601d\u8def<\/h4>\n\n\n\n<p>\u6b64\u9898\u8003\u8651\u52a8\u6001\u89c4\u5212\uff0c\u6784\u5efa\u4e00\u4e2a\u4e8c\u7ef4\u6570\u7ec4<code>dp<\/code>\uff0c\u7528<code>dp[i][j]<\/code>\u8868\u793a\u4ee5<code>nums[i]<\/code>\u7ed3\u5c3e\u7684\u542b\u6709<code>j<\/code>\u4e2a\u4e0d\u540c\u6570\u5b57\u7684\u5b50\u5e8f\u5217\u7684\u6700\u957f\u957f\u5ea6\u3002<\/p>\n\n\n\n<p>\u5148\u5bf9<code>dp<\/code>\u8fdb\u884c\u521d\u59cb\u5316\uff0c\u65e0\u8bba<code>j<\/code>\u4e3a\u591a\u5c11\uff0c<code>dp[i][j]<\/code>\u59cb\u7ec8\u5927\u4e8e\u7b49\u4e8e1\uff0c\u53ef\u4ee5\u521d\u59cb\u5316<code>dp<\/code>\u4e2d\u6240\u6709\u5143\u7d20\u4e3a1\u3002\u7136\u540e\u5bf9<code>dp<\/code>\u4e2d\u7684\u5143\u7d20\u4f9d\u6b21\u904d\u5386\uff0c\u7531\u4e8e\u8003\u8651\u7684\u662f\u4ee5<code>nums[i]<\/code>\u7ed3\u5c3e\u7684\u5b50\u5e8f\u5217\uff0c\u4e5f\u5c31\u662f\u8bf4\u904d\u5386\u5230\u7684<code>nums[i]<\/code>\u5fc5\u987b\u53d6\uff0c\u6240\u4ee5\u53ea\u9700\u8981\u904d\u5386<code>i<\/code>\u4e4b\u524d\u7684\u5143\u7d20\u3002\u82e5<code>nums[i] == nums[m]<\/code>\uff0c\u6b64\u65f6\u7684<code>dp[i][j]<\/code>\u53ef\u4ee5\u8868\u793a\u4e3a<code>dp[m][j]+1<\/code>\uff0c\u7136\u540e\u53d6\u6700\u5927\u503c\u3002\u82e5<code>nums[i] != nums[m]<\/code>\uff0c\u4e5f\u5c31\u610f\u5473\u7740<code>j<\/code>\u8981\u589e\u52a01\uff0c\u6b64\u65f6\u7684<code>dp[i][j]<\/code>\u53ef\u4ee5\u8868\u793a\u4e3a<code>dp[m][j-1]+1<\/code>\uff0c\u7136\u540e\u53d6\u6700\u5927\u503c\u3002<\/p>\n\n\n\n<p>\u6700\u7ec8\u5f97\u5230<code>dp<\/code>\u7684\u6700\u5927\u503c\uff0c\u8fd4\u56de\u3002<\/p>\n\n\n\n<p>\u65f6\u95f4\u590d\u6742\u5ea6$$O(N^2*k)$$<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">\ud83d\ude05\u5410\u69fd<\/h4>\n\n\n\n<p>\u5bf9\u4e8e\u65b0\u624b\u6211\u6765\u8bf4\uff0c\u8fd9\u771f\u7684\u7b97\u4e0d\u4e0a\u4e2d\u7b49\uff0c\u592a\u56f0\u96be\u4e86\uff0c\u505a\u4e86\u4e00\u4e0b\u5348\uff0c\u5149\u52a8\u6001\u89c4\u5212\u5c31\u7406\u89e3\u4e86\u534a\u5929\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\ud83d\udcd5\u9898\u5e72 \u4e2d\u7b49 \u7ed9\u4f60\u4e00\u4e2a\u6574\u6570\u6570\u7ec4&nbsp;nums&nbsp;\u548c\u4e00\u4e2a&nbsp;\u975e\u8d1f&nbsp;\u6574\u6570&#038;nbsp [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[10,12,14],"class_list":["post-137","post","type-post","status-publish","format-standard","hentry","category-python","tag-leetcode","tag-dynamic-programming","tag-hash-table"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/seandictionary.top\/wp-json\/wp\/v2\/posts\/137","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seandictionary.top\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seandictionary.top\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seandictionary.top\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seandictionary.top\/wp-json\/wp\/v2\/comments?post=137"}],"version-history":[{"count":0,"href":"https:\/\/seandictionary.top\/wp-json\/wp\/v2\/posts\/137\/revisions"}],"wp:attachment":[{"href":"https:\/\/seandictionary.top\/wp-json\/wp\/v2\/media?parent=137"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seandictionary.top\/wp-json\/wp\/v2\/categories?post=137"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seandictionary.top\/wp-json\/wp\/v2\/tags?post=137"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}