使用队列和map实现lru

设计LRU缓存结构

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

使用队列和map实现

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        ArrayList<Integer>list = new ArrayList();

        Queue<int[]> queue = new LinkedList<int[]>();
        Map<Integer, int[]> map = new HashMap();

            for (int i = 0; i < operators.length; i++) {
                //size > k
                if (queue.size() > k) {
                    int[] poll = queue.poll();
                    map.remove(poll[1]);
                }
                //opt == 1
                if (operators[i][0] == 1) {
                    int[] r = map.get(operators[i][1]);
                    if (r != null) {
                        map.remove(operators[i][1]);
                        queue.remove(r);
                    } 
                    map.put(operators[i][1], operators[i]);
                    queue.offer(operators[i]);
                }
                //opt == 2
                if (operators[i][0] == 2) {
                    //有,放result数组
                    int[] r = map.get(operators[i][1]);
                    if (r != null) {
                        queue.remove(r);
                        queue.offer(r);
                        list.add(r[2]); 
                    } else {
                        list.add(-1);
                    }
                }
            }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
2022-12-19 15:48
重庆工商大学_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-12 12:42
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
7 1 评论
分享

全站热榜

正在热议