Cùng giải leetcode! Bài 1561. Maximum Number of Coins You Can Get bằng ngôn ngữ Golang

1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài

Link bài tập: Maximum Number of Coins You Can Get

Có 3n đống tiền xu với kích thước khác nhau, bạn và bạn bè của bạn sẽ chọn đống tiền như sau:

• Trong mỗi bước, bạn sẽ chọn bất kỳ 3 đống tiền nào (không nhất thiết liên tiếp).
• Trong lựa chọn của bạn, Alice sẽ chọn đống có số tiền xu nhiều nhất.
• Bạn sẽ chọn đống tiếp theo có số tiền xu nhiều nhất.
• Bạn bè của bạn, Bob, sẽ chọn đống cuối cùng.
• Lặp lại quá trình cho đến khi không còn đống tiền xu nào.

Cho một mảng số nguyên piles, trong đó piles[i] là số tiền xu trong đống thứ i.

Hãy trả về số tiền xu tối đa mà bạn có thể có.

Ví dụ 1:

Đầu vào: piles = [2,4,1,2,7,8]
Đầu ra: 9
Giải thích: Chọn bộ 3 đống tiền (2, 7, 8), Alice chọn đống có 8 tiền xu, bạn chọn đống có 7 tiền xu và Bob chọn đống cuối cùng.
Chọn bộ 3 đống tiền (1, 2, 4), Alice chọn đống có 4 tiền xu, bạn chọn đống có 2 tiền xu và Bob chọn đống cuối cùng.
Số tiền xu tối đa mà bạn có thể có là: 7 + 2 = 9.
Mặt khác, nếu chọn sắp xếp này (1, 2, 8), (2, 4, 7) bạn chỉ có được 2 + 4 = 6 tiền xu, không phải là tối ưu.

Ví dụ 2:

Đầu vào: piles = [2,4,5]
Đầu ra: 4

Ví dụ 3:

Đầu vào: piles = [9,8,7,6,5,1,2,3,4]
Đầu ra: 18

Constraints:

• 3 <= piles.length <= 10^5
• piles.length % 3 == 0
• 1 <= piles[i] <= 10^4

3. Phân tích

3.1. Gợi ý

Đống tiền xu nào bạn sẽ không bao giờ được nhặt?

• Để tối ưu hóa nhất theo yêu cầu đề bài, đống tiền mà bạn sẽ không bao giờ được nhặt sẽ là những đống tiền có số xu lớn nhất trong mỗi 3 đống tiền chọn ra.

Bob luôn phải lấy đống xu cuối cùng, bất kể có bao nhiêu xu. Bạn sẽ đưa đống xu nào cho Bob?

• Yep, bạn sẽ đưa đống xu có số lượng xu ít nhất trong mỗi cặp 3 đống xu đã chọn, tại vì Alice luôn là người lấy đống tiền có nhiều xu nhất, bạn được lấy đống tiền xu nhiều thứ nhì, vậy nên Bob phải là người lấy đống có ít xu nhất để bạn lấy được số xu tối đa có thể lấy trong điều kiện đề bài.

3.2. Ý tưởng

Vậy làm thể nào để lấy được số xu tối đa? Tất nhiên bạn không thể lấy những đống xu có số lượng lớn nhất trong mảng piles được.
Ta sẽ phải sắp xếp lại mảng piles theo thứ tự tăng dần. Ta cần một biến chứa số xu tối đa mà ta có thể lấy làm kết quả trả về. Bên cạnh đó, ta quy ước n = piles.length.
Sau khi sắp xếp rồi, các bạn sẽ thấy số xu tối đa ta có thể lấy luôn nằm ở vị trí bắt đầu từ i = n - 2 rồi tiếp tục lùi dần về 0 với bước nhảy là 2. Tại sao? Tại vì mỗi lần chọn ra ba đống xu, ta luôn chọn đống xu ở giữa, vậy nên đống xu ta chọn sau khi đã sắp xếp mảng sẽ có index luôn nằm cách nhau 2 đơn vị.
Cộng dồn số xu này lại là có số xu cần trả về.
Tuy nhiên, ta chỉ có thể thực hiện việc cộng dồn này với số lần k = n / 3 mà thôi.

4. Code chạy bằng cơm

Hãy cùng xem ví dụ 3:

Đầu tiên ta sẽ sắp xếp lại mảng này theo thứ tự tăng dần:

Để tối đa hóa số xu mà ta lấy được, ta sẽ chọn các cặp 3 đống xu như sau:
Đống đầu tiên sẽ là (1, 8, 9):

Tiếp theo là (2, 6, 7):

Cuối cùng là (3, 4, 5):

Vậy đống xu mà ta sẽ chọn là những đống nào? Chính là những đống sau:

Các bạn để ý index của ba đống xu này:

Chúng sẽ bắt đầu từ vị trí i = n - 2, sau đó giảm dần 2 đơn vị, ta thực hiện việc này với số lần k = n / 3.
Vậy nên ta sẽ tạo vòng lặp với hai con trỏ, một con trỏ i chỉ tới vị trí đống xu ta sẽ lấy, một con trỏ k là số lần ta được phép lấy xu, chừng nào k > 0 thì ta vẫn tiếp tục lấy.
Thử chạy code nhé:
Dùng vòng lặp for với hai con trỏ i và k, với điều kiện là k > 0, bước di chuyển sẽ là k-- và i -= 2.
Đầu tiên, tại vị trí i = 7 ta có:

Tại vị trí i = 5 ta có:

Tại vị trí i = 3 ta có:

Sau vòng lặp này, k = k - 1 = 0, như vậy vòng lặp sẽ dừng. Ta trả về kết quả là 18.

5. Code bằng máy

Code Golang của chúng ta như sau:

func maxCoins(piles []int) int {
	sort.Ints(piles)
	maxCoin := 0
	n := len(piles)
	

	for k, i := n / 3, n - 2; k > 0; k, i = k - 1, i - 2 {
		maxCoin += piles[i]
	}

	return maxCoin
}

6. Kết thúc

Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!