Giả sử chúng ta có một số tảng đá, mỗi tảng đá có trọng lượng là một số nguyên dương. Trong mỗi lượt, chúng ta sẽ lấy hai tảng đá nặng nhất và đập chúng vào nhau. coi các viên đá có khối lượng x, y và x <=y. Kết quả của cú đập này có thể có hai loại.
- Nếu x =y, thì cả hai viên đá đều bị phá hủy hoàn toàn;
- Ngược lại, khi x! =y, viên đá có trọng lượng x bị phá hủy hoàn toàn và viên đá có trọng lượng y có trọng lượng mới là y-x.
Cuối cùng, chỉ còn lại nhiều nhất 1 viên đá. Chúng ta phải tìm trọng lượng của viên đá này (0 khi không còn viên đá nào.)
Vì vậy, nếu trọng lượng viên đá là [2,7,4,1,8,1], thì kết quả sẽ là 1. Lúc đầu chọn 7 và 8, sau đó lấy 1, vì vậy mảng sẽ là [2,4,1,1 , 1], thứ hai lấy 2 và 4. Mảng sẽ là [2,1,1,1], sau đó chọn 2 và 1, mảng sẽ là [1,1,1], sau đó chọn hai viên đá có trọng lượng 1, thì cả hai sẽ bị hủy, do đó mảng sẽ là [1]. Đây là câu trả lời
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Nếu mảng trọng lượng đá W không có phần tử nào, thì trả về 0
- Nếu W chỉ có một phần tử thì trả về W [0]
- trong khi W có nhiều hơn một phần tử -
- sắp xếp W
- s1:=phần tử cuối cùng của W, s2:=phần tử cuối cùng thứ hai của W
- nếu s1 =s2, thì hãy xóa s1 và s2 khỏi W
- nếu không thì s1:=| s1 - s2 |, hãy xóa phần tử cuối cùng khỏi W, sau đó đặt s1 làm phần tử cuối cùng của W
- nếu W có một phần tử, thì trả về phần tử đó, nếu không trả về 0
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution(object): def lastStoneWeight(self, stones): """ :type stones: List[int] :rtype: int """ if len(stones) ==0: return 0 if len(stones) == 1: return 1 while len(stones)>1: stones.sort() s1,s2=stones[-1],stones[-2] if s1==s2: stones.pop(-1) stones.pop(-1) else: s1 = abs(s1-s2) stones.pop(-1) stones[-1] = s1 if len(stones): return stones[-1] return 0 ob1 = Solution() print(ob1.lastStoneWeight([2,7,4,1,6,1]))
Đầu vào
[2,7,4,1,6,1]
Đầu ra
1