最大最小排列.org

下一个排列

题目

思路

从后往前遍历，找到第一个a[i]>a[i-1]的元素，然后在nums[a:]中找到最小的大于a[i-1]的元素，替换a[i-1]，此时nums[a:]依然为降序，反转即可

code

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(i, j):
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1

        for i in range(len(nums)-1, 0, -1):
            if nums[i] > nums[i-1]:
                j = i
                while j<len(nums) and nums[j] > nums[i-1]:
                    j += 1
                nums[i-1], nums[j-1] = nums[j-1], nums[i-1]
                reverse(i, len(nums)-1)
                return
        reverse(0, len(nums)-1)
        return

第k个排列

题目

思路

• 暴力：利用下一个排列逐步求更大的最小排列，直到第k个
• 回溯+剪枝：确定第一个数后，后面的数的可能性有n!种，如果小于k，那么确定的第一个数不是答案的一部分，因此第一个数应该是nums的第二个，再计算后面的数的可能性有没有超过k，没有的话，便可以确定第一位数，以此类推

code

# 暴力-7500ms
class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        nums = list(range(1, n+1))
        def helper(nums):
            for i in range(len(nums)-1, 0, -1):
                if nums[i] > nums[i-1]:
                    j = i
                    while j<len(nums) and nums[j]>nums[i-1]:
                        j += 1
                    nums[i-1], nums[j-1] = nums[j-1], nums[i-1]
                    tmp = nums[i:][::-1]
                    return nums[:i] + tmp
        for i in range(1, k):
            nums = helper(nums)
        return ''.join([str(n) for n in nums])

# 回溯+剪枝-40ms
import math
class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        # 剪枝
        nums = list(range(1, n+1))
        ans = ''
        count = 0
        def dfs(path, ns):
            nonlocal ans, count, k
            if len(path)==len(nums):
                ans = ''.join([str(n) for n in path])
                count = 1
                return   
            for i, n in enumerate(ns):
                if not count:
                    if math.factorial(len(ns[:i]+ns[i+1:]))>=k:
                        path.append(n)
                        ns_ = ns[:i] + ns[i+1:]
                        dfs(path, ns_)
                        path.pop()
                    else:
                        k -= math.factorial(len(ns[:i]+ns[i+1:]))
		else:
		    break
        dfs([], nums)
        return ans

全排列

题目

思路

个人题解

code

# 回溯
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 回溯DFS
        ans = []
        def dfs(path, ns):
            if len(path) == len(nums):
                ans.append(path[:])
                return
            for i, n in enumerate(ns):
                path.append(n)
                ns_ = ns[:i] + ns[i+1:]
                dfs(path, ns_)
                path.pop()
        dfs([], nums)
        return ans    

# DP
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return None
        dp = [[] for i in range(len(nums))]
        dp[0] = [[nums[0]]]
        for i in range(1, len(nums)):
            # 状态转移
            for ans in dp[i-1]:
                # 尾插
                dp[i].append(ans+[nums[i]])
                # 前插
                for j in range(len(ans)):
                    dp[i].append(ans[:j]+[nums[i]]+ans[j:])
        return dp[-1]

全排列II

题目

思路

• 回溯：和全排列的不同点在于数组有重复数字，因此回溯过程需要对重复出现的进行剪枝，需要进行排序，将重复数字聚拢在一起

code

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 回溯
        ans = []
        nums.sort()
        def dfs(path, ns):
            if len(path) == len(nums):
                ans.append(path[:])
                return
            for i, n in enumerate(ns):
                if i==0 or ns[i] != ns[i-1]:
                    path.append(n)
                    ns_ = ns[:i] + ns[i+1:]
                    dfs(path, ns_)
                    path.pop()
        dfs([], nums)
        return ans