今日刷题重点----哈希表
242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram" 输出: true
示例 2:
输入: s = "rat", t = "car" 输出: false
方法一:hash表
由于字符串中的都是小写字母,所以我们可以用数组来作为Hash表.
参考代码1
bool isAnagram(string s, string t) { int arr[30] = {0}; for(int i = 0;i < s.size();i++){ arr[s[i]-'a']++; } for(int i = 0;i < t.size();i++){ arr[t[i]-'a']--; } for(int i = 0;i <30;i++){ if(arr[i]){ return false; } } return true; }
- 时间复杂度:O(n)
- 空间复杂度:O(1)
方法二
使用sort后,判断两个字符串是否相等
参考代码2
bool isAnagram(string s, string t) { if(s.size()!=t.size()){ return false; } sort(s.begin(),s.end()); sort(t.begin(),s.end()); if(s!=t){ return false; } return true; }
时间复杂度:O ( n l o g n )
空间复杂度O ( 1 )
383. 赎金信
为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。
给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符构成。
如果可以构成，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b" 输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab" 输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab" 输出：true
方法一:hash表
因为是字符,所以可以采用数组的hash表(也可以使用unordered_map的hash表,因为考虑到效率而且还不需要排序)
注:使用数组还是使用set/map类型的hash表,要认真考虑,如果元素用数组可以很好的表示,那就使用数组.比如字符…
参考代码1(使用数组)
明日补充...
参考代码2(使用unordered_map)
//时间复杂度 O(n) 空间复杂度O(n) bool canConstruct(string s1, string s2) { if(s1.size()>s2.size()) { return false; } unordered_map<char,int> sMap; for(char c : s2) { if(sMap.find(c)==sMap.end()) { sMap[c] = 1; } else { sMap[c]++; } } for(char c : s1) { if(sMap.find(c)!=sMap.end()) { sMap[c]--; if(sMap[c]<0){ return false; } }else{ return false; } } return true; }
时间复杂度:O ( n )
空间复杂度:O ( n )
方法二:双指针
因为要求是ransomNote由magazine组成,所以我们可以先对其进行排序.
然后每个指针都指向一个串,然后从前往后遍历,如果相同就都++,如果j对应的字符大于了i对应的字符,说明不满足了.如果j对应的字符小于i对应的字符,说明magazine中的该字符是满足的而且还用不完.
如果i对ransomNote遍历完,j都能找到对应的,则说明满足.
参考代码3
bool canConstruct(string ransomNote, string magazine) { if(ransomNote.size()>magazine.size()) { return false; } sort(ransomNote.begin(),ransomNote.end()); sort(magazine.begin(),magazine.end()); //cout<<ransomNote<<"--"<<magazine<<endl; int i,j; for(i = 0,j = 0; i < ransomNote.size(); i++,j++) { if(j>=magazine.size()) { return false; } if(ransomNote[i]==magazine[j]) { continue; } else if(ransomNote[i]>magazine[j]) { i--; } else { return false; } } return true; }
时间复杂度:O ( n l o g n + n )
空间复杂度:O ( 1 )
方法三:暴力解法
参考代码
明日补充...
349. 两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4]
方法一:hash表
- 我们使用unordered_set类型的hash表:输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序
- 当然我们也可以使用数组来实现hash表…
参考代码
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> result;//存放结果 unordered_set<int> numsSet(nums1.begin(),nums1.end()); for(int num : nums2) { //如果发现 nums2的元素 ,在numsSet中出现过 if(numsSet.find(num)!=numsSet.end()) { result.insert(num); } } return vector<int>(result.begin(),result.end()); }
参考代码2
明日补充...
350. 两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9]
方法一:hash表
因为不去重,不考虑顺序,而且考虑到了效率我们可以采用unordered_map类型的hash表
具体实现:
- 把nums1中的元素放到
unordered_map numsMap中,然后遍历nums中的每个元素num. - 如果num在numsMap的值>0,则说明可以放到交集里面…如果小于等于0,则从numsMap中移除.
参考代码1
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { vector<int> res; unordered_map<int,int> numsMap; for(int i = 0; i < nums1.size(); i++) { if(numsMap.find(nums1[i])==numsMap.end()) { numsMap[nums1[i]]=1; } else { numsMap[nums1[i]]++; } } for(int i = 0; i < nums2.size(); i++) { if(numsMap.find(nums2[i])!=numsMap.end()) { numsMap[nums2[i]]--; res.push_back(nums2[i]); if(numsMap[nums2[i]]==0) { //如果该元素在map中的值已经减为了0,则删除该元素. numsMap.erase(nums2[i]); } } } return res; }
时间复杂度:O ( n )
空间复杂度:O ( n )
方法二:双指针
此方法和上面的方法二思路一致,不再阐述…
参考代码2
//方法二:双指针 O(nlogn) 空间O(n) vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { vector<int> nums3; int i = 0,j = 0; sort(nums1.begin(),nums1.end()); sort(nums2.begin(),nums2.end()); while(i<nums1.size() && j<nums2.size()) { if(nums1[i]==nums2[j]) { nums3.push_back(nums1[i]); i++,j++; } else if(nums1[i]<nums2[j]) { i++; } else if(nums1[i]>nums2[j]) { j++; } } return nums3; }
时间复杂度:O ( n l o g n )
空间复杂度:O ( 1 )
