2024-12-23：找出分数最低的排列。用go语言，给定一个数组 nums，它包含从 0 到 n-1 的一个排列。我们定义一

福大大架构师每日一题

发布于 2024-12-24 18:35:03

5900

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2024-12-23：找出分数最低的排列。用go语言，给定一个数组 nums，它包含从 0 到 n-1 的一个排列。

我们定义一个排列 perm 的分数为：

任务是找出一个排列 perm，使得其分数最低。

如果有多个排列的分数相同，则需要返回字典序最小的那个排列。

2 <= n == nums.length <= 14。

nums 是 [0, 1, 2, ..., n - 1] 的一个排列。

输入：nums = [1,0,2]。

输出：[0,1,2]。

字典序最小且分数最低的排列是 [0,1,2]。这个排列的分数是 |0 - 0| + |1 - 2| + |2 - 1| = 2 。

答案2024-12-23：

chatgpt[1]

题目来自leetcode3149。

大体步骤如下：

2.使用动态规划来解决这个问题，首先初始化一个数组 f，并使用一个数组 g 来记录每一步得到的结果对应的下一步的选择。

3.从后往前遍历，更新分数，然后回溯找出结果。

总的时间复杂度：

• 这种动态规划的运行时间为 O(2^n * n^2)，其中 n 表示数组的长度，由于使用了一个二维数组 f 来保存中间结果，所以时间复杂度是指数级别的。

总的额外空间复杂度：

• 需要额外的二维数组 f 和 g 来保存中间结果，因此额外空间复杂度为 O(2^n * n)，其中 n 表示数组的长度。

Go完整代码如下：

package main

import(
"fmt"
"math/bits"
"math"
)

func findPermutation(a []int)[]int{
    n :=len(a)
    u :=1<<n -1
    f :=make([][]int,1<<n)
    g :=make([][]int,1<<n)
for i :=range f {
        f[i]=make([]int, n)
for j :=range f[i]{
            f[i][j]= math.MaxInt
}
        g[i]=make([]int, n)
}
for j :=range f[u]{
        f[u][j]= abs(j - a[0])
        g[u][j]=-1
}
for s := u -2; s >0; s -=2{// 注意偶数不含 0，是无效状态
for _s :=uint(s); _s >0; _s &= _s -1{
            j := bits.TrailingZeros(_s)
for cus, lb := u^s,0; cus >0; cus ^= lb {
                lb = cus &-cus
                k := bits.TrailingZeros(uint(lb))
                v := f[s|lb][k]+ abs(j-a[k])
if v < f[s][j]{
                    f[s][j]= v
                    g[s][j]= k
}
}
}
}

    ans :=make([]int,0, n)
for s, j :=0,0; j >=0;{
        ans =append(ans, j)
        s |=1<< j
        j = g[s][j]
}
return ans
}

func abs(x int)int{if x <0{return-x };return x }

func main(){
    a :=[]int{1,0,2}
    fmt.Println(findPermutation(a))
}