g***j
发帖数: 1275 | 1 不知道为什么不能copy文字过来，所有空格都无法copy，所以只能给一个link了
http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Int
这上面的最后一题的Better solution是什么意思？ 没有看明白，哪个大虾给小弟解释
一下？ | b*******S
发帖数: 17 | 2 題目問
有一個 ransom string,還有一個magazine string
然後要求是不是能從magazine string裡面湊出ransom string裡面要用的所有
characters,而且從magazine string找出的character只能在ransom string裡用一次
比如說ransom string="hello"
magazine string="heeollo"
這樣就應該傳回true
第一解是說在兩個string都去算character counts, 如果對每個字母,magazine string
的character count比ransom string的character counter都高 那就是true
以上為例 ransom string的o有1個, magazine string的o有兩個 所以true
第二解是說 若magazine string超長 那我們是不是可以先把ransom string的char
counts算出來 然後在慢慢掃過magazine string. 遇到一個character就把他對映在
ransom string的char count減一
以剛剛的例子, hello會產生出以下的char counts
h-->1
e-->1
l-->2
o-->1
然後呢, 在掃magazine string,先遇到h,就把h的countr減一 變
h-->0
e-->1
l-->2
o-->1
再遇到e,再把e的counter減一,變
h-->0
e-->0
l-->2
o-->1
再遇到e,因為counter已經是0了 就不變了
用這樣的方法 就可以不用traverse所有的magazine string.所以會比第一解要好 | l****c
发帖数: 782 | 3 解释的真清楚啊，赞啊
string
【在 b*******S 的大作中提到】
: 題目問
: 有一個 ransom string,還有一個magazine string
: 然後要求是不是能從magazine string裡面湊出ransom string裡面要用的所有
: characters,而且從magazine string找出的character只能在ransom string裡用一次
: 比如說ransom string="hello"
: magazine string="heeollo"
: 這樣就應該傳回true
: 第一解是說在兩個string都去算character counts, 如果對每個字母,magazine string
: 的character count比ransom string的character counter都高 那就是true
: 以上為例 ransom string的o有1個, magazine string的o有兩個 所以true
|
|
