2016头条校招笔试题(LRU)算法之JAVA实现

操作系统中可以使用LRU（Least Recently Used）内存淘汰旧数据的策略，如果内存需要加载新数据但空间不足，则会按照最近访问时间进行排序，并将最老的数据淘汰。假设现在内存空间大小为5，原本内存中没有数据，对内存中数据的访问顺序如下：1, 2, 5, 3, 4, 6,1, 4, 3, 6, 7, 8, 3, 9 问访问过程中发生缺页的次数是多少次？ 

JAVA实现：

首先实现一个固定长度的集合队列

package com.itstyle.list;

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;  

/**
 * 实现一个固定长度的集合队列
 * 在开发中，有时候我们会遇到这样的需求：
 * 对一个集合操作，提前为集合指定最大大小，在我们不断向集合中添加数据的时候，当数据内容超过最大值的时候，自动将最先入队的元素移除队列。
 * @param <E>
 */
public class LimitQueue<E> implements Queue<E> {  

    /**
     * 队列长度，实例化类的时候指定
     */
    private int limit;    

    Queue<E> queue = new LinkedList<E>();    

    public LimitQueue(int limit){
        this.limit = limit;
    }

    /**
     * 入队
     */
    @Override
    public boolean offer(E e){
        if(queue.size() >= limit){
            //如果超出长度,入队时,先出队
            queue.poll();
        }
        return queue.offer(e);
    }    

    /**
     * 出队
     */
    @Override
    public E poll() {
        return queue.poll();
    }    

    /**
     * 获取队列
     */
    public Queue<E> getQueue(){
        return queue;
    }    

    /**
     * 获取限制大小
     */
    public int getLimit(){
        return limit;
    }    

    @Override
    public boolean add(E e) {
        return queue.add(e);
    }    

    @Override
    public E element() {
        return queue.element();
    }    

    @Override
    public E peek() {
        return queue.peek();
    }    

    @Override
    public boolean isEmpty() {
        return queue.size() == 0 ? true : false;
    }    

    @Override
    public int size() {
        return queue.size();
    }    

    @Override
    public E remove() {
        return queue.remove();
    }    

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return queue.addAll(c);
    }    

    @Override
    public void clear() {
        queue.clear();
    }    

    @Override
    public boolean contains(Object o) {
        return queue.contains(o);
    }    

    @Override
    public boolean containsAll(Collection<?> c) {
        return queue.containsAll(c);
    }    

    @Override
    public Iterator<E> iterator() {
        return queue.iterator();
    }    

    @Override
    public boolean remove(Object o) {
        return queue.remove(o);
    }    

    @Override
    public boolean removeAll(Collection<?> c) {
        return queue.removeAll(c);
    }    

    @Override
    public boolean retainAll(Collection<?> c) {
        return queue.retainAll(c);
    }    

    @Override
    public Object[] toArray() {
        return queue.toArray();
    }    

    @Override
    public <T> T[] toArray(T[] a) {
        return queue.toArray(a);
    }
}

执行方法：

package com.itstyle.list;

import java.util.ArrayList;
import java.util.List;

/**
 * 操作系统中可以使用LRU（Least Recently Used）内存淘汰旧数据的策略，如果内存需要加载新数据但空间不足，
 * 则会按照最近访问时间进行排序，并将最老的数据淘汰。假设现在内存空间大小为5，原本内存中没有数据，对内存中数据的访问顺序如下：
 * 1, 2, 5, 3, 4, 6,1, 4, 3, 6, 7, 8, 3, 9 问访问过程中发生缺页的次数是多少次？
 *
 */
public class LRU {
	public static void main(String[] args) {
		LimitQueue<String> list = new LimitQueue<String>(5);
		Integer[] array = new  Integer[]{1, 2, 5, 3, 4, 6,1, 4, 3, 6, 7, 8, 3, 9 };
		List<Integer> page = new ArrayList<Integer>();
		for(Integer i :array){
			if(list.contains(i.toString())){
				list.remove(i);
			}else{
				page.add(i);
			}
			list.offer(i.toString());
		}
		System.out.println("缺页数量"+page.size()+",缺页数据"+page.toString());
	}
}

最终执行结果：缺页数量10,缺页数据[1, 2, 5, 3, 4, 6, 1, 7, 8, 9]