题解 | #设计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;
        }
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-16 14:00
白火同学:其实你可以了解一下HR在Boss聊天的机制,想赢牌的前提是先会玩牌。 如果HR长时间没有理你,有可能是因为你的消息被其他应聘者的消息给挤到下面了,HR从上到下有可能只看个三四百个人就要到理想数量的简历了,而你恰好没有被看到,时间一长,你的消息在越来越下面。这种情况就需要你自己活跃一下,把消息提上去。 也可能是HR招的合适的人选了,但会一直挂着岗位,为了省重新开招聘岗位的钱,方便后面随时修改招聘要求。 当然也可能是HR吃饱了没事耍你玩,要了你的简历又不看,就看你自己怎么理解了。
点赞 评论 收藏
分享
认真搞学习:这么良心的老板真少见
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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