[Thuật toán – LeetCode 1518] Giải bài Water Bottles bằng 15 ngôn ngữ khác nhau

Đầu năm rảnh rỗi, mình ngồi xem tí thuật toán, tiện làm thứ fun & crazy đầu năm: giải bài tập bằng 15 ngôn ngữ hỗ trợ của LeetCode.

Trong này có ngôn ngữ mình học bài bản, có ngôn ngữ mình học mì ăn liền để chơi; có gì sai sót, mong được anh em chỉ bảo

Các ngôn ngữ bao gồm: C++, Java, Python, Python3, C, C#, Javascript, Go, Rust, Ruby, Swift, Kotlin, Scala và PHP.

Đề bài

Nguồn: LeetCode 1518 problem

Link bài gốc: Link

Tóm tắt:

• Đầu vào:
  • Số thứ nhất: số lượng chai nước đầy ban đầu
  • Số thứ hai: số lượng chai rỗng để đổi được 1 chai đầy
  • Mỗi lần có chai nước đầy, uống hết và đếm số chai nước đã uống được. Lấy chai rỗng, đổi lấy chai đầy cho tới khi không đổi được nữa (hết chai rỗng, hoặc số chai rỗng ít hơn số để đổi được chai đầy).
• Đầu ra mong muốn:
  • Số lượng chai nước đầy tối đa uống được.

Anh em cứ hiểu đơn giản giống ngày xưa uống nước ngọt, xong đi đổi đồng nát ý. Số lượng lon coca rỗng để đổi được 1 lon coca thật do bác đồng nát quy ước.

Giải thuật

Giải thuật khá đơn giản. Bạn xem sơ đồ sau:

Code

Mình mô tả giải thuật với code Go ở đây

	func numWaterBottles(numBottles int, numExchange int) int {
	res := numBottles // Khởi tạo bằng số lượng chai đầy
	for numBottles >= numExchange { // Vòng lặp
	tmp := numBottles/ numExchange // Số lượng chai mới đổi được
	res += tmp // Cộng số chai mới vào kết quả tổng
	numBottles = tmp + numBottles %numExchange // Tính lại số chai rỗng
	}
	return res
	}

view raw leetcode-1518-water-bottle.go hosted with ❤ by GitHub

Các ngôn ngữ khác, bạn hãy click vào link này: Link

Cảm ơn bạn, vì đã đọc bài ^^