算法->哈希表
1. 两数之和 - 力扣(LeetCode)
给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 target
的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
输入: nums = [2,7,11,15], target = 9
输出: [0,1]
解释: 因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:
输入: nums = [3,2,4], target = 6
输出: [1,2]
示例 3:
输入: nums = [3,3], target = 6
输出: [0,1]
解题思路
- 暴力 O(n^2)
- 哈希表优化
建立nums[i] 和 i 的映射关系。
遍历数组nums。将已经遍历过的元素存放到哈希表中,在哈希表中查找target-nums[i]即可。找说明存在,返回元素所在位置的实值即可。O(n)
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
//暴力求解 O(n^2)
// for(int i = 1; i < nums.size(); ++i)
// {
// int j = i-1;
// while(j >= 0)
// {
// if(nums[j] == target - nums[i])
// {
// return {j,i};
// }
// j--;
// }
// }
// return {-1,-1};
//哈希表优化
unordered_map<int,int> hash;
for(int i =0 ; i < nums.size();i++)
{
int x = target - nums[i];
if(hash.count(x))
{
return {hash[x],i};
}
hash.insert(make_pair(nums[i],i));
}
return {-1,-1};
}
};
判定是否互为字符重排 - 力扣(LeetCode)
给定两个由小写字母组成的字符串 s1
和 s2
,请编写一个程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。
示例 1:
输入: s1 = "abc", s2 = "bca"
输出: true
示例 2:
输入: s1 = "abc", s2 = "bad"
输出: false
说明:
0 <= len(s1) <= 100
0 <= len(s2) <= 100
算法原理
使用数组模拟哈希表,遍历s1映射到哈希表中,在遍历s2在哈希表中确定是否出现。
实现
class Solution
{
public:
bool CheckPermutation(string s1, string s2)
{
if(s1.size() != s2.size())
{
return false;
}
int hash[26] = {0};
for(auto& e : s1)
{
hash[e - 'a']++;
}
for(auto& e : s2)
{
hash[e - 'a']--;
if(hash[e - 'a'] < 0)
{
return false;
}
}
return true;
}
};
217. 存在重复元素 - 力扣(LeetCode)
给你一个整数数组 nums
。如果任一值在数组中出现 至少两次 ,返回 true
;如果数组中每个元素互不相同,返回 false
。
示例 1:
输入: nums = [1,2,3,1]
输出: true
示例 2:
输入: nums = [1,2,3,4]
输出: false
示例 3:
输入: nums = [1,1,1,3,3,4,3,2,4,2]
输出: true
解题思路
使用STL容器unordered_map,统计数组中每个元素出现的次数。
遍历u_map判断是否有超过两次的即可
代码实现
class Solution
{
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_map<int,int> hash;
for(auto& e: nums)
{
hash[e]++;
}
for(auto& e: hash)
{
if(e.second >= 2)
{
return true;
}
}
return false;
}
};
219. 存在重复元素 II
给你一个整数数组 nums
和一个整数 k
,判断数组中是否存在两个 不同的索引 **i
和 **j
,满足 nums[i] == nums[j]
且 abs(i - j) <= k
。如果存在,返回 true
;否则,返回 false
。
示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k = 2
输出: false
解题思路
使用哈希表建立nums[i] 和 i 的映射关系,遍历数组,如果nums[i]在哈希表中确定索引位置进行做差判罚。
不在哈希表中,就插入到哈希表中,如果abs(i - j) > k 就更新nums[i] 和 i 的映射关系
代码实现
class Solution
{
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
if(nums.size() <= 1)
{
return false;
}
//num[i] 和 i的映射关系
unordered_map<int,int> hash;
for(size_t i = 0; i < nums.size(); ++i)
{
int num = nums[i];
//nums[i]在哈希表中就进行判断
if(hash.count(num) && i - hash[num] <= k)
{
return true;
}
//不在哈希表中 更新nums[i] 和i 的映射关系
hash[num] = i;
//不能使用insert 无法更新
//hash.insert(make_pair(num,i));
}
return false;
}
};
LCR 033. 字母异位词分组 - 力扣(LeetCode)
给定一个字符串数组 strs
,将 变位词 组合在一起。 可以按任意顺序返回结果列表。
注意: 若两个字符串中每个字符出现的次数都相同,则称它们互为变位词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
解题思路
遍历strs判断是否为异位词,使用sort排序后,一样就是异位词。如果一样是异位词,就更新映射关系(映射关系为<string,vector<string>>
),不是就插入到哈希表中。
利用unordered_map的[]
操作符即可完成。
然后遍历哈希表,将结果提取出来(哈希表中的实值),返回即可。
代码实现
class Solution
{
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
unordered_map<string,vector<string>> hash;
//利用排序判断是否为异位词
//是异位词更新映射关系,不是插入到哈希表中(利用[[])。
for(auto &e : strs)
{
string tmp = e;
sort(tmp.begin(),tmp.end());
hash[tmp].push_back(e);
}
//遍历哈希表,将实值提取出来返回
vector<vector<string>> ret;
for(auto e :hash)
{
ret.push_back(e.second);
}
return ret;
}
};
原文地址:https://blog.csdn.net/FBI_BAIGOU/article/details/136336283
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!