目录
两数之和
面试题 01.02. 判定是否互为字符重排
存在重复元素
存在重复元素 II
字母异位词分组
两数之和
1. 两数之和
思路1：两层for循环
思路2：逐步添加哈希表
思路3：一次填完哈希表
如果一次填完，那么相同元素的值，所映射的下标是最后一个的，然而并不会导致代码出问题，不管 i 是正向还是反向遍历，原因1：只需要能找到num的下标就行；2：对于num = target / 2 时 ，当前元素不影响，说结果就是这里的覆盖并不影响，因为思路2也是会覆盖掉之前出现过的元素
细节：当前下标不能和 hash[num] 相同 反例：{1 ，3， 4} target = 6，也就是当前元素只有一个，且为 target / 2这时候可能出错
参考代码2
class Solution1 {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash;
hash[nums[0]] = 0;
for (int i = 1; i < nums.size(); i++)
{
int num = target - nums[i];
if (hash.count(num)) return { hash[num], i };
hash[nums[i]] = i;
}
return { -1, -1 };
}
};参考代码3
class Solution1 {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash;
int n = nums.size();
for (int i = 0; i < n; i++)
hash[nums[i]] = i;
//for (int i = 0; i < n; i++)
for (int i = n - 1; i >= 0; i--)
{
int num = target - nums[i];
if (hash.count(num) && hash[num] != i)
return { i, hash[num] };
}
return { -1, -1 };
}
};面试题 01.02. 判定是否互为字符重排
面试题 01.02. 判定是否互为字符重排
思路1：两个数组，一个去比较另一个
思路2：一个数组，去比较0
思路3：sort排序string， sort要求是的一个可以下标随机访问的容器，string重载了[]
参考代码 两个数组
class Solution {
public:
bool CheckPermutation(string s1, string s2) {
if (s1.size() != s2.size()) return false;
int hash1[26] = { 0 }, hash2[26] = { 0 };
for (auto e : s1)
hash1[e - 'a']++;
for (auto e : s2)
hash2[e - 'a']++;
for (int i = 0; i < 26; i++)
if (hash1[i] != hash2[i])
return false;
return true;
}
};一个数组
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']--;
for (int i = 0; i < 26; i++)
if (hash[i] < 0) return false;
return true;
}
};sort
class Solution {
public:
bool CheckPermutation(string s1, string s2) {
if (s1.size() != s2.size()) return false;
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
return s1 == s2;
}
};存在重复元素
217. 存在重复元素
参考代码
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_map<int, int> hash;
for (auto e : nums)
if (hash.count(e)) return true;
else hash[e]++;
return false;
}
};存在重复元素 II
219. 存在重复元素 II
参考代码
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> hash;
for(int i = 0; i < nums.size(); i++)
{
if(hash.count(nums[i]) && hash[nums[i]] + k >= i) return true;
hash[nums[i]] = i;
}
return false;
}
};字母异位词分组
49. 字母异位词分组
对于往ret里压数据，是参考资料的，原来是这么想的，但是不对，hash只会用一点，还没学。。
参考代码
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;
unordered_map<string, vector<string>>::iterator it = hash.begin();
while (it != hash.end())
{
ret.push_back(it->second);
++it;
}
return ret;
}
};
