【每日刷题】Day184
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 1700. 无法吃午餐的学生数量 - 力扣（LeetCode）
2. 146. LRU 缓存 - 力扣（LeetCode）
1. 1700. 无法吃午餐的学生数量 - 力扣（LeetCode）
//思路：队列
//本题要点在于如何判断剩下的学生无法吃午餐，其实无非就是两种情况：
//当满足这两种情况的任意一种时，剩余的学生就无法吃到午餐。
class Solution {
int flag = 0;
public:
int countStudents(vector<int>& students, vector<int>& sandwiches)
{
int sum = 0;//这里用sum变量来判断两种情况
queue<int> student;
queue<int> sandwiche;
for(auto& i : students)
{
student.push(i);
sum+=i;
}
for(auto& i : sandwiches)
sandwiche.push(i);
while(true)
{
if(student.front()==sandwiche.front())
{
sum-=student.front();
student.pop();
sandwiche.pop();
}
else
{
int tmp = student.front();
student.pop();
student.push(tmp);
}
if(student.empty()) break;
//sum==(sandwiche.front()+student.size()) 判断的是情况①
//sum<sandwiche.front() 判断的是情况②
if((sum==(sandwiche.front()+student.size()))||sum<sandwiche.front())
break;
}
return student.size();
}
};
2. 146. LRU 缓存 - 力扣（LeetCode）
//思路：双向链表+哈希表
//哈希表用于查询 key 是否已经存储；双向链表用于进行插入节点以及更新使用过的节点：保证最久没有使用过的节点处于链表末尾
class LRUCache
{
struct ListNode//链表节点
{
int _key,_val;
ListNode* _next;
ListNode* _prev;
ListNode():_key(-1),_val(-1),_next(nullptr),_prev(nullptr)
{}
ListNode(int key,int val):_key(key),_val(val),_next(nullptr),_prev(nullptr)
{}
};
public:
LRUCache(int capacity)
{
_head = new ListNode();
_tail = new ListNode();
_head->_next = _tail;//头尾节点采用 "哨兵位" 形式
_tail->_prev = _head;
_capacity = capacity;
}
int get(int key)
{
if(ma.count(key))//如果要获取的key存在，则返回对应的val
{
ListNode* curr = ma[key];
DeleteNode(curr);
MoveToHead(curr);//同时，将节点更新到链表头部，表示当前节点为最新访问过的
return ma[key]->_val;
}
return -1;//不存在则返回-1
}
void put(int key, int value)
{
if(!ma.count(key))//不存在key，新插入节点
{
ListNode* newnode = new ListNode(key,value);
MoveToHead(newnode);//同时更新节点到链表头部，表示当前节点为最新访问过的
ma[key] = newnode;//写入哈希表中
_size++;//更新当前队列长度
}
else//存在key，则更新val
{
ListNode* curr = ma[key];//获取已经存在的key对应的节点
curr->_val = value;
DeleteNode(curr);//因为key对应的节点已经存在于队列中，因此更新时需要将原本旧节点所在位置的前后节点更新
MoveToHead(curr);//将节点更新到链表头部
}
if(_size>_capacity)//超出容量，删除尾部最久未使用的key对应的节点
{
ListNode* tail = GetTail();//因为使用的是"哨兵位"模式，因此tail->_prev指向的就是链表尾部节点
ma.erase(tail->_key);
DeleteNode(tail);
delete tail;
_size--;
}
}
//获取尾部节点：最久未访问的节点
ListNode* GetTail()
{
return _tail->_prev;
}
//删除节点
void DeleteNode(ListNode* curr)
{
curr->_prev->_next = curr->_next;
curr->_next->_prev = curr->_prev;
}
//将节点更新到链表头部
void MoveToHead(ListNode* curr)
{
curr->_prev = _head;
curr->_next = _head->_next;
_head->_next->_prev = curr;
_head->_next = curr;
}
private:
int _capacity = 0;
int _size = 0;
ListNode* _head;
ListNode* _tail;
unordered_map<int,ListNode*> ma;//哈希表 key 映射 结点指针
};
