擅长:python、mysql、java
<p>据我所知,你可以做的一个改进就是这样做:</p>
<pre><code>code += ch
if code in codes:
origin.append(codes[code])
code = ""
</code></pre>
<p>具体来说,每次修改<code>code</code>时都要检查<code>if code in codes:</code>。例如,对于长度为<em>k</em>的代码,您将执行O(1+2+3+…+<em>k</em>)=O(0.5*<em>k</em>*<em>k</em>+1)=O(<em>k</em>²) 在这里操作。相反,您应该预处理<code>codes</code>,方法是构建一个哈夫曼树,并沿树向下遍历一个O(<em>k</em>)来解码代码(从根开始,每次读取一个1或0,然后沿着相应的子边往下走;一旦你找到了一个字母,在解码后的消息中输出它并移回你的树的根)。这不仅显式地节省了检查<code>if code in codes:</code>的时间复杂性,而且还避免了每次执行<code>code += ch</code>时重建字符串<code>code</code></p>
<p>除此之外,我不确定您是否可以进一步优化。我想知道将每个解码的字母转换成<code>byte</code>并附加到输出列表是否比将字母解码成列表然后通过<code>bytes(origin)</code>转换列表更快</p>