Leetcode two sum
Obecnie uczę się języka C ++ pochodzącego z języka Python, więc dołączę rozwiązanie w języku python i c ++ dla następującego stwierdzenia problemu:
Biorąc pod uwagę tablicę liczb całkowitych i docelową liczbę całkowitą, zwraca indeksy dwóch liczb tak, aby sumowały się do celu. Możesz założyć, że każde wejście miałoby dokładnie jedno rozwiązanie i nie możesz dwukrotnie użyć tego samego elementu. Możesz zwrócić odpowiedź w dowolnej kolejności.
Przykład 1:
Dane wejściowe: liczba = [2,7,11,15], cel = 9
Produkcja: [0,1]
Przykład 2:
Dane wejściowe: liczba = [3,2,4], cel = 6
Produkcja: [1,2]
Chciałbym poznać Twoją opinię / sugestie dotyczące ulepszeń wydajności / inne sugestie. Oto 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')
Statystyki Leetcode:
Czas działania: 772 ms, szybciej niż 36,98% zgłoszeń online w Pythonie dla dwóch sum. Wykorzystanie pamięci: 14,4 MB, mniej niż 49,82% zgłoszeń online w Pythonie dla dwóch 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");
}
Statystyki Leetcode:
Czas działania: 384 ms, szybciej niż 34,03% zgłoszeń online C ++ dla dwóch sum. Wykorzystanie pamięci: 9,3 MB, mniej niż 12,99% zgłoszeń online w języku C ++ dla dwóch sum.
Odpowiedzi
Nie jestem ekspertem w C ++, ale mogę podzielić się opinią na temat rozwiązania w Pythonie.
Twoje obecne rozwiązanie działa w \$O(n^2)\$. Zasadniczo dla każdej liczby ndanych wejściowych numsznajdź target - nw nums. Jak to ulepszyć?
Drugą część algorytmu można ulepszyć z \$O(n)\$do \$O(1)\$. Zamiast szukać target - nna liście, możesz użyć słownika:
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
Wyniki:
Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
Dołącz tylko te pliki nagłówkowe, których potrzebujesz
W swoim two_sum.hpliku nie potrzebujesz iostream, ponieważ nie używasz żadnej z jego funkcji. Pamiętaj, że #includedosłownie kopiuje-wkleja plik, więc jeśli dołączasz ten plik nagłówkowy do wielu plików, może to potencjalnie spowolnić czas kompilacji.
Podzielone deklaracje i definicje
Zazwyczaj możesz podzielić swoje pliki na dwie części: plik nagłówkowy (zwykle kończący się na *.h, *.hpp, *.hh) i plik źródłowy (zwykle kończący się na *.cpp, *.cc). Plik nagłówkowy składa się tylko z deklaracji, a plik źródłowy zawiera implementację.
W twoim przypadku plik nagłówkowy będzie wyglądał następująco:
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
a twój plik źródłowy będzie wyglądał następująco:
two_sum.cpp
#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
...
}
W rzeczywistości, jeśli spróbujesz zawrzeć swój two_sum.h(wraz z implementacją) w wielu plikach, złamiesz zasadę jednej definicji . Twoje pliki źródłowe będą zawierały wiele definicji tej samej funkcji, a linker wypluje błąd. Jednym ze sposobów obejścia jest zaznaczanie funkcji inline, ale najprawdopodobniej chcesz zrobić to pierwsze.
Nie using namespacew plikach nagłówkowych
Nie rób using namespaceani żadnego z jego wariantów w pliku nagłówkowym. Ponieważ plik nagłówkowy jest kopiowany i wklejany w wielu plikach źródłowych, może powodować irytujące błędy. Spójrz tutaj
Użyj odniesienia const
Ponieważ two_sum_solutionnie modyfikuje numswektora, przekaż go przez odwołanie do stałej.
size_t vs int dla indeksów tablicy
Rozważ użycie size_t zamiast int dla indeksów tablicowych
Używaj autojak najwięcej
W Twoim kodzie jest kilka przypadków, w których możesz użyć autozamiast określać typ. Przykłady:
auto match = target - nums[i]; auto v = two_sum_solution(v1, 22);
Najbardziej wewnętrzna pętla jest bezcelowa
Po prostu zrób
results.push_back(i);
results.push_back(j);
Ponadto po znalezieniu rozwiązania możesz chcieć natychmiast zwrócić wynik.
Być może możesz poprawić wydajność, tworząc mapę wartości -> indeks w pierwszej iteracji podanej tablicy.
Obecnie Twój program wykonuje następujące czynności (złożoność czasowa):
- iteruj po wszystkich
index, valueparach tablicy ( \$ O(n) \$) - szukaj
target - valuew tablicy ( \$ O(n) \$) - indeks wyszukiwania
target - value( \$ O(n) \$)
A ponieważ wszystkie są zagnieżdżone, możesz \$ O(n^2) \$(to nie jest \$ n^3 \$ ponieważ ostatnie wyszukiwanie nie jest wykonywane dla każdej iteracji).
Moje proponowane rozwiązanie:
- Utwórz mapę / dyktando
{value: index}( \$ O(n) \$) - Iteruj po
index, valuetablicy ( \$ O(n) \$) - Wyszukaj i zwróć indeks z mapy / 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
Jest to dla mnie interesujące, ponieważ pochodzę z języka C i zacząłem używać Pythona w pracy w ciągu ostatnich kilku lat, więc podobnie jak ty miałem odwrotną ścieżkę. Kiedy zaczynałem Pythona, bardzo preferowałem rozwiązania takie jak Twoje, ponieważ przeglądanie list jest tak wyraźne i przejrzyste.
Jednak od tego czasu dowiedziałem się, że bardziej biegli programiści Pythona w pracy lepiej rozumieją mój kod, gdy korzystam z biblioteki standardowej. Kiedy zacząłem inwestować w naukę tych narzędzi, przyniosło to podwójny efekt: 1) uczynił mój kod bardziej zwięzłym i 2) był bardziej wydajny w czasie i / lub przestrzeni.
W takim przypadku rozwiązałbym problem z combinationsz itertoolspaczki:
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)
Prawdopodobnie istnieje jeszcze lepsze, bardziej zwięzłe i przejrzyste rozwiązanie przy użyciu Numpy, która jest w rzeczywistości standardową biblioteką w mojej branży (nauka o danych), ale nie wszędzie jest to prawdą.
Jedyna rzecz, która różni się od twojego kodu: nie ma miejsca na błędy typu off-by-one. Z mojego doświadczenia wynika, że koduj w ten sposób
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
jest dla mnie łatwy do napisania, trudny do odczytania, a konserwacja obejmuje całą gambit od łatwych do niemożliwych. Innymi słowy, ręczne zarządzanie indeksami w Pythonie daje mi wystarczającą ilość liny, na której mogę się zawiesić, a standardowe funkcje biblioteczne były świetną alternatywą.
Poznaj swoje pojemniki
std::unordered_mapjest twoim przyjacielem w tym problemie. Jeśli nigdy wcześniej nie widziałeś liczby, po prostu użyj funkcji operator[]lub, insertaby dodać liczbę i jej indeks. Podczas używania findzwróci iterator, który jest key-valueparą.
na przykład: auto location = m.find(numToFind);
location->firstjest twoim kluczem i location->secondjest twoją wartością
Kiedy wrócisz, nie używaj push_back
Możesz po prostu wrócić listę initializer jak: {i,j}.