Leetcode due somma
Attualmente sto imparando il c ++ proveniente da uno sfondo di python, quindi includerò una soluzione in python e in c ++ per la seguente dichiarazione del problema:
Dato un array di numeri interi num e un obiettivo intero, restituisce gli indici dei due numeri in modo che si sommino a destinazione. Puoi presumere che ogni input abbia esattamente una soluzione e non puoi utilizzare lo stesso elemento due volte. Puoi restituire la risposta in qualsiasi ordine.
Esempio 1:
Input: nums = [2,7,11,15], target = 9
Uscita: [0,1]
Esempio 2:
Input: nums = [3,2,4], target = 6
Uscita: [1,2]
Vorrei sentire i vostri commenti / suggerimenti per miglioramenti delle prestazioni / altri suggerimenti. Ecco il link
two_sum.py
def two_sum(nums: list, target: int):
for i, n in enumerate(nums):
match = target - n
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
if __name__ == '__main__':
if result := two_sum([2, 7, 11, 15], 22):
print(f'Indices:\n{result}')
else:
print('No matches found')
Statistiche Leetcode:
Runtime: 772 ms, più veloce del 36,98% degli invii online di Python per Two Sum. Utilizzo della memoria: 14,4 MB, meno del 49,82% degli invii online di Python per Two Sum.
two_sum.h
#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;
vector<int> two_sum_solution(vector<int> &nums, int target) {
vector <int> results;
for (int i = 0; i < nums.size(); ++i) {
int match = target - nums[i];
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[j] == match) {
for (int index_match : {
i, j
})
results.push_back(index_match);
}
}
}
return results;
}
#endif //LEETCODE_TWO_SUM_H
main.cpp
#include <vector>
#include "two_sum.h"
using std::vector;
int main() {
vector<int> v1{2, 7, 11, 15};
vector<int> v = two_sum_solution(v1, 22);
if (!v.empty()) {
cout << "Indices:" << endl;
for (auto i: v)
cout << i << " ";
}
else (cout << "No matches found");
}
Statistiche Leetcode:
Runtime: 384 ms, più veloce del 34,03% degli invii in linea C ++ per Two Sum. Utilizzo della memoria: 9,3 MB, meno del 12,99% degli invii in linea C ++ per Two Sum.
Risposte
Non sono un esperto di C ++ ma posso dare un feedback sulla soluzione Python.
La tua soluzione attuale viene eseguita in \$O(n^2)\$. Fondamentalmente, per ogni numero ndi input nums, trova target - nin nums. Come migliorarlo?
La seconda parte dell'algoritmo può essere migliorata da \$O(n)\$a \$O(1)\$. Invece di cercare target - nin un elenco, puoi usare un dizionario:
def two_sum(nums: list, target: int):
num_index = {}
for i, n in enumerate(nums):
match = target - n
if match in num_index:
return num_index[match], i
num_index[n] = i
return -1
Risultati:
Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
Includi solo i file di intestazione di cui hai bisogno
Nel tuo two_sum.hfile, non è necessario iostream, poiché non stai utilizzando nessuna delle sue funzionalità. Ricorda che #includeletteralmente copia-incolla il file, quindi se includi questo file di intestazione in più file, potrebbe potenzialmente rallentare i tempi di compilazione.
Dichiarazioni e definizioni separate
In genere, dividi i tuoi file in due parti: il file di intestazione (normalmente termina con *.h, *.hpp, *.hh) e il file sorgente (normalmente termina con *.cpp, *.cc). Il file di intestazione consiste solo delle dichiarazioni e il file di origine contiene l'implementazione.
Quindi, nel tuo caso, il tuo file di intestazione sarà simile a questo:
two_sum.h
#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <vector>
std::vector<int> two_sum_solution(std::vector<int> &nums, int target);
#endif // LEETCODE_TWO_SUM_H
e il tuo file sorgente sarà simile a questo:
two_sum.cpp
#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
...
}
In effetti, se provi a includere il tuo two_sum.h(con l'implementazione) in più file, infrangeresti la regola di una definizione . I file di origine conterrebbero più definizioni della stessa funzione e il linker sputerà un errore. Un modo per aggirare è contrassegnare le funzioni inline, ma molto probabilmente vorrai fare il primo.
No using namespacenei file di intestazione
Non fare using namespaceo nessuna delle sue varianti in un file di intestazione. Poiché il file di intestazione viene copiato incollato in più file di origine, può causare fastidiosi errori. Vedere qui
Usa riferimento const
Poiché two_sum_solutionnon sta modificando il numsvettore, passalo per riferimento const.
size_t vs int per gli indici di array
Considera l'idea di usare size_t invece di int per gli indici degli array
Usa autoil più possibile
Ci sono un paio di istanze nel codice in cui puoi usare autoinvece di specificare il tipo. Esempi:
auto match = target - nums[i]; auto v = two_sum_solution(v1, 22);
Il ciclo più interno è inutile
Fallo semplicemente
results.push_back(i);
results.push_back(j);
Inoltre, una volta trovata la soluzione, potresti voler restituire immediatamente il risultato.
Puoi forse migliorare le prestazioni creando una mappa di valore -> indice nella prima iterazione sull'array dato.
Attualmente, il tuo programma esegue le seguenti operazioni (complessità temporale):
- itera su tutte le
index, valuecoppie dell'array ( \$ O(n) \$) - cerca
target - valuenell'array ( \$ O(n) \$) - indice di ricerca di
target - value( \$ O(n) \$)
E poiché sono tutti annidati, puoi \$ O(n^2) \$(non è \$ n^3 \$ perché l'ultima ricerca non viene eseguita per ogni iterazione).
La mia soluzione proposta:
- Crea una mappa / dict di
{value: index}( \$ O(n) \$) - Itera su
index, valuearray ( \$ O(n) \$) - Cerca e restituisci l'indice dalla mappa / dict ( \$ O(1) \$)
def two_sum(numbers: list[int], target: int):
lookup: dict = {
value: index
for index, value in enumerate(numbers)
}
for index, value in enumerate(numbers):
match = target - value
if search_index := lookup.get(match):
return index, search_index
return None
Questo è interessante per me perché vengo da uno sfondo C e ho iniziato a usare Python negli ultimi anni per lavoro, quindi ho seguito il percorso inverso come te. Quando ho avviato Python, preferivo di gran lunga soluzioni come la tua perché scorrere gli elenchi è così esplicito e chiaro.
Tuttavia, da allora ho imparato che i programmatori Python più esperti al lavoro comprendono meglio il mio codice quando uso la libreria standard. Una volta che ho iniziato a investire nell'apprendimento di questi strumenti, ha avuto il doppio effetto di 1) rendere il mio codice più succinto e 2) essere più efficiente nel tempo e / o nello spazio.
In questo caso, risolverei il problema con combinationsdal itertoolspacchetto:
from itertools import combinations
def two_sum(nums, target):
pairs_with_indices = combinations(enumerate(nums), 2)
# result is a generator comprehension.
winning_pairs = ((index_i, index_j)
for (index_i, i), (index_j, j) in pairs_with_indices
if sum((i, j)) == target)
# Insert as much error checking as you need...
return next(winning_pairs)
Probabilmente c'è una soluzione ancora migliore, più concisa e chiara usando Numpy, che è effettivamente una libreria standard nel mio campo di lavoro (scienza dei dati) ma non è vero ovunque.
Una cosa è diversa dal tuo codice: non c'è spazio per errori off-by-one. Nella mia esperienza, codice come questo
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
è facile per me scrivere, difficile da leggere e la manutenibilità abbraccia l'intera mossa da facile a impossibile. In altre parole, la gestione manuale degli indici in Python mi dà abbastanza corda per impiccarmi e le funzioni di libreria standard sono state un'ottima alternativa.
Conosci i tuoi contenitori
std::unordered_mapè tuo amico in questo problema. Ogni volta che non hai mai visto un numero in precedenza, usa semplicemente la funzione operator[]o insertper aggiungere il numero e il suo indice. Quando si utilizza find, restituirà un iteratore, che è una key-valuecoppia.
per esempio: auto location = m.find(numToFind);
location->firstè la tua chiave ed location->secondè il tuo valore
Quando torni, non usare push_back
Si può semplicemente restituire un lista di inizializzazione del tipo: {i,j}.