Leetcode hai tổng
Tôi hiện đang học c ++ từ nền tảng python, vì vậy tôi sẽ bao gồm một giải pháp trong python và trong c ++ cho câu lệnh vấn đề sau:
Cho một mảng các số nguyên và một mục tiêu số nguyên, trả về các chỉ số của hai số sao cho chúng cộng lại thành mục tiêu. Bạn có thể giả định rằng mỗi đầu vào sẽ có chính xác một giải pháp và bạn không thể sử dụng cùng một phần tử hai lần. Bạn có thể gửi lại câu trả lời theo bất kỳ thứ tự nào.
Ví dụ 1:
Đầu vào: nums = [2,7,11,15], target = 9
Đầu ra: [0,1]
Ví dụ 2:
Đầu vào: nums = [3,2,4], target = 6
Đầu ra: [1,2]
Tôi muốn nghe phản hồi / đề xuất của bạn để cải thiện hiệu suất / đề xuất khác. Đây là liên kết
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')
Thống kê Leetcode:
Thời gian chạy: 772 mili giây, nhanh hơn 36,98% số lần gửi trực tuyến Python cho Two Sum. Sử dụng bộ nhớ: 14,4 MB, ít hơn 49,82% số lần gửi trực tuyến Python cho 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");
}
Thống kê Leetcode:
Thời gian chạy: 384 mili giây, nhanh hơn 34,03% số lần gửi trực tuyến C ++ cho Two Sum. Sử dụng bộ nhớ: 9,3 MB, ít hơn 12,99% số lần gửi trực tuyến C ++ cho Hai Tổng.
Trả lời
Tôi không phải là chuyên gia về C ++ nhưng tôi có thể đưa ra phản hồi về giải pháp Python.
Giải pháp hiện tại của bạn chạy trong \$O(n^2)\$. Về cơ bản, với mỗi số nđầu vào nums, hãy tìm target - ntrong nums. Làm thế nào để cải thiện nó?
Phần thứ hai của thuật toán có thể được cải thiện từ \$O(n)\$đến \$O(1)\$. Thay vì tra cứu target - ntrong danh sách, bạn có thể sử dụng từ điển:
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
Các kết quả:
Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
Chỉ bao gồm các tệp tiêu đề mà bạn cần
Trong two_sum.htệp của bạn , bạn không cần iostream, vì bạn không sử dụng bất kỳ chức năng nào của nó. Hãy nhớ rằng #includenghĩa đen là sao chép-dán tệp, vì vậy nếu bạn đưa tệp tiêu đề này vào nhiều tệp, nó có thể làm chậm thời gian biên dịch của bạn.
Khai báo và định nghĩa tách
Thông thường, bạn sẽ chia tệp của mình thành hai phần: tệp tiêu đề (thường kết thúc bằng *.h, *.hpp, *.hh) và tệp nguồn (thường kết thúc bằng *.cpp, *.cc). Tệp tiêu đề chỉ bao gồm các khai báo và tệp nguồn chứa phần triển khai.
Vì vậy, trong trường hợp của bạn, tệp tiêu đề của bạn sẽ trông như thế này:
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
và tệp nguồn của bạn sẽ trông như thế này:
two_sum.cpp
#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
...
}
Trên thực tế, nếu bạn cố gắng bao gồm two_sum.h(cùng với việc triển khai) vào nhiều tệp, bạn sẽ vi phạm Quy tắc một định nghĩa . Các tệp nguồn của bạn sẽ chứa nhiều định nghĩa của cùng một chức năng và trình liên kết sẽ đưa ra lỗi. Một cách để thực hiện là đánh dấu các chức năng inline, nhưng rất có thể bạn muốn làm điều đó.
Không có using namespacetrong tệp tiêu đề
Không làm using namespacehoặc bất kỳ biến thể nào của nó trong tệp tiêu đề. Vì tệp tiêu đề được sao chép dán khắp nhiều tệp nguồn, nó có khả năng gây ra các lỗi khó chịu. Xem tại đây
Sử dụng tham chiếu const
Vì two_sum_solutionkhông sửa đổi numsvectơ, hãy chuyển nó bằng tham chiếu const.
size_t so với int cho chỉ số mảng
Cân nhắc sử dụng size_t thay vì int cho các chỉ số mảng
Sử dụng autocàng nhiều càng tốt
Có một vài trường hợp trong mã của bạn mà bạn có thể sử dụng autothay vì chỉ định loại. Ví dụ:
auto match = target - nums[i];
auto v = two_sum_solution(v1, 22);
Vòng lặp bên trong nhất là vô nghĩa
Đơn giản là làm
results.push_back(i);
results.push_back(j);
Ngoài ra, khi bạn đã tìm ra giải pháp, bạn có thể muốn trả lại kết quả ngay lập tức.
Bạn có thể có thể cải thiện hiệu suất bằng cách tạo một bản đồ giá trị -> chỉ mục trong lần lặp đầu tiên trên mảng đã cho.
Hiện tại, chương trình của bạn thực hiện những việc sau (độ phức tạp về thời gian):
- lặp qua tất cả các
index, valuecặp của mảng ( \$ O(n) \$) - tìm kiếm
target - valuetrong mảng ( \$ O(n) \$) - chỉ mục tra cứu của
target - value( \$ O(n) \$)
Và vì tất cả những thứ này đều được lồng vào nhau, bạn có thể \$ O(n^2) \$(nó không phải là \$ n^3 \$ bởi vì tra cứu cuối cùng không được thực hiện cho mỗi lần lặp).
Giải pháp đề xuất của tôi:
- Tạo bản đồ / dict của
{value: index}( \$ O(n) \$) - Lặp lại
index, valuemảng ( \$ O(n) \$) - Tra cứu và trả về chỉ mục từ bản đồ / 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
Điều này thật thú vị đối với tôi bởi vì tôi đến từ nền tảng C và bắt đầu sử dụng Python vài năm qua cho công việc, vì vậy tôi đã có con đường ngược lại như bạn. Khi tôi bắt đầu Python, tôi rất thích các giải pháp như của bạn vì việc lặp qua các danh sách rất rõ ràng và rõ ràng.
Tuy nhiên, kể từ khi tôi biết được rằng các lập trình viên Python thành thạo hơn tại nơi làm việc hiểu mã của tôi tốt hơn khi tôi sử dụng thư viện chuẩn. Một khi tôi bắt đầu đầu tư vào việc học những công cụ đó, nó có tác dụng kép 1) làm cho mã của tôi ngắn gọn hơn và 2) hiệu quả hơn về thời gian và / hoặc không gian.
Trong trường hợp này, tôi sẽ giải quyết vấn đề combinationstừ itertoolsgói:
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)
Có lẽ còn có một giải pháp rõ ràng và ngắn gọn hơn tốt hơn bằng cách sử dụng Numpy, đây là thư viện tiêu chuẩn hiệu quả trong dòng công việc của tôi (khoa học dữ liệu) nhưng điều đó không đúng ở mọi nơi.
Một điều khác với mã của bạn: không có chỗ cho lỗi từng lỗi một. Theo kinh nghiệm của tôi, mã như thế này
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
đối với tôi rất dễ viết, khó đọc và khả năng bảo trì trải dài trên toàn bộ gambit từ dễ đến không thể. Nói cách khác, việc quản lý các chỉ mục theo cách thủ công bằng Python giúp tôi có đủ sợi dây để gắn bó với bản thân và các hàm thư viện tiêu chuẩn là một sự thay thế tuyệt vời.
Biết vùng chứa của bạn
std::unordered_maplà bạn của bạn trong vấn đề này. Bất cứ khi nào bạn chưa từng nhìn thấy một số nào trước đây, chỉ cần sử dụng operator[]hoặc inserthàm để thêm số và chỉ mục của nó. Khi sử dụng find, nó sẽ trả về một trình lặp, là một key-valuecặp.
ví dụ:
auto location = m.find(numToFind);
location->firstlà chìa khóa của bạn và
location->secondlà giá trị của bạn
Khi bạn quay lại, không sử dụng push_back
Bạn chỉ có thể trả về một danh sách initializer như: {i,j}.