{"id":593,"date":"2020-09-26T11:01:06","date_gmt":"2020-09-26T03:01:06","guid":{"rendered":"http:\/\/39.96.58.60\/?p=593"},"modified":"2022-10-18T16:45:05","modified_gmt":"2022-10-18T08:45:05","slug":"leetcode-60-%e7%ac%ack%e4%b8%aa%e6%8e%92%e5%88%97","status":"publish","type":"post","link":"https:\/\/www.yatenglg.cn\/blog\/?p=593","title":{"rendered":"Leetcode 60. \u7b2ck\u4e2a\u6392\u5217"},"content":{"rendered":"

\u7ed9\u51fa\u96c6\u5408 [1,2,3,\u2026,n<\/em>]<\/code>\uff0c\u5176\u6240\u6709\u5143\u7d20\u5171\u6709 n<\/em>! \u79cd\u6392\u5217\u3002<\/p>\n

\u6309\u5927\u5c0f\u987a\u5e8f\u5217\u51fa\u6240\u6709\u6392\u5217\u60c5\u51b5\uff0c\u5e76\u4e00\u4e00\u6807\u8bb0\uff0c\u5f53 n <\/em>= 3 \u65f6, \u6240\u6709\u6392\u5217\u5982\u4e0b\uff1a<\/p>\n

    \n
  1. \"123\"<\/code><\/li>\n
  2. \"132\"<\/code><\/li>\n
  3. \"213\"<\/code><\/li>\n
  4. \"231\"<\/code><\/li>\n
  5. \"312\"<\/code><\/li>\n
  6. \"321\"<\/code><\/li>\n<\/ol>\n

    \u7ed9\u5b9a n<\/em> \u548c k<\/em>\uff0c\u8fd4\u56de\u7b2c k<\/em> \u4e2a\u6392\u5217\u3002<\/p>\n

    \u8bf4\u660e\uff1a<\/strong><\/p>\n

      \n
    • \u7ed9\u5b9a n<\/em> \u7684\u8303\u56f4\u662f [1, 9]\u3002<\/li>\n
    • \u7ed9\u5b9a k <\/em>\u7684\u8303\u56f4\u662f[1,  n<\/em>!]\u3002<\/li>\n<\/ul>\n

      \u793a\u4f8b 1:<\/strong><\/p>\n

      \u8f93\u5165:<\/strong> n = 3, k = 3\n\n\u8f93\u51fa:<\/strong> \"213\"\n\n<\/pre>\n
      \u793a\u4f8b 2:<\/strong><\/p>\n
      \u8f93\u5165:<\/strong> n = 4, k = 9\n\n\u8f93\u51fa:<\/strong> \"2314\"\n\n<\/pre>\n
      **\u96be\u5ea6**: Medium<\/p>\n
      **\u6807\u7b7e**: \u6570\u5b66\u3001 \u56de\u6eaf\u7b97\u6cd5\u3001<\/p>\n
      \n
      \n# -*- coding: utf-8 -*-\n# @Author  : LG\n\n\"\"\"\n\u8d85\u65f6\n\n\u89e3\u9898\u601d\u8def\uff1a\n    \u56de\u6eaf\n\"\"\"\nclass Solution:\n    def getPermutation(self, n: int, k: int) -> str:\n        result = []\n\n        def backtrack(current:list, used:list):\n            if len(current) == n:\n                result.append(current[:])\n            for i in range(1, n+1):\n                if i not in used:\n                    current.append(i)\n                    used.append(i)\n                    backtrack(current, used)\n                    current.pop()\n                    used.pop()\n        backtrack([], [])\n        return ''.join([str(i) for i in result[k-1]])\n\n\n\"\"\"\n\u6267\u884c\u7528\u65f6\uff1a6032 ms, \u5728\u6240\u6709 Python3 \u63d0\u4ea4\u4e2d\u51fb\u8d25\u4e865.03% \u7684\u7528\u6237\n\u5185\u5b58\u6d88\u8017\uff1a31.5 MB, \u5728\u6240\u6709 Python3 \u63d0\u4ea4\u4e2d\u51fb\u8d25\u4e866.66% \u7684\u7528\u6237\n\n\u89e3\u9898\u601d\u8def\uff1a\n    \u6307\u5b9a\u8d77\u59cb\u9996\u5b57\u7b26\u56de\u6eaf\n\"\"\"\nclass Solution:\n    def getPermutation(self, n: int, k: int) -> str:\n        result = []\n        nums = 1\n        for i in range(1, n):\n            nums *= i\n        start = (k-1) \/\/ (nums)+1\n        extra = (k-1) % nums\n\n        def backtrack(current:list, used:list):\n            if len(current) == n:\n                result.append(current[:])\n            for i in range(1, n+1):\n                if i not in used:\n                    current.append(i)\n                    used.append(i)\n                    backtrack(current, used)\n                    current.pop()\n                    used.pop()\n\n        backtrack([start], [start])\n        return ''.join([str(i) for i in result[extra]])\n\n\n\"\"\"\n\u6267\u884c\u7528\u65f6\uff1a36 ms, \u5728\u6240\u6709 Python3 \u63d0\u4ea4\u4e2d\u51fb\u8d25\u4e8693.06% \u7684\u7528\u6237\n\u5185\u5b58\u6d88\u8017\uff1a13.6 MB, \u5728\u6240\u6709 Python3 \u63d0\u4ea4\u4e2d\u51fb\u8d25\u4e8684.55% \u7684\u7528\u6237\n\n\u89e3\u9898\u601d\u8def\uff1a\n    \u4f8b\u5b50\uff1a\n            4 9 \n    \n        4   8\/\/(3*2*1) = 1      1234    2\n            8%(3*2*1)  = 2      \n        3   2\/\/(2*1)   = 1      134     3\n            2%(2*1)    = 0      \n        2   0%1        = 0      14      1\n            0\/\/1       = 0      \n        1   0          = 0      4       4\n        \n            4 23 \n    \n        4   22\/\/(3*2*1)= 3      1234    4\n            22%(3*2*1) = 4      \n        3   4\/\/(2*1)   = 2      123     3\n            4%(2*1)    = 0      \n        2   0%1        = 0      12      1\n            0\/\/1       = 0      \n        1   0          = 0      2       2\n        \n            3   3\n        3   2\/\/(2*1)    = 1     123     2\n            2%(2*1)     = 0\n        2   0\/\/1        = 0     13      1\n            0%1         = 0\n        1   0           = 0     3       3\n\n\"\"\"\nclass Solution:\n    def getPermutation(self, n: int, k: int) -> str:\n        result = []\n        nums = list(range(1, n+1))\n        mul = 1\n        for i in nums:\n           mul *= i\n        k = k-1\n        for i in range(n, 0, -1):\n            mul = mul \/ i\n            index = int(k \/\/ mul)\n            result.append(nums[index])\n            k = k % mul\n            del nums[index]\n\n        return ''.join([str(i) for i in result])<\/code><\/pre>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
      \u7ed9\u51fa\u96c6\u5408 [1,2,3,\u2026,n]\uff0c\u5176\u6240\u6709\u5143\u7d20\u5171\u6709 n! \u79cd\u6392\u5217\u3002 \u6309\u5927\u5c0f\u987a\u5e8f\u5217\u51fa\u6240\u6709\u6392\u5217\u60c5…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":[],"categories":[11,1],"tags":[],"_links":{"self":[{"href":"https:\/\/www.yatenglg.cn\/blog\/index.php?rest_route=\/wp\/v2\/posts\/593"}],"collection":[{"href":"https:\/\/www.yatenglg.cn\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.yatenglg.cn\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.yatenglg.cn\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.yatenglg.cn\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=593"}],"version-history":[{"count":1,"href":"https:\/\/www.yatenglg.cn\/blog\/index.php?rest_route=\/wp\/v2\/posts\/593\/revisions"}],"predecessor-version":[{"id":594,"href":"https:\/\/www.yatenglg.cn\/blog\/index.php?rest_route=\/wp\/v2\/posts\/593\/revisions\/594"}],"wp:attachment":[{"href":"https:\/\/www.yatenglg.cn\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=593"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.yatenglg.cn\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=593"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.yatenglg.cn\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=593"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}