找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

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

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

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

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

x
本帖最后由 Sophia 于 2-17-2016 04:53 PM 编辑 - _" G; k8 a9 K0 q& |  Z: W
5 ^/ `0 D. K, T9 ^% u; t) }
原帖子7 e; ?% O0 M9 L
, @& P  ^; i5 P# W) |
string只有可能有A、B、C三个字母组成,如果任何紧邻的三个字母各不相同,那就不是“valid string”。求长度为n的valid string有多少个
- ~' H) A/ l9 H: h" k- n- h8 L1 }比如: ABBBCA不是valid,ACCBCCA是valid
* A: h) b: J  q# W& N/ ~' x8 Z
# g: Y0 [$ Z3 v# C& w

2 E; ?: B' h+ S- s$ t8 H首先我觉得题目应该是紧邻三个字母不全相同吧………………: h. S* J5 b7 }5 O# \

) d' r5 n. M! g1 `/ ~
0 N7 P/ x5 w% u; V6 \3 J
dp【i】[0]表示长度为i的合法串,最后两个字符不相等的时候有多少种。
- i# z# S6 A1 k1 j  D8 O/ [0 w$ ]
( p9 z2 e" W5 [( K0 Q5 pdp【i】[1]表示长度为i的合法串,最后两个字符相同的时候有多少种。
$ j3 `7 I  G9 {& E9 r2 Z6 d
: `5 }( }6 X, e* ^) ^* `

  u" o8 x4 z# h4 [; pdp[1][0] = 3
9 `  n6 o8 o3 @4 C5 p% s( mdp[1][1] = 0, z9 K4 w6 p. y
, g, J5 T' v3 l: f; }
; D' p# `: j6 }
考虑下状态转换,根据最后两位的情况可以决定添加哪些字母合法,有:
3 K' v1 X) p$ C" [dp【i】[0] = (dp[i - 1][0] + dp[i - 1][1]) * 2
" d, @* h  B2 _2 fdp【i】[1] = dp[i -1][0]  7 D  w- s0 f. F

& \! D6 t: |5 E
9 Q2 e, S" p! z6 R" _" u
注意dp【i】[0,1]只与dp[i - 1][0,1]有关,于是直接递推,可以滚动数组,把空间复杂度降低为O(1),时间复杂度为O(n)。  l& s4 V, o0 A. T: H  w& V) U2 ~
: H& s) U, N# [1 h. W, U! t) b$ C

4 O3 h2 o- p4 m7 K有一个O(logn)时间的算法,和求斐波那契数一样:) O% J: y1 r! _  m. [; W$ b
0 N1 c% W- V  X/ r5 N3 B( s
/ l/ p+ T& f3 W( |
考虑2 * 2矩阵  
: Q3 G2 K7 `8 K$ i1 O4 [4 |  {8 u% n: @& D; c4 m' B/ P
( C" C2 c" p# u) h7 [' ?
2    1
( K$ i) v4 E0 k$ E7 [2    0
' n! x/ f6 D5 O  Z) R6 @
- i' O8 ?% K3 Z; b( q1 E
" {& X, F7 c) |  B) H! M1 V3 a
1 * 2 的的向量 (dp[i - 1][0], dp[i - 1][1]) 乘以上个矩阵,就会得到(dp【i】[0], dp【i】[1]),于是问题转化为求那个矩阵的(n - 1)次方,这个有经典的求幂算法——powermod,时间复杂度O(logn),空间复杂度O(1)。7 Y3 c  M, x6 I: C' g. H& j- B

9 ~" C# p/ b( D" \( M  g
- J+ ?4 o! V0 c. L. v, K8 k
最后结果 dp[n][0] + dp[n][1]
) ?3 K2 C0 ~) y- \! z3 |! L, I
$ w! m$ V9 i! U来源: 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!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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