Skip to main content

Другие задачи

Хэш-карты почти вездесущи. Мы обсудили некоторые из наиболее распространенных шаблонов, но существует неограниченное количество способов включения хэш-таблиц в алгоритм. Из-за того, насколько важны хэш-таблицы, мы рассмотрим еще несколько примеров того, как хэш-таблицы могут использоваться в различных задачах. Крайне важно, чтобы вы чувствовали себя комфортно с хэш-таблицами, если вы хотите пройти собеседование.

Пример 1​

https://leetcode.com/problems/group-anagrams/description/

Big O
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  if (strs.length <= 1) return [strs];
  const map = new Map();

  for (const str of strs) {
    const key = str.split("").sort().join("");
    const group = map.get(key) || [];
    group.push(str);
    map.set(key, group);
  }

  return Array.from(map.values());
};

Пример 2​

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Big O
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  const map = new Map();
  let max = 0;
  let start = 0;

  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i]) && map.get(s[i]) >= start) {
      start = map.get(s[i]) + 1;
    }

    map.set(s[i], i);
    max = Math.max(max, i - start + 1);
  }

  return max;
};

Стоит прорешать для лучшего понимания