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

今天的一道面试题没能写出来,求思路。

  •  1
     
  •   letianqiu · 2019-05-17 17:02:44 +08:00 · 4417 次点击
    这是一个创建于 2001 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Screenshot from 2019-05-17 18-50-10.png 第一感觉是 DP,但是深入思考之后发现前 K 列可能并不符合同行和同列的颜色不完全相同,但是加上一列可以使得整个 K+1 列变成符合要求的 pattern。这种情况下,简单的 DP 的状态是无法表示这种情况的。想了几种状态的表示,比如分成前 k 列有 j 行是颜色完全相同的,但是感觉都不太正确。不知道这题应该从哪个方面入手。

    28 条回复    2019-05-20 12:11:25 +08:00
    zycpp
        1
    zycpp  
       2019-05-17 17:04:35 +08:00 via iPhone   ❤️ 1
    机试还是面试
    wfgu
        2
    wfgu  
       2019-05-17 17:14:45 +08:00 via Android   ❤️ 1
    写状态转移矩阵,然后矩阵幂吧。感觉
    HuHui
        3
    HuHui  
       2019-05-17 17:18:58 +08:00
    阿里?
    wutiantong
        4
    wutiantong  
       2019-05-17 17:20:22 +08:00
    174 这个结果能快速求出么?
    letianqiu
        5
    letianqiu  
    OP
       2019-05-17 17:28:13 +08:00
    @wutiantong 174 感觉上是作为 base case 的。
    @HuHui 不是
    @zycpp 机试
    wutiantong
        6
    wutiantong  
       2019-05-17 17:33:00 +08:00
    @letianqiu 所以你觉得 174 这个数字是怎么来的呢?是直接数出来的,还是有办法推算出来?
    rrfeng
        7
    rrfeng  
       2019-05-17 17:38:24 +08:00
    我好奇这种题来个数学家直接写公式(假如有通项公式的话)能算过吗?
    wutiantong
        8
    wutiantong  
       2019-05-17 17:40:19 +08:00
    @rrfeng 只要正确,当然算过了,而且很 nice 啊
    lance6716
        9
    lance6716  
       2019-05-17 17:42:26 +08:00 via Android
    记录最近三行的状态就行了啊
    LucKkK
        10
    LucKkK  
       2019-05-17 17:45:23 +08:00
    是我膨胀了 居然还敢看一下题目
    wutiantong
        11
    wutiantong  
       2019-05-17 17:56:36 +08:00
    174 = 6*6*6 - ( 2*3*8 - 6 )
    Justin13
        12
    Justin13  
       2019-05-17 18:06:33 +08:00 via Android
    感觉是排列组合的问题
    linhua
        13
    linhua  
       2019-05-17 18:08:51 +08:00
    2 个不同的 总共有 A(3,2) = 6 个

    不考虑第二点 : 列可以重复总共有 6*6*6
    只有一列重复: 总共有 6*2*2
    两列都重复:总共有 6

    所有总共有 6*6*6 - 6*2*2 *2(减两次,减多了,再加上后面的 6 ) + 6
    clatisus
        14
    clatisus  
       2019-05-17 18:10:17 +08:00 via iPhone   ❤️ 1
    dp[i][j][k] (i,j,k\in {0,1,2,3})。每一行记录四种状态:全红、全蓝、全绿、已经至少有两种颜色。

    转移的时候枚举这一列的颜色,有 24 种(去掉全色)。

    这道题 n 不大,直接转移的话复杂度是 O(4^3*24*n)。矩阵乘法优化的话就是 O((4^3)^3*log n)。
    clatisus
        15
    clatisus  
       2019-05-17 18:14:20 +08:00 via iPhone
    @HuHui 阿里笔试界面…一言难尽的丑 而且还有摄像头验证保证你没有办法低头打草稿
    wutiantong
        16
    wutiantong  
       2019-05-17 18:21:06 +08:00
    if n > 2; f3(n) = f3(n-1) *24 + f2(n-1) * 3 * 3 * 16 + t1(n-1) * 3 * 3 * 10 + s1(n-1) * 3 * 6 * 11 + 174
    f3(2) = 174

    if n > 2; f2(n) = f2(n-1) * 8 + t1(n-1) * 6 + s1(n-1) * 2 * 5 + 28
    f2(2) = 28

    if n >=2; t1(n) = 2^n - 2
    if n >= 2; s1(n) = 3^n - 3
    wutiantong
        17
    wutiantong  
       2019-05-17 18:24:26 +08:00   ❤️ 1
    能看懂我写的这些递归式的同学 排列组合一定学得不错。
    clatisus
        18
    clatisus  
       2019-05-17 18:26:53 +08:00 via iPhone
    好像还有个更快的做法:

    你对行进行容斥,枚举有几行满足行是同色的,然后就只需要对每一列选一个颜色使得列不同色。这里的列是独立的,计算一列的答案之后快速幂 O(log n) 就可以。

    所以复杂度是 O(mlog n),这里 m=3,因为容斥只需要知道有多少行同色,乘上组合数就行,不用枚举 2^m。
    geelaw
        19
    geelaw  
       2019-05-17 18:37:49 +08:00 via iPhone   ❤️ 1
    进行如下计算:
    满足第二个条件的
    满足第二个条件且第一行全同
    满足第二个条件且前两行分别全同
    满足第二个条件且前三行分别全同

    然后用容斥原理算出需要的答案。

    也可以用动态规划来做,用 f(0/1/2/3,0/1/2/3,0/1/2/3,k) 表示如下状态的染色方法数:
    前三个参数表示第一二三行是否已经有两个颜色,是则是 0,否则不是 0 且等于全同的颜色;
    第三个参数表示一共有多少列。

    初始状态是 f(x,y,z,1)=0 若 xyz=0,否则等于 1。
    状态转移方程写起来比较麻烦,略去。
    wpzero
        20
    wpzero  
       2019-05-18 07:28:57 +08:00 via iPhone
    n 等于 2 174 n 等于 3 156
    cjh1095358798
        21
    cjh1095358798  
       2019-05-18 08:26:09 +08:00
    完蛋,不会
    ZeroW
        22
    ZeroW  
       2019-05-18 15:25:44 +08:00 via Android
    高中排列组合问题・_・?还是比较难的那种
    letianqiu
        23
    letianqiu  
    OP
       2019-05-19 15:44:15 +08:00
    @wpzero 你的答案是不正确的
    @wutiantong 你的递归结果是错误的。
    @geelaw 我不是很明白你这么分组的正确性,比如一行完全相同颜色,这行不一定出现在第一行。我稍微修改了一下你的定义。对于有一行颜色全同的,我分成满足第二个条件且第一行颜色都是 R,满足第二个条件且第一行颜色都是 G,满足第二个条件且第一行都是 B,满足第二个条件且第二行都是 R,。。。一共 9 个集合,然后应用容斥原理,就可以算出答案。
    geelaw
        24
    geelaw  
       2019-05-19 18:12:45 +08:00
    @letianqiu #23 各行之间是对称的,答案是 A-3B+3C-D。在计算 B 的时候已经考虑了第一行可以以三种方式全同,在计算 C 的时候已经考虑了前两行可以以 9 种方式分别全同(实际计算需要拆开成 3+6 ),等等。
    letianqiu
        25
    letianqiu  
    OP
       2019-05-19 19:16:49 +08:00
    @geelaw 懂了,我实际上就是把所有的可能具体列出来,你则是把对称的归到一起了。
    wutiantong
        26
    wutiantong  
       2019-05-20 09:55:12 +08:00
    @letianqiu 因为我 f2()的式子少算了两个系数 2,应该是 f2(n) = f2(n-1) * 8 + t1(n-1) * 2 * 6 + s1(n-1) * 2 * 2 * 5 + 28
    我这次验算过了,结果没问题。
    wutiantong
        27
    wutiantong  
       2019-05-20 11:37:36 +08:00
    还可以给出另一个递推关系:

    p3(2) = 24*23 - 9*8*7 + (18*6+9*2) = 174
    p3(3) = 24*23*22 - 9*8*7*6 + 18*6 = 9228
    p3(4) = 24*23*22*21 - 9*8*7*6*5
    ...
    p3(n) = 24!/(24-n)! - 9!/(8-n)!
    ...
    p3(8) = 24!/16! - 9!
    p3(9) = 24!/15!
    ...
    p3(24) = 24!
    p3(25) = 0
    ...

    结果为:
    f3(n) = p3(n) + p3(n-1) * G(n, n-1) + p3(n-2) * G(n, n-2) + ... + p3(2) * G(n, 2)

    其中:
    G(n, i) = G(n-1, i) * i + G(n-1, i-1)
    G(n, n) = 1
    G(n, 1) = 1
    wutiantong
        28
    wutiantong  
       2019-05-20 12:11:25 +08:00 via iPhone
    @geelaw 结果还是你的解法最简洁直接啊
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3382 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 77ms · UTC 00:40 · PVG 08:40 · LAX 16:40 · JFK 19:40
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.