Ввод конфликтов из-за проблемы с Leetcode в LRU-кеше - PullRequest
Новая
       30

Ввод конфликтов из-за проблемы с Leetcode в LRU-кеше

0 голосов
/ 11 октября 2018

Я пытаюсь решить этот вопрос из LeetCode (https://leetcode.com/problems/lru-cache/description/), но я нахожу проблему с определенным входом. Я также использую их форум, но они слишком долго отвечают.

Я хотел бы знать, почему окончательный вывод для этой записи ["LRUCache", "put", "put", "get", "put", "put", "get"] [[2], [2,1], [2,2], [2], [1,1], [4,1], [2]] равно (-1) вместо 2.

Насколькокак я знаю, конечная конфигурация кэша будет [(4,1), (2,2)), тогда будет возвращено 2, а не -1. ​​

Спасибо!

Вот код, который я написал: 

public class LRUCache {

    HashMap<Integer, Integer> keyToArrayPosition = new HashMap<>();
    Tuple [] cache;
    int head;
    int tail;
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new Tuple[this.capacity];
        head = 0;
        tail = 0;
    }

    public int get(int key) 
    {    
        if(keyToArrayPosition.keySet().contains(key))
        {
            int position = keyToArrayPosition.get(key);
            Tuple t = cache[position];
            return t.value;
        }
        return -1;
    }

    public void put(int key, int value) 
    {
        Tuple t = new Tuple(key, value);
        //set
        if(keyToArrayPosition.keySet().contains(key))
        {
            int position = keyToArrayPosition.get(key);
            cache[position] = t;
            return;
        }

        if(tail <= capacity - 1)
        { 
            cache[tail] = t;
            keyToArrayPosition.put(key, tail);
            tail++;
        }
        else
        {
            tail--;
            keyToArrayPosition.remove(cache[cache.length - 1].key);
            for(int i = tail; i > 0; i--)
            {
                cache[i] = cache[i - 1];
                keyToArrayPosition.put(cache[i].key, i);
            }
            cache[0] = t;
            keyToArrayPosition.put(key, 0);
            tail++;
        }
    }
}

class Tuple
{
   public int key;
   public int value;

    public Tuple(int key, int value)
    {
        this.key = key;
        this.value = value;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
...