题解 | #设计LRU缓存结构#

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    typedef struct KeyValue
    {
        int nKey;
        int nValue;
    }KeyValue;

    vector<KeyValue> vecCache;

    int GetCache(int nKey)
    {
        for(int i=0;i<vecCache.size();i++)
        {
            if(nKey == vecCache[i].nKey)
            {
                int nRet = vecCache[i].nValue;
                if(i != vecCache.size()-1)
                {
                    KeyValue tmp = vecCache[i];
                    for(int j=i;j<vecCache.size();j++)
                    {
                        vecCache[j] = vecCache[j+1];
                    }
                    vecCache[vecCache.size()-1] = tmp;
                }
                return nRet;
            }
        }
        return -1;
    }

    void InsertCache(KeyValue keyValue, int k)
    {
        if(vecCache.size() > 0 && vecCache.size() >= k)
        {
            vecCache.erase(vecCache.begin());
        }


        for(int i=0;i<vecCache.size();i++)
        {
            if(keyValue.nKey == vecCache[i].nKey)
            {
                vecCache[i].nValue = keyValue.nValue;
                return;
            }
        }
        vecCache.push_back(keyValue);
    }

    vector<int> LRU(vector<vector<int> >& operators, int k) 
    {
        vector<int> vecRet;
        // write code here
        for(int i=0;i<operators.size();i++)
        {
            vector<int> & one_operator = operators[i];
            int nType = one_operator[0];
            if(nType == 1)
            {
                int nKey = one_operator[1];
                int nValue = one_operator[2];
                KeyValue tmpKeyValue;
                tmpKeyValue.nKey = nKey;
                tmpKeyValue.nValue = nValue;
                InsertCache(tmpKeyValue,k);
            }
            else if(nType == 2)
            {
                int nKey = one_operator[1];
                vecRet.push_back(GetCache(nKey));
            }
            else
            {
                continue;
            }
        }
        return vecRet;
    }
};