Su Şüşələri Leetcode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur microsoft
alqoritmlər kodlaşdırma Görməmiş müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 25

Problem bəyanat

“Su butulkaları” problemində bizə iki ədəd verilir, yəni “numBottle”, ümumi su butulkalarının ümumi sayını və bir dəfəyə dəyişdirə biləcəyimiz boş su butulkalarının ümumi sayını saxlayacaq “numExchange”. su şüşəsi.

Tam su şüşəsindən su içdikdən sonra boş su şüşəsinə çevrilir. Bizim vəzifəmiz içə biləcəyimiz maksimum tam su şüşələrini tapmaqdır.

misal

numBottles = 15, numExchange = 4
19

Explanation:

Su Şüşələri Leetcode HəlliPin

İlk raund: içmək 15 şüşə su 15 boş şüşə verir.

İkinci tur: bu 15 su şüşəsindən 3 tam su şüşəsi alırıq və 3 boş şüşə ilə qalırıq. İçmək 3 cəmi 6 boş şüşə ilə ayrıldığımız su şüşələri.

Üçüncü tur: bu 6 su şüşəsindən 1 tam su şüşəsi alırıq və 2 boş şüşə ilə qalırıq. İndi qaldığımız 1 su şüşəsini ümumilikdə 3 boş şüşə ilə için.

Şüşəni dəyişdirmək üçün ən azı 4 şüşə tələb olunduğundan, artıq tam su şüşəsi ala bilmərik. Yəni içə biləcəyimiz maksimum su şüşəsi 15 + 3 + 1 = 19.

Su Şüşələri Leetcode Çözümünə yanaşma

Problemi həll etmək üçün əsas yanaşma sualların verildiyini etməkdir.

  1. Bütün su şüşələrini için, sonra boş su şüşələrinə çevrilir.
  2. Bütün boş su şüşələrindən tam su şüşələri alırsınız.
  3. Boş su şüşəsindən tam su şüşəsi ala bilməyincə bu addımları təkrarlayın.
  4. İşləmə müddətində içdiyimiz tam su şüşələrinin sayını qaytarın.

Yaxşılaşdırmaq olar mürəkkəblik bir neçə müşahidələr apararaq həll yolu:

  1. NumBottle tam su şüşələrimiz var, buna görə içə biləcəyimiz minimum tam su şüşələri olacaqdır.
  2. 1 tam su şüşəsi = 1 vahid su + 1 boş su şüşəsi.
  3. NumExchange boş su şüşələrindən 1 tam su şüşəsi (1 ədəd su + 1 boş su şüşəsi) alırıq. Bu şey (numExchange-1) su şüşələri 1 vahid su verən kimi də təfsir edilə bilər.
  4. Ancaq son turda (numExchange-1) boş şüşə varsa, onda bir vahid su ala bilmərik.
  5. Beləliklə, nəticəmiz numBottle + (numBottle / (numExchange -1)) olacaq və numBottle% (numExchange -1) == 0 olarsa, son cavabdan 1-i çıxarın.

Həyata keçirilməsi

Su Şüşələri üçün C ++ kodu

#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

Su Şüşələri üçün Java kodu

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

Su Şüşələrinin Leetcode Solüsyonunun Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (1).

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki cavabı saxlamaq üçün yalnız dəyişəndən istifadə edirik.

References

Şərh yaz

Translate »