当前位置:网站首页>leetcode刷题 (5.28) 哈希表
leetcode刷题 (5.28) 哈希表
2022-07-06 08:14:00 【Freya】
1. 有效的字母异位词
题目:
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
输入: s = "anagram", t = "nagaram"
输出: true
输入: s = "rat", t = "car"
输出: false
思路:
用一个长度为26的数组表示哈希表,s中字母在哈希表中对应位置(s[i] - ‘a’)加一,t中字母再依次减一,最后看哈希表是否全为0,否则false.
笔记:
当遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间,因为要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。
当要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。
python中ord()表示取ASCII值。
C++:
// 时间复杂度为O(n), 空间复杂度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. 两个数组的交集
题目:
给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
解释:[4,9] 也是可通过的
思路:
C++:
用unordered_set实现
注意:直接使用set 不仅占用空间比数组大,而且速度要比数组慢(所以能用数组还是尽量用数组)
Python:
两个数组变为两个集合,集合求交集,再还原为数组(list)
笔记:
C++:
- for ( : ) 用于遍历数组
- unordered_set::find()函数是C++ STL中的内置函数,用于在容器中搜索元素。
返回找到元素的迭代器,否则返回指向unordered_set末尾的迭代器。
Python:
& :集合求交集
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) {
// 常用find和end组合来判断num_set中是否含有num
// 如果nums_set中含有nums2中的元素就把它插到result_set中
// 这里nums_set是nums1转化得来(去重)
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))
边栏推荐
- Make learning pointer easier (3)
- [Yugong series] creation of 009 unity object of U3D full stack class in February 2022
- 22. Empty the table
- Leetcode question brushing record | 203_ Remove linked list elements
- Summary of phased use of sonic one-stop open source distributed cluster cloud real machine test platform
- 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
- 数据治理:元数据管理篇
- 远程存储访问授权
- WebRTC系列-H.264预估码率计算
- 07- [istio] istio destinationrule (purpose rule)
猜你喜欢
Use Alibaba icon in uniapp
Go learning notes (3) basic types and statements (2)
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
A Closer Look at How Fine-tuning Changes BERT
Easy to use tcp-udp_ Debug tool download and use
Uibehavior, a comprehensive exploration of ugui source code
Wincc7.5 download and installation tutorial (win10 system)
hcip--mpls
"Designer universe": "benefit dimension" APEC public welfare + 2022 the latest slogan and the new platform will be launched soon | Asia Pacific Financial Media
[count] [combined number] value series
随机推荐
Epoll and IO multiplexing of redis
华为云OBS文件上传下载工具类
Codeforces Global Round 19(A~D)
Make learning pointer easier (3)
ESP series pin description diagram summary
化不掉的钟薛高,逃不出网红产品的生命周期
C语言 - 位段
Machine learning - decision tree
Nacos Development Manual
wincc7.5下载安装教程(Win10系统)
Data governance: misunderstanding sorting
TiDB备份与恢复简介
在 uniapp 中使用阿里图标
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
Esrally domestic installation and use pit avoidance Guide - the latest in the whole network
23. Update data
Use dumping to back up tidb cluster data to S3 compatible storage
How to use information mechanism to realize process mutual exclusion, process synchronization and precursor relationship
MySQL view tablespace and create table statements
JS select all and tab bar switching, simple comments