写一篇软文多少钱,seo搜索引擎优化网站,网站编排,wordpress自动发货如何设置一些理论知识
哈希函数是一种映射关系#xff0c;根据关键词key#xff0c;经过一定函数关系得到元素的位置。
常见的哈希函数构造方法 直接定址法 除留余数法 叠加法 随机数法
哈希冲突
不同关键字通过相同哈希函数计算出相同的哈希地址#xff0c;该种现象称为哈希…一些理论知识
哈希函数是一种映射关系根据关键词key经过一定函数关系得到元素的位置。
常见的哈希函数构造方法 直接定址法 除留余数法 叠加法 随机数法
哈希冲突
不同关键字通过相同哈希函数计算出相同的哈希地址该种现象称为哈希冲突或者哈希碰撞
--------
熟练掌握几种常见的STL。
一、有效的字母异位词
知识点 统计字母个数操作技巧 record[s[i] - a]; 数组也是哈希表哦~
题目
给定两个字符串 *s* 和 *t* 编写一个函数来判断 *t* 是否是 *s* 的字母异位词。
注意若 *s* 和 *t* 中每个字符出现的次数都相同则称 *s* 和 *t* 互为字母异位词。
242. 有效的字母异位词 - 力扣LeetCode
题解
class Solution {
public:bool isAnagram(string s, string t) {vectorint record(26, 0);// 统计s中字母个数for(int i 0; i s.size(); i){record[s[i] - a];}for(int j 0; j t.size(); j){record[t[j] - a]--;}for(int k 0; k record.size(); k){if(record[k] ! 0){return false;}}return true;}
}; 二、两个数组的交集
知识点 unordered_set 无序集合存储唯一元素与 set 不同unordered_set 不会对元素进行排序而是使用哈希表来实现快速的查找和插入操作。 unordered_set 使用哈希表来实现这使得查找、插入和删除操作的平均时间复杂度为常数级别O(1)。 find 如果找到了find 返回指向该元素的迭代器否则返回 nums1_set.end()表示未找到。
题目
给定两个数组 nums1 和 nums2 返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
349. 两个数组的交集 - 力扣LeetCode
题解
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint result_set;unordered_setint nums1_set(nums1.begin(), nums1.end());
for (int i 0; i nums2.size(); i){if(nums1_set.find(nums2[i]) ! nums1_set.end()){result_set.insert(nums2[i]);}}
return vectorint (result_set.begin(), result_set.end());}
};
三、快乐数
知识点 停止条件的设置
在计算每个位置上的数字的平方和时如果出现了之前已经计算过的结果就会形成一个循环。这是因为每个数字的平方和可能会有限个而如果在计算的过程中遇到了之前的结果就会陷入一个循环不断重复。
题目
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为 对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true 不是则返回 false 。
202. 快乐数 - 力扣LeetCode
题解
class Solution {
public:int get_sum(int n){int sum 0;while(n){sum (n % 10) * (n % 10);n / 10;}return sum;}
bool isHappy(int n) {unordered_setint result_sum;while(1){int sum get_sum(n);if(sum 1) return true;if(result_sum.find(sum) result_sum.end()){result_sum.insert(sum);}else{return false;}n sum;}}
}; 四、两数之和
知识点
学会 unordered_map 的用法
映射底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率std::map红黑树key有序key不可重复key不可修改O(log n)O(log n)std::multimap红黑树key有序key可重复key不可修改O(log n)O(log n)std::unordered_map哈希表key无序key不可重复key不可修改O(1)O(1)
题目
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
1. 两数之和 - 力扣LeetCode
题解
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_map int, int nums_map;for(int i 0; i nums.size(); i){int tmp target - nums[i];auto goal nums_map.find(tmp);if(goal ! nums_map.end()){return {goal-second, i};}nums_map.insert(pairint,int(nums[i], i));}return {};}
}; 五、四数相加 II
知识点 时间复杂度 不需要考虑去重哈希表
题目
给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足 0 i, j, k, l n nums1[i] nums2[j] nums3[k] nums4[l] 0
454. 四数相加 II - 力扣LeetCode
题解
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {unordered_mapint,int Map;
for (int i : nums1){for(int j : nums2){Map[i j]; }}
int count 0;for (int i : nums3){for(int j : nums4){if(Map.find(-(i j)) ! Map.end()){count Map[-(i j)];}}}return count;}
};
六、赎金信
题目
给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以返回 true 否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
383. 赎金信 - 力扣LeetCode
题解
解法类似于 ‘有效的字母异位词’
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int record[26] {0};for(int i 0; i magazine.size(); i){record[magazine[i] - a];}
for(int j 0; j ransomNote.size(); j){record[ransomNote[j] - a]--;}
for(int k 0; k 26; k){if(record[k] 0){return false;}}return true;}
};
