C++模拟笔记

LRU 缓存

struct Node {
    int key, val;
    Node(int _key, int _value) : key(_key), val(_value) {}
};

class LRUCache {
public:
    LRUCache(int capacity) {
        this -> capacity = capacity;
    }
    
    void insert(int key, int value) {
        key_list.push_back({key, value});
        hash[key] = --key_list.end();
    }

    int get(int key) {
        if (capacity == 0) return -1;
        auto it = hash.find(key);
        if (it == hash.end()) return -1;
        list<Node>::iterator node = it -> second;
        int val = node -> val;
        key_list.erase(node);
        insert(key, val);
        return val;
    }
    
    void put(int key, int value) {
        if (capacity == 0) return;
        if (get(key) != -1) {
            hash[key] -> val = value;
            return;
        }
        if (hash.size() < capacity) {
            insert(key, value);
        } else {
            int remove_key = key_list.front().key;
            key_list.pop_front();
            hash.erase(remove_key);
            insert(key, value);
        }
    }

private:
    int capacity;
    list<Node> key_list;
    unordered_map<int, list<Node>::iterator> hash;
};

/**
 * 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);
 */

LFU 缓存

主要考虑数据结构的选用。哈希表 key_table 存储 key 与 值信息与它在链表中的位置 的映射，如果没有 freq 的要求（即简单的 LRU），只需要维护一个 list 即可，可以解决时间先后问题。但是考虑到有 freq 的要求，这里就可以对 list 进行拆分，可以用一个哈希表来存储 freq 与 list 的映射 freq_table。这样就可以首先解决 freq 问题，同时根据 list 解决 LRU 最近最久未使用问题。

struct Node {
    int key, val, freq;
    Node(int _key, int _val, int _freq) : key(_key), val(_val), freq(_freq) {}
};

class LFUCache {
public:
    LFUCache(int capacity) {
        this -> capacity = capacity;
        min_freq = 0;
        freq_table.clear();
        key_table.clear();
    }
    
    int get(int key) {
        if (capacity == 0) return -1;
        auto it = key_table.find(key);
        if (it == key_table.end()) return -1;
        list<Node>::iterator node = it -> second;
        int freq = node -> freq, value = node -> val;
        freq_table[freq].erase(node);
        if (freq_table[freq].size() == 0) {
            freq_table.erase(freq);
            if (freq == min_freq) {
                min_freq += 1;
            }
        }
        freq_table[freq + 1].push_back({key, value, freq + 1});
        key_table[key] = -- freq_table[freq + 1].end();
        return value;
    }
    
    void put(int key, int value) {
        if (capacity == 0) return;
        auto it = key_table.find(key);
        if (it == key_table.end()) {
            if(key_table.size() == capacity) {
                int remove_key = freq_table[min_freq].front().key;
                freq_table[min_freq].pop_front();
                key_table.erase(remove_key);
                if (freq_table[min_freq].size() == 0) {
                    freq_table.erase(min_freq);
                }
            }
            min_freq = 1;
            freq_table[min_freq].push_back(Node(key, value, min_freq));
            key_table[key] = -- freq_table[min_freq].end();
            return;
        }
        list<Node>::iterator node = it -> second;
        int freq = node -> freq;
        freq_table[freq].erase(node);
        if (freq_table[freq].size() == 0) {
            freq_table.erase(freq);
            if (freq == min_freq) {
                min_freq += 1;
            }            
        }
        freq_table[freq + 1].push_back({key, value, freq + 1});
        key_table[key] = -- freq_table[freq + 1].end();   
    }

private:
    int capacity, min_freq;
    unordered_map<int, list<Node>> freq_table;
    unordered_map<int, list<Node>::iterator> key_table;
};

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

K 个一组反转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    public void reverse(ListNode head, ListNode tail) {
        // 找起点
        ListNode pre = tail.next;
        ListNode cur = head;
        // pre!=tail or cur!=tail.next
        while (pre != tail) {
            ListNode ne = cur.next;
            cur.next = pre;
            pre = cur;
            cur = ne;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode p = dummy;
        // 组入口
        while (p.next != null) {
            // 探测组出口
            ListNode tail = p;
            for (int i = 0; i < k; i ++ ) {
                tail = tail.next;
                if (tail == null) {
                    return dummy.next;
                }
            }

            // 反转
            reverse(head, tail);
            // 观察者指向末尾
            p.next = tail;
            // 更新观察者
            p = head;
            // 更新下一组的head
            head = head.next;
        }

        return dummy.next;
    }
}