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

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

一、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是一名中国矿业大学(北京) 大一的新生，希望得到你的关注
如果可以的话，记得一键三联！