当前位置:网站首页>腾讯面试算法题
腾讯面试算法题
2022-07-06 09:29:00 【狗蛋儿l】
描述
设计LRU(最近最少使用)缓存结构,该结构在构造时确定大小,假设大小为K,并有如下两个功能
set(key, value):将记录(key, value)插入该结构
get(key):返回key对应的value值
提示:
1.某个key的set或get操作一旦发生,认为这个key的记录成了最常使用的,然后都会刷新缓存。
2.当缓存的大小超过K时,移除最不经常使用的记录。
3.输入一个二维数组与K,二维数组每一维有2个或者3个数字,第1个数字为opt,第2,3个数字为key,value
若opt=1,接下来两个整数key, value,表示set(key, value)
若opt=2,接下来一个整数key,表示get(key),若key未出现过或已被移除,则返回-1
对于每个opt=2,输出一个答案
4.为了方便区分缓存里key与value,下面说明的缓存里key用""号包裹
进阶:你是否可以在O(1)的时间复杂度完成set和get操作
示例1
输入:
[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3
返回值:
[1,-1]
说明:
[1,1,1],第一个1表示opt=1,要set(1,1),即将(1,1)插入缓存,缓存是{“1”=1}
[1,2,2],第一个1表示opt=1,要set(2,2),即将(2,2)插入缓存,缓存是{“1”=1,“2”=2}
[1,3,2],第一个1表示opt=1,要set(3,2),即将(3,2)插入缓存,缓存是{“1”=1,“2”=2,“3”=2}
[2,1],第一个2表示opt=2,要get(1),返回是[1],因为get(1)操作,缓存更新,缓存是{“2”=2,“3”=2,“1”=1}
[1,4,4],第一个1表示opt=1,要set(4,4),即将(4,4)插入缓存,但是缓存已经达到最大容量3,移除最不经常使用的{“2”=2},插入{“4”=4},缓存是{“3”=2,“1”=1,“4”=4}
[2,2],第一个2表示opt=2,要get(2),查找不到,返回是[1,-1]
示例2
输入:
[[1,1,1],[1,2,2],[2,1],[1,3,3],[2,2],[1,4,4],[2,1],[2,3],[2,4]],2
返回值:
[1,-1,-1,3,4]
#include<unordered_map>
class Solution {
public:
/**
* lru design
* @param operators int整型vector<vector<>> the ops
* @param k int整型 the k
* @return int整型vector
*/
int capacity;
list<pair<int,int>> lrulst;
unordered_map<int,list<pair<int,int>>::iterator > lruhash;
vector<int> LRU(vector<vector<int> >& operators, int k) {
vector<int> result; capacity = k;
result.reserve(operators.size());
if(k!=0)
{
for(const vector<int>& opt: operators)
{
if(opt[0]==1) set(opt[1],opt[2]);
else if(opt[0]==2) result.push_back(get(opt[1]));
}
}
return result;
}
void set(int key,int val){
auto iter = lruhash.find(key);
if(iter == lruhash.end())
{
if(capacity == lrulst.size())
{
lruhash.erase(lrulst.back().first);
lrulst.pop_back();
}
}
else lrulst.erase(iter->second);
lrulst.push_front({key,val});
lruhash[key] = lrulst.begin();
}
int get(int key){
auto iter = lruhash.find(key);
if(iter == lruhash.end()) return -1;
int val = iter->second->second;
lrulst.erase(iter->second);
lrulst.push_front(*iter->second);
return val;
}
};
链表翻转
题目:链表翻转。给出一个链表和一个数k,比如链表1→2→3→4→5→6,k=2,翻转后2→1→4→3→6→5,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→5→6,用程序实现Node* RotateList(Node* list, size_t k). 提示:这个题是链表逆置的升级变型。
算法思想:
这个题是链表逆置的升级变型,我们可以将此链表先按照以k为单位分为若干个小链表,再将小链表进行翻转,最后将小链表链接起来,依次进行,当小链表的长度小于k时,将其直接连接在链表后面即可。
代码实现:
#include <iostream>
#include <stdio.h>
#include <cstring>
typedef int DataType;
typedef struct ListNode
{
DataType _data;
struct ListNode* _next;
}Node,*pNode,*pList;
void Init(pList* pplist)
{
assert(pplist);
*pplist = NULL;
}
pNode BuyNode(DataType x)
{
pNode pnode = (pNode)malloc(sizeof(Node));
if (pnode == NULL)
{
perror("malloc");
return NULL;
}
pnode->_data = x;
pnode->_next = NULL;
return pnode;
}
void Push(pList* pplist,DataType x)
{
pNode NewNode = BuyNode(x);
if (*pplist == NULL)
{
*pplist = NewNode;
}
else
{
pNode cur = *pplist;
while (cur->_next)
{
cur = cur->_next;
}
cur->_next = NewNode;
}
}
pNode Reverse(pList plist)
{
pNode cur = plist;
if(cur == NULL)
return NULL;
if (cur->_next)
{
Reverse(cur->_next);
}
printf("%d ", cur->_data);
return cur;
}
pNode getLastNode(pList plist)
{
pNode pHead = plist;
while (pHead->_next != NULL)
{
pHead = pHead->_next;
}
return pHead;
}
pNode SwapListByK(pList plist, size_t k)
{
pNode pnode = plist;
pNode pNewNode;
pNode pNextNode;
pNode LastNode = NULL;
pNode tmp = NULL;
size_t pos;
if (k <= 1)
return plist;
plist = NULL;
while (pnode)
{
pos = 0;
pNewNode = pnode;
while (pnode && pos < k - 1)
{
tmp = pNewNode;
pnode = pnode->_next;
if (pnode == NULL)
{
break;
}
pos++;
}
if (pnode == NULL)
{
return tmp; //如果需要反转的不足k个元素,则直接连在后面
}
if (pnode)
{
pNextNode = pnode->_next;
pnode->_next = NULL;
if (LastNode != NULL)
{
LastNode->_next = NULL;
}
pNewNode = Reverse(pNewNode);
if (plist == NULL)
plist = pNewNode;
else
LastNode->_next = pNewNode;
pnode = getLastNode(pNewNode);
pnode->_next = pNextNode;
LastNode = pnode;
pnode = pNextNode;
}
else
{
break;
}
}
return pnode;
}
void Printf(pList plist)
{
pList cur = plist;
while (cur)
{
printf("%d ", cur->_data);
cur = cur->_next;
}
printf(" NULL\n");
}
void Test()
{
pList plist;
Init(&plist);
Push(&plist, 1);
Push(&plist, 2);
Push(&plist, 3);
Push(&plist, 4);
Push(&plist, 5);
Push(&plist, 6);
Push(&plist, 7);
Printf(plist);
pNode ret = SwapListByK(plist, 3);
Printf(ret);
}
边栏推荐
- useEffect,函数组件挂载和卸载时触发
- Kubernetes集群部署
- 875. 爱吃香蕉的珂珂 - 力扣(LeetCode)
- Chapter 5 detailed explanation of consumer groups
- Effet d'utilisation, déclenché lorsque les composants de la fonction sont montés et déchargés
- <li>圆点样式 list-style-type
- Share an example of running dash application in raspberry pie.
- Chapter III principles of MapReduce framework
- QT按钮点击切换QLineEdit焦点(含代码)
- Li Kou - 298th weekly match
猜你喜欢
FLV格式详解
Chapter 5 yarn resource scheduler
解决Intel12代酷睿CPU单线程只给小核运行的问题
Chapter 6 rebalance details
浏览器打印边距,默认/无边距,占满1页A4
Chapter III principles of MapReduce framework
Click QT button to switch qlineedit focus (including code)
Pull branch failed, fatal: 'origin/xxx' is not a commit and a branch 'xxx' cannot be created from it
SF smart logistics Campus Technology Challenge (no T4)
Some problems encountered in installing pytorch in windows11 CONDA
随机推荐
Research Report of desktop clinical chemical analyzer industry - market status analysis and development prospect prediction
生成随机密码/验证码
第 300 场周赛 - 力扣(LeetCode)
Some problems encountered in installing pytorch in windows11 CONDA
第三章 MapReduce框架原理
VMware Tools和open-vm-tools的安装与使用:解决虚拟机不全屏和无法传输文件的问题
QT按钮点击切换QLineEdit焦点(含代码)
Codeforces Round #798 (Div. 2)A~D
Spark的RDD(弹性分布式数据集)返回大结果集
Tert butyl hydroquinone (TBHQ) Industry Research Report - market status analysis and development prospect forecast
China double brightening film (dbef) market trend report, technical dynamic innovation and market forecast
Codeforces Round #801 (Div. 2)A~C
QT有关QCobobox控件的样式设置(圆角、下拉框,向上展开、可编辑、内部布局等)
Codeforces - 1526C1&&C2 - Potions
Double specific tyrosine phosphorylation regulated kinase 1A Industry Research Report - market status analysis and development prospect prediction
第2章 HFDS的Shell操作
第5章 消费者组详解
Chapter 5 yarn resource scheduler
input 只能输入数字,限定输入
Is the sanic asynchronous framework really so strong? Find truth in practice