秋招突击——7/8——复习{快速排序模版题——数组中第K大的元素、LRU缓存的实现}——新作{单调栈模版题——每日温度}
文章目录
- 引言
- 复习
- 快速排序模版题——数组中第K大的元素
- 回顾实现
- LRU缓存的实现
- 个人实现
- 参考实现
- 新作
- 栈——每日温度
- 个人实现
- 参考实现
- 总结
引言
- 今天又是新的一周了，今天继续加油，起的挺早的，背完书睡了一会，整的有点懵，先把今天的算法题做了！
- 不知道今天字节一面，能不能通过，不过据说好难呀，字节是大厂里面最难面试的！
- 看了一下他的内容，感觉要求还是很高的，重点要求高可用高并发，尤其是消息队列那一部分，什么kafka这些暂时还不会，权当接受鞭笞了吧！
- 一紧张，一个上午啥也不想干，就想停在这里，这样可不行呀！
复习
快速排序模版题——数组中第K大的元素
第一次做题的链接
回顾实现
- 规定了时间复杂度是O(n)，所以这里是基于快排实现的，快排的时间复杂度是O（nlogn），但是这里每次都取一半，最终的结果逼近2n，就是O（n）时间复杂度，这里直接使用快排的模板去做。
- 实现如下
模板记录
- 这里的模板写错了，应该是以j作为分割线，因为最终肯定是j移动到中间的
- 进行交换的之后，要判定i和j之间的相对关系
class Solution { public: int quicksort(vector &nums,int l,int r,int k){ if(l >= r) return nums[k]; int i - l - 1 ,j = r + 1 ,x =(l + r) >>1; while(i nums[x]); swap(nums[i],nums[j]); } quicksort(nums,l,x - 1,k),quicksort(nums,x + 1,r,k); } int findKthLargest(vector& nums, int k) { return quicksort(nums,0,nums.size() - 1,k); } }; void quick_sort(int q[],int l,int r){ if(l >= r) return ; // 确定中间值、左边界、右边界 // 中间元素不参加排序，i是从x的左侧一个开始，j是从x的右侧开始 int i = l - 1,j = r + 1,x = q[l + r >> 1]; while(i x); if(i这个模板有几个特征需要注意
- 如果数量是奇数的话，最终j就是第k个已经排序好的元素
- 如果数量是偶数的话，左右边界会互换，然后左右边界并不一定是已经排序好的元素，所以要始终进行重排序
注意，是第k大的元素，就是要从大到小进行排序，这里搞错了，搞反了！！
class Solution { public: int quicksort(vector &nums,int l,int r,int k){ if(l == r) return nums[k]; int i = l - 1 ,j = r + 1 ,x =nums[(l + r) >>1]; while(i x); do j --;while(nums[j]LRU缓存的实现
- 第一次完成链接
- 题目链接
注意
- 一个人是如何在一个地方跌倒了两次的，命运总是如此巧合，在腾讯的时候就面试过这道题，然后在字节的时候又来了，太真实了！兄弟！
- 没必要了，这道题你怎么都得背下来，不仅仅是背下来，你还得在clion中再写一遍！从头写一遍！
个人实现
- 今天手撕部分主要有以下两个缺点
- leetcode官网用习惯了，连类的构造函数都不会写了，正常手撕代码题，并不会像leetcode一样，给你打好一个框架
- 我的命名方式太差了，居然和平常些算法题一样，怎么简单怎么来了，完全没有意义！不要省这个时间，然后键盘好好用用！老师打错字，打慢点没事的！
下面是我个人实现
- 上一次没有好好做，然后这一次做了才发现一个问题，就是没有办法好好确认最后一个节点的指针的坐标，所以就没有办法进行节点清除
- 很多地方，写的都是不对的，有很大的问题，并没有判定是否为空！不然就是非法内存访问了！
class LRUCache { public: struct Node{ int value; Node* pre; Node* next; Node(int v):value(v),pre(nullptr),next(nullptr){}; }; int capacity; int cur_capacity; unordered_map dict; Node* dummy; Node* tail; LRUCache(int capacity){ this->capacity = capacity; this->cur_capacity = 0; this->dummy = new Node(-1); this->tail = dummy; } void moveFirst(Node* node_move){ // remove the node_move in the list if(node_move->next) node_move->next->pre = node_move->pre; node_move->pre->next = node_move->next; // move the node_move to first node_move->pre = dummy; dummy->next = node_move; Node* temp = dummy->next; if(temp){ node_move->next = temp; temp->pre = node_move; } } int get(int key){ // analysis the key exists if(dict.count(key) == 0) return -1; // move the Node to the first moveFirst(dict[key]); return dict[key]->value; } void put(int key,int value){ // judge the whether the key exists if(dict.count(key) == 0){ // the key does not exists dict[key] = new Node(value); if(cur_capacity == 0) tail = dict[key]; // the capacity is not full if(cur_capacity next = dummy->next; dict[key]->pre = dummy; dummy->next = dict[key]; if(dummy->next) dummy->next->pre = dict[key]; cur_capacity ++; }else{ // the cache is full ,remove the tail node; tail = tail->pre; delete tail->next; } }else{ dict[key]->value = value; moveFirst(dict[key]); } } }; /** * 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); */总结
- 这里写的真的是糟糕，有几个地方是有问题的，具体以下几个部分
- 指针那里的操作还是有很大的问题，不是不理解，是感觉自己不规范，每次都忘记判定下一个next指针是否为空，然后做了很多不必要的判断
- 第二个就是，命名也没有很规范
参考实现
- 这里的思路基本上是一致的，主要是看看他怎么实现删除最后一个节点的，以及如何维护不同指针的！
#include #include using namespace std; class LRUCache{ public: struct Node{ // int value; 多个变量，同类型，同行进行命名 int key,val; Node *left,*right; // 指针的命名这里也是有问题的，就是 // Node* right; // Node(int v):value(v),pre(nullptr),next(nullptr){}; Node(int _key,int _val):key(_key),val(_val),left(NULL),right(NULL){}; } *L ,*R; unordered_map dict; int num;// 这个cache的容量大小 LRUCache(int capacity){ num = capacity; // 同时建立头节点和尾节点，这样能够防止空指针，比我的高明多了 L = new Node(-1,-1),R = new Node(-1,-1); L->right = R,R->left = L; } void insert(Node *p){ // insert new node to the first // assign the left and right point of the node p->right = L->right; p->left = L; // assign the left the node L->right->left = p; L->right = p; } void remove(Node *p){ // remove the final node p->right->left = p->left; p->left->right = p->right; } int get(int key){ // analysis the key exists if(dict.count(key) == 0) return -1; // remove the node and insert the node again auto p = dict[key]; remove(p); insert(p); return p->val; } void put(int key,int value){ // judge the whether the key exists if(dict.count(key) == 0){ // judge the size of cache by the dict if(dict.size() == num){ // the cache is full auto p = R->left; remove(p); dict.erase(key); delete p; } // insert new node to cache auto p = new Node(key,value); insert(p); dict[key] = p; }else{ auto p = dict[key]; p->val = value; // refresh the node access time remove(p); insert(p); } } }; int main(){ LRUCache lru(2) ; lru.put(1,3); lru.put(1,4); lru.put(1,5); cout // 获取程序开始时间 clock_t start = clock(); // 模拟一些操作 for (volatile int i = 0; i left->right = p->right; } int get(int key){ // analysis the key exists if(dict.count(key) == 0) return -1; auto p = dict[key]; p->useTime = clock(); remove(p); // judge whether the node exists if((clock() - p->useTime) > duraTime) { delete p; dict.erase(key); return -1; } // remove the node and insert the node again insert(p); return p->val; } void put(int key,int value){ // judge the whether the key exists if(dict.count(key) == 0){ // judge the size of cache by the dict if(dict.size() == num){ // the cache is full auto p = R->left; remove(p); dict.erase(key); delete p; } // insert new node to cache auto p = new Node(key,value); p->useTime = clock(); insert(p); dict[key] = p; }else{ auto p = dict[key]; p->val = value; p->useTime = clock(); // refresh the node access time remove(p); insert(p); } } }; int main(){ LRUCache lru(2,2000000.00) ; lru.put(1,3); lru.put(1,4); lru.put(1,5); cout class Node { int key, val; Node left, right; long useTime; Node(int _key, int _val) { key = _key; val = _val; left = null; right = null; useTime = 0; } } private Node L, R; private Map num = capacity; duraTime = duration; // assign the life of the node // 同时建立头节点和尾节点，这样能够防止空指针，比我的高明多了 L = new Node(-1, -1); R = new Node(-1, -1); L.right = R; R.left = L; dict = new HashMap // insert new node to the first // assign the left and right point of the node p.right = L.right; p.left = L; // assign the left the node L.right.left = p; L.right = p; // refresh the StartTiem p.useTime = System.currentTimeMillis(); } private void remove(Node p) { // remove the final node p.right.left = p.left; p.left.right = p.right; } public int get(int key) { // analysis the key exists if (!dict.containsKey(key)) return -1; Node p = dict.get(key); p.useTime = System.currentTimeMillis(); remove(p); // judge whether the node exists if ((System.currentTimeMillis() - p.useTime) duraTime) { dict.remove(key); return -1; } // remove the node and insert the node again insert(p); return p.val; } public void put(int key, int value) { // judge the whether the key exists if (!dict.containsKey(key)) { // judge the size of cache by the dict if (dict.size() == num) { // the cache is full Node p = R.left; remove(p); dict.remove(p.key); } // insert new node to cache Node p = new Node(key, value); p.useTime = System.currentTimeMillis(); insert(p); dict.put(key, p); } else { Node p = dict.get(key); p.val = value; p.useTime = System.currentTimeMillis(); // refresh the node access time remove(p); insert(p); } } public static void main(String[] args) { LRUCache lru = new LRUCache(2, 2000000.00); lru.put(1, 3); lru.put(1, 4); lru.put(1, 5); System.out.println(lru.get(1)); // 应该打印 5 lru.put(4, 5); System.out.println(lru.get(3)); // 应该打印 -1 因为 key 3 不存在 } } public: vector int m = temp.size(); vector // compare the top elements while(!upst.empty() && temp[i] temp[upst.top()]){ f[upst.top()] = i - upst.top(); upst.pop(); } upst.push(i); } return f; } }; public: vector int m = temp.size(); vector while(!upst.empty() && temp[i] = temp[upst.top()]) upst.pop(); if(upst.size()) f[i] = upst.top() - i; upst.push(i); } return f; } };
- 这里的思路基本上是一致的，主要是看看他怎么实现删除最后一个节点的，以及如何维护不同指针的！
- 这里写的真的是糟糕，有几个地方是有问题的，具体以下几个部分
- 今天手撕部分主要有以下两个缺点
文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。
