Last Stone Weight

Q: Độ phức tạp thời gian của Last Stone Weight là bao nhiêu?

Với đống cực đại, tối đa n-1 vòng gồm hai lần lấy phần tử ra và một lần thêm phần tử vào sẽ tốn thời gian O(n log n) và không gian O(n) . Sắp xếp toàn bộ đống sau mỗi vòng sẽ tốn thời gian O(n² log n) .

DễHeap

+10

Bạn có một đống đá, trong đó stones[i] là khối lượng của viên đá i. Ở mỗi lượt, lấy hai viên đá nặng nhất và đập chúng vào nhau. Nếu chúng có khối lượng bằng nhau, cả hai viên đều bị phá hủy. Nếu không, viên nhẹ hơn bị phá hủy, còn khối lượng của viên nặng hơn giảm đi bằng hiệu giữa hai khối lượng.

Hãy viết lastStoneWeight, hàm này thực hiện các lượt cho đến khi còn lại nhiều nhất một viên đá, rồi trả về khối lượng của viên đá đó hoặc 0 nếu không còn viên nào.

Hàm

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: trọng lượng của những viên đá trong đống
Trả vềinteger: trọng lượng của viên đá cuối cùng, hoặc 0 nếu không còn viên nào

Ràng buộc

1 ≤ stones.length ≤ 10⁴
1 ≤ stones[i] ≤ 1000

Ví dụ

Đầu vào: stones = [3, 9, 4, 6, 2]
Đầu ra: 0
Giải thích: 9 và 6 để lại 3, sau đó 4 và 3 để lại 1, rồi 3 và 2 để lại thêm một 1. Hai viên đá 1 phá hủy lẫn nhau, nên đáp án là 0.

Đầu vào: stones = [10, 4, 1]
Đầu ra: 5
Giải thích: 10 và 4 còn lại 6, và 6 với 1 còn lại 5. Còn lại một viên đá nặng 5.

Đầu vào: stones = [8]
Đầu ra: 8
Giải thích: Một viên đá không có gì để đập vào, nên trọng lượng 8 của nó chính là đáp án.

Câu hỏi mở rộng

Các trọng số tối đa là 1000. Bạn có thể tận dụng giới hạn đó để hoàn thành trong thời gian O(n + W), với W là trọng số lớn nhất, mà không cần heap không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Không có công thức nào giúp bạn bỏ qua các lượt: bạn phải chơi từng lượt. Mỗi lượt cần lấy hai viên đá nặng nhất trong một đống đá luôn thay đổi, vì viên đá bị đập vỡ có thể quay lại với trọng lượng nhẹ hơn. Đống tối đa đưa ra viên đá nặng nhất và nhận lại một viên mới trong O(log n).

Sắp xếp chồng đá sau mỗi lượt

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Hãy làm đúng theo quy tắc: sắp xếp đống đá, lấy hai viên nặng nhất ở cuối ra, rồi đặt hiệu của chúng trở lại nếu hiệu đó khác không. Mỗi vòng lại sắp xếp, vì hiệu có thể nằm ở bất kỳ vị trí nào. Trong ví dụ đầu tiên, 9 và 6 tạo ra 3, nên đặt số này bên dưới 4.

Mỗi vòng loại bỏ ít nhất một viên đá, nên có tối đa n-1 vòng, mỗi vòng sắp xếp tối đa n viên đá: O(n² log n). Với n = 10^4, cần khoảng 10^4 lần sắp xếp tối đa 10^4 số.

Thuật toán

Sao chép các viên đá vào một danh sách có tên pile.
Khi danh sách còn nhiều hơn một viên đá, hãy sắp xếp danh sách theo thứ tự tăng dần.
Lấy hai viên đá cuối cùng ra, heaviest và second.
Nếu chúng khác nhau, thêm heaviest - second trở lại danh sách.
Trả về viên đá còn lại, hoặc 0 nếu danh sách trống.

def lastStoneWeight(stones):
    pile = list(stones)
    while len(pile) > 1:
        pile.sort()  # the two heaviest stones move to the end
        heaviest = pile.pop()
        second = pile.pop()
        if heaviest != second:
            pile.append(heaviest - second)
    return pile[0] if pile else 0

Đống cực đại

Ý tưởng

Max-heap giữ giá trị lớn nhất ở trên cùng, việc lấy phần tử trên cùng ra hoặc thêm một giá trị có độ phức tạp O(log n). Hãy đưa mọi viên đá vào đó. Ở mỗi vòng, lấy ra hai viên nặng nhất rồi thêm lại phần chênh lệch nếu nó khác không; heap sẽ đưa viên đá vào đúng vị trí. Với [10, 4, 1], bạn lấy ra 10 và 4, rồi thêm lại 6, sau đó lấy ra 6 và 1, rồi thêm lại 5.

Có nhiều nhất n-1 vòng, mỗi vòng gồm hai lần lấy ra và một lần thêm vào, nên độ phức tạp thời gian là O(n log n) và độ phức tạp không gian là O(n). Trong các ngôn ngữ không có heap tích hợp sẵn, lời giải lưu heap trong một mảng, với nút cha của chỉ số i nằm ở (i-1)/2.

Thuật toán

Đưa mọi viên đá vào một đống ưu tiên cực đại.
Trong khi đống ưu tiên còn nhiều hơn một viên đá, lấy viên nặng nhất ra, rồi lấy viên nặng thứ hai ra.
Nếu chúng khác nhau, thêm heaviest - second vào đống.
Trả về phần tử trên cùng của đống, hoặc 0 nếu đống trống.

import heapq


def lastStoneWeight(stones):
    # heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
    heap = [-w for w in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        heaviest = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if heaviest != second:
            heapq.heappush(heap, -(heaviest - second))
    return -heap[0] if heap else 0

Lỗi thường gặp và trường hợp biên

Trả về phần tử trên cùng của đống rỗng. Khi hai viên đá cuối cùng có cùng khối lượng, như trong ví dụ đầu tiên, không còn gì và đáp án là 0.
Vô tình dùng đống tối thiểu. heapq của Python và PriorityQueue mặc định của Java lấy ra giá trị nhỏ nhất; hãy đổi dấu khối lượng hoặc truyền vào bộ so sánh đảo ngược.
Quên đổi dấu khi dùng khối lượng âm. Cả hai giá trị lấy ra đều âm, vì vậy giá trị cần thêm vào là -(heaviest - second).
Sắp xếp một lần lúc đầu rồi duyệt danh sách. Hiệu số có thể nhẹ hơn những viên đá bạn chưa chạm đến, nên thứ tự sẽ không còn đúng sau vòng đầu tiên.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Last Stone Weight là bao nhiêu?

Với đống cực đại, tối đa n-1 vòng gồm hai lần lấy phần tử ra và một lần thêm phần tử vào sẽ tốn thời gian O(n log n) và không gian O(n). Sắp xếp toàn bộ đống sau mỗi vòng sẽ tốn thời gian O(n² log n).

Tại sao nên dùng heap cho Last Stone Weight thay vì danh sách đã sắp xếp?

Danh sách đã sắp xếp cho biết ngay hai viên đá nặng nhất, nhưng chèn hiệu số trở lại đúng thứ tự sẽ dịch chuyển tối đa n mục, với độ phức tạp O(n²) qua tất cả các vòng. Heap chỉ cần trả lời “giá trị nào lớn nhất” và nhận thêm giá trị mới, cả hai thao tác đều có độ phức tạp O(log n), đáp ứng đúng những gì mô phỏng cần.

Thứ tự đập các vật có cùng trọng lượng có làm thay đổi đáp án không?

Không. Khi nhiều viên đá có cùng trọng lượng lớn nhất, dù bạn chọn hai viên nào thì chúng cũng nặng như nhau, nên đống đá sau lượt đó vẫn có các trọng lượng như cũ. Đáp án chỉ phụ thuộc vào trọng lượng.

def lastStoneWeight(stones):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

stones = [3, 9, 4, 6, 2]

Đầu ra mong đợi