Leetcode iki toplamı
Şu anda python arka planından gelen c ++ 'ı öğreniyorum, bu nedenle aşağıdaki problem ifadesi için python ve c ++' da bir çözüm ekleyeceğim:
Sayı tamsayı dizisi ve bir tamsayı hedefi verildiğinde, iki sayının dizinlerini toplamları hedefe kadar gelecek şekilde döndür. Her girdinin tam olarak bir çözümü olacağını varsayabilir ve aynı öğeyi iki kez kullanamayabilirsiniz. Cevabı herhangi bir sırayla iade edebilirsiniz.
Örnek 1:
Giriş: nums = [2,7,11,15], hedef = 9
Çıktı: [0,1]
Örnek 2:
Giriş: nums = [3,2,4], hedef = 6
Çıktı: [1,2]
Performans iyileştirmeleri için geri bildiriminizi / önerilerinizi / diğer önerilerinizi duymak isterim. İşte bağlantı
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')
Leetcode istatistikleri:
Çalışma Zamanı: 772 ms, Two Sum için Python çevrimiçi gönderimlerinin% 36.98'inden daha hızlı. Bellek Kullanımı: 14,4 MB, İki Toplam için Python çevrimiçi gönderimlerinin% 49,82'sinden az.
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");
}
Leetcode istatistikleri:
Çalışma süresi: 384 ms, Two Sum için C ++ çevrimiçi gönderimlerin% 34.03'ünden daha hızlı. Bellek Kullanımı: 9.3 MB, Two Sum için C ++ çevrimiçi gönderimlerinin% 12.99'undan azı.
Yanıtlar
C ++ konusunda uzman değilim ama Python çözümü hakkında geri bildirim verebilirim.
Mevcut çözümünüz \$O(n^2)\$. Temel olarak, her numara için ngiriş numsbulmak target - niçinde nums. Nasıl geliştirilir?
Algoritmanın ikinci bölümü \ ' den geliştirilebilir$O(n)\$için \$O(1)\$. target - nBir listede aramak yerine bir sözlük kullanabilirsiniz:
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
Sonuçlar:
Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
Yalnızca ihtiyacınız olan başlık dosyalarını ekleyin
Senin içinde two_sum.hdosyaya ihtiyacınız yok iostreamonun işlevselliğini herhangi kullanmıyorsanız beri. #includeDosyayı kelimenin tam anlamıyla kopyalayıp yapıştırdığını unutmayın , bu nedenle bu başlık dosyasını birden çok dosyaya eklerseniz, derleme sürelerinizi potansiyel olarak yavaşlatabilir.
Bölünmüş bildirimler ve tanımlar
Tipik olarak, dosyalarınızı iki bölüme ayırırsınız: başlık dosyası (normalde ile biten *.h, *.hpp, *.hh) ve kaynak dosyası (normalde ile biten *.cpp, *.cc). Başlık dosyası yalnızca bildirimlerden oluşur ve kaynak dosya uygulamayı içerir.
Yani sizin durumunuzda başlık dosyanız şöyle görünecek:
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
ve kaynak dosyanız şöyle görünecek:
two_sum.cpp
#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
...
}
Aslında, two_sum.h(uygulama ile birlikte) kendinizi birden fazla dosyaya dahil etmeye çalışırsanız , Tek Tanım Kuralı'nı ihlal etmiş olursunuz . Kaynak dosyalarınız aynı işlevin birden çok tanımını içerir ve bağlayıcı bir hata verir. Etrafta dolaşmanın bir yolu, işlevleri işaretlemektir inline, ancak büyük olasılıkla ilkini yapmak istersiniz.
Hiçbir using namespacebaşlık dosyalarında
using namespaceBir başlık dosyasında yapmayın veya varyantlarından herhangi birini yapmayın . Başlık dosyası birden çok kaynak dosyaya kopyalandığından, can sıkıcı hatalara neden olma potansiyeli vardır. Buraya bakın
Sabit referansı kullan
Yana two_sum_solutionmodifiye olmayan numsvektör, const referans ile geçmek.
dizi indeksleri için size_t - int
Dizi indeksleri için int yerine size_t kullanmayı düşünün
autoMümkün olduğunca çok kullanın
Kodunuzda auto, türü belirtmek yerine kullanabileceğiniz birkaç örnek vardır . Örnekler:
auto match = target - nums[i];
auto v = two_sum_solution(v1, 22);
En içteki döngü anlamsız
Basitçe yap
results.push_back(i);
results.push_back(j);
Ayrıca, çözümü bulduğunuzda, sonucu hemen döndürmek isteyebilirsiniz.
Verilen dizi üzerinde ilk yinelemede bir değer haritası -> indeks oluşturarak performansı artırabilirsiniz.
Şu anda, programınız aşağıdakileri yapmaktadır (zaman karmaşıklığı):
index, valuedizinin tüm çiftlerini yineleyin ( \$ O(n) \$)- aramak
target - value(dizideki \$ O(n) \$) - arama dizini
target - value( \$ O(n) \$)
Ve bunların hepsi iç içe olduğundan, \$ O(n^2) \$(değil \$ n^3 \$ çünkü her yineleme için son arama yapılmamaktadır).
Önerdiğim çözüm:
- Bir harita / dikte oluştur
{value: index}( \$ O(n) \$) index, valueDizi üzerinde yineleyin ( \$ O(n) \$)- Haritadan / dikteden ( \$ 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
This is interesting to me because I come from a C background and started using Python the past few years for work, so I've had the reverse path as you. When I started Python, I greatly preferred solutions like yours because looping through lists is so explicit and clear.
However, I since learned that more proficient Python programmers at work understand my code better when I use the standard library. Once I began to invest in learning those tools, it had the double effect of 1) making my code more succinct and 2) being more efficient in time and/or space.
In this case, I would solve the problem with combinations from the itertools package:
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)
There's probably an even better more succinct and clear solution using Numpy, which is effectively standard library in my line of work (data science) but that's not true everywhere.
One thing that's different than your code: there is no room for off-by-one-errors. In my experience, code like this
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
is easy for me to write, hard to read and maintainability spans the whole gambit from easy to impossible. In other words, managing indices manually in Python gives me just enough rope to hang myself with, and standard library functions have been a great alternative.
Know your containers
std::unordered_map is your friend in this problem. Whenever you've never previously seen a number, simply use the operator[] or insert function to add the number and its index. When using find, it will return an iterator, which is a key-value pair.
eg:
auto location = m.find(numToFind);
location->first is your key, and
location->second is your value
When you return, don't use push_back
You can simply return an initializer list like: {i,j}.