ขวดน้ำ Leetcode Solution


ระดับความยาก สะดวกสบาย
ถามบ่อยใน ไมโครซอฟท์
โลภ

คำชี้แจงปัญหา

ในปัญหา "Water Bottles" เราจะได้รับ XNUMX ค่าคือ "numBottle" ซึ่งจะเก็บจำนวนขวดน้ำทั้งหมดและ "numExchange" ซึ่งจะเก็บจำนวนขวดน้ำเปล่าทั้งหมดที่เราสามารถแลกเปลี่ยนได้ในแต่ละครั้งและได้รับเต็ม ขวดน้ำ.

หลังจากดื่มน้ำจากขวดน้ำเต็มแล้วจะกลายเป็นขวดน้ำเปล่า งานของเราคือค้นหาจำนวนขวดน้ำเต็มจำนวนสูงสุดที่เราสามารถดื่มได้

ตัวอย่าง

numBottles = 15, numExchange = 4
19

คำอธิบาย:

ขวดน้ำ Leetcode Solution

รอบแรก: ดื่ม 15 น้ำเปล่าให้ขวดเปล่า 15 ขวด

รอบที่สอง: จากขวดน้ำ 15 ขวดเราได้น้ำเต็ม 3 ขวดและเหลือ 3 ขวดเปล่า ดื่ม 3 ขวดน้ำตอนนี้เราเหลือ 6 ขวดเปล่า

รอบที่สาม: จากขวดน้ำทั้ง 6 ขวดเราจะได้น้ำเต็ม 1 ขวดและเหลืออีก 2 ขวด ดื่มน้ำ 1 ขวดตอนนี้เหลือ 3 ขวด

เนื่องจากต้องใช้ขวดอย่างน้อย 4 ขวดในการแลกเปลี่ยนขวดเราจึงไม่สามารถซื้อขวดน้ำเต็มได้อีกต่อไป จำนวนขวดน้ำสูงสุดที่เราสามารถดื่มได้คือ 15 + 3 + 1 = 19.

แนวทางการแก้ปัญหา Leetcode สำหรับขวดน้ำ

แนวทางพื้นฐานในการแก้ปัญหาคือทำในสิ่งที่ถาม

  1. ดื่มน้ำเต็มขวดแล้วเปลี่ยนเป็นขวดน้ำเปล่า
  2. จากขวดน้ำเปล่าซื้อน้ำเต็มขวด
  3. ทำซ้ำขั้นตอนเหล่านี้จนกว่าเราจะไม่สามารถซื้อน้ำเต็มขวดจากขวดน้ำเปล่าได้
  4. ส่งคืนจำนวนขวดน้ำทั้งหมดที่เราดื่มในระหว่างกระบวนการ

เราสามารถปรับปรุงไฟล์ ความซับซ้อน ของการแก้ปัญหาโดยทำการสังเกตเล็กน้อย:

  1. เรามีจำนวนขวดน้ำเต็มจำนวนขวดดังนั้นนี่จะเป็นจำนวนขวดน้ำเต็มขั้นต่ำที่เราสามารถดื่มได้
  2. ขวดน้ำเต็ม 1 ขวด = น้ำ 1 หน่วย + น้ำเปล่า 1 ขวด
  3. จาก numExchange ขวดน้ำเปล่าเราจะได้รับน้ำเต็ม 1 ขวด (น้ำ 1 หน่วย + น้ำเปล่า 1 ขวด) สิ่งนี้ยังสามารถตีความได้ว่า (numExchange-1) ขวดน้ำให้น้ำ 1 หน่วย
  4. แต่ถ้าในรอบที่แล้วถ้าเรามี (numExchange-1) ขวดเปล่าเราจะไม่สามารถรับน้ำได้หนึ่งหน่วย
  5. ดังนั้นผลลัพธ์ของเราจะเป็น numBottle + (numBottle / (numExchange -1)) และถ้า numBottle% (numExchange -1) == 0 ให้ลบ 1 ออกจากคำตอบสุดท้าย

การดำเนินงาน

รหัส C ++ สำหรับขวดน้ำ

#include <bits/stdc++.h> 
using namespace std; 
    int numWaterBottles(int numBottles, int numExchange) {
        int ans= numBottles + (numBottles) / (numExchange - 1);
        if((numBottles) %(numExchange - 1)==0)
            ans--;
        return ans;
    }
int main() 
{ 
 int numBottles = 15, numExchange = 4;
 int ans=numWaterBottles(numBottles,numExchange);
 cout<<ans<<endl;
 return 0;
}
19

รหัส Java สำหรับขวดน้ำ

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int numWaterBottles(int numBottles, int numExchange) {
        int ans= numBottles + (numBottles) / (numExchange - 1);
        if((numBottles) %(numExchange - 1)==0)
            ans--;
        return ans;
    }
  public static void main(String[] args) {
     int numBottles = 15, numExchange = 4;
     int ans=numWaterBottles(numBottles,numExchange); 
        System.out.println(ans);
  }
}
19

การวิเคราะห์ความซับซ้อนของโซลูชัน Leetcode ของขวดน้ำ

ความซับซ้อนของเวลา

ความซับซ้อนของเวลาของรหัสข้างต้นคือ O (1).

ความซับซ้อนของพื้นที่

ความซับซ้อนของช่องว่างของรหัสข้างต้นคือ O (1) เนื่องจากเราใช้เพียงตัวแปรในการจัดเก็บคำตอบ

อ้างอิง