LeetCode 高频算法题：随机链表复制 + TopK 高频单词

LeetCode 高频算法题随机链表复制 TopK 高频单词本文为你详细讲解两道面试超高频算法题——随机链表的深度拷贝、前K个高频单词包含完整思路、代码和细节解析。 文章目录文章目录LeetCode 高频算法题随机链表复制 TopK 高频单词 文章目录[toc]一、138. 随机链表的复制题目描述核心思路代码实现C关键细节二、692. 前K个高频单词题目描述核心思路代码实现C关键细节三、题型总结 四、总结 一、138. 随机链表的复制题目描述给你一个长度为n的链表每个节点包含一个额外增加的随机指针random该指针可以指向链表中的任何节点或空节点。请构造这个链表的深拷贝。深拷贝应该正好由n个全新节点组成新节点的next和random指针都指向新链表中的节点返回复制链表的头节点。示例 1输入head [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出[[7,null],[13,0],[11,4],[10,2],[1,0]]核心思路哈希表映射用哈希表存储原节点 → 新节点的对应关系第一次遍历创建所有新节点建立映射第二次遍历根据原节点的next和random给新节点赋值指针深拷贝所有节点都是新创建的与原链表完全独立代码实现C/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val _val; next NULL; random NULL; } }; */classSolution{public:Node*copyRandomList(Node*head){// 哈希表key 是原节点value 是拷贝后的新节点unordered_mapNode*,Node*map;Node*curhead;// 1. 第一遍遍历创建所有新节点存入哈希表while(cur!nullptr){map[cur]newNode(cur-val);curcur-next;}// 2. 第二遍遍历给新节点赋值 next 和 random 指针curhead;while(cur!nullptr){map[cur]-nextmap[cur-next];map[cur]-randommap[cur-random];curcur-next;}// 返回复制链表的头节点returnmap[head];}};关键细节深拷贝必须 new 新节点不能直接使用原节点指针哈希表作用快速通过原节点找到对应的新节点解决 random 指针难题时间复杂度O(n)两次遍历链表空间复杂度O(n)哈希表存储 n 个节点二、692. 前K个高频单词题目描述给定一个单词列表words和一个整数k返回前k个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同的频率按字典序升序排序。示例 1输入: words [i,love,leetcode,i,love,coding], k 2 输出: [i,love]核心思路统计频率用哈希表统计每个单词出现次数自定义排序频率高的排前面频率相同字典序小的排前面截取前k个输出结果代码实现CclassSolution{public:vectorstringtopKFrequent(vectorstringwords,intk){// 1. 统计单词频率unordered_mapstring,intcountMap;for(autoword:words){countMap[word];}// 2. 把哈希表转成vector方便排序vectorpairstring,intvec(countMap.begin(),countMap.end());// 3. 自定义排序规则sort(vec.begin(),vec.end(),[](constpairstring,inta,constpairstring,intb){// 频率不同频率高的在前if(a.second!b.second){returna.secondb.second;}// 频率相同字典序小的在前returna.firstb.first;});// 4. 取前k个单词vectorstringres;for(inti0;ik;i){res.push_back(vec[i].first);}returnres;}};关键细节排序规则先比频率再比字典序Lambda 表达式用于自定义排序代码简洁时间复杂度O(n log n)主要来自排序空间复杂度O(n)存储单词与频率三、题型总结 题目核心考点数据结构时间复杂度138. 随机链表复制深拷贝、哈希表链表 哈希表O(n)692. 前K个高频单词频率统计、自定义排序哈希表 排序O(n log n)四、总结 随机链表复制利用哈希表建立新旧节点映射完美解决 random 随机指针问题是链表深拷贝的标准解法。前K个高频单词统计频率 自定义排序面试中 TopK 问题的基础题型必须掌握排序规则。