腾讯音乐笔试 2023-04-13场

腾讯音乐笔试 2023-04-13场

只能说，难度倒排也算是一种潮流了？🤮

第一题

规定一个好数组：

• 数组中的元素只有0，1，2；
• 数组中任意两个相邻的数字都不相同；

定义一个数组的权值是相邻两个数字的绝对值之和。例如数组1, 3, 2, 4, 1，则有权值为：$W =

3-1

+

2-3

+

4-2

+

1-4

=8$

那么，求所有长度为$n$的的好数组的权值之和，结果取$10^9+7$的模。

• $1 \le n \le 10^9$

思路

我们应用一下递推的思想，因为不难发现，数组$n_{k+1}$是由数组$n_k$发展而来的，那么我们枚举一下数组$n_k$的末尾，肯定只有三个数字，他们各自对$n_{k+1}$有什么贡献呢：

每个数字的贡献之和是$8$，又由于好数组的定义，任意相邻的数字不相同，则当数组$n_k$的末尾为$0$，那么给数组$n_{k+1}$的贡献就是2个：$01$和$02$，前$k-1$的数组切片是张得一样的。那么不难得出如下结论：

\[\begin{aligned} n_{k+1} &= 2 n_k + 8 \times 2^{k-1} \end{aligned}\]

其中为什么是$2^{k-1}$呢，我们发现，当$n_1$时，共计三种：{0, 1, 2}，对于$n_2$的贡献分别是1次，则是$2^0$；到$n_2$时，共计六种：{01, 02, 10, 12, 20, 21}，那么对于$n_3$的贡献分别是2次，则是$2^1$。

接下来就是通过这个递推公式往下推了：

\[\begin{aligned} n_{k+1} &= 2 n_k + 8 \times 2^{k-1} \\ &= 2(2n_{k-1}+8 \times 2^{k-2}) + 8 \times 2^{k-1} &= 4 n_k + 2 \times 8 \times 2^{k-1} \\ &= 4(2n_{k-2}+8 \times 2^{k-3}) + 2 \times 8 \times 2^{k-1} &= 8 n_{k-1} + 3 \times 8 \times 2^{k-1} \\ &= \cdots &= 2^{k-1}n_2+(k-1) \times 8 \times 2^{k-1} \\ &= 2^{k-1} \times 8 = (k-1) \times 2^{k+2} &= k \times 2^{k+2} \\ \end{aligned}\]

所以有：

\[n_k = (k-1) \times 2^{k+1}\]

是不是很简单？但是本题其实还没有完结，我们再回头看一下$n$的范围，好家伙，绝对超了int64，那乘法我们还不能直接用，得做个小操作——二分求$2^{k+1}$，同时取模：(2**s) % (1e9+7) == (2**(s/2))**2 * 2**(s%2)。

至此，全体的坑才算全绕过了。

代码

func fun(n int) int {
	mod := int64(1e9 + 7)
	sum := int64(n-1) % mod
	k := int64(n + 1)
	var dfs func(i int64) int64
	dfs = func(i int64) int64 {
		if i == 0 {
			return 1
		}
		num := dfs(i / 2)
		num = (num * num) % mod
		if i%2 == 1 {
			num = (num * 2) % mod
		}
		return num
	}

	return int((sum * dfs(k)) % mod)
}

复杂度

• 时间复杂度：$O(\log n)$
• 空间复杂度：$O(\log n)$（递归栈）

第二题

给一棵二叉树，节点个数为$n$，节点上都有权值$w$，替换权值为：以该节点为根的子树的所有权值之积的末尾零的个数。

思路

又是零，自然想到$2 \times 5$，那么我们只要递归+回溯统计2和5的个数就行了，简单的DFS，没什么难度。

代码

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func valueOfTree(root *TreeNode) *TreeNode {
	var dfs func(node *TreeNode) (int, int)
	dfs = func(node *TreeNode) (two int, five int) {
		if node == nil {
			return 0, 0
		}

		two, five = count(node.Val)
		t, f := dfs(node.Left)
		two += t
		five += f
		t, f = dfs(node.Right)
		two += t
		five += f
		if two > five {
			node.Val = five
		} else {
			node.Val = two
		}

		return two, five
	}

	dfs(root)

	return root
}

func count(num int) (two, five int) {
	if num == 0 {
		return 0, 0
	}
	for num%2 == 0 {
		num /= 2
		two++
	}
	for num%5 == 0 {
		num /= 5
		five++
	}
	return two, five
}

复杂度

• 时间复杂度：$O(n \log w)$
• 空间复杂度：$O(n)$

第三题

构建一个大小为$\frac{n \times (n+1)}{2}$的数组，其中有1个1，2个2，……，n个n，但是相邻数字不相同。求其中一个数组（任意一个返回）。

思路

以$n=6$为例：654321_65432_6543_654_65_6，还看不出来？看代码吧。

代码

func fun(n int) []int {
	idx := 0
	ans := make([]int, (n*(n+1))/2)
	for i := 1; i <= n; i++ {
		for j := n; j >= i; j-- {
			ans[idx] = j
			idx++
		}
	}
	return ans
}

复杂度

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$