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;}};三、
代码如下（示例）：
四、
代码如下（示例）：
五、
代码如下（示例）：
六、
代码如下（示例）：
七、
代码如下（示例）：
八、
代码如下（示例）：
九、
代码如下（示例）：
十、
代码如下（示例）：
十一、
代码如下（示例）：
十二、
代码如下（示例）：
、
十三、
代码如下（示例）：
十四、
代码如下（示例）：
十五、
代码如下（示例）：
十六、
代码如下（示例）：
十七、
代码如下（示例）：
十八、
代码如下（示例）：
十九、
代码如下（示例）：
二十、
代码如下（示例）：
总结
这篇文章是作者搜集大量面经和资料这里出来的。感谢你的支持
作者wkm是一名中国矿业大学(北京) 大一的新生，希望得到你的关注
如果可以的话，记得一键三联！