网站营销力,网站搭建心得,个人兴趣网站设计,大连网站设计菲尔莱斯先验知识记录#xff1a;
遇到哈希问题#xff0c;想到三种数据结构#xff1a;
①数组#xff1a;适用于哈希值比较小#xff0c;范围较小#xff0c;
②set#xff1a;适用于哈希值较大。
③map#xff1a;如果需要用到键值对#xff0c;则用之。 242.有效的字母…先验知识记录
遇到哈希问题想到三种数据结构
①数组适用于哈希值比较小范围较小
②set适用于哈希值较大。
③map如果需要用到键值对则用之。 242.有效的字母异位符。
代码随想录链接
力扣链接
问题描述
就是看两个字符串里面的字符是不是一样的它们包含的字母以及个数是否是一致的。
思路
因为单个字母总共有26个所以建立数组形式的hash表。初始的hash表各个元素为0。经过字符串1的遍历后hash表此时对应位置的字母数为字符串1的字母数。
再去遍历字符串2如果遍历后的hash字母表存在字母对应的值不为0则说明两个字符串包含的字母及字母数不同。如果每个hash表中每个位置的字母都为0那么说明两个字符串中是异位关系。
注意此时hash表中的字母位置使用hash[string1[i]-a]表示这个很妙因为这就相当于取出字符串每个字符对应到hash数组中且一一对应。
伪代码
新建数组hash字母表
遍历字符串1对对应位置的hash字母表数值1表示字符串1中的hash字母表中字母个数
遍历字符串2对对应位置的hash字母表数值-1表示字符串2中的hash字母表字母个数-字符串1中对应位置的字母个数
遍历hash字母表如果某个位置不为0说明两个字符串不是异味关系返回false
遍历完成后返回true代码
bool isAnagram(string s, string t) {int hash[26]{0};for(int i 0 ; is.size();i){//遍历字符串s使得s对应的字母表每个都有其对应次数。//s[i]就是s的每个字符s[i]-‘a’代表了其对应哈希表的索引从0-25。字符串t同理。hash[s[i]-a];}for(int i 0 ; i t.size() ; i){hash[t[i]-a]--;}for(int i 0 ; i 26; i){if (hash[i]!0){return false;}}return true;
}349.两个数组的交集。
代码随想录链接
力扣链接
问题描述
两个数组取交集最后的结果要不重复。
思路
有两种思路解决
①set将数组1的元素存入set去重。遍历数组2如果元素在set中则放入另个集合中作为返回值返回。
遍历数组1将数组中每个元素去重后放入number_set中
遍历数组2如果数组2中有元素在number_set中则放入result_set中
将result_set转为vector作为返回值返回②数组力扣上有数组中单个元素大小限制故将hash表数组设置为1000出头的大小。
新建hash表大小为1000出头
遍历数组1对数组1的每个元素放到hash数组中为1.
遍历数组2如果数组中有数字对应hash值为1将元素放入result_set中
将result_set转为vector作为返回值返回解法①代码
vectorint intersection(vectorint nums1, vectorint nums2) {setint result_set;//方法1setint number_set ;for(int i 0 ; i nums1.size() ; i){number_set.insert(nums1[i]);}for(int i 0 ; i nums2.size();i){if (number_set.find(nums2[i])! number_set.end()){result_set.insert(nums2[i]);}}vector int vt;vt.assign(result_set.begin(),result_set.end());return vt;
}解法②代码
vectorint intersection(vectorint nums1, vectorint nums2) {setint result_set;//方法2int hash[1001]{0};//遍历nums1若有数字则为1for(int i 0 ; i nums1.size() ; i){hash[nums1[i]]1;}for(int i 0 ; i nums2.size();i){if (hash[nums2[i]]){result_set.insert(nums2[i]);}}vector int vt;vt.assign(result_set.begin(),result_set.end());return vt;
}
