#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;
}