网站建设公司swot分析,室内设计者联盟官网,视频怎么转成网址,htaccess wordpress146.LRU缓存
题目链接#xff1a;146.lru-cache
解法#xff1a;
这个题代码量大#xff0c;光看题解就1个小时多了#xff0c;看完写下来花了两小时多...
使用哈希表双向链表来实现LRU缓存的特性#xff0c;即哈希表可以实现get为O(1)复杂度#xff0c;双向链表可以…146.LRU缓存
题目链接146.lru-cache
解法
这个题代码量大光看题解就1个小时多了看完写下来花了两小时多...
使用哈希表双向链表来实现LRU缓存的特性即哈希表可以实现get为O(1)复杂度双向链表可以实现put、remove都是O(1)的复杂度。
代码实现时这里双向链表靠近头部的键值对是最久未使用的而靠近尾部的键值对是最近使用的。也有的实现头部放最近使用的尾部放最久未使用。
而删除最久未使用的node时需要在哈希表和双向链表中都删除那么可以由双向链表得到最久未使用的node从而得到node的key再从哈希表中删除这是哈希表和双向链表之间的联系。
一个技巧是使用dummy虚拟节点有的题解用两个dummy表示首尾节点有的题解只用了一个dummy。个人认为写法要容易理解简洁是其次的要求。两个dummy的写法更好理解。
题解参考labuladong代码多一些但是很清晰然后翻译成了C版本labuladongLRU缓存
边界条件无
时间复杂度对于 put 和 get 都是 O(1)
空间复杂度O(capacity)
class Node {
public:int key, val;Node *pre, *next;Node (int k0, int v0): key(k), val(v), pre(nullptr), next(nullptr) {};
};class DoubleList {
private:Node *head, *tail;int size;public:DoubleList() {head new Node();tail new Node();head-next tail;tail-pre head;size 0;}int getSize() {return size;}// 末尾的node是最近使用的void addLast(Node* x) {x-next tail;x-pre tail-pre;x-next-pre x;x-pre-next x;size;}void remove(Node* x) {x-pre-next x-next;x-next-pre x-pre;size--;}// 开头的node是最久未使用的返回的目的是为了在map中删除Node* removeFirst() {if (head-next tail) return nullptr;Node* first head-next;remove(first);return first;}
};class LRUCache {
private:unordered_mapint, Node* map;DoubleList cache;int cap;private:// 用于get时把node作为最近使用的void makeRecently (int key) {Node* node map[key];cache.remove(node);cache.addLast(node);}void addRecently (int key, int val) {Node* node new Node(key, val);cache.addLast(node);map[key] node;}void deleteKey (int key) {Node* node map[key];cache.remove(node);map.erase(key);delete node;}void removeLeastRecently () {Node* node cache.removeFirst();int key node-key;map.erase(key);delete node;}public:LRUCache(int capacity): cap(capacity){};int get(int key) {// 如果不存在则返回-1if (map.find(key) map.end()) return -1;makeRecently(key);return map[key]-val;}void put(int key, int value) {// 如果存在则先删除再加入if (map.find(key) ! map.end()) {deleteKey(key);addRecently(key, value);return;}// 如果不存在且空间满了则先移除最久未使用if (cap cache.getSize()) {removeLeastRecently();}addRecently(key, value);}
};
333.最大的二分搜索树
题目链接333.largest-bst-subtree
解法
参考题解https://www.cnblogs.com/grandyang/p/5188938.html
这个题有follow up那么首先给出O(n^2)的解法。
每个节点都当做根节点来验证其是否是二叉搜索数。如果当前node是二叉搜索树就记录节点的个数并返回节点个数如果不是二叉搜索树那就验证左右子树是否为二叉搜索树分别记录节点的个数然后取二者中的最大值进行返回。
思路可以说是DFS和分而治之左子树和右子树分别进行DFS。
由于每个节点都要对树遍历一次所以时间复杂度为O(n^2)。
下面是O(n)复杂度的解法。
只允许遍历一次整个二叉树由于满足要求的二叉搜索子树必定是有叶节点的所以思路就是先递归到最左子节点然后逐层往上递归。对于每一个节点都记录当前最大的 BST 的节点数当做为左子树的最大值和做为右子树的最小值。
当每次遇到左子节点不存在或者当前节点值大于左子树的最大值且右子树不存在或者当前节点值小于右子树的最小数时说明 BST 的节点数又增加了一个更新结果及其参数。
如果当前节点不是 BST 的节点那么更新 BST 的节点数 res 为左右子节点的各自的 BST 的节点数的较大值。
这个O(n)的解法实在看得眼花缭乱这次也没有理解得很好。下次再细看了。
边界条件无
时间复杂度O(n)
空间复杂度O(h)树的深度
// O(n^2)的解法
class Solution {
public:int largestBSTSubtree(TreeNode* root) {if (!root) return 0;// 如果root是BST那么左右子树一定是但root一定是比左右子树更大的BST所以直接returnif (isValid(root, INT_MIN, INT_MAX)) return count(root);return max(largestBSTSubtree(root-left), largestBSTSubtree(root-right));}bool isValid(TreeNode* root, int min, int max) {if (!root) return true;if (root-val min || root-val max) return false;// 该节点满足那么继续看左右节点是否满足return isValid(root-left, min, root-val) isValid(root-right, root-val, max);}int count(TreeNode* node) {if (!node) return 0;return count(node-left) count(node-right) 1;}
};
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
// O(n)的解法
class Solution {
public:int largestBSTSubtree(TreeNode* root) {// res中有三个元素: 以当前结点为根结点的树的最小值最大值最大的 BST 子树的结点个数vectorint res helper(root);return res[2];}vectorint helper(TreeNode* node) {if (!node) return {INT_MAX, INT_MIN, 0};vectorint left helper(node-left), right helper(node-right);// 大于左子树的最大值小于右子树的最小值那么是BSTif (node-val left[1] node-val right[0]) {return {min(node-val, left[0]), max(node-val, right[1]), left[2] right[2] 1};} else {// 这里不太好理解这是用于破坏BST规则node-val left[1] node-val right[0]return {INT_MIN, INT_MAX, max(left[2], right[2])};}}
};
621.任务调度器
题目链接task-scheduler
解法
这种题真是奇技淫巧思想确实精妙但是属于脑筋急转弯类型。吐槽一下刷这些题真是浪费青春造孽啊
没啥好说的直接参考题解桶思想
边界条件无
时间复杂度O(nlogn)排序
空间复杂度O(1)
class Solution {
public:int leastInterval(vectorchar tasks, int n) {// 总的任务数int len tasks.size();// 统计每个任务的数量vectorint vec(26);for (char c: tasks) {vec[c-A];}// 按任务数量进行降序排列任务是啥不重要了sort(vec.begin(), vec.end(), [](int x, inty) {return x y;});// 统计任务数量最多且数量相等的任务有多少个int cnt 1;while (cnt vec.size() vec[cnt] vec[0]) {cnt;}return max(len, (vec[0]-1)*(n1)cnt);}
};
