win8 里面一输入中文 "我“ 字，程序就崩溃 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PDA - 掌中宝

win8 里面一输入中文 "我“ 字，程序就崩溃

win8 里面一输入中文 "我“ 字，程序就崩溃# PDA - 掌中宝

a*n2012-12-31 08:12

1 楼

倒在最后一个INTERVIEW。。对方MD，说话特快，好几次都要重复了我才听懂。。。问
了一算法题，没做好，跟大家请教一下，就是：把数学PI转成字符串，找第一个长度为
４的重复字符串，我的答案是，把每４个串做成HASH，存HASH MAP，然后找重复。然后
问复杂度，我说是O（N）。对方说不对，我只好说，如果重复的串在K个位置出现的话
，在第K个循环后能找到。ASSUME HASH 算法时间固定和插入、查找时间固定。。。结
果好象也不对。。。。

h*g2012-12-31 08:12

2 楼

已经下了Offer，准备找银行贷款。

x*y2012-12-31 08:12

3 楼

特别是qq, chrome 有时候也崩溃
咋整？

b*u2012-12-31 08:12

4 楼

pi转了字符串才给你么？无穷长？

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

: 倒在最后一个INTERVIEW。。对方MD，说话特快，好几次都要重复了我才听懂。。。问
: 了一算法题，没做好，跟大家请教一下，就是：把数学PI转成字符串，找第一个长度为
: ４的重复字符串，我的答案是，把每４个串做成HASH，存HASH MAP，然后找重复。然后
: 问复杂度，我说是O（N）。对方说不对，我只好说，如果重复的串在K个位置出现的话
: ，在第K个循环后能找到。ASSUME HASH 算法时间固定和插入、查找时间固定。。。结
: 果好象也不对。。。。

a*a2012-12-31 08:12

5 楼

我前年买房时在zillow上找到的在宾州的一个agent，去年跟他作了一次refi，这几天
又张罗着跟他做refi，感觉他给的quote都挺好，打交道的过程也挺顺利。你可以试试
。声明这不是广告贴，我压根没见到过这个人，都是email和电话往来，也没什么
referral fee的。
James Sanocki
Sales Manager
888.546.2814 x203
267.819.0578 Direct
215.689.4324 eFax
j******[email protected]
http://www.seckelcapital.com/

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

: 已经下了Offer，准备找银行贷款。

g*t2012-12-31 08:12

6 楼

那就输入“俺”呗。

b*u2012-12-31 08:12

7 楼

A是哪个银行？想了一圈没想到A开头的。。

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

: pi转了字符串才给你么？无穷长？

w*u2012-12-31 08:12

8 楼

作为一个高尚的纯粹的中文人，要放弃小我，把自己融入到社会主义大家庭里。

b*u2012-12-31 08:12

9 楼

我会弄个bitmap，四位digit有10k，用10k/32+1个unsigned int。每读一个digit把后
四位查下出现没。第几位出现就需要多少时间。

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

a*y2012-12-31 08:12

10 楼

你输入俄

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

: 特别是qq, chrome 有时候也崩溃
: 咋整？

l*a2012-12-31 08:12

11 楼

AE

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

: A是哪个银行？想了一圈没想到A开头的。。

Z*a2012-12-31 08:12

12 楼

洒家，贫僧，寡人，老子，老夫，鄙人，晚辈都可以代替

b*u2012-12-31 08:12

13 楼

ae不是银行，是payment tech firm..

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

: AE

w*u2012-12-31 08:12

14 楼

据说自称＂人家＂的比自称＂姐＂的要受欢迎。

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

: 洒家，贫僧，寡人，老子，老夫，鄙人，晚辈都可以代替

a*n2012-12-31 08:12

15 楼

A是AMAZON，上个星期ONSITE的。银行就是WALL ST那几个哪。。。
>每读一个digit把后
>四位查下出现没。第几位出现就需要多少时间。
我就是这么回答的啊，他说不对。。。。还特别问多少个循环后，我说K个循环啊。。
。。不知道PI是不是有特别的规律,,感觉不是算法不对，而是复杂度不对，，，所以想请教一下大家。。

c*h2012-12-31 08:12

16 楼

为嘛？

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

: 据说自称＂人家＂的比自称＂姐＂的要受欢迎。

r*92012-12-31 08:12

17 楼

是不是还得检查下重复的四位有没有和被重复的四位重合？
也就是:
a1-a2-a3-a4-a5-a6-a7
你发现a4-a5-a6-a7是重复的，还得保证a4-a5-a6-a7!=ai-a(i+1)-a(i+2)-a(i+3), for
i=1,2,3.

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

: 我会弄个bitmap，四位digit有10k，用10k/32+1个unsigned int。每读一个digit把后
: 四位查下出现没。第几位出现就需要多少时间。

L*i2012-12-31 08:12

18 楼

输入”偶“

i*e2012-12-31 08:12

19 楼

你思路应该没错，唯一能想到的一个优化就是如 biggu 所说的，用 bitmap 来储存当
hash使用，稍微节省空间一些，但复杂度基本不变。有可能是你说 O(n)，但是没解释
什么是 n 呢？这题你也不知道到何时才能找到重复那四个decimal？除非你能数学证明
出来。

w*u2012-12-31 08:12

20 楼

＂看姐不打断你的狗腿！＂
＂人家不要嘛＂

【在 c*****h 的大作中提到】

: 为嘛？

S*e2012-12-31 08:12

21 楼

是不是可以可以这样理解：10000个4位字符串中必有两个一样的，所以扫描10000个字
符之后一定有重复，复杂度是O(1)?

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

t*y2012-12-31 08:12

22 楼

“人家还想要”

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

: ＂看姐不打断你的狗腿！＂
: ＂人家不要嘛＂

i*e2012-12-31 08:12

23 楼

Ahh... you are right! Can't believe I missed it.
There's only maximum of 10000 possibilities for 4 digits.

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

: 是不是可以可以这样理解：10000个4位字符串中必有两个一样的，所以扫描10000个字
: 符之后一定有重复，复杂度是O(1)?

k*g2012-12-31 08:12

24 楼

弱人路过，木有看懂...
第一个长度为４的重复字符串是不是指：“0123412345” 这里面的1234?
那解法说的“每四个做一个hash”的话，上面就要做10个hash值？

b*u2012-12-31 08:12

25 楼

great point!

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

: 是不是可以可以这样理解：10000个4位字符串中必有两个一样的，所以扫描10000个字
: 符之后一定有重复，复杂度是O(1)?

b*u2012-12-31 08:12

26 楼

有个相关的问题是11111算不算两个1111？不算的话上面的算法要处理下边界条件。

m*a2012-12-31 08:12

27 楼

。。。别跟我说是抽屉原理

是不是可以可以这样理解：10000个4位字符串中必有两个一样的，所以扫描10000个字
符之后一定有重复，复杂度是O(1)?

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

: 是不是可以可以这样理解：10000个4位字符串中必有两个一样的，所以扫描10000个字
: 符之后一定有重复，复杂度是O(1)?

a*n2012-12-31 08:12

28 楼

面食完后，我也想到他是不是想问这个，可是他应该换一种问法。。SIGH，前面都过了
N论了，就倒在这儿。。。。

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

: 是不是可以可以这样理解：10000个4位字符串中必有两个一样的，所以扫描10000个字
: 符之后一定有重复，复杂度是O(1)?

a*n2012-12-31 08:12

29 楼

我解释了，说如果重复的数字出现在Kth位置，检查的次数为K。

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

: 你思路应该没错，唯一能想到的一个优化就是如 biggu 所说的，用 bitmap 来储存当
: hash使用，稍微节省空间一些，但复杂度基本不变。有可能是你说 O(n)，但是没解释
: 什么是 n 呢？这题你也不知道到何时才能找到重复那四个decimal？除非你能数学证明
: 出来。

h*w2012-12-31 08:12

30 楼

这道题的解法，我会用dictionary tree, 在遍历的时候同时建立tree, 最多有10*9*8*
7个4排列，可以到这个级别然后遍历，哪位大虾指点一下我的解法？

h*w2012-12-31 08:12

31 楼

还有就是用Hash了，4个一组，直接map到table, 原table为NULL, 每map一个table
increase one, till some collision happen, and then check the value same or
just the key value same, the time complex is O(n) to build up the table, but
the find time should be O(1)

t*d2012-12-31 08:12

32 楼

in this case, o(n) is not good enough. since Pi is infinite.

z*c2012-12-31 08:12

33 楼

这道题可能还要考察其实不需要每次读一个字符都算前四位。假设上个前四位放在int
n里。新的字符是a。这次就算（n%1000）*10+a-'0'。

a*n2012-12-31 08:12

34 楼

就是不知道到底啥是标准答案。。。。

y*o2012-12-31 08:12

35 楼

hashmap
所有四位数0000 to 9999做hash key，value是出现次数
然后遍历， if（occurrence）
++value
if（value>1)
break;
return key;

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

y*o2012-12-31 08:12

36 楼

这个好
就是搞个9999的数组，初始化都是-1
然后根据数字填数，
while(1){
i=index到index+3
if value[i]!=-1
return i
else
value[i]=index;
++index;
}

but

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

: 还有就是用Hash了，4个一组，直接map到table, 原table为NULL, 每map一个table
: increase one, till some collision happen, and then check the value same or
: just the key value same, the time complex is O(n) to build up the table, but
: the find time should be O(1)