LC中经典数据结构题集

1206. 设计跳表——对链表的二分优化

class Skiplist {
public:

    struct Node {
        // 向右向下指针
        Node *right, *down;
        int val;
        Node(Node *right, Node *down, int val): right(right), down(down), val(val) {}
    }*head;

    const static int MAX_LEVEL = 32;
    vector<Node*> pathList;

    Skiplist() {
        head = new Node(NULL, NULL, -1);
        pathList.reserve(MAX_LEVEL);
    }
    
    bool search(int target) {
        Node *p = head;
        while (p) {
            // 左右寻找目标区间
            while (p->right && p->right->val < target) {
                p = p->right;
            }
            // 没找到目标值，则继续往下走
            if (!p->right || p->right->val > target) {
                p = p->down;
            } else {
                //找到目标值，结束
                return true;
            }
        }
        return false;
    }
    
    void add(int num) {
        //从上至下记录搜索路径
        pathList.clear();
        Node *p = head;
        // 从上到下去搜索 次小于num的 数字，等于就是另外一种实现里的 prevs
        while (p) {
            // 向右找到次小于num的p
            while(p->right && p->right->val < num) {
                p = p->right;
            }
            pathList.push_back(p);
            p = p->down;
        }
        bool insertUp = true;
        Node *downNode = NULL;
        // 从下至上搜索路径回溯，50%概率
        // 这里实现是会保证不会超过当前的层数的，然后靠头结点去额外加层， 即每次新增一层
        while(insertUp && pathList.size() > 0) {
            Node *insert = pathList.back();
            pathList.pop_back();
            // add 新节点
            insert->right = new Node(insert->right, downNode, num);
            // 把新结点赋值为downNode
            downNode = insert->right;
            // 50%
            insertUp = (rand() & 1) == 0;
        }
        // 新增一层
        if (insertUp) {
            head = new Node(new Node(NULL, downNode, num), head, -1);
        }
    }
    
    bool erase(int num) {
        Node *p = head;
        bool seen = false;
        while (p) {
            // 当前层向右找到次小的点
            while (p->right && p->right->val < num) {
                p = p->right;
            }
            // 无效点，或者 太大， 则到下一层去
            if (!p->right || p->right->val > num) {
                p = p->down;
            } else {
                // 搜索到目标结点，进行删除操作，结果记录为true
                // 继续往下层搜索，删除一组目标结点
                seen = true;
                p->right = p->right->right;
                p = p->down;
            }
        }
        return seen;
    }
};

/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */

460. LFU 缓存——双链表+双哈希表

class LFUCache {
public:

    struct Node {
        Node *left, *right;
        int key, val;
        Node (int _key, int _val) {
            key = _key, val = _val;
            left = right = NULL;
        }
    };

    struct Block {
        Block *left, *right;
        Node *head, *tail;
        int cnt;
        Block(int _cnt) {
            cnt = _cnt;
            left = right = NULL;
            head = new Node(-1, -1), tail = new Node(-1, -1);
            head->right = tail, tail->left = head;
        }
        ~Block() {
            delete head;
            delete tail;
        }
        void insert(Node *p) {
            p->right = head->right;
            head->right->left = p;
            head->right = p;
            p->left = head;
        }
        void remove(Node *p) {
            p->right->left = p->left;
            p->left->right = p->right;
        }   
        bool empty() {
            return head->right == tail;
        }
    }*head, *tail;

    int n;
    unordered_map<int, Node*> hash_node;
    unordered_map<int, Block*> hash_block;

    LFUCache(int capacity) {
        n = capacity;
        head = new Block(0), tail = new Block(INT_MAX);
        head->right = tail, tail->left = head;
    }
    
    void insert(Block *p) {
        auto cur = new Block(p->cnt + 1);
        cur->right = p->right;
        p->right->left = cur;
        cur->left = p;
        p->right = cur;
    }

    void remove(Block *p) {
        p->right->left = p->left;
        p->left->right = p->right;
        delete p;
    }

    int get(int key) {
        if (hash_block.count(key) == 0) return -1;  
        auto block = hash_block[key];
        auto node = hash_node[key];
        block->remove(node);
        if (block->right->cnt != block->cnt + 1) insert(block);
        block->right->insert(node);
        hash_block[key] = block->right;
        if (block->empty()) remove(block);
        return node->val;
    }
    
    void put(int key, int value) {
        if (!n) return ;
        if (hash_block.count(key)) {
            auto node = hash_node[key];
            node->val = value;
            get(key);
        } else {    
            if (hash_block.size() == n) {
                auto p = head->right->tail->left;
                head->right->remove(p);
                if (head->right->empty()) remove(head->right);
                hash_block.erase(p->key);
                hash_node.erase(p->key);
                delete p;
            }
            auto p = new Node(key, value);
            if (head->right->cnt > 1) insert(head);
            head->right->insert(p);
            hash_block[key] = head->right;
            hash_node[key] = p;
        }
    }
};

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

146. LRU 缓存——链表+哈希表

class LRUCache {
public:

    struct Node {
        int key, val;
        Node *next, *prev;
        Node(int _key, int _val): key(_key), val(_val), next(nullptr), prev(nullptr) {};
    } *L, *R;

    unordered_map<int, Node*> hash; 
    int n;

    LRUCache(int capacity) {
        n = capacity;
        L = new Node(-1, -1), R = new Node(-1, -1);
        L->next = R, R->prev = L;
    }

    void insert_node(Node *p) {
        p->next = L->next, L->next->prev = p, p->prev = L, L->next = p;
    }

    void delete_node(Node *p) {
        p->next->prev = p->prev, p->prev->next = p->next;
    }
    
    int get(int key) {
        if (hash.count(key)) {
            auto p = hash[key];
            delete_node(p);
            insert_node(p);
            return p->val;
        } else {
            return -1;
        }
    }
    
    void put(int key, int value) {
        if (hash.count(key)) {
            auto p = hash[key];
            delete_node(p);
            p->val = value;
            insert_node(p);
        } else {
            if (n == hash.size()) {
                auto q = R->prev;
                delete_node(q);
                hash.erase(q->key);
            }
            auto p = new Node(key, value);
            hash[key] = p;
            insert_node(p);
        }
    }
};

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

707. 设计链表——链表

class MyLinkedList {
public:

    struct Node {
        int val;
        Node *next;
        Node (int _val) : val(_val), next(NULL) {}
    }*head;

    MyLinkedList() {
        head = NULL;
    }
    
    int get(int index) {
        if (index < 0) return -1;
        auto p = head;
        for (int i = 0; i < index && p; i ++) p = p->next;
        if (!p) return -1;
        return p->val; 
    }
    
    void addAtHead(int val) {
        auto cur = new Node(val);
        cur->next = head;
        head = cur;
    }
    
    void addAtTail(int val) {
        if (!head) head = new Node(val);
        else {
            auto p = head;
            while (p->next) p = p->next;
            p->next = new Node(val);
        }
    }
    
    void addAtIndex(int index, int val) {
        if (index <= 0) addAtHead(val);
        else {
            int len = 0;
            for (auto p = head; p; p = p->next) len ++;
            if (index == len) addAtTail(val);
            else if (index < len) {
                auto p = head;
                for (int i = 0; i < index - 1; i ++) p = p->next;
                auto cur = new Node(val);
                cur->next = p->next;
                p->next = cur;
            }
        }
    }
    
    void deleteAtIndex(int index) {
        int len = 0;
        for (auto p = head; p; p = p->next) len ++;
        if (index >= 0 && index < len) {
            if (!index) head = head->next;
            else {
                auto p = head;
                for (int i = 0; i <index - 1; i ++) p = p->next;
                p->next = p->next->next;
            }
        } 
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

705. 设计哈希集合——哈希set

const int N = 1997;
class MyHashSet {
public:
    vector<int> h[N];

    MyHashSet() {

    }
    
    int find(vector<int> &h, int key) {
        for (int i = 0; i < h.size(); i ++) 
            if (h[i] == key) return i;
        return -1;
    }

    void add(int key) {
        int t = key % N;
        int k = find(h[t], key);
        if (k == -1) h[t].push_back(key);
    }
    
    void remove(int key) {
        int t = key % N;
        int k = find(h[t], key);
        if (k != -1) h[t].erase(h[t].begin() + k);
    }
    
    bool contains(int key) {    
        int t = key % N;
        int k = find(h[t], key);
        return k != -1;
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

706. 设计哈希映射——HashMap

class MyHashMap {
public:

    struct Node {
        int key, val;
        Node *next;
        Node (int _key, int _val): key(_key), val(_val), next(nullptr) {}
    };

    const int N = 1331;
    vector<Node*> data;

    MyHashMap() {
        data = vector<Node*>(N, nullptr);
    }

    void append(int key, int value) {
        int idx = key % N;
        Node *pre = data[idx];
        Node *cur = pre;
        while (cur != nullptr) {
            if (cur->key == key) {
                cur->val = value;
                return ;
            }
            pre = cur;
            cur = cur->next;
        }
        pre->next = new Node(key, value);
    }

    void put(int key, int value) {
        int idx = key % N;
        if (data[idx] == nullptr) {
            data[idx] = new Node(key, value);
        } else {
            append(key, value);
        }
    }
    
    int get(int key) {
        int idx = key % N;
        Node *cur = data[idx];
        if (!cur) return -1;
        else {
            while (cur != nullptr) {
                if (cur->key == key) return cur->val;
                cur = cur->next;
            }
        }
        return -1;
    }
    
    void remove(int key) {
        int idx = key % N;
        Node *cur = data[idx];
        Node *pre = cur;
        while (cur != nullptr) {
            if (cur->key == key) {
                if (pre == cur) data[idx] = cur->next;
                else pre->next = cur->next;
                return ;
            }
            pre = cur;
            cur = cur->next;
        }
    }
};

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

706. 设计哈希映射——HashMap

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


class HashMap {
public: 

	struct Node {
		int key, val;
		Node *next;
		Node (int _key, int _val): key(_key), val(_val), next(nullptr) {} 
	};
		
	const int N = 131;
	vector<Node*> data;
		
	HashMap() {
		data = vector<Node*>(N, nullptr);
	}
	
	void append(int key, int value) {
		int idx = key % N;
		Node *pre = data[idx];
		Node *cur = pre;
		while (cur != nullptr) {
			if (cur->key == key) {
				cur->val = value;
				return ;
			}
			pre = cur;
			cur = cur->next;
		}
		pre->next = new Node(key, value);
	}
	
	void put(int key, int value) {
		int idx = key % N;
		if (data[idx] == nullptr) {
			data[idx] = new Node(key, value);
		} else {
			append(key, value);
		}
	}
	
	int get(int key) {
		int idx = key % N;
		Node *cur = data[idx];
		if (cur == nullptr) {
			return -1;
		} else {
			while (cur != nullptr) {
				if (cur->key == key) {
					return cur->val;
				}
				cur = cur->next;
			}
		}
		return -1;
	}
	
	void remove(int key) {
		int idx = key % N;
		Node *pre = data[idx];
		Node *cur = pre;
		while (cur != nullptr) {
			if (cur->key == key) {
				if (pre == cur) data[idx] = cur->next;
				else pre->next = cur->next;
				return ;
			}
			pre = cur;
			cur = cur->next;
		}
	}
};

int main() {
	HashMap* obj = new HashMap();
	obj->put(1, 2);
	int param = obj->get(1);
	cout << param << endl;
	obj->remove(1);	
	param = obj->get(1);
	cout << param << endl;
	return 0;
}

208. 实现 Trie ——前缀树

class Trie {
public:

    struct Node {
        bool is_end;
        Node *son[26];
        Node() {
            is_end = false;
            for (int i = 0; i < 26; i ++) son[i] = NULL;
        }
    } *root;

    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        auto p = root;
        for (auto &c: word) {
            int u = c - 'a';
            if (p->son[u] == NULL) p->son[u] = new Node();
            p = p->son[u];
        }
        p->is_end = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        auto p = root;
        for (auto &c: word) {
            int u = c - 'a';
            if (p->son[u] == NULL) return false;
            p = p->son[u];
        }
        return p->is_end;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        auto p = root;
        for (auto &c: prefix) {
            int u = c - 'a';
            if (p->son[u] == NULL) return false;
            p = p->son[u];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */