找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Google] 一道google onsite题目

[复制链接]

22

主题

8

精华

257

积分

高级会员

Rank: 3Rank: 3

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

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

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

x
给一个List<List<Character>>,打印出所有组合; M* C9 x: u- ~5 |" @3 W6 {. n
eg.
% P! l$ ]: f; a) D2 y4 Z{* k0 C. R" h* _7 E+ L! I: ]
    {a, b},2 y& M9 a0 ^- V  _# b2 I& C! O$ g
    {c, d, e},
$ x* K- v4 {9 `" ]- _# Z4 }4 |3 _6 R    {f, g}
) d' l4 U' n. G0 o5 \- Q- M}9 g4 \- Z. ^* P# Y9 o0 I
2 G5 F; m2 x- ?! Z! c# E
打印出来:5 u+ t# r$ {. r* [9 Y
{a, c, f}( R% s9 r5 d% W9 |
{a, c, g}
. _4 X+ p0 J3 F2 h, F{a, d, f}
" j3 u. d& v! F! x{a, d, g}
% T& i' l9 M2 l0 F  x2 ], E. G{a, e, f}3 i5 y9 |/ C) y* t6 d) U
{a, e, g}
1 N2 C/ k: ~8 e+ c{b, c, f}
' }9 {* n7 }8 H2 B1 q5 d0 y2 i......2 t: ]; i" j- j% o

' a& Y' a# `& c7 b2 y) z很容易想到的解法是
/ `% Q( d% x# m) F) ?0 v6 z先计算前两个list的组合{a, c} {a, d} {a, e} {b, c} {b, d} {b, e},得到结果再与第三个list计算,最后打印出来,但这样需要额外的空间保存中间结果,类似树的level traverse
* i$ N9 G* y. k. a; o; X怎么优化空间复杂度,不需要维护中间结果  H1 b5 v% ^5 `' A! v

: v& B$ }& R* |% O  t% t5 F* X$ N( b9 J6 W+ C& b- m

本帖被以下淘专辑推荐:

  • · 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就可以搞出来了啊。。。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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