Algoritmos & Estruturas de Dados

1function twoSum(nums, target) {
2  const map = new Map();
3
4  for (let i = 0; i < nums.length; i++) {
5    // Calcula o complemento necessário
6    const complement = target - nums[i];
7
8    // Verifica se o complemento já foi visto
9    if (map.has(complement)) {
10      return [map.get(complement), i];
11    }
12
13    // Armazena o valor atual e seu índice
14    map.set(nums[i], i);
15  }
16
17  return [];
18}

1class HashTable {
2  constructor(size = 7) {
3    this.buckets = new Array(size).fill(null).map(() => []);
4    this.size = size;
5  }
6
7  hash(key) {
8    let h = 0;
9    for (const ch of key) h = (h + ch.charCodeAt(0)) % this.size;
10    return h;
11  }
12
13  set(key, value) {
14    const idx = this.hash(key);
15    const bucket = this.buckets[idx];
16    // Verifica se a chave já existe (atualiza)
17    const existing = bucket.find(([k]) => k === key);
18    if (existing) existing[1] = value;
19    else bucket.push([key, value]);
20  }
21
22  get(key) {
23    const idx = this.hash(key);
24    const pair = this.buckets[idx].find(([k]) => k === key);
25    return pair ? pair[1] : undefined;
26  }
27}

1function twoSumSorted(numbers, target) {
2  let left = 0;
3  let right = numbers.length - 1;
4
5  while (left < right) {
6    const sum = numbers[left] + numbers[right];
7
8    if (sum === target) {
9      return [left, right];
10    } else if (sum < target) {
11      // Soma muito pequena, avança esquerda
12      left++;
13    } else {
14      // Soma muito grande, recua direita
15      right--;
16    }
17  }
18
19  return [-1, -1];
20}

1function maxSumSubarray(arr, k) {
2  let windowSum = 0;
3
4  // Soma da primeira janela
5  for (let i = 0; i < k; i++) {
6    windowSum += arr[i];
7  }
8  let maxSum = windowSum;
9
10  // Desliza a janela
11  for (let i = k; i < arr.length; i++) {
12    // Remove elemento que saiu, adiciona novo
13    windowSum = windowSum - arr[i - k] + arr[i];
14
15    // Atualiza o máximo
16    maxSum = Math.max(maxSum, windowSum);
17  }
18
19  return maxSum;
20}

1function binarySearch(arr, target) {
2  let low = 0;
3  let high = arr.length - 1;
4
5  // Continua enquanto houver espaço de busca
6  while (low <= high) {
7    // Calcula o índice do meio
8    const mid = Math.floor((low + high) / 2);
9
10    if (arr[mid] === target) {
11      // Elemento encontrado!
12      return mid;
13    } else if (arr[mid] < target) {
14      // Descarta metade esquerda (valores menores)
15      low = mid + 1;
16    } else {
17      // Descarta metade direita (valores maiores)
18      high = mid - 1;
19    }
20  }
21
22  // Elemento não encontrado
23  return -1;
24}

1function buildPrefixSum(arr) {
2  const prefix = [0];
3
4  // Constrói o array de prefix sum
5  for (let i = 0; i < arr.length; i++) {
6    prefix.push(prefix[i] + arr[i]);
7  }
8
9  return prefix;
10}
11
12// Consulta de range em O(1)
13function rangeSum(prefix, left, right) {
14  return prefix[right + 1] - prefix[left];
15}

1function reverseList(head) {
2  let prev = null;
3  let curr = head;
4
5  while (curr !== null) {
6    // Salva o próximo nó
7    const next = curr.next;
8
9    // Inverte o ponteiro
10    curr.next = prev;
11
12    // Avança prev e curr
13    prev = curr;
14    curr = next;
15  }
16
17  // prev é o novo head
18  return prev;
19}

1function isValid(s) {
2  const stack = [];
3  const pairs = { ')': '(', ']': '[', '}': '{' };
4
5  for (const ch of s) {
6    if ('([{'.includes(ch)) {
7      // Abertura: push na stack
8      stack.push(ch);
9    } else {
10      // Fechamento: verifica match
11      if (stack.length === 0 || stack[stack.length - 1] !== pairs[ch]) {
12        return false;
13      }
14      // Match: pop da stack
15      stack.pop();
16    }
17  }
18
19  // Válido se stack vazia
20  return stack.length === 0;
21}

1function inOrderTraversal(root) {
2  const result = [];
3
4  function inOrder(node) {
5    if (node === null) return;
6
7    // Visita subárvore esquerda
8    inOrder(node.left);
9
10    // Processa o nó atual
11    result.push(node.val);
12
13    // Visita subárvore direita
14    inOrder(node.right);
15  }
16
17  inOrder(root);
18  return result; // Retorna valores em ordem crescente
19}

1class MinHeap {
2  constructor() { this.heap = []; }
3
4  insert(val) {
5    // Adiciona no final
6    this.heap.push(val);
7
8    // Bubble up: troca com pai enquanto menor
9    let idx = this.heap.length - 1;
10    while (idx > 0) {
11      const parent = Math.floor((idx - 1) / 2);
12      if (this.heap[parent] <= this.heap[idx]) break;
13      // Troca com o pai
14      [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
15      idx = parent;
16    }
17  }
18}

1class TrieNode {
2  constructor() {
3    this.children = {};
4    this.isEnd = false;
5  }
6}
7
8class Trie {
9  constructor() { this.root = new TrieNode(); }
10
11  insert(word) {
12    let node = this.root;
13
14    for (const ch of word) {
15      // Cria nó se não existe
16      if (!(ch in node.children)) {
17        node.children[ch] = new TrieNode();
18      }
19      // Avança para o filho
20      node = node.children[ch];
21    }
22
23    // Marca fim de palavra
24    node.isEnd = true;
25  }
26}

1function bfs(graph, start) {
2  const visited = new Set();
3  // Fila FIFO para controlar a ordem de visita
4  const queue = [start];
5
6  while (queue.length > 0) {
7    // Remove o primeiro da fila
8    const node = queue.shift();
9
10    if (visited.has(node)) continue;
11    // Marca o nó como visitado
12    visited.add(node);
13    console.log("Visitando:", node);
14
15    // Adiciona todos os vizinhos não visitados à fila
16    for (const neighbor of graph[node]) {
17      if (!visited.has(neighbor)) {
18        queue.push(neighbor);
19      }
20    }
21  }
22}
23
24// Exemplo de grafo como lista de adjacência
25const graph = {
26  A: ["B", "C"],
27  B: ["A", "D", "E"],
28  C: ["A", "F", "G"],
29  D: ["B", "H"],
30  E: ["B"],
31  F: ["C", "I"],
32  G: ["C"],
33  H: ["D"],
34  I: ["F"],
35};
36
37bfs(graph, "A");

1function mergeSort(arr) {
2  // Caso base: array de 1 elemento já está ordenado
3  if (arr.length <= 1) return arr;
4
5  // Divide o array ao meio
6  const mid = Math.floor(arr.length / 2);
7  const left = mergeSort(arr.slice(0, mid));
8  const right = mergeSort(arr.slice(mid));
9
10  // Combina as duas metades ordenadas
11  return merge(left, right);
12}
13
14function merge(left, right) {
15  const result = [];
16  let i = 0, j = 0;
17
18  // Compara elementos das duas metades e insere o menor
19  while (i < left.length && j < right.length) {
20    if (left[i] <= right[j]) {
21      result.push(left[i]);
22      i++;
23    } else {
24      result.push(right[j]);
25      j++;
26    }
27  }
28
29  // Copia os elementos restantes de cada metade
30  return result.concat(left.slice(i), right.slice(j));
31}

1function subsets(nums) {
2  const result = [];
3
4  function backtrack(start, current) {
5    // Adiciona o subset atual ao resultado
6    result.push([...current]);
7
8    // Tenta incluir cada elemento restante
9    for (let i = start; i < nums.length; i++) {
10      current.push(nums[i]);      // escolha
11      backtrack(i + 1, current);   // explora
12      current.pop();               // desfaz (backtrack)
13    }
14  }
15
16  backtrack(0, []);
17  return result;
18}

1function climbStairs(n) {
2  // Cria tabela DP
3  const dp = new Array(n + 1);
4
5  // Casos base
6  dp[0] = 1; // 1 forma de ficar parado
7  dp[1] = 1; // 1 forma de subir 1 degrau
8
9  // Preenche bottom-up
10  for (let i = 2; i <= n; i++) {
11    dp[i] = dp[i - 1] + dp[i - 2];
12  }
13
14  return dp[n];
15}

1function intervalScheduling(intervals) {
2  // Ordena por tempo de fim
3  intervals.sort((a, b) => a[1] - b[1]);
4
5  const selected = [];
6  let lastEnd = -Infinity;
7
8  for (const [start, end] of intervals) {
9    // Se não conflita com o último selecionado
10    if (start >= lastEnd) {
11      // Seleciona esta atividade
12      selected.push([start, end]);
13      lastEnd = end;
14    }
15  }
16
17  return selected;
18}

1function mergeIntervals(intervals) {
2  // Ordena por start
3  intervals.sort((a, b) => a[0] - b[0]);
4
5  const merged = [intervals[0]];
6
7  for (let i = 1; i < intervals.length; i++) {
8    const last = merged[merged.length - 1];
9
10    // Verifica overlap
11    if (intervals[i][0] <= last[1]) {
12      // Merge: estende o end
13      last[1] = Math.max(last[1], intervals[i][1]);
14    } else {
15      // Sem overlap: novo intervalo
16      merged.push(intervals[i]);
17    }
18  }
19
20  return merged;
21}

1function singleNumber(nums) {
2  let result = 0;
3
4  // XOR de todos os elementos
5  for (const num of nums) {
6    result ^= num;
7  }
8
9  // Duplicados se cancelam (a^a=0)
10  // Resta apenas o único
11  return result;
12}

1function topologicalSort(numNodes, edges) {
2  // Constrói grafo e calcula in-degrees
3  const adj = Array.from({length: numNodes}, () => []);
4  const inDegree = new Array(numNodes).fill(0);
5
6  for (const [u, v] of edges) {
7    adj[u].push(v);
8    inDegree[v]++;
9  }
10
11  // Enfileira nós com in-degree 0
12  const queue = [];
13  for (let i = 0; i < numNodes; i++) {
14    if (inDegree[i] === 0) queue.push(i);
15  }
16
17  const order = [];
18
19  while (queue.length > 0) {
20    const node = queue.shift();
21    order.push(node);
22
23    // Reduz in-degree dos vizinhos
24    for (const neighbor of adj[node]) {
25      inDegree[neighbor]--;
26      // Se in-degree chega a 0, enfileira
27      if (inDegree[neighbor] === 0) {
28        queue.push(neighbor);
29      }
30    }
31  }
32
33  return order;
34}