算法思想

题目要求很简单，输出查找字典的次数，当内存中有的时候不需要查表，没有的时候才需要查字典

所需要的数据结构显而易见需要一个队列，可以实现每一次添加元素，和移除元素

queue可以直接使用contains方法,判断元素有没有出现过

或者可以选择用一个hashset方法进行存储

但是困扰我的是怎么判断这个数字有没有在缓存中出现过，我一开始i想的是采用一个int数组，记录出现的数字，相当于内存
由于每一次内存的满了，但又需要添加新元素的时候，队列需要移除元素，那么数组的元素的顺序应该怎么办呢？
好吧----其实数组的顺序根本无需考虑，每一次数组位1的元素的个数一定是小于等于m的，int数组的作用就是用来判断这个数在不在缓冲区中
然后就是因为这个困惑，，，卡住了最后看了题解，才明白原来数组里面的元素无需考虑顺序

数组代码

速度要慢一些

package day;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 机器翻译1 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        int m=scanner.nextInt();
        int n=scanner.nextInt();
        int a[]=new int [n];
        for(int i=0;i<n;i++){
            a[i]=scanner.nextInt();
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        int res=0;
        int b[]=new int [1010];
        for(int i=0;i<n;i++){
            if(b[a[i]]==0){
                if(queue.size()==m) {
                    b[queue.poll()]=0;
                }
                res++;
                queue.offer(a[i]);
                b[a[i]]=1;
            }
        }
        System.out.println(res);
    }

}

contains

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class  Main  {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub


        Scanner scanner = new Scanner(System.in);
        int m=scanner.nextInt();
        int n=scanner.nextInt();
        int a[]=new int [n];
        for(int i=0;i<n;i++){
            a[i]=scanner.nextInt();
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        int res=0;
        for(int i=0;i<n;i++){
            if(!queue.contains(a[i]) ){
                if( queue.size()<m){
                    queue.offer(a[i]);
                }
                else {
                    queue.poll();
                    queue.offer(a[i]);
                }
                res++;
            }
        }
        System.out.println(res);
    }

}

hashset

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main  {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        int m=scanner.nextInt();
        int n=scanner.nextInt();
        int a[]=new int [n];
        for(int i=0;i<n;i++){
            a[i]=scanner.nextInt();
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        HashSet<Integer> hashSet = new HashSet<Integer>();
        int res=0;
        for(int i=0;i<n;i++){
            if(!hashSet.contains(a[i])){
                if(queue.size()==m) {
                    hashSet.remove(queue.poll());
                }
                queue.offer(a[i]);
                res++;
                hashSet.add(a[i]);
            }
        }
        System.out.println(res);
    }

}