当前位置：首页 > news >正文

C++ 后端面试必刷大厂算法题（附代码实现）第一期

news 2026/6/6 7:19:05

C++ 后端面试必刷大厂算法题

文章目录

C++ 后端面试必刷大厂算法题
一、3.无重复字符的最长子串
二、146. LRU 缓存
三、
四、
五、
六、
七、
八、
九、
十、
十一、
十二、
十三、
十四、
十五、
十六、
十七、
十八、
十九、
二十、
总结

一、3.无重复字符的最长子串

做到吐！

代码如下（示例）：

class Solution{public:intlengthOfLongestSubstring(string s){intn=s.size(),left=0,right=0,ret=0;inthash[128];while(right<n){hash[s[right]]++;while(hash[s[right]]>1){hash[s[left++]]--;}ret=max(ret,right-left+1);right++;}returnret;}};

二、146. LRU 缓存

代码如下（示例）：

// 官方答案structDLinkedNode{intkey,value;DLinkedNode*prev;DLinkedNode*next;};class LRUCache{private:unordered_map<int,DLinkedNode*>cache;DLinkedNode*head;DLinkedNode*tail;intsize;intcapacity;public:LRUCache(int_capacity):capacity(_capacity),size(0){// 使用伪头部和伪尾部节点head=newDLinkedNode();tail=newDLinkedNode();head->next=tail;tail->prev=head;}intget(intkey){if(!cache.count(key)){return-1;}// 如果 key 存在，先通过哈希表定位，再移到头部DLinkedNode*node=cache[key];moveToHead(node);returnnode->value;}voidput(intkey,intvalue){if(!cache.count(key)){// 如果 key 不存在，创建一个新的节点DLinkedNode*node=newDLinkedNode(key,value);// 添加进哈希表cache[key]=node;// 添加至双向链表的头部addToHead(node);++size;if(size>capacity){// 如果超出容量，删除双向链表的尾部节点DLinkedNode*removed=removeTail();// 删除哈希表中对应的项cache.erase(removed->key);// 防止内存泄漏delete removed;--size;}}else{// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部DLinkedNode*node=cache[key];node->value=value;moveToHead(node);}}voidaddToHead(DLinkedNode*node){node->prev=head;node->next=head->next;head->next->prev=node;head->next=node;}voidremoveNode(DLinkedNode*node){node->prev->next=node->next;node->next->prev=node->prev;}voidmoveToHead(DLinkedNode*node){removeNode(node);addToHead(node);}DLinkedNode*removeTail(){DLinkedNode*node=tail->prev;removeNode(node);returnnode;}};