题解 | #设计LRU缓存结构#

设计LRU缓存结构

http://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61

优先队列

提供另一种思路解决问题,不能算最优解吧,能过此题。

  • 优先队列:设置一个标志位用来表示最近处理情况。优先队列的排序就以次标志位,升序、小顶堆,对顶就是最久未使用元素。
  • 设一个全局变量recent。每次添加元素的时候,recent++。这样做有个问题++到上限之后怎么办。但题目的数据量不过几千无需考虑次问题。
  • 再用一个HashMap快速检索 使用存在要查询的元素。
  • PriorityQueue的remove(o), 是删除o.equal()的元素。时间复杂度 O(n)


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
		int recent = 0;
		PriorityQueue<Node> que = new PriorityQueue<Node>((o1, o2) -> o1.re - o2.re);
		HashMap<Integer, Integer> map = new HashMap<>();
		ArrayList<Integer> list = new ArrayList<>();
		for (int[] operator : operators) {
			if (operator[0] == 1) {
				if (que.size() < k) {
					map.put(operator[1], operator[2]);
					que.add(new Node(recent++, operator[1], operator[2]));
				} else {
					Node poll = que.poll();
					que.add(new Node(recent++, operator[1], operator[2]));
					map.remove(poll.key);
					map.put(operator[1], operator[2]);
				}
			} else {
				if (map.containsKey(operator[1])) {
					int val = map.get(operator[1]);
					que.remove(new Node(operator[1]));
					list.add(val);
					que.add(new Node(recent++, operator[1], val));
				} else {
					list.add(-1);
				}
			}

		}
		int ans[] = new int[list.size()];
		int len = list.size();
		for (int i = 0; i < len; i++) {
			ans[i] = list.get(i);
		}
		return ans;
	}
    class Node  {
         int re;
         int key;
         int val;

        public Node(int re, int key, int val) {
            this.re = re;
            this.key = key;
            this.val = val;
        }

        public Node(int key) {
            this.key = key;
        }

        @Override
        public boolean equals(Object obj) {
        	//用于删除 key 相同的元素
            Node a = (Node) obj;
            return key == a.key;
        }
    }
}
全部评论

相关推荐

05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
投递美团等公司9个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务