Force button brush question 01 (reverse linked list + sliding window +lru cache mechanism)

I haven't written a summary for a long time , Then I was busy writing projects some time ago , I seldom brush questions , Let's write an explanation today .

  Reverse a linked list

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* p;
        p=head;
        ListNode* q=nullptr;
        while(p){
            ListNode* next = p->next;// Record the next digit of the current position 
            p->next=q;// Link the chain of the current position to the previous position 
            q=p;// Update previous 
            p=next;// Move to the next position to continue the previous operation 
        }
        return q;
    }
};

  The sliding window

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s==""){// It is specially judged that there is no character 
            return 0;
        }
       map<char,int>a;
       int sum=0;
       int flag;
       for(int i=0,j=0;j<s.length();j++){
           if(a.find(s[j])!=a.end()){// If there are the same characters , to update i Subscript 
                i=max(a[s[j]],i);
           }
           sum=max(sum,j-i+1);// to update sum value 
           a[s[j]]=j+1;// take value The value is set to the character subscript +1, Make it easy to get the character position 

       }
        return sum;
    }
};

Violence at first , It's not right , Time overrun , Then we use window sliding , By updating the i,j Two subscripts to find the maximum length

struct Link{// Create a bidirectional linked list node 
    int k,v;
    struct Link* prev,*next;
};
class LRUCache {
private:
    int Maxsize;
    int size=0;
    struct Link*head,*tail;
    map<int,Link*>num;
public:
    LRUCache(int capacity) {
        head=new Link();// Bidirectional list initialization 
        tail=new Link();
        head->next=tail;
        tail->prev=head;
        Maxsize=capacity;// Set maximum 
    }

    int get(int key) {

        if(num.find(key)==num.end()){
        // If there is no such keyword , The output -1
            return -1;
        }
        Link *p;// Insert the used node into the head of the linked list 
        p=num[key];
        p->prev->next=p->next;
        p->next->prev=p->prev;
        Link *temp=head->next;
        head->next=p;
        p->prev=head;
        p->next=temp;
        temp->prev=p;
        return p->v;
    }

    void put(int key, int value) {
        if(num.find(key)!=num.end()){// If map The keyword already exists in , Then change value value 
            num[key]->v=value;
            Link *p;
        p=num[key];// Move the node to the front 
        p->prev->next=p->next;
        p->next->prev=p->prev;
        Link *temp=head->next;
        head->next=p;
        p->prev=head;
        p->next=temp;
        temp->prev=p;
            return;
        }
        size++;// Length plus one 
         Link *p;
            p=new Link();// Join this node , Add the header 
            p->k=key;
            p->v=value;
            p->next=head->next;
            p->next->prev=p;
            head->next=p;
            p->prev=head;
            num[key]=p;
        if(size>Maxsize){// If the maximum capacity is exceeded , Then remove the earliest used node , That is, the node at the end of the table 
            int k=tail->prev->k;
            tail->prev=tail->prev->prev;
            tail->prev->next=tail;
            num.erase(k);// from map Remove the node from the table 
        }
    }
};

This problem is mainly the combination of hash table and bidirectional linked list , The hash table key The value corresponds to the node of the bidirectional linked list ,
Follow the nearest node to the header , The earlier you use, the farther away from the end of the table , When the capacity exceeds the maximum limit ,
Remove the nodes at the end of the table , At the same time, don't forget to remove the values in the hash table .