V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
leolin
V2EX  ›  程序员

一道算法面试题

  •  
  •   leolin · 2020-01-27 15:00:41 +08:00 · 3433 次点击
    这是一个创建于 1523 天前的主题,其中的信息可能已经有所发展或是发生改变。

    编程:数值增殖,给一个数字比如 4,增殖一次成 1 2 3 4,再增殖一次就是按照每个数字,再拓展成 1 到 X 的数列( 1 1 2 1 2 3 1 2 3 4 ),然后问第 K 次形成的序列里第 P 位是多少?

    14 条回复    2020-01-28 06:20:24 +08:00
    ppyybb
        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
    LzyRapx
        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)
    firemiles
        3
    firemiles  
       2020-01-27 16:35:54 +08:00
    @ppyybb #1 这个可行,要是递推公式能求出通项公式就更好了
    LzyRapx
        4
    LzyRapx  
       2020-01-27 16:55:53 +08:00
    无聊写写,大概就是这样。

    https://paste.ubuntu.com/p/fN8FkhWkbJ/
    ssynhtn
        5
    ssynhtn  
       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 成立为止
    ssynhtn
        6
    ssynhtn  
       2020-01-27 17:35:24 +08:00
    ppyybb
        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 凑到这个组合数上面来就得到了结果。但是整个思路有点类似于靠猜想和凑的思路,不知道正解推导的思路是啥(硬算?)
    keith1126
        8
    keith1126  
       2020-01-27 18:29:15 +08:00
    @ppyybb #7

    目测可以用数学归纳法证明,不过结论还是靠观察猜出来的。
    ppyybb
        9
    ppyybb  
       2020-01-27 18:30:27 +08:00 via iPhone
    @keith1126 数学归纳法就更加靠猜测了,直接程度还不如我从杨辉三角联想到组合数的性质来推导,至少不太跳跃。
    LzyRapx
        10
    LzyRapx  
       2020-01-27 18:39:15 +08:00
    能不能在短时间内想出来,不是看面试官给的 P 的范围吗? P <= 10^9 和 P <= 10^18 完全可以是不一样的做法。
    ssynhtn
        11
    ssynhtn  
       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 的情况计算出公式后, 结合递推式, 熟悉组合数的性质的话也能直接就能看出长度公式
    ppyybb
        12
    ppyybb  
       2020-01-27 20:24:40 +08:00 via iPhone
    直观上的理解似乎是 a 个元素取 k 个数,但是这 k 个数又是可以重复的且存在全序关系,因此除了第一个数,再增加 k-1 个数,代表当每一个数需要选的和前一个数一样的那种可能?感觉不太严格,虽然结果肯定是对的
    charlie21
        13
    charlie21  
       2020-01-27 22:44:12 +08:00 via iPhone
    直接上数学归纳法搞出公式完事
    xiadong1994
        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])。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2929 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 14:06 · PVG 22:06 · LAX 07:06 · JFK 10:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.