წყლის ბოთლები Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან microsoft
ხარბ

პრობლემის განცხადება

პრობლემის ”წყლის ბოთლები” მოცემულია ორი მნიშვნელობა, კერძოდ ”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 Solution

პრობლემის გადაჭრის ძირითადი მიდგომაა ის, რაც კითხვებს სვამს.

  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

წყლის ბოთლების ჯავა კოდი

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 Solution

დროის სირთულე

ზემოთ მოცემული კოდის სირთულეა O (1)

კოსმოსური სირთულის

ზემოთ მოცემული კოდის სივრცის სირთულეა O (1) რადგან პასუხის შესანახად ვიყენებთ მხოლოდ ცვლადს.

ლიტერატურა