回覆列表
-
1 # 1234567啊額
-
2 # 直爽餃子WK
僅壓縮連續重複出現的字元。比如字串”abcbc”由於無連續重複字元，壓縮後的字串還是”abcbc”。
2、壓縮欄位的格式為”字元重複的次數+字元”。例如：字串”xxxyyyyyyz”壓縮後就成為”3x6yz”。
示例
輸入：“cccddecc” 輸出：“3c2de2c”
輸入：“adef” 輸出：“adef”
輸入：“pppppppp” 輸出：“8p”
主要說來就是進行字串處理類的問題，主要涉及到：
1.字串的輸入與輸出；
2.基本常用的C語言的字串的函式使用；
3.對於多重情況的考慮；
4.將數字轉換成字串並進行拼接；
方法1：最簡單就是將所有字元加起來，程式碼如下：
unsigned long HashString(const char *pString, unsigned long tableSize)
{
unsigned long hashValue = 0;
while(*pString)
hashValue += *pString++;
return hashValue % tableSize;
}
分析：如果字串的長度有限，而散列表比較大的話，浪費比較大。例如，如果字串最長為16位元組，那麼用到的僅僅是散列表的前16*127=2032。假如散列表含2729項，那麼2032以後的項都用不到。
方法2：將上次計算出來的hash值左移5位（乘以32），再和當前關鍵字相加，能得到較好的均勻分佈的效果。
unsigned long HashString(const char *pString,unsigned long tableSize)
{
unsigned long hashValue = 0;
while (*pString)
hashValue = (hashValue << 5) + *pString++;
return hashValue % tableSize;
}
分析：這種方法需要遍歷整個字串，如果字串比較大，效率比較低。
方法3：利用哈夫曼演算法，假設只有0-9這十個字元組成的字串，我們藉助哈夫曼演算法，直接來看例項：
#define Size 10
int freq[Size];
string code[Size];
string word;
struct Node
{
int id;
int freq;
Node *left;
Node *right;
Node(int freq_in):id(-1), freq(freq_in)
{
left = right = NULL;
}
};
struct NodeLess
{
bool operator()(const Node *a, const Node *b) const
{
return a->freq < b->freq;
}
};
void init()
{
for(int i = 0; i < Size; ++i)
freq[i] = 0;
for(int i = 0; i < word.size(); ++i)
++freq[word[i]];
}
void dfs(Node *root, string res)
{
if(root->id >= 0)
code[root->id] = res;
else
{
if(NULL != root->left)
dfs(root->left, res+"0");
if(NULL != root->right)
dfs(root->right, res+"1");
}
}
void deleteNodes(Node *root)
{
if(NULL == root)
return ;
if(NULL == root->left && NULL == root->right)
delete root;
else
{
deleteNodes(root->left);
deleteNodes(root->right);
delete root;
}
}
void BuildTree()
{
priority_queue<Node*, vector<Node*>, NodeLess> nodes;
for(int i = 0; i < Size; ++i)
{
//0 == freq[i] 的情況未處理
Node *newNode = new Node(freq[i]);
newNode->id = i;
nodes.push(newNode);
}
while(nodes.size() > 1)
{
Node *left = nodes.top();
nodes.pop();
Node *right = nodes.top();
nodes.pop();
Node *newNode = new Node(left->freq + right->freq);
newNode->left = left;
newNode->right = right;
nodes.push(newNode);
}
Node *root = nodes.top();
dfs(root, string(""));
deleteNodes(root);
}