找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4659|回复: 4
收起左侧

[精选面经题目] G家老题 Valid String 回答

  [复制链接]
发表于 2-17-2016 11:17 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 2-17-2016 04:53 PM 编辑 % ?9 C  }' g6 M2 `" T- L
. T. \' U% |. ?0 g1 X$ E, ^
原帖子. O% s6 A% _9 g, S( V6 l" B

) A0 A9 v0 ^1 m; l1 |. _string只有可能有A、B、C三个字母组成,如果任何紧邻的三个字母各不相同,那就不是“valid string”。求长度为n的valid string有多少个
# g( }" T) l' Q. U2 E; B比如: ABBBCA不是valid,ACCBCCA是valid
/ z- _) k* z, U6 W# P; A8 o/ q- ~7 k# \" \1 `4 c1 v8 d* v7 p

1 R1 @( a! W# O# U首先我觉得题目应该是紧邻三个字母不全相同吧………………; l$ g0 `: ~2 n5 A  \
4 H) f5 R3 P, S4 k8 M' g* C1 G
8 t- q5 X! O" P
dp【i】[0]表示长度为i的合法串,最后两个字符不相等的时候有多少种。
' {! ]: ?- j0 P7 h& O" s, T7 i  \* W) F0 X
dp【i】[1]表示长度为i的合法串,最后两个字符相同的时候有多少种。
0 f7 J) Q7 P9 V
  z- m9 Q" k1 t$ [+ |$ m

2 z# R* f' q3 B4 x/ a0 }dp[1][0] = 3
- _) C6 a) u* q# B" x: D3 pdp[1][1] = 0! y9 @- }) t6 e6 k8 z

( M7 x6 R  l9 b9 y; J) U7 b
9 @- X/ n( [- p
考虑下状态转换,根据最后两位的情况可以决定添加哪些字母合法,有:5 @) s# {& l! p3 {; B: F4 n% J
dp【i】[0] = (dp[i - 1][0] + dp[i - 1][1]) * 2
; L: ^7 t2 r9 G  O1 l, s4 J. Ldp【i】[1] = dp[i -1][0]  
2 A8 t, G" r3 e6 X$ V3 v7 g  P; ]  H1 J' P
" \: g: F4 q$ ^, `- z* u: P. ^
注意dp【i】[0,1]只与dp[i - 1][0,1]有关,于是直接递推,可以滚动数组,把空间复杂度降低为O(1),时间复杂度为O(n)。
0 D/ E, _" r; n+ d# j+ X2 u) v) |- P! ~: }. M0 @9 o% f% p9 v

5 f$ V/ k, }/ [; l有一个O(logn)时间的算法,和求斐波那契数一样:* h$ E% b# E6 X" }
" S2 V( e( w8 B, m+ ]1 K

. r5 _6 D' r( [' Z+ x考虑2 * 2矩阵  
' }, @* Z& I) L/ C1 `; v7 z: ]$ |' B
6 |/ X* i# n- [9 D0 s
2    1
* }- I* C0 g3 M2    03 n' t) V+ Y0 V1 f/ k" ]" T) Y

" m9 k: k8 X" T$ {4 I# X
) g! V+ a' G) I$ I6 X* |' m
1 * 2 的的向量 (dp[i - 1][0], dp[i - 1][1]) 乘以上个矩阵,就会得到(dp【i】[0], dp【i】[1]),于是问题转化为求那个矩阵的(n - 1)次方,这个有经典的求幂算法——powermod,时间复杂度O(logn),空间复杂度O(1)。
" Y- K' a2 W' {; }7 J# y/ u$ C  m, T# F; D. w

8 O0 l' @0 e( l) S8 ~) p" c. m最后结果 dp[n][0] + dp[n][1]* |+ U8 q! \5 y1 z! l8 W

7 r6 A* v/ I; {" s来源: G家老题 Valid String 回答

本帖被以下淘专辑推荐:

  • · Google|主题: 3, 订阅: 0
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

13

主题

4

精华

477

积分

高级会员

Rank: 3Rank: 3

积分
477
发表于 2-17-2016 12:51 PM | 显示全部楼层
赞,受益匪浅!之前知道DP,但是不知道转化成矩阵相乘和powermod。

3

主题

0

精华

82

积分

资深会员

Rank: 2

积分
82
发表于 5-4-2016 02:05 AM | 显示全部楼层
It's a good problem!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表