Esplorazione dei Pattern di Programmazione Essenziali

Nell’informatica, padroneggiare i principali pattern di programmazione può migliorare notevolmente le tue capacità di problem-solving. Questo articolo esplora una varietà di pattern, dalle tecniche più semplici come la somma prefixata fino a metodi più complessi come il backtracking, ciascuno utile per affrontare diverse tipologie di sfide.

1. Somma Prefixata (Prefix Sum)

Panoramica: La tecnica della somma prefixata consiste nel calcolare la somma cumulativa di un array (o di un’altra sequenza), permettendo di rispondere in modo efficiente a query di somma su intervalli.

Casi d’Uso:

• Problemi di query su intervalli
• Calcolo di medie mobili
• Risoluzione di problemi di programmazione dinamica

Esempio (JavaScript):

function prefixSums(arr) {
  const prefix = [0];
  for (let i = 0; i < arr.length; i++) {
    prefix.push(prefix[i] + arr[i]);
  }
  return prefix;
}

const arr = [1, 2, 3, 4];
console.log(prefixSums(arr)); // [0, 1, 3, 6, 10]

2. Tecnica dei Due Puntatori (Two Pointers)

Panoramica: La tecnica dei due puntatori utilizza due indici per attraversare strutture dati, spesso partendo da estremità opposte o muovendosi a velocità diverse.

Casi d’Uso:

• Trovare coppie che sommano a un valore specifico
• Fusione di array ordinati
• Rimozione di duplicati

Esempio (JavaScript):

function twoSumSorted(arr, target) {
  let left = 0,
    right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    else if (sum < target) left++;
    else right--;
  }
  return [];
}

console.log(twoSumSorted([1, 2, 3, 4, 6], 7)); // [0, 3]

3. Finestra Scorrevole (Sliding Window)

Panoramica: Questo pattern prevede il mantenimento di una finestra che scorre sui dati per calcolare dinamicamente i valori su sottoarray o sottostringhe.

Casi d’Uso:

• Trovare il sottoarray con somma massima/minima
• Risolvere problemi di sottostringhe nelle stringhe
• Elaborazione di dati in tempo reale

Esempio (JavaScript):

function maxSubarraySum(arr, k) {
  let maxSum = 0,
    currentSum = 0;
  for (let i = 0; i < arr.length; i++) {
    currentSum += arr[i];
    if (i >= k - 1) {
      maxSum = Math.max(maxSum, currentSum);
      currentSum -= arr[i - (k - 1)];
    }
  }
  return maxSum;
}

console.log(maxSubarraySum([1, 4, 2, 10, 23, 3, 1, 0, 20], 4)); // 39

4. Inversione di una Lista Collegata (Linked List Reversal)

Panoramica: L’inversione di una lista collegata è un pattern comune che consiste nel invertire i puntatori di una lista per modificarne l’ordine dei nodi.

Casi d’Uso:

• Riordinare i dati
• Risolvere problemi nei colloqui tecnici
• Manipolare strutture dati

Esempio (JavaScript):

function reverseLinkedList(head) {
  let prev = null;
  let current = head;
  while (current !== null) {
    let next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

5. Stack Monotonico (Monotonic Stack)

Panoramica: Uno stack monotonico viene mantenuto in ordine crescente o decrescente. È utile per risolvere problemi che richiedono di trovare l’elemento successivo maggiore o minore.

Casi d’Uso:

• Problemi di intervallo azionario (Stock Span)
• Trovare gli elementi più vicini maggiori o minori
• Problemi sui diagrammi a istogramma

Esempio (JavaScript):

function nextGreaterElements(arr) {
  const result = new Array(arr.length).fill(-1);
  const stack = [];
  for (let i = 0; i < arr.length; i++) {
    while (stack.length && arr[i] > arr[stack[stack.length - 1]]) {
      result[stack.pop()] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

console.log(nextGreaterElements([2, 1, 2, 4, 3])); // [4, 2, 4, -1, -1]

6. Primi K Elementi (Top K Elements)

Panoramica: Questo pattern consiste nel trovare i primi K elementi in un dataset, spesso utilizzando heap.

Casi d’Uso:

• Problemi di ranking o ordinamento
• Analisi dei dati in tempo reale
• Sistemi di raccomandazione

Esempio (JavaScript con un Min-Heap):

class MinHeap {
  constructor() {
    this.heap = [];
  }

  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ];
      index = parentIndex;
    }
  }

  extractMin() {
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.sinkDown(0);
    return min;
  }

  sinkDown(index) {
    const length = this.heap.length;
    while (true) {
      let left = 2 * index + 1;
      let right = 2 * index + 2;
      let smallest = index;

      if (left < length && this.heap[left] < this.heap[smallest])
        smallest = left;
      if (right < length && this.heap[right] < this.heap[smallest])
        smallest = right;
      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] = [
        this.heap[smallest],
        this.heap[index],
      ];
      index = smallest;
    }
  }
}

function findTopKElements(nums, k) {
  let minHeap = new MinHeap();
  for (let num of nums) {
    minHeap.insert(num);
    if (minHeap.heap.length > k) {
      minHeap.extractMin();
    }
  }
  return minHeap.heap;
}

console.log(findTopKElements([3, 1, 5, 12, 2, 11, 7], 3)); // Output: Top 3 elements

7. Intervalli Sovrapposti

Panoramica: Questo modello riguarda la fusione o l’elaborazione di intervalli che si sovrappongono, un compito comune nei problemi di pianificazione.

Casi d’uso:

• Fusione degli orari delle riunioni
• Sistemi di prenotazione
• Applicazioni per calendari

Esempio (JavaScript):

function mergeIntervals(intervals) {
  if (!intervals.length) return intervals;
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      merged.push(intervals[i]);
    }
  }
  return merged;
}

console.log(
  mergeIntervals([
    [1, 3],
    [2, 6],
    [8, 10],
    [15, 18],
  ]),
); // [[1,6],[8,10],[15,18]]

8. Ricerca Binaria Modificata

Panoramica: Una variante della classica ricerca binaria, questo modello è adattato per trovare risposte in uno spazio di ricerca modificato o vincolato.

Casi d’uso:

• Trovare un elemento di picco
• Ricerca in array ordinati ruotati
• Problemi di ottimizzazione in cui una funzione di decisione è monotona

Esempio (JavaScript - Trovare un elemento di picco):

function findPeakElement(nums) {
  let left = 0,
    right = nums.length - 1;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] < nums[mid + 1]) left = mid + 1;
    else right = mid;
  }
  return left;
}

console.log(findPeakElement([1, 2, 3, 1])); // 2

9. Ricerca in Profondità (DFS)

Panoramica: DFS è una tecnica di traversamento di grafi che esplora il più lontano possibile lungo ogni ramo prima di fare marcia indietro.

Casi d’uso:

• Risoluzione di enigmi come i labirinti
• Ordinamento topologico
• Componenti connesse nei grafi

Esempio (JavaScript):

function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  console.log(start);
  for (let neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

const graph = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F"],
  D: [],
  E: ["F"],
  F: [],
};

dfs(graph, "A");

10. Ricerca in Ampiezza (BFS)

Panoramica: BFS esplora un grafo livello per livello, rendendolo ideale per trovare il percorso più breve nei grafi non ponderati.

Casi d’uso:

• Problemi di percorso più breve
• Traversamento per ordine di livello negli alberi
• Analisi delle reti sociali

Esempio (JavaScript):

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set([start]);
  while (queue.length) {
    const vertex = queue.shift();
    console.log(vertex);
    for (let neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

bfs(graph, "A");

11. Traversamento di Matrice

Panoramica: Il traversamento di matrice consiste nel navigare attraverso un array 2D, un’operazione comune nell’elaborazione delle immagini e nello sviluppo di giochi.

Casi d’uso:

• Ricerca di elementi in una griglia
• Algoritmi di riempimento per inondazione (Flood Fill)
• Trovare percorsi nei labirinti

Esempio (JavaScript):

function traverseMatrix(matrix) {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      console.log(matrix[i][j]);
    }
  }
}

const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];
traverseMatrix(matrix);

12. Backtracking

Panoramica: Il backtracking è una tecnica ricorsiva utilizzata per risolvere i problemi in modo incrementale, abbandonando le soluzioni che non soddisfano i criteri.

Casi d’uso:

• Risoluzione di puzzle (ad esempio, Sudoku, N-Queens)
• Problemi combinatori
• Problemi di soddisfazione dei vincoli

Esempio (JavaScript - N-Queens):

function solveNQueens(n) {
  function isSafe(board, row, col) {
    for (let i = 0; i < row; i++) {
      if (board[i] === col || Math.abs(board[i] - col) === row - i) {
        return false;
      }
    }
    return true;
  }

  function backtrack(board, row) {
    if (row === n) {
      solutions.push([...board]);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (isSafe(board, row, col)) {
        board[row] = col;
        backtrack(board, row + 1);
        board[row] = -1;
      }
    }
  }

  let solutions = [];
  backtrack(new Array(n).fill(-1), 0);
  return solutions;
}

console.log(solveNQueens(4));

Conclusione

Ognuno di questi modelli di programmazione è uno strumento potente nel kit di un sviluppatore. Che tu stia ottimizzando le prestazioni del tuo codice con somme prefissate o risolvendo puzzle complessi con il backtracking, comprendere queste tecniche ti aiuterà ad affrontare una vasta gamma di problemi in modo efficace. Sperimenta con questi modelli, integrali nei tuoi progetti e migliora le tue capacità di problem solving!