算法训练营题目回顾

题目:重编码

题目分析: 此题为典型哈夫曼编码问题,思路为出现次数少的用的01数长度相对长~ 也就是深度相对较深~出现次数多(可以为深度)尽量小,最后使得

sum(d*n..此为出现次数与深度的乘积总和) 最小. 。。因为此题仅需求出其长度 所以可以根据huffman树启示 直接求出sum;

注(此题邓老师还有一个巧妙地运用队列和栈的解法,在视频中待整理)

以下是依据优先级队列属性求sum最小值的解法

int getAnswer(n , vector m){
priority_queue pq;ll sum =0;
for(int i =0;i<n;i++){
pq.push(m[i]);
}

while(pq.size()>1){
ll new_elem =0;
for(int j=0;j<2;j++){
new_elem+=pq.top();
pq.pop();
}
pq.push(new_elem);
sum+=new_elem;
}
return sum;
}
//此方法巧妙之处就在于巧妙地运用huffman树的特性但却不需要具体实现huffman树的结构从而直接得到需要求得sum的最小值. 需要使用到每个叶子节点的深度但却并不是也并不需要先求出各个节点的深度然后再用深度乘上个数然后再求和,而是每每选最小的节点然后直接使其合并 合并得到的值加入总和,即每当一个分支(此分支根节点值为最小俩节点之一)的所有节点深度须+1 (即当前最小的俩节点合并)则加上分支根节点的值即可,


题目:数字盒子:(此题可为理解散列表实现做铺垫)
const int MAX=1000007
vector<int> a[MAX];
int Hash(int x){
return  x%MAX;
}

ll getAnswer(int op,int x){

int h =Hash(x);
vector<ll>::iterator ptr = table[h].end();//返回向量尾指针   
    for(vector<ll>::iterator it =a[h].begin();it<a[h].end();it++){
    if(*it==x){ptr=it;break;}
    } 

switch(op){
case 1://insert
if(ptr==a[h].end()){a[h].pushback(x);return 1;}break;
case 2:if(a[h].end()!=ptr){
for(vector<ll>::iterator it =a[h].begin();it<a[h].end();it++)
if(*it==x){*it=a[h].back();a[h].popback();/*此处操作略微高级,由于我们不需要理会vector内的顺序性 只需要考虑是否存在X即可 所以此操作在vector值多的时候可将vector删除的时间复杂度由O(n)减至O(1);*/

return 1;
}
return 0;
}
}
}
//另外在此处说明 vector的back()方法返回最后一个元素 而end()方法返回最后一个元素的下一个元素(可理解为哨兵元素);
我来评几句
登录后评论

已发表评论数()

相关站点

热门文章