Hai con trỏ, không bảng
Vì sao điều này quan trọng "Tìm hai thứ cộng lại bằng X" có một câu trả lời nổi tiếng: đặt mọi thứ vào một tập và tra phần tử đi cặp. Nó nhanh, và nó cần một bản sao của toàn bộ dữ liệu. Khi dữ liệu đã được sắp xếp, bạn gần như không cần bộ nhớ nào.
Một dịch vụ quà tặng bán các gói gồm hai sản phẩm khác nhau với một giá gói cố định. Bảng giá sản phẩm đã được sắp xếp, không có giá trị lặp, và nằm trên một thiết bị nhúng có rất ít bộ nhớ trống. Với một giá gói, bạn cần số cặp sản phẩm có giá cộng lại đúng bằng giá đó.
prices = [1, 2, 3, 4, 5, 6] # sorted, no repeats
count_pairs(Tape(prices), 7) # 3: (1, 6), (2, 5), (3, 4)Viết count_pairs(tape, target). tape là một Tape các giá nguyên, sắp xếp tăng dần, không có giá trị lặp. Trả về số cặp gồm hai phần tử khác nhau cộng lại đúng bằng target (mỗi cặp tính một lần). Ngân sách: với 20.000 phần tử đọc nhiều nhất 60.000 giá trị, và dùng nhiều nhất 16.000 byte bộ nhớ làm việc trong lúc hàm của bạn chạy (đo bằng tracemalloc; một tập hay list 20.000 giá là hơn 150.000 byte). len(tape) là miễn phí.
Bạn thấy vấn đề gì trong bài học này? Hãy báo cáo nó · Hỏi về bài học này
Bài tập này sẽ sớm mở.
Hoàn thành bài học trước đó để mở khóa bài này. Toàn bộ khóa học là miễn phí, không cần tài khoản, và bạn có thể đọc bài học này ngay bây giờ.
Trình duyệt này đang chặn cookie cho learn.floati.life, nên các bài học bạn đã hoàn thành tại đây không thể mở theo thứ tự. Hãy cho phép cookie cho trang web này và tải lại trang.