之前的blog:https://blog.csdn.net/weixin_43303286/article/details/131765317
我用的方法是在leetcode再过一遍例题,明显会的就复制粘贴,之前没写出来就重写,然后从拓展题目中找题目来写。辅以Labuladong的文章看。然后刷题不用CLion了,使用leetcode自带模拟面试环境。
哈希表章节的题目思路很清晰,主要是C++中的写法。
242.有效的字母异位词
这题就是字典加加减减的事,一看就有思路了。使用数组代替hashtable
349. 两个数组的交集
这里注意在C++的std::unordered_set
中,查找一个元素的平均时间复杂度是O(1)。这是因为unordered_set
是使用哈希表实现的,哈希表提供了常数时间的平均查找时间,前提是哈希函数能够将元素均匀地分布在哈希表的桶中,并且没有发生哈希冲突。
在C++的std::unordered_set
中,你可以使用find
函数来查找元素。find
函数返回一个迭代器,指向找到的元素,如果元素不存在,则返回unordered_set
的end()
迭代器。
在C++的std::unordered_set
中插入元素可以使用insert
函数
我的第一个解法使用两个set:
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> sets(nums1.begin(), nums1.end());unordered_set<int> res;for(int num: nums2){if(sets.find(num) != sets.end()){res.insert(num);}}return vector<int> (res.begin(), res.end());}
};
内存爆了,看看之前的解法:感觉这个时间复杂度更差hhh
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int> table;set<int> res;for(int num : nums1){table[num]++;}for(int num : nums2){if(table[num] > 0){res.insert(num);}}vector<int> res1(res.begin(),res.end());//使用迭代器构建vector。return res1;}
1. 两数之和
使用hashtable,其中key是值,value是对应的下标
这里注意使用iter取hash表中的迭代器,it->second表示value,没有括号。
160. 相交链表
二刷有点思路了,先遍历一遍求长度,然后移动短的跟长的对齐,再依次比较相等就返回(这里比的不是值而是指针):
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;int lengthA = 0, lengthB = 0;while(curA != nullptr){lengthA++;curA = curA->next;}while(curB != nullptr){lengthB++;curB = curB->next;}//这里要重新开始遍历,要对curA curB进行重新赋值curA = headA;curB = headB;//假设A为短的链表,B为长的链表if(lengthA > lengthB){swap(lengthA,lengthB);swap(curA,curB);}int gap = lengthB - lengthA;while(gap--){curB = curB->next;}while(curA != nullptr){if(curA == curB){return curA;}curA = curA->next;curB = curB->next;}return nullptr;}
};
z