妞妞一周没上站了！ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>bagua - 娱乐八卦

妞妞一周没上站了！

妞妞一周没上站了！# bagua - 娱乐八卦

b*r2013-08-23 07:08

1 楼

print words from a boggle:
Given an NxN matrix, and a dictionary, print a list of all words that
appear in the matrix. You can not use the same letter twice. For example,
if the matrix were:
W A
D R
You could find the words: WAR, WARD, DRAW and RAW （一个字符只能用一次）
没想出好的方法，大牛们？

d*g2013-08-23 07:08

2 楼

怎么准备老婆的身份资料，以备签证官问到?
老婆的OPT身份7月底过期，grace period到9月底。
现在想要将老婆transfer成一个技术学校的F1，或者是转成F2.
9月底之前办都可以，现在还没确定。因为在带小宝。
需要出示老婆的申请OPT时的I-20表，还是必须去办一下转F1或F2的手续，然后出示转
的手续的证明。
谢谢各位！

w*i2013-08-23 07:08

3 楼

k*e2013-08-23 07:08

4 楼

need more clear definitions of the shifting operation

【在 b****r 的大作中提到】

: print words from a boggle:
: Given an NxN matrix, and a dictionary, print a list of all words that
: appear in the matrix. You can not use the same letter twice. For example,
: if the matrix were:
: W A
: D R
: You could find the words: WAR, WARD, DRAW and RAW （一个字符只能用一次）
: 没想出好的方法，大牛们？

d*g2013-08-23 07:08

5 楼

顶一下,有人有经验或者听说过类似案例吗?
谢谢!

【在 d**g 的大作中提到】

: 怎么准备老婆的身份资料，以备签证官问到?
: 老婆的OPT身份7月底过期，grace period到9月底。
: 现在想要将老婆transfer成一个技术学校的F1，或者是转成F2.
: 9月底之前办都可以，现在还没确定。因为在带小宝。
: 需要出示老婆的申请OPT时的I-20表，还是必须去办一下转F1或F2的手续，然后出示转
: 的手续的证明。
: 谢谢各位！

w*n2013-08-23 07:08

6 楼

每天忙的很，恩。乐不思蜀

m*f2013-08-23 07:08

7 楼

所谓shift就是上下左右移动把

【在 k***e 的大作中提到】

: need more clear definitions of the shifting operation

s*22013-08-23 07:08

8 楼

你申请你父母过来旅游，邀请信上不提你老婆，当然不需要你老婆的任何材料。

b*a2013-08-23 07:08

9 楼

小姨昨天回来了，在扭腰转机。
其他的你们懂的

【在 w****n 的大作中提到】

: 每天忙的很，恩。乐不思蜀

m*f2013-08-23 07:08

10 楼

我觉得这题要递归, 给定Matrix M 出发点(i,j), 假设搜索长度为n的单词,
int findString(int i, int j, int n, string s) {
if (0==n) check s 是不是在字典里, return 1/0;
int total = 0;
for ( M(i,j) 所有neighbour) {
if (neighbour不在s中) total+= findstring(i',j', n-1, s');
}
return total;
}
然后循环所有(i,j,n)....麻烦的是好像不能用DP, n^2个出发点每个最多词长都是n^2......汗..
可能的优化就是在字典里做些处理, 列出每个单位词长的可能出发字母...

E*e2013-08-23 07:08

11 楼

问道你老婆的可能性很小，小于10%,但是也不能排除。遇到比较严格的签证官，会问你
是否结婚，是否有小孩。还是准备一下老婆的情况为好。
先申请转身份吧。目前快过期的I-20也带着。签证的时候不问不主动提到。问到则解释。

A*u2013-08-23 07:08

12 楼

你也消失了很久
我们都懂

小姨昨天回来了，在扭腰转机。
其他的你们懂的

【在 b*a 的大作中提到】

: 小姨昨天回来了，在扭腰转机。
: 其他的你们懂的

t*e2013-08-23 07:08

13 楼

just as 迷宫travel. BFS, DFS all could do.

d*i2013-08-23 07:08

14 楼

他是在挖沙子赎身

【在 A*********u 的大作中提到】

: 你也消失了很久
: 我们都懂
:
: 小姨昨天回来了，在扭腰转机。
: 其他的你们懂的

b*r2013-08-23 07:08

15 楼

恩改了原帖把shift去掉，就讨论给定的一个NxN的matrix
一个词里的字母在matrix里必须是neighbor(横竖斜均可），每个字母用一次

【在 k***e 的大作中提到】

: need more clear definitions of the shifting operation

b*a2013-08-23 07:08

16 楼

赞助叔叔点吧

【在 d******i 的大作中提到】

: 他是在挖沙子赎身

b*r2013-08-23 07:08

17 楼

先把shift条件去掉了，就在一个fixed的矩阵里找
word的长度没限制最大就是NxN

【在 m*****f 的大作中提到】

: 我觉得这题要递归, 给定Matrix M 出发点(i,j), 假设搜索长度为n的单词,
: int findString(int i, int j, int n, string s) {
: if (0==n) check s 是不是在字典里, return 1/0;
: int total = 0;
: for ( M(i,j) 所有neighbour) {
: if (neighbour不在s中) total+= findstring(i',j', n-1, s');
: }
: return total;
: }
: 然后循环所有(i,j,n)....麻烦的是好像不能用DP, n^2个出发点每个最多词长都是n^2......汗..

w*i2013-08-23 07:08

18 楼

你回国一趟变年轻了哈，瓜伯成瓜叔了

【在 b*a 的大作中提到】

: 赞助叔叔点吧

m*f2013-08-23 07:08

19 楼

没限制word长度阿, 直接循环1到nxn

【在 b****r 的大作中提到】

: 先把shift条件去掉了，就在一个fixed的矩阵里找
: word的长度没限制最大就是NxN

w*n2013-08-23 07:08

20 楼

几个包子还是没问题的

【在 b*a 的大作中提到】

: 赞助叔叔点吧

b*r2013-08-23 07:08

21 楼

是不是循环没什么trick了，优化也就是从每个点走出去 check这个path 如果不是prefix in
dictionary 就马上跳过? 这个recursive function怎么写好呢

【在 m*****f 的大作中提到】

: 没限制word长度阿, 直接循环1到nxn

w*n2013-08-23 07:08

22 楼

挖沙子强身健体

【在 w***i 的大作中提到】

: 你回国一趟变年轻了哈，瓜伯成瓜叔了

m*f2013-08-23 07:08

23 楼

prefix可以把, 也可以建一个trie, 每个节点纪录可能成词的剩下长度, 其实都是
pruning...

【在 b****r 的大作中提到】

: 是不是循环没什么trick了，优化也就是从每个点走出去 check这个path 如果不是prefix in
: dictionary 就马上跳过? 这个recursive function怎么写好呢

H*M2013-08-23 07:08

24 楼

这题除了backtrack prune之外还有啥好法子啊？
prune还得看字典的数据结构。如果是trie还好，hashtable的话，prune都没发prune吧？

【在 b****r 的大作中提到】

b*r2013-08-23 07:08

25 楼

我说assume 字典是trie, 并且提供containPrefix() interviewer说好你先写循环再
讨论字
典不晓得这个recursion还有什么trick

吧？

【在 H*M 的大作中提到】

: 这题除了backtrack prune之外还有啥好法子啊？
: prune还得看字典的数据结构。如果是trie还好，hashtable的话，prune都没发prune吧？

m*f2013-08-23 07:08

26 楼

oh, 那interviewer有说什么是标准答案么, 你的循环做得怎么样?

【在 b****r 的大作中提到】

: 我说assume 字典是trie, 并且提供containPrefix() interviewer说好你先写循环再
: 讨论字
: 典不晓得这个recursion还有什么trick
:
: 吧？

b*r2013-08-23 07:08

27 楼

我记得我就是从(i,j)出发，走一步mark一下避免重复，有prefix就继续，没有就切换
的下一个
neighbor. 然后所有点都这么走一边。写完了他没说啥，就说这是个经典问题（晕）
当时有点紧张，
不知道他到底想要什么答案。所以想问问高手这个递归怎么写漂亮..

【在 m*****f 的大作中提到】

: oh, 那interviewer有说什么是标准答案么, 你的循环做得怎么样?

g*y2013-08-23 07:08

28 楼

呵呵，这个是经典问题啊。。。以前怎么没见到过呢。。。
递归的话不难写，不要忘记一些undo的操作就好了(比如unmark，指向trie的某node的指针往上回走一层)
不过我还是觉得，自己建一个trie比较方便

【在 b****r 的大作中提到】

: 我记得我就是从(i,j)出发，走一步mark一下避免重复，有prefix就继续，没有就切换
: 的下一个
: neighbor. 然后所有点都这么走一边。写完了他没说啥，就说这是个经典问题（晕）
: 当时有点紧张，
: 不知道他到底想要什么答案。所以想问问高手这个递归怎么写漂亮..

m*f2013-08-23 07:08

29 楼

hmm..你这么一说我觉得我给定词长是多余的, 每步都测一下便是, 真是土阿...

【在 b****r 的大作中提到】

H*M2013-08-23 07:08

30 楼

觉得这题跟permutation很像呵呵，我是说程序体

的指针往上回走一层)

【在 g*******y 的大作中提到】

: 呵呵，这个是经典问题啊。。。以前怎么没见到过呢。。。
: 递归的话不难写，不要忘记一些undo的操作就好了(比如unmark，指向trie的某node的指针往上回走一层)
: 不过我还是觉得，自己建一个trie比较方便

b*r2013-08-23 07:08

31 楼

没错感觉mark/unmark这里容易出错
我说assume containPrefix改一改返回3个值
0=No;
1=Yes, but not a word;
2=Yes, is also a word;
我写的是visit每一个neighbor时都call一下containPrefix()返回true的话就mark再往
下走
写着写着就比较晕呵呵大牛能不能给个code参考下.
另：自己建trie怎么讲呢？

的指针往上回
走一层)

【在 g*******y 的大作中提到】

z*e2013-08-23 07:08

32 楼

我很想问一句：30分钟内，你们确定有足够时间把trie/whatever都实现了？

b*r2013-08-23 07:08

33 楼

trie什么的都写不现实吧，我就假设字典支持noFound, isPrefix(), isWordandPrefix
()
主要时间就是写递归都不太够。。

【在 z***e 的大作中提到】

: 我很想问一句：30分钟内，你们确定有足够时间把trie/whatever都实现了？