155 lines
3.9 KiB
C++
155 lines
3.9 KiB
C++
#include "哈希表.h"
|
|
#include <vector>
|
|
#include <unordered_map>
|
|
#include <string>
|
|
#include <map>
|
|
#include <algorithm>
|
|
|
|
using namespace std;
|
|
|
|
bool 哈希表::canConstruct(string ransomNote, string magazine) {
|
|
if (ransomNote.size() > magazine.size())
|
|
return false;
|
|
|
|
vector<int> vct(26);
|
|
for (char ch : magazine) {
|
|
vct[ch - 'a']++;
|
|
}
|
|
for (char ch : ransomNote) {
|
|
vct[ch - 'a']--;
|
|
if (vct[ch - 'a'] < 0)
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
bool 哈希表::isIsomorphic(string s, string t) {
|
|
vector<int> vct1(256);
|
|
vector<int> vct2(256);
|
|
if (s.length() != t.length())
|
|
return false;
|
|
for (int i = 0; i < s.length(); i++) {
|
|
if (vct1[s[i]] == 0)
|
|
vct1[s[i]] = t[i];
|
|
else if (vct1[s[i]] != t[i])
|
|
return false;
|
|
if (vct2[t[i]] == 0)
|
|
vct2[t[i]] = s[i];
|
|
else if (vct2[t[i]] != s[i])
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
std::vector<std::string> splitBySpace(const std::string& str) {
|
|
std::vector<std::string> tokens;
|
|
size_t start = 0;
|
|
size_t end = str.find(' ');
|
|
|
|
while (end != std::string::npos) {
|
|
std::string token = str.substr(start, end - start);
|
|
if (!token.empty()) {
|
|
tokens.push_back(token);
|
|
}
|
|
start = end + 1;
|
|
end = str.find(' ', start);
|
|
}
|
|
|
|
// 添加最后一个token
|
|
std::string lastToken = str.substr(start);
|
|
if (!lastToken.empty()) {
|
|
tokens.push_back(lastToken);
|
|
}
|
|
|
|
return tokens;
|
|
}
|
|
bool 哈希表::wordPattern(string pattern, string s) {
|
|
unordered_map<char, string> map;
|
|
unordered_map<string, char> sToPt;
|
|
vector<string> vec = splitBySpace(s);
|
|
if (pattern.length() != vec.size())
|
|
return false;
|
|
for (int i = 0; i < vec.size(); i++) {
|
|
if (map.find(pattern[i]) == map.end())
|
|
map[pattern[i]] = vec[i];
|
|
else if (map[pattern[i]] != vec[i])
|
|
return false;
|
|
|
|
if (sToPt.find(vec[i]) == sToPt.end())
|
|
sToPt[vec[i]] = pattern[i];
|
|
else if (sToPt[vec[i]] != pattern[i])
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
vector<vector<string>> 哈希表::groupAnagrams(vector<string>& strs) {
|
|
map<string, vector<string>> myMap;
|
|
for (int i = 0; i < strs.size(); i++) {
|
|
string str = strs[i];
|
|
sort(str.begin(), str.end());
|
|
myMap[str].push_back(strs[i]);
|
|
// 不用以下判断，可以直接上面行操作
|
|
/*if (myMap.find(str) == myMap.end()) {
|
|
vector<string> vec = { strs[i] };
|
|
myMap.insert({ str, vec });
|
|
}
|
|
else {
|
|
myMap[str].push_back(strs[i]);
|
|
}*/
|
|
}
|
|
vector<vector<string>> ans;
|
|
for (auto var : myMap) {
|
|
ans.push_back(var.second);
|
|
}
|
|
return ans;
|
|
}
|
|
|
|
bool 哈希表::containsNearbyDuplicate(vector<int>& nums, int k) {
|
|
#if 这是执行效果有点儿低
|
|
map<int, vector<int>> myMap;
|
|
for (int i = 0; i < nums.size(); i++) {
|
|
myMap[nums[i]].push_back(i);
|
|
}
|
|
for (auto var : myMap) {
|
|
vector<int> vec = var.second;
|
|
if (vec.size() > 1) {
|
|
for (int i = 1; i < vec.size(); i++) {
|
|
if (vec[i] - vec[i - 1] <= k)
|
|
return true;
|
|
}
|
|
}
|
|
}
|
|
return false;
|
|
#else
|
|
// 只用最新的来比较久可以了
|
|
unordered_map<int, int> dictionary;
|
|
int length = nums.size();
|
|
for (int i = 0; i < length; i++) {
|
|
int num = nums[i];
|
|
if (dictionary.count(num) && i - dictionary[num] <= k)
|
|
return true;
|
|
dictionary[num] = i;
|
|
}
|
|
return false;
|
|
#endif
|
|
}
|
|
|
|
int 哈希表::longestConsecutive(vector<int>& nums) {
|
|
if (nums.size() == 0)
|
|
return 0;
|
|
sort(nums.begin(), nums.end());
|
|
int ans = 1;
|
|
int max = 1;
|
|
for (int i = 1; i < nums.size(); i++) {
|
|
if (nums[i] - nums[i - 1] == 1) {
|
|
ans++;
|
|
if (max < ans)
|
|
max = ans;
|
|
}
|
|
else if (nums[i] != nums[i - 1]) {
|
|
ans = 1;
|
|
}
|
|
}
|
|
return max;
|
|
} |