↓Skip to main content
  1. Posts/

LeetCode-3149 找出分数最低的排列

·1 min·
Table of Contents

LeetCode-3149 找出分数最低的排列 #

Solution 1 #

注意到一个排列左移一位对结果没有影响, 所以我们寻找的分数最低的排列中字典序最小的一定是 $0$ 开头的. 每次选择排列时, 需要保存当前用过的元素集合 $s$ 和最后一个使用到的元素 $x$ , 根据规则构造.

代码如下:

class Solution:
    def findPermutation(self, nums: List[int]) -> List[int]:
        n = len(nums)

        @cache
        def f(s, x):
            if s == (1 << n) - 1:
                return abs(x - nums[0])
            res = inf
            for i in range(n):
                if s & (1 << i) == 0:
                    res = min(res, f(s | (1 << i), i) + abs(x - nums[i]))
            return res
        
        ans = []
        def make_ans(s, x):
            ans.append(x)
            if s == (1 << n) - 1:
                return
            final_res = f(s, x)
            for i in range(n):
                if s & (1 << i) == 0:
                    if f(s | (1 << i), i) + abs(x - nums[i]) == final_res:
                        make_ans(s | 1 << i, i)
                        return
            
        make_ans(1, 0)
        return ans