Day1 题目 : 21. Merge two ordered lists, 146. LRU cache, 25

Can use JS to achieve I use JS to achieve 2333, try to practice a practice JS this day are linked list, can see the previous study notes review: data structure study notes < 1 > linear table

21. Merge two ordered lists (easy)

Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.

• The recursion is done.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}* /
var mergeTwoLists = function(list1, list2) {
    let p1 = list1
    let p2 = list2
    if(! p1 && ! p2)return null
    else if(! p1)return p2
    else if(! p2)return p1
    else if(p1.val <= p2.val) {
        p1.next = mergeTwoLists(p1.next, p2)
        return p1
    } else {
        p2.next = mergeTwoLists(p2.next, p1)
        return p2
    }
};
Copy the code

146.LRU cache (medium)

Design and implement a data structure that satisfies the LRU (least recently used) cache constraints. Implement the LRUCache class:

• LRUCache(int capacity) 以 Positive integerAs the capacitycapacityInitialize theLRUThe cache
• int get(int key)If the keywordkeyExists in the cache, returns the value of the keyword, otherwise returns- 1 。
• void put(int key, int value)If the keywordkeyIf it already exists, change its data valuevalue ; If not, the group is inserted into the cachekey-value . If the number of keywords exceeds capacity due to the insert operation, the value is yesOut ofThe longest unused keyword.

The functions get and PUT must run in O(1) average time complexity.

Train of thought

Bidirectional linked list (short tail), the end of the list is the least recently used, once used, move to the head of the list.

struct DLNode {	
    int key, val;
    DLNode* prev;
    DLNode* next;
    DLNode(int key = - 1.int val = - 1) :prev(nullptr), next(nullptr), key(key), val(val){}
};
Copy the code

Put inserts the keyword and value if the keyword is not present, or ejects the end of the list if the keyword is full.

void put(int key, int value) {
    if(cache.find(key) == cache.end() || cache[key] == nullptr) {
        // Insert the keyword header if the keyword does not exist
        if(size == capacity) {  // Full evict last one
            cache[tail->prev->key] = nullptr;
            remove(tail->prev);
        }
        DLNode* newp = insert(key, value);
        cache[key] = newp;
    } else {    // The group values are modified
        cache[key] = move2head(cache[key]); cache[key]->val = value; }}Copy the code

When get, if the keyword does not exist, -1 is returned. If it does exist, its corresponding node is moved to the head of the linked list.

int get(int key) {
    if(cache.find(key) == cache.end() || cache[key] == nullptr) 
	    return - 1;
    cache[key] = move2head(cache[key]);
    return cache[key]->val;
}
Copy the code

The complete code

struct DLNode {
    int key, val;
    DLNode* prev;
    DLNode* next;
    DLNode(int key = - 1.int val = - 1) :prev(nullptr), next(nullptr), key(key), val(val){}
};
class LRUCache {
public:
    int capacity;
    int size;
    unordered_map<int, DLNode*> cache;
    DLNode* head;
    DLNode* tail;
    LRUCache(int c): capacity(c), size(0) {
        head = new DLNode(a); tail =new DLNode(a); head->next = tail; tail->prev = head; }void remove(DLNode* p) {
        p->prev->next = p->next;
        p->next->prev = p->prev;
        delete p;
        --size;
    }
    DLNode* insert(int key, int val) {  / / head
        DLNode* temp = head->next;
        DLNode* newp = new DLNode(key, val);
        newp->next = temp;
        newp->prev = head;
        temp->prev = newp;
        head->next = newp;
        ++size;
        return newp;
    }
    DLNode* move2head(DLNode* p) {
        DLNode* newp = insert(p->key, p->val);
        remove(p);
        return newp;
    }
    int get(int key) {
        if(cache.find(key) == cache.end() || cache[key] == nullptr) return - 1;
        cache[key] = move2head(cache[key]);
        return cache[key]->val;
    }
    
    void put(int key, int value) {
        if(cache.find(key) == cache.end() || cache[key] == nullptr) {// Insert the keyword header if the keyword does not exist
            if(size == capacity) {  // Full evict last one
                cache[tail->prev->key] = nullptr;
                remove(tail->prev);
            }
            DLNode* newp = insert(key, value);
            cache[key] = newp;
        } else {    // The group values are modified
            cache[key] = move2head(cache[key]); cache[key]->val = 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); * /
Copy the code

25. Flipping linked lists in groups of K (difficulty)

You are given a linked list, each k nodes in a group of flipped, please return to the flipped list.

K is a positive integer whose value is less than or equal to the length of the list.

If the total number of nodes is not an integer multiple of k, keep the last remaining nodes in the same order.

Train of thought

Prev set to NULL (inertia 2333), should be set to E.ext because there may be more lists to follow. ReverseList (s, e), which returns the head and tail of the reverse list

var reverseList = function(s, e) {
    let prev = e.next;		// Notice here
    let nowv = s;
    while(prev ! = e) {// And here
        let temp = nowv.next;
        nowv.next = prev;
        prev = nowv;
        nowv = temp;
    }
    return [e, s];
}
Copy the code

Use a linked list with empty nodes, and note that if there are less than K nodes, do not reverse them.

var reverseKGroup = function(head, k) {
    let ehead = new ListNode(0);
    ehead.next = head;
    let prev = ehead;  // the first node
    while(head) {
        let end = prev;
        for(let i = 0; i < k; ++i) {
            end = end.next;
            if(! end)return ehead.next;
        }
        let temp = end.next;
        [head, end] = reverseList(head, end);   
        // return the reversed list head & end
        prev.next = head;
        prev = end;
        end.next = temp;
        head = end.next;
    }
    return ehead.next;
};
Copy the code

The complete code

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
 
var reverseList = function(s, e) {
    let prev = e.next;
    let nowv = s;
    while(prev ! = e) {let temp = nowv.next;
        nowv.next = prev;
        prev = nowv;
        nowv = temp;
    }
    return [e, s];
}
/ * * *@param {ListNode} head
 * @param {number} k
 * @return {ListNode}* /
var reverseKGroup = function(head, k) {
    let ehead = new ListNode(0);
    ehead.next = head;
    let prev = ehead;  // the first node
    while(head) {
        let end = prev;
        for(let i = 0; i < k; ++i) {
            end = end.next;
            if(! end)return ehead.next;
        }
        let temp = end.next;
        [head, end] = reverseList(head, end);   
        // return the reversed list head & end
        prev.next = head;
        prev = end;
        end.next = temp;
        head = end.next;
    }
    return ehead.next;
};
Copy the code