LeetCode刷题|LeetCode刷题day22 算法|职场和发展|leetcode

算法打卡第二十二天,今天你刷题了吗

大家一起来刷题!

文章图片

【LeetCode刷题|LeetCode刷题day22】今日刷题重点----哈希表
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(nlogn) O(nlogn)
空间复杂度 O ( 1 ) O(1) 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 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) O(n)
空间复杂度: O ( n ) 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<=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(nlogn+n) O(nlogn+n)
空间复杂度: O ( 1 ) O(1) 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 intersection(vector& nums1, vector& nums2) { unordered_set result; //存放结果 unordered_set numsSet(nums1.begin(),nums1.end()); for(int num : nums2) { //如果发现 nums2的元素 ,在numsSet中出现过 if(numsSet.find(num)!=numsSet.end()) { result.insert(num); } } return vector(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 intersect(vector& nums1, vector& nums2) { vector res; unordered_map 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) O(n)
空间复杂度: O ( n ) O(n) O(n)

方法二:双指针此方法和上面的方法二思路一致,不再阐述…
参考代码2

//方法二:双指针 O(nlogn)空间O(n) vector intersect(vector& nums1, vector& nums2) { vector nums3; int i = 0,j = 0; sort(nums1.begin(),nums1.end()); sort(nums2.begin(),nums2.end()); while(inums2[j]) { j++; } } return nums3; }

时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度: O ( 1 ) O(1) O(1)

大家卷起来啊,加油!!!冲他姥姥的!