当前位置:网站首页>Leetcode question brushing (5.28) hash table
Leetcode question brushing (5.28) hash table
2022-07-06 08:20:00 【Freya】
1. Effective alphabetic words
subject :
Given two strings s and t , Write a function to determine t Whether it is s Letter heteronym of .
Be careful : if s and t Each character in the has the same number of occurrences , said s and t They are mutually alphabetic words .
Input : s = "anagram", t = "nagaram"
Output : true
Input : s = "rat", t = "car"
Output : false
Ideas :
Use a length of 26 Array of represents hash table ,s The corresponding position of the middle letter in the hash table (s[i] - ‘a’) Add one ,t The middle letters are then subtracted by one , Finally, check whether the hash table is all 0, otherwise false.
note :
When it comes to quickly determining whether an element appears in the set , Think about hashifa .
But hashifa also sacrificed space for time , Because you need to use extra arrays ,set Or is it map To store data , In order to achieve fast search .
When it comes to using collections to solve hash problems , priority of use unordered_set, Because its query and add delete efficiency is optimal , If you need the set to be ordered , Then use set, If it requires not only order but also duplicate data , Then use multiset.
python in ord() It means take ASCII value .
C++:
// The time complexity is O(n), Spatial complexity O(1)
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {
0};
for(int i = 0; i < s.size(); i++){
record[s[i] - 'a']++;
}
for(int i = 0; i < t.size(); i++){
record[t[i] - 'a']--;
}
for(int i = 0; i < 26; i++){
if(record[i] != 0){
return false;
}
}
return true;
}
};
Python:
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
record = [0] * 26
for i in range(len(s)):
record[ord(s[i]) - ord("a")] += 1
for i in range(len(t)):
record[ord(t[i]) - ord("a")] -= 1
for i in range(26):
if record[i] != 0:
return False
break
return True
2. Intersection of two arrays
subject :
Given two arrays nums1 and nums2 , return Their intersection . Every element in the output must be only Of . We can Regardless of the order of the output results .
Input :nums1 = [1,2,2,1], nums2 = [2,2]
Output :[2]
Input :nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output :[9,4]
explain :[4,9] It is also passable
Ideas :
C++:
use unordered_set Realization
Be careful : Use it directly set Not only does it take up more space than arrays , And it's slower than arrays ( So can we use arrays or try to use arrays )
Python:
Two arrays become two sets , Intersection of sets , Then revert to array (list)
note :
C++:
- for ( : ) For traversing arrays
- unordered_set::find() The function is C++ STL Built in functions in , Used to search for elements in containers .
Returns the iterator that found the element , Otherwise, it points back to unordered_set Iterator at the end .
Python:
& : Intersection of sets
C++:
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for (int num : nums2) {
// Commonly used find and end Combine to judge num_set Whether contains num
// If nums_set contains nums2 Insert it into result_set in
// here nums_set yes nums1 Converted ( duplicate removal )
if (nums_set.find(num) != nums_set.end()){
result_set.insert(num);
}
}
return vector<int> (result_set.begin(), result_set.end());
}
};
Python:
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))
边栏推荐
- "Friendship and righteousness" of the center for national economy and information technology: China's friendship wine - the "unparalleled loyalty and righteousness" of the solidarity group released th
- Oracle time display adjustment
- LDAP應用篇(4)Jenkins接入
- vulnhub hackme: 1
- ESP series pin description diagram summary
- Wireshark grabs packets to understand its word TCP segment
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- 08- [istio] istio gateway, virtual service and the relationship between them
- 21. Delete data
- Epoll and IO multiplexing of redis
猜你喜欢
Yyds dry goods inventory three JS source code interpretation eventdispatcher
Make learning pointer easier (3)
IP lab, the first weekly recheck
Zhong Xuegao, who cannot be melted, cannot escape the life cycle of online celebrity products
3. File operation 3-with
IoT -- 解读物联网四层架构
synchronized 解决共享带来的问题
vulnhub hackme: 1
Uibehavior, a comprehensive exploration of ugui source code
wincc7.5下载安装教程(Win10系统)
随机推荐
National economic information center "APEC industry +": economic data released at the night of the Spring Festival | observation of stable strategy industry fund
Asia Pacific Financial Media | "APEC industry +" Western Silicon Valley invests 2trillion yuan in Chengdu Chongqing economic circle to catch up with Shanghai | stable strategy industry fund observatio
A Closer Look at How Fine-tuning Changes BERT
IP lab, the first weekly recheck
Yu Xia looks at win system kernel -- message mechanism
Restore backup data on S3 compatible storage with br
Oracle time display adjustment
ESP series pin description diagram summary
Go learning notes (3) basic types and statements (2)
[secretly kill little partner pytorch20 days -day01- example of structured data modeling process]
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Yyds dry goods inventory three JS source code interpretation eventdispatcher
Online yaml to CSV tool
Use Alibaba icon in uniapp
[research materials] 2021 Research Report on China's smart medical industry - Download attached
CAD ARX gets the current viewport settings
Mobile Test Engineer occupation yyds dry goods inventory
Introduction to number theory (greatest common divisor, prime sieve, inverse element)
C language - bit segment
Nacos Development Manual