这是一个创建于 1764 天前的主题，其中的信息可能已经有所发展或是发生改变。
编程：数值增殖，给一个数字比如 4，增殖一次成 1 2 3 4，再增殖一次就是按照每个数字，再拓展成 1 到 X 的数列（ 1 1 2 1 2 3 1 2 3 4 ），然后问第 K 次形成的序列里第 P 位是多少？
 |
1
ppyybb 2020-01-27 16:14:08 +08:00 via iPhone
我给一个思路吧，不知是否可行：
1. 分解问题，令 f （ x，k ）代表从数字 x 进行变换 k 次之后的数列长度，k 从 0 开始 2. f 的动态规划方程可以这样： f （ x，k ）= f （ 1，k - 1 ）+ f （ 2，k -1 ）+ ... f （ x - 1，k - 1 ） f （ x-1，k ）= f （ 1，k-1 ）+ ... f （ x-1，k-1 ） 所以有 f （ x，k ）= f （ x-1，k ）+ f （ x，k-1 ） 计算出来的复杂度是 O （ xk ），这是预处理的过程。 3. 假设需要查询位置 p，令 g （ x，k，p ）为题目所求，即变化后的数列的第 p 项，这个时候遍历 f （ 1，k-1 ），f （ 2，k-1 ）... f （ x，k-1 ）并维护当前数列的长度（也就是 sum ） 找到 p 所在的位置 t，假设前面长度为 sum，则问题可以直接规约到 g （ t，k-1，p - sum ） 这一步的时间复杂度是 O （ x ） 4. 不断递降可以将 k 降低到 1，一共需要 k 次，因此总复杂度是 O （ xk ） 5. 对于 k 为 1 的情况，结果是显然的。 6. 第三步的复杂度可以进一步降低，通过预处理求出 f 数列前缀和，那么可以进行二分查找找到第一个大于 p 的一项，降低为 logx |
 |
2
LzyRapx 2020-01-27 16:35:19 +08:00
用两个二分就可以了。
迭代 K 次可以看成形成 K 块，每块的长度为 i(1,2,3,4,5,....n), 因为前 i+1 块的和肯定是大于前 i 块的和的，也就是说是单调递增的，二分出是属于哪一块。最后在这一块里进行二分找出那一位数字就可以了。 简单就是：将找 112123123412345...的第 P 位转化为找 1234567891011...的第 P 位。 复杂度就是：O(logn * logn) |
|
4
LzyRapx 2020-01-27 16:55:53 +08:00
|
 |
5
kx5d62Jn1J9MjoXP 2020-01-27 17:33:04 +08:00
这题在面试的时候是几乎不可能当场想出来的...
一个数 a 在经过 K 次增殖后形成的数列长度为 C(a+K-1, K) // a+K-1 中选 K 个数 1: 对于输入 X, 如果 X == C(j+K-1, K), 那么结果就是 j 2: 否则 let X = X - C(j+K-1, K), let K = K-1, 继续递归直到 1 成立为止 |
|
6
kx5d62Jn1J9MjoXP 2020-01-27 17:35:24 +08:00
|
|
7
ppyybb 2020-01-27 18:27:32 +08:00 via iPhone
@ssynhtn 如果只做到我在一楼给出来的程度是完全可以的。
推了下这个公式，大概思路是联想到类似杨辉三角的性质，然后引入组合数的性质 c （ n，k ）= c （ n-1，k ）+ c （ n-1，k-1 ），类似于一楼 f 的递推公式，然后想办法把 n 和 i 凑到这个组合数上面来就得到了结果。但是整个思路有点类似于靠猜想和凑的思路，不知道正解推导的思路是啥（硬算？） |
|
9
ppyybb 2020-01-27 18:30:27 +08:00 via iPhone
@keith1126 数学归纳法就更加靠猜测了，直接程度还不如我从杨辉三角联想到组合数的性质来推导，至少不太跳跃。
|
|
10
LzyRapx 2020-01-27 18:39:15 +08:00
能不能在短时间内想出来，不是看面试官给的 P 的范围吗？ P <= 10^9 和 P <= 10^18 完全可以是不一样的做法。
|
|
11
kx5d62Jn1J9MjoXP 2020-01-27 19:15:36 +08:00
@ppyybb
实际上我是通过 f(a, k) = Sum(f(j, k-1), 1<=j<=a)连续套用 k 次 得到 k 个下标的求和式 f(a, k) = Sum(1, 1<=j_1<=j_2<=j_3...<=j_k<=a)然后得到的 如果是递推的话, 对 K 是 1,2,3 的情况计算出公式后, 结合递推式, 熟悉组合数的性质的话也能直接就能看出长度公式 |
|
12
ppyybb 2020-01-27 20:24:40 +08:00 via iPhone
直观上的理解似乎是 a 个元素取 k 个数，但是这 k 个数又是可以重复的且存在全序关系，因此除了第一个数，再增加 k-1 个数，代表当每一个数需要选的和前一个数一样的那种可能？感觉不太严格，虽然结果肯定是对的
|
 |
13
charlie21 2020-01-27 22:44:12 +08:00 via iPhone
直接上数学归纳法搞出公式完事
|
 |
14
xiadong1994 2020-01-28 06:20:24 +08:00
面试里这种 x 变换之后求 y 位一般就是两种办法，要么是有通项公式的纯数学问题，要么是动态规划 /递推。
这题写几个例子就很容易想到第 k 层的长度是第 k-1 层元素的和，那么就可以用前缀和算出第 k 层的 p 位是第 k-1 层的哪一位（假设为 p_{k-1})扩展而来并且可知是 p_{k-1}扩展后的第几位。接下来问题就是第 k-1 层的第 p_{k-1}位是什么，以此类推。 而求每一层的分块长度就是基本的二维 DP，第 k 层的元素可以分成第 1 层（第一次增殖后）中元素（ 1,2,3...n ）分别增殖 k-1 次而来，因此 k 层 i 块长度就是 sum(dp[k-1][0], dp[k-1][1],...,dp[k-1][i])，因为是前缀和所以可以简化为 sum(dp[k-1][i], dp[k][i-1])。 |
Select Language