每天写两道(二)LRU缓存、数组中最大的第k个元素

2024-05-29 11:12

本文主要是介绍每天写两道(二)LRU缓存、数组中最大的第k个元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

146.LRU 缓存

. - 力扣(LeetCode)

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 

思路:双向链表+一个哨兵节点,使用map记录(key,node)

(图和思路都是偷力扣大佬的) 

实现:

class Node {constructor(key, value) {this.key = keythis.value = valuethis.pre = nullthis.next = null}
}class LRUCache {constructor(capacity) {this.capacity = capacitythis.dummy = new Node()this.dummy.next = this.dummythis.dummy.pre = this.dummy// 哈希表 用来存key和节点nodethis.keyToNodeMap = new Map()}// 删除x节点delete(x) {x.pre.next = x.nextx.next.pre = x.pre}// 将节点添加在链表头 哨兵节点后addTop(x) {x.pre = this.dummyx.next = this.dummy.nextx.pre.next = xx.next.pre = x}getNode(key) {// 没有该节点if (!this.keyToNodeMap.has(key)) { return null;}// 有 拿出来放在头部const node = this.keyToNodeMap.get(key); this.delete(node); this.addTop(node); return node;}get(key) {const node = this.getNode(key)return node?node.value:-1}put(key, value) {let node = this.getNode(key)// 有这个值 拿出来更新if (node) {node.value = value} else {// 新建节点放入node = new Node(key, value)this.keyToNodeMap.set(key, node)this.addTop(node)// 判断有没有溢出if (this.keyToNodeMap.size > this.capacity) {const backNode = this.dummy.prethis.keyToNodeMap.delete(backNode.key)this.delete(backNode)}}}
}

215.数组中最大的第k个元素

. - 力扣(LeetCode)

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 

思路:

看的是这位佬的:. - 力扣(LeetCode)

利用大根堆根节点最大的特性,构建大根堆,将根节点与最末尾节点交换,移出这个最大节点,再进行排序。。。

利用的是堆的思想,但实际是用数组来实现的 

顺序存储二叉树的特点:

第 n 个元素的 左子节点 为 2*n+1
第 n 个元素的 右子节点 为 2*n+2
第 n 个元素的 父节点 为 (n-1)/2
最后一个非叶子节点为 Math.floor(arr.length/2)-1

实现:

var findKthLargest = function (nums, k) {let len = nums.length// 先构建大根堆buildMaxHeap(nums, len)// 循环 将大根堆根节点和最末尾的节点交换// 循环到第k+1个最大就停止 最后返回的nums的根节点就是目标数// 这里for循环要用nums.length,不能用len,因为len是会改变的for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {swap(nums, 0, i) // 将最大节点和最末尾的节点交换// 调整大根堆maxHeapify(nums, 0, --len) // 移到最后的节点不参与调整}return nums[0] // 返回第k个最大的值// 创建大根堆 自下而上构建大根堆function buildMaxHeap(nums, len) {// 最小非叶子节点:Math.floor(arr.length/2)-1for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {maxHeapify(nums, i, len)}}function maxHeapify(nums, i, len) {let left = i * 2 + 1 // i的左子节点let right = i * 2 + 2 // i的右子节点let largest = i // 最大值的节点下标// 和左子节点比较if (left < len && nums[left] > nums[largest]) {largest = left}// 和右子节点比较if (right < len && nums[right] > nums[largest]) {largest = right}if (i !== largest) {swap(nums, i, largest) // 将子节点与父节点交换maxHeapify(nums, largest, len) // 再继续向下比较}}function swap(nums, a, b) {let temp = nums[a]nums[a] = nums[b]nums[b] = temp}};

 今天写的两道都有点难,对于我这个白痴来说,所以明天还要再写一遍!!!

这篇关于每天写两道(二)LRU缓存、数组中最大的第k个元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1013509

相关文章

每天认识几个maven依赖(ActiveMQ+activemq-jaxb+activesoap+activespace+adarwin)

八、ActiveMQ 1、是什么? ActiveMQ 是一个开源的消息中间件(Message Broker),由 Apache 软件基金会开发和维护。它实现了 Java 消息服务(Java Message Service, JMS)规范,并支持多种消息传递协议,包括 AMQP、MQTT 和 OpenWire 等。 2、有什么用? 可靠性:ActiveMQ 提供了消息持久性和事务支持,确保消

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若

poj 2135 有流量限制的最小费用最大流

题意: 农场里有n块地,其中约翰的家在1号地,二n号地有个很大的仓库。 农场有M条道路(双向),道路i连接着ai号地和bi号地,长度为ci。 约翰希望按照从家里出发,经过若干块地后到达仓库,然后再返回家中的顺序带朋友参观。 如果要求往返不能经过同一条路两次,求参观路线总长度的最小值。 解析: 如果只考虑去或者回的情况,问题只不过是无向图中两点之间的最短路问题。 但是现在要去要回

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta

poj 3422 有流量限制的最小费用流 反用求最大 + 拆点

题意: 给一个n*n(50 * 50) 的数字迷宫,从左上点开始走,走到右下点。 每次只能往右移一格,或者往下移一格。 每个格子,第一次到达时可以获得格子对应的数字作为奖励,再次到达则没有奖励。 问走k次这个迷宫,最大能获得多少奖励。 解析: 拆点,拿样例来说明: 3 2 1 2 3 0 2 1 1 4 2 3*3的数字迷宫,走两次最大能获得多少奖励。 将每个点拆成两个