摘要： 題目：http://poj.org/problem?id=1521題目大意：給定字符串，求哈夫曼編碼長和它與等長編碼的比值做這道題目的時候wrang了好幾次，但是，經(jīng)過調(diào)試之后，我徹底了解了哈夫曼樹的過程說來相當有價值了。在下面我也會分享出來的。View Code #include <iostream> #include "cstdio"#include "string"#include "cstring"#include <queue> using namespace std; struct Num{ int 閱讀全文

摘要： DescriptionFarmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needsN(1 ≤N≤ 20,000) planks of wood, each having some integer lengthLi(1 ≤Li≤ 50,000) units. He then purchases a single long board just long enough to saw into theNplanks (i 閱讀全文

摘要： 基本術語 哈夫曼樹又稱為最優(yōu)樹. 1、路徑和路徑長度 在一棵樹中，從一個結點往下可以達到的孩子或子孫結點之間的通路，稱為路徑。 通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結點的層數(shù)為1， 則從根結點到第L層結點的路徑長度為L-1。 2、結點的權及帶權路徑長度 若將樹中結點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結點的權。 結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。 3、樹的帶權路徑長度 樹的帶權路徑長度規(guī)定為所有葉子結點的帶權路徑長度之和，記為WPL。Huffman的構造方法 假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分... 閱讀全文

摘要： 暴雪公司有個經(jīng)典的字符串的hash公式先提一個簡單的問題，假如有一個龐大的字符串數(shù)組，然后給你一個單獨的字符串，讓你從這個數(shù)組中查找是否有這個字符串并找到它，你會怎么做？有一個方法最簡單，老老實實從頭查到尾，一個一個比較，直到找到為止，我想只要學過程序設計的人都能把這樣一個程序作出來，但要是有程序員把這樣的程序交給用戶，我只能用無語來評價，或許它真的能工作，但也只能如此了。最合適的算法自然是使用HashTable（哈希表），先介紹介紹其中的基本知識，所謂Hash，一般是一個整數(shù)，通過某種算法，可以把一個字符串"壓縮"成一個整數(shù)，這個數(shù)稱為Hash，當然，無論如何，一個32位 閱讀全文