华为笔试第二题哈夫曼树

华为笔试第二题，求大佬告知错在哪里........

                     1       
        2       
        3       
        4       
        5       
        6       
        7       
        8       
        9       
        10       
        11       
        12       
        13       
        14       
        15       
        16       
        17       
        18       
        19       
        20       
        21       
        22       
        23       
        24       
        25       
        26       
        27       
        28       
        29       
        30       
        31       
        32       
        33       
        34       
        35       
        36       
        37       
        38       
        39       
        40       
        41       
        42       
        43       
        44       
        45       
        46       
        47       
        48       
        49       
        50       
        51       
        52       
        53       
        54       
               list2=[]        
         list3=[]        
         classNode(object):        
         def__init__(self,name=None,value=None):        
         self._name=name        
         self._value = value        
         self._left=None        
         self._right = None        
         classHuffmanTree(object):        
         def __init__(self, char_weights):        
         self.a=[Node(part[0],part[1])forpart in char_weights]        
         whilelen(self.a)!=1:        
         self.a.sort(key=lambda node:node._value,reverse=True)        
         c=Node(value=(self.a[-1]._value+self.a[-2]._value))        
         c._left=self.a.pop(-1)        
         c._right=self.a.pop(-1)        
         self.a.append(c)        
         self.root=self.a[0]        
         self.b=range(10)        
         def pre(self,tree,length):        
         node=tree        
         if(not node):        
         return        
         elif node._name:        
         list1=''        
         fori in range(length):        
         list1+=str(self.b[i])        
         list2.append(node._name)        
         list3.append(list1)        
         return        
         self.b[length]=0        
         self.pre(node._left,length+1)        
         self.b[length]=1        
         self.pre(node._right,length+1)        
         def get_code(self):        
         self.pre(self.root,0)        
         if__name__=='__main__':        
         dic=[]        
         i = raw_input()        
         forj in set(i):        
         dic.append((j,i.count(j)))        
         char_weights=dic        
         tree = HuffmanTree(char_weights)        
         tree.get_code()        
         r=''        
         forl in i:        
         form in range(len(list2)):        
         ifl==list2[m]:        
         r+=str(list3[m])        
         print r        
        
        
        
         # # abbcccdddd #1101111111010100000       测试用例 为什么和我的不一样，求大佬告知！        
     
     

#华为#

全部评论

推荐最新楼层

昨日的梦

吉林大学 C++

#include<iostream> #include<map> #include<string> #include<set> using namespace std; int main() { string s; getline(cin, s); map<char, int> count; for (int i = 0;i < s.size();i++) { if (count.find(s[i]) != count.end()) { count[s[i]]++; } else count.insert(pair<char, int>(s[i], 1)); } map<int, set<string>> quanzhi; for (map<char, int>::iterator it = count.begin();it != count.end();it++) { string temp = ""; if (quanzhi.find((*it).second) != quanzhi.end()) { quanzhi[(*it).second].insert(temp + (*it).first); } else { set<string> temp1; temp1.insert(temp + (*it).first); quanzhi.insert(pair<int, set<string>>((*it).second, temp1 )); } } map<char,string> ans; while (quanzhi.size() > 1) { string temp = ""; int a1, a2; string s1, s2; map<int, set<string>>::iterator it = quanzhi.begin(); a1 =(*it).first; if ((*it).second.size() > 1) { s1 = *(*it).second.begin(); (*it).second.erase((*it).second.begin()); a2= (*it).first; s2= *(*it).second.begin(); (*it).second.erase((*it).second.begin()); } else { s1 = *(*it).second.begin(); (*it).second.erase((*it).second.begin()); it++; a2 = (*it).first; s2 = *(*it).second.begin(); (*it).second.erase((*it).second.begin()); } if (quanzhi[a1].size() == 0) { if (a1 == a2) { quanzhi.erase(a1); } else { quanzhi.erase(a1); if (quanzhi[a2].size() == 0) quanzhi.erase(a2); } } if (a1 < a2) { for (int i = 0;i < s1.size();i++) { if (ans.find(s1[i]) != ans.end()) { ans[s1[i]] = '0' + ans[s1[i]]; } else { ans.insert(pair<char, string>(s1[i], "0")); } } for (int i = 0;i < s2.size();i++) { if (ans.find(s2[i]) != ans.end()) { ans[s2[i]] = '1' + ans[s2[i]]; } else { ans.insert(pair<char, string>(s2[i], "1")); } } } else if (a1 > a2) { for (int i = 0;i < s1.size();i++) { if (ans.find(s1[i]) != ans.end()) { ans[s1[i]] = '1' + ans[s1[i]]; } else { ans.insert(pair<char, string>(s1[i], "1")); } } for (int i = 0;i < s2.size();i++) { if (ans.find(s2[i]) != ans.end()) { ans[s2[i]] = '0' + ans[s2[i]]; } else { ans.insert(pair<char, string>(s2[i], "0")); } } } else { if (s1.size() <= s2.size()) { for (int i = 0;i < s1.size();i++) { if (ans.find(s1[i]) != ans.end()) { ans[s1[i]] = '0' + ans[s1[i]]; } else { ans.insert(pair<char, string>(s1[i], "0")); } } for (int i = 0;i < s2.size();i++) { if (ans.find(s2[i]) != ans.end()) { ans[s2[i]] = '1' + ans[s2[i]]; } else { ans.insert(pair<char, string>(s2[i], "1")); } } } else { for (int i = 0;i < s1.size();i++) { if (ans.find(s1[i]) != ans.end()) { ans[s1[i]] = '1' + ans[s1[i]]; } else { ans.insert(pair<char, string>(s1[i], "1")); } } for (int i = 0;i < s2.size();i++) { if (ans.find(s2[i]) != ans.end()) { ans[s2[i]] = '0' + ans[s2[i]]; } else { ans.insert(pair<char, string>(s2[i], "0")); } } } } if (quanzhi.find(a1 + a2) != quanzhi.end()) { quanzhi[a1 + a2].insert(s1 + s2); } else { set<string> tee; tee.insert(s1 + s2); quanzhi.insert(pair<int, set<string>>(a1 + a2, tee)); } } for (int i = 0;i < s.size();i++) { cout << ans[s[i]]; } } 过了，但是代码挺垃圾的

华为笔试第二题哈夫曼树

全站热榜