推特 OA 2019

indiroia 发表于 2018-8-14 02:40
我也是用 map
然後取substring時是根據map key 的字串長度由小到大去找
中間三個test case實在想不到是 ...

我想的是会不会key是10010和1001000000 你就只取了前者 没用后者这样的？

fer23333333 发表于 2018-8-14 02:56
我想的是会不会key是10010和1001000000 你就只取了前者 没用后者这样的？

可是根據題目敘述
In this encoding scheme, no code can be a prefix of another. For example, if the code for a is “01”, then the code for b cannot be “011”
所以10010跟1001000000不可能同時是key. 這不符合Huffman的定義

indiroia 发表于 2018-8-14 03:05
可是根據題目敘述
In this encoding scheme, no code can be a prefix of another. For example, if the ...

emmmm那我也不知道了，本来想用backtracking 看来也不是corner case 的原因

greedy 暴力解就可以过

tqzzj 发表于 2018-8-14 04:51
greedy 暴力解就可以过

您好 可以麻煩您再說清楚一些如何用 greedy 嗎？
因為我現在用 map 存 parse 過後的 codes，然後再讀 encoded string, 找到符合就存到 stringbuilder，最後輸出的方法
感覺就滿像暴力解的
但還是不清楚哪裡出了問題
謝謝

leebigyu 发表于 2018-8-14 07:20
您好 可以麻煩您再說清楚一些如何用 greedy 嗎？
因為我現在用 map 存 parse 過後的 codes，然後再讀 en ...

huffman编码就是说前缀不可能一样。如果a 为01，b不可能为011，所以就每次decode的时候后面的点+1，直到在map里有这个编码为止。

leebigyu 发表于 2018-8-14 07:20
您好 可以麻煩您再說清楚一些如何用 greedy 嗎？
因為我現在用 map 存 parse 過後的 codes，然後再讀 en ...

huffman编码就是说前缀不可能一样。如果a 为01，b不可能为011，所以就每次decode的时候后面的点+1，直到在map里有这个编码为止。

求解我的huffman和prime tree 后5个test都超时 = =

tqzzj 发表于 2018-8-14 11:23
huffman编码就是说前缀不可能一样。如果a 为01，b不可能为011，所以就每次decode的时候后面的点+1，直到 ...

我其實就是這樣解..但不知道為什麼 3~7 的 test case 過不了 T^T

leebigyu 发表于 2018-8-14 11:59
我其實就是這樣解..但不知道為什麼 3~7 的 test case 過不了 T^T

好吧，我这样写的思路是可以全过的。可能你是有的小地方没有注意吧。具体再查查吧