6.29 problem solving

I wrote two topics today .

The first topic is difficult .

The title is the above .

The meaning of the topic is to design three kinds of functions . Then output the function type you want to use and the input value .

Then we can do different operations , Get the answer . 

The first function is to set the size of the cache . A number to find out if it exists in the cache , If it exists, input its value . If it doesn't exist, negative one will be output .

The third is to add and replace the key value pair if it exists .  If it does not exist, add it . Then, if the capacity has been exceeded , Delete the key value pairs that have not been used for the longest time

Then the big idea of this problem is to solve it with a hash table and a two-way linked list .

The hash table is used to store key value pairs    A two-way linked list is used as a container

The addition operation is to take the data to be added as a new header node .

For the replaced data, put , After this data is deleted , Then add it . In this way, he will be ranked in the head node . That is to put his priority higher .

Then delete the tail node . That is, point to an empty node .  The difficulty of this topic does not lie in the thinking , It may be how to write a complete hash table and a two-way linked list . Data structure . 

struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;// Connect to the previous node 
    DLinkedNode* next;// Connect to the next node 
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        //  Use head and tail nodes 
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        
        DLinkedNode* node = cache[key];
        moveToHead(node);// For mobile , Move to the head 
        return node->value;
    }
    
    void put(int key, int value) {
        if (!cache.count(key)) {
            //  If  key  non-existent , Create a new node 
            DLinkedNode* node = new DLinkedNode(key, value);
            //  Add to hash table 
            cache[key] = node;
            //  Add to the head of the bidirectional list 
            addToHead(node);
            ++size;
            if (size > capacity) {
                //  If the capacity is exceeded , Delete the tail node of the bidirectional linked list 
                DLinkedNode* removed = removeTail();
                //  Delete the corresponding entry in the hash table 
                cache.erase(removed->key);
                delete removed;
                --size;
            }
        }
        else {
            //  If  key  There is , First, locate through the hash table , Revise  value, And move to the head 
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {// Add a node 
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(DLinkedNode* node) {// Delete a node 
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);// The requirement to move to the head is accomplished by deleting and adding once at a time 
    }

    DLinkedNode* removeTail() {// To delete the tail node 
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

That's the code .

Then there is another question .

There is nothing to say about this topic . If used sort  Maybe it's just a few lines . But a fast platoon can also solve this problem if it is not used .  It is to sort and then output the specified   Reciprocal k The data of one location is enough . 

The code is the following .

inline int partition(int* a, int l, int r) {
    int x = a[r], i = l - 1;
    for (int j = l; j < r; ++j) {
        if (a[j] <= x) {
            int t = a[++i];
            a[i] = a[j], a[j] = t;
        }
    }
    int t = a[i + 1];
    a[i + 1] = a[r], a[r] = t;
    return i + 1;
}

inline int randomPartition(int* a, int l, int r) {
    int i = rand() % (r - l + 1) + l;
    int t = a[i];
    a[i] = a[r], a[r] = t;
    return partition(a, l, r);
}

int quickSelect(int* a, int l, int r, int index) {
    int q = randomPartition(a, l, r);
    if (q == index) {
        return a[q];
    } else {
         if(q < index){
           return quickSelect(a, q + 1, r, index);
         }else{
            return  quickSelect(a, l, q - 1, index);
         }                
    }
}

int findKthLargest(int* nums, int numsSize, int k) {
    srand(time(0));
    return quickSelect(nums, 0, numsSize - 1, numsSize - k);
}

That's all for today's topic .