EPI-Hash Tables

struct ContactList {
  bool operator==(const ContactList& that) const {
    return unordered_set<string>(names.begin(), names.end()) == unordered_set<string>(that.names.begin(), that.names.end());
  }
  vector<string> name;
};

struct HashContactList {
  size_t operator()(const ContactList& contacts) const {
    size_t hash_code = 0;
    for (const string& name: unordered_set<string>(contracts.names.begin(), contracts.names.end())) {
      hash_code ^= hash<string>()(name);
    }
  }
}

vector<ContactList> MergeContractLists(cont vector<ContactList>& contracts) {
  unordered_set<ContactList, HashContractList> unique_contracts(contracts.begin(), contracts.end());

  return {unique_contracts.begin(), unique_contracts.end()};
}

// 都不允许键重复
// unordered_set 存储k
.insert(val);  //return a pair of iterator and boolean denoting whether the insertion took place.
.erase(val); // 
.find(val); // return iterator or end()
.size();
.count(val);
.contains(val); //c++20

// unordered_map 存储k-v

.insert({k, v});
.emplace({k, v});
.earse(k);
.find(k);
.size();


// functional header
hash<typename>()(val);
//int, bool, string, unique_ptr, shared_ptr, etc.

vector<vector<string>> FindAnagrams(const vector<string>& dictionary) {
  // TODO - you fill in here.
  std::unordered_map<string, vector<string>> sorted_string_to_anagrams;
  for (const string& s: dictionary) {
      string sorted_s(s);
      std::sort(sorted_s.begin(), sorted_s.end());
      sorted_string_to_anagrams[sorted_s].emplace_back(s);
  }

  vector<vector<string>> ret;
  for (const auto& p: sorted_string_to_anagrams) {
      if (p.second.size() >= 2) {
          ret.emplace_back(p.second);
      }
  }
  return ret;
}

bool CanFormPalindrome(const string& s) {
  // TODO - you fill in here.
  std::unordered_map<char, int> cnt;
  for (const char& ch: s) {
      ++cnt[ch];
  }
  int odd_cnt = 0;
  for (const auto& p: cnt) {
      if (p.second % 2 != 0) {
          ++odd_cnt;
      }
      if (odd_cnt > 1) {
          return false;
      }
  }
  return true;
}

bool IsLetterConstructibleFromMagazine(const string& letter_text,
                                       const string& magazine_text) {
  // TODO - you fill in here.
  std::unordered_map<char, int> cnt;
  for (const char& ch: magazine_text) {
      ++cnt[ch];
  }
  for (const char& ch: letter_text) {
      if (cnt.find(ch) == cnt.end()) {
          return false;
      }
      --cnt[ch];
      if (cnt[ch] < 0) {
          return false;
      }
  }
  return true;
}

bool IsLetterConstructibleFromMagazine(const string& letter_text,
                                       const string& magazine_text) {
  // TODO - you fill in here.
  std::unordered_map<char, int> cnt;
  for (const char& ch: letter_text) {
      ++cnt[ch];
  }
  for (const char& ch: magazine_text) {
      auto iter = cnt.find(ch);
      if (iter != cnt.end()) {
          --iter->second;
          if (iter->second == 0) {
              cnt.erase(iter);
              if (cnt.empty()) {
                  break;
              }
          }

      }
  }
  return cnt.empty();
}

#include <vector>
#include <unordered_map>
#include <list>

class LruCache {
 public:
  LruCache(size_t capacity) {
      this->capacity = capacity;
  }
  int Lookup(int isbn) {
    // TODO - you fill in here.
    auto iter = isbn_price_table_.find(isbn);
    if (iter == isbn_price_table_.end()) {
        return -1;
    }
    int ret_val = iter->second.second;
    MoveFront(isbn, iter);
    return ret_val;
  }
  void Insert(int isbn, int price) {
    // TODO - you fill in here.
    auto iter = isbn_price_table_.find(isbn);
    if (iter == isbn_price_table_.end()) {
        // 未找到
        if (isbn_price_table_.size() == capacity) {
            // 需要替换一个出去
            int subs_isbn = lru_queue_.back();
            isbn_price_table_.erase(subs_isbn);
            lru_queue_.pop_back();

        }
        lru_queue_.emplace_front(isbn);
        isbn_price_table_.insert({isbn, {lru_queue_.begin(), price}});
    } else {
        MoveFront(isbn, iter); //找到项目，更新lru
    }
  }
  bool Erase(int isbn) {
    // TODO - you fill in here.
    auto iter = isbn_price_table_.find(isbn);
    if (iter == isbn_price_table_.end()) {
        return false;
    }
    lru_queue_.erase(iter->second.first);
    isbn_price_table_.erase(iter);
    return true;
  }

private:
    typedef std::unordered_map<int, std::pair<std::list<int>::iterator, int>> Table;
    Table isbn_price_table_;
    std::list<int> lru_queue_;
    size_t capacity;

    void MoveFront(int isbn, const Table::iterator& it) {
        lru_queue_.erase(it->second.first);
        lru_queue_.emplace_front(isbn);
        it->second.first = lru_queue_.begin();
    }
};

BinaryTreeNode<int>* Lca(const unique_ptr<BinaryTreeNode<int>>& node0,
                         const unique_ptr<BinaryTreeNode<int>>& node1) {
  // TODO - you fill in here.
  std::unordered_set<BinaryTreeNode<int>*> node_set;
  BinaryTreeNode<int> *p0 = node0.get(), *p1 = node1.get();
  while (p0 && p1) {
      auto iter = node_set.find(p0);
      if (iter != node_set.end()) {
          return *iter;
      }
      node_set.insert(p0);
      p0 = p0->parent;

      iter = node_set.find(p1);
      if (iter != node_set.end()) {
          return *iter;
      }
      node_set.insert(p1);
      p1 = p1->parent;
  }
  auto *residual = p0 == nullptr ? p1 : p0;
  while (residual != nullptr) {
      auto iter = node_set.find(residual);
      if (iter != node_set.end()) {
          return *iter;
      }
      residual = residual->parent;
  }
  return nullptr;
}

struct Subarray {
  int start, end;
};

Subarray FindSmallestSubarrayCoveringSet(
    const vector<string> &paragraph, const unordered_set<string> &keywords) {
  // TODO - you fill in here.
  // 记录当前cover的关键字
  std::unordered_map<string, int> keywords_to_cover;
  for (auto &k: keywords) {
      ++keywords_to_cover[k];
  }
  int remain_to_cover = keywords_to_cover.size();

  Subarray result = {-1, -1};
  for (int left = 0, right = 0; right < paragraph.size(); ++right) {
      auto r_word = paragraph[right];
      //keywords 中的同一个单词可能会在paragraph中出现多次
      if (keywords.count(r_word) && --keywords_to_cover[r_word]>=0) {
          --remain_to_cover;
      }
      // remain_to_cover == 0 意味着当前已经找到一个满足条件的区间，将left右移至下一个关键词位置。
      while (remain_to_cover == 0) {
          if (result.start == -1 || right - left < result.end - result.start) {
              result = {left, right};
          }
          if (keywords.count(paragraph[left]) && ++keywords_to_cover[paragraph[left]] > 0){
              ++remain_to_cover;
          }
          ++left;
      }
  }
  return result;
}

struct Subarray {
  // Represent subarray by starting and ending indices, inclusive.
  int start, end;
};

Subarray FindSmallestSequentiallyCoveringSubset(
    const vector<string>& paragraph, const vector<string>& keywords) {
  // TODO - you fill in here.
  // 记录keyword的位置
  std::unordered_map<string, int> keyword_to_idx;
  for (int i = 0; i < keywords.size(); ++i) {
//      keyword_to_idx[keywords[i]] = i;
      keyword_to_idx.emplace(keywords[i] , i);
  }

  // 少打一个,  调了半天...
  vector<int> key_latest_occurrence(keywords.size(), -1);

  vector<int> shortest_subarray(keywords.size(), std::numeric_limits<int>::max());
  Subarray ret = {-1, -1};
  int shortest_array_len = std::numeric_limits<int>::max();
  for (int i = 0; i < paragraph.size(); ++i) {
      if (keyword_to_idx.count(paragraph[i])) {
          int key_idx = keyword_to_idx[paragraph[i]];
          if (key_idx == 0) {
              // 第一个keyword
              shortest_subarray[key_idx] = 1;
          } else if (shortest_subarray[key_idx-1] != std::numeric_limits<int>::max()) {

              shortest_subarray[key_idx] = shortest_subarray[key_idx-1] + i - key_latest_occurrence[key_idx-1];
          }
          key_latest_occurrence[key_idx] = i;

          if (key_idx == keywords.size() - 1 && shortest_array_len > shortest_subarray.back()) {
              shortest_array_len = shortest_subarray.back();
              ret = {i - shortest_subarray.back() + 1, i};
          }
      }
  }
  return ret;
}

int LongestSubarrayWithDistinctEntries(const vector<int>& A) {
  // TODO - you fill in here.
  std::unordered_map<int, int> last_appearance; //记录元素上次出现的位置
  int longest_array_start_idx = 0, result = 0;
  for (int i = 0; i < A.size(); ++i) {
      auto insert_ret = last_appearance.insert({A[i], i});
      if (!insert_ret.second) {  // 插入不成功, 说明A[i]之前出现过
          int prev_idx = insert_ret.first->second;
          if (prev_idx >= longest_array_start_idx) { // A[i] 在滑窗内
              longest_array_start_idx = prev_idx + 1;
          }
          insert_ret.first->second = i; // 更新位置
      }
      result = std::max(result, i - longest_array_start_idx + 1);
  }
  return result;
}

int LongestContainedRange(const vector<int>& A) {
  // TODO - you fill in here.
  std::unordered_set<int> filter(A.begin(), A.end());
  int ret = 0;
  while (!filter.empty()) {
      int c_val = *filter.begin();
      filter.erase(c_val);
      int c_length = 1, bias = 1;
      while(filter.count(c_val+bias)) {
          filter.erase(c_val + bias); // 剔除已经访问过的元素
          ++bias;
          ++c_length;
      }
      bias = -1;
      while (filter.count(c_val + bias)) {
          filter.erase(c_val + bias);
          --bias;
          ++c_length;
      }
      ret = std::max(ret, c_length);
  }
  return ret;
}

bool FindAllSubstringsHelper(const string& s, std::unordered_map<string, int> word_cnt, int st_idx, int word_len, int num_words) {
    int nb = 0;
    for (int i = st_idx; nb < num_words;) {
        string c_sub = s.substr(i, word_len);
        auto iter = word_cnt.find(c_sub);
        if (iter == word_cnt.end()) {
            return false; //不匹配
        }
        if (--(iter->second) < 0) {
            return false; // 出现过多次
        }
        ++nb;
        i = st_idx + nb * word_len;
    }
    return true;
}
vector<int> FindAllSubstrings(const string& s, const vector<string>& words) {
  // TODO - you fill in here.
  std::unordered_map<string, int> word_cnt;
  for (auto &each: words) {
      ++word_cnt[each];
  }
  int word_len = words[0].size();
  vector<int> ret;
  // 下面的条件是 <=
  for (int i = 0; i + word_len * words.size() <= s.size(); ++i) {
      if (FindAllSubstringsHelper(s, word_cnt, i, word_len, words.size())) {
          ret.emplace_back(i);
      }
  }

  return ret;
}

bool TestCollatzConjecture(int n) {
  // TODO - you fill in here.
  return true;
}

bool TestCollatzConjecture(int n) {
  // TODO - you fill in here.
  std::unordered_set<long> table;
  for (int i = 1; i <= n; ++i) {
      long c_val = i;
      std::unordered_set<long> search_path;
      while (c_val != 1) {
          if (table.find(c_val) != table.end()) {
              // 当前序列已经存在过
              break;
          }
          if (search_path.find(c_val) != search_path.end()) {
              return false; // 序列进入循环， 证伪
          }
          search_path.insert(c_val);
          if (c_val % 2 == 0) {
              c_val /= 2;
          } else {
              c_val = c_val * 3 + 1;
          }
      }
      table.insert(search_path.begin(), search_path.end()); //更新搜索序列
  }
  return true;
}