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

举报
福大大架构师每日一题 发表于 2024/12/23 09:27:34 2024/12/23
【摘要】 2024-12-23:找出分数最低的排列。用go语言,给定一个数组 nums,它包含从 0 到 n-1 的一个排列。我们定义一个排列 perm 的分数为:score(perm) = |perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + … + |perm[n - 1] - nums[perm[0]]|任务是找出一个排列 perm,使得...

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

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

score(perm) = |perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + … + |perm[n - 1] - nums[perm[0]]|

任务是找出一个排列 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

题目来自leetcode3149。

大体步骤如下:

1.计算分数的过程是根据给定的 perm 排列计算|perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + … + |perm[n - 1] - nums[perm[0]|,即每个 perm[i] 与对应 nums[perm[i]] 之间的绝对差的和。

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))
}

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。