找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Google] 一道google onsite题目

[复制链接]

22

主题

8

精华

257

积分

高级会员

Rank: 3Rank: 3

积分
257
发表于 4-10-2015 01:42 AM | 显示全部楼层 |阅读模式

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

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

x
给一个List<List<Character>>,打印出所有组合  M9 l4 n* I7 U
eg.
% ]- ?4 n3 ]# H$ I; }( [( }{
0 X+ ]% S7 N5 p7 I    {a, b},
( J0 Q. o% I, ]$ F9 F    {c, d, e},; S6 R( g" G- c, g& E
    {f, g}& H6 E6 P- U, \" {3 L
}
6 {- G+ `! k4 K# h" H  k* B3 t
* g$ E" Q% ^- j( d打印出来:! `- S$ B6 h0 \8 W
{a, c, f}
- d" G6 ^0 B) |8 A/ n{a, c, g}
* `+ O& h! o! z" a{a, d, f}: E( a1 z- _. H7 M
{a, d, g}; i( {+ E& B/ n5 V0 G2 O" s
{a, e, f}/ s! y! {) `7 `  a3 ]2 j
{a, e, g}% ]# H8 V( ~& n/ n3 {$ _
{b, c, f}
* x. W6 o. |9 m  s......
# a$ d4 f' `3 C5 |7 u& ?, Q" `& \  S8 l+ R
很容易想到的解法是
/ g8 q9 R4 s7 a6 n$ v) D1 ]2 f& ^先计算前两个list的组合{a, c} {a, d} {a, e} {b, c} {b, d} {b, e},得到结果再与第三个list计算,最后打印出来,但这样需要额外的空间保存中间结果,类似树的level traverse1 T& n* j6 f, }. I/ y
怎么优化空间复杂度,不需要维护中间结果
- @5 O% O4 D  d* R' t
  C" M0 b' F/ x; M/ }" D* O; ~& j6 J4 p

本帖被以下淘专辑推荐:

  • · Google|主题: 53, 订阅: 25

0

主题

0

精华

66

积分

资深会员

Rank: 2

积分
66
发表于 4-10-2015 12:46 PM | 显示全部楼层
lc原题,letter combinations of a phone number.
发表于 4-10-2015 01:52 AM | 显示全部楼层
不可能不需要吧。。。dfs

34

主题

28

精华

900

积分

超级会员

Rank: 4

积分
900

最佳新人热心会员

发表于 4-10-2015 03:09 AM | 显示全部楼层
直接一个dfs就可以搞出来了啊。。。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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