当前位置: 首页 > news >正文

哪个行业最需要做网站北京已感染上千万人

哪个行业最需要做网站,北京已感染上千万人,58同城网站建设推广,外销平台有哪些视频讲解 哈希 双向链表 为什么要用双向链表? 快速删除节点(O(1)) 如果是单链表的话,删除一个节点时,需要从头遍历,找到前驱节点,才能修改 prev->next,导致 O(n)…

视频讲解

哈希 + 双向链表

为什么要用双向链表?

快速删除节点(O(1))

如果是单链表的话,删除一个节点时,需要从头遍历,找到前驱节点,才能修改 prev->next,导致 O(n) 的时间复杂度

双向链表存储了两个指针,一个指针指向下一个节点,另一个指针指向上一个节点(前驱指针)。所以我们可以根据前驱指针快速找到上一个节点,然后移除掉当前节点。

demo:

class LRUCache {
public:struct Node{int key,val;Node *prev,*next;Node(int k,int v) : key(k) , val(v) , prev(nullptr) , next(nullptr){}};map<int,Node*>mp;Node *L,*R; //双哨兵int n; //LRU的总数//创建操作LRUCache(int capacity) {n = capacity;L = new Node(-1,-1);R = new Node(-1,-1);L->next = R;R->prev = L;}//获取值操作 (获得值的时候需要注意:如果有值存在哈希表中的话,那么就要将这个值放在最新的地方)//比如: L | 2 1 4 | R //我们查询1这个数,那么查完后需要变成: L | 2 4 1 | R int get(int key) {if(mp.count(key)){Node* node = mp[key];remove(node); //在链表中移除该节点 通过双向指针移除insert(node->key,node->val); // 在链表中插入该节点return node->val;}else{return -1;}}//插入操作void put(int key, int value) {if(mp.count(key)){Node* node = mp[key];remove(node);insert(key,value); //这里需要用给的key和value而不是node->key和node->val(因为可能插入的是新的值)}else{if(mp.size() == n){Node* node = L->next; //满了,需要移除的节点remove(node);insert(key,value);}else{insert(key,value);}}}//以下为自定义新增函数 remove是移除节点的函数 insert是插入节点的函数//同时在链表和哈希表中删除nodevoid remove(Node* node){Node* pre = node->prev;Node* nxt = node->next;pre->next = nxt;nxt->prev = pre;mp.erase(node->key);}//同样要同时操作链表和哈希表void insert(int key,int val){Node* node = new Node(key,val);Node* pre = R->prev;//这里是最后一个插入的数//向右pre->next = node;node->next = R;//向左node->prev = pre;R->prev = node;mp[key] = node;}};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/

http://www.ds6.com.cn/news/6791.html

相关文章:

  • 在国外做h网站怎么样外贸国际网站推广
  • 做网站推广需要什么今日国际新闻最新消息事件
  • 做软件常用的网站有哪些软件有哪些云搜索引擎
  • 网站建设什么打王思聪沈阳头条今日头条新闻最新消息
  • 电子商城网站制作数据库网页设计图
  • 网站备案期间做什么百度seo搜索引擎优化
  • 空间站对接热门关键词排名查询
  • 武汉站建设哈尔滨百度网站快速优化
  • 网站模版库外贸独立站建站
  • 龙岩有什么兼职可以做深圳优化公司高粱seo较
  • 外贸网站做SEO河北seo技术培训
  • 西安企业网站建设托管搜索词和关键词
  • 三站一体网站制作百度广告推广费用
  • 网页小游戏列表游戏优化
  • 怎么利用爬虫技术 提高网站排名app推广好做吗
  • 百度大全网站怎么策划一个营销方案
  • 做网站一定要域名吗大数据营销推广精准粉
  • 广州东莞最新疫情郑州seo服务
  • ps做网站像素大小营销网站都有哪些
  • wordpress主题添加中文版关键词优化包含
  • 哪个网站可以查企业信息万网注册域名查询官方网站
  • 网站数据库建表百度热度
  • 西宁网络信息 网站建设推广图片制作
  • 网站预算表怎么做网站推广 方法
  • 浙江省政府 加强政府网站建设游戏推广公司怎么接游戏的
  • 深圳分销网站制作中国国家数据统计网
  • wordpress 网站制作网络营销的8个基本职能
  • wordpress缩略图大小网站优化员seo招聘
  • 如何做阿里巴巴国际网站济南seo公司
  • 在北京做网站制作一个月多少钱seo教程 百度网盘