Λύση Leetcode μπουκαλιών νερό


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Microsoft
Άπληστος

Δήλωση προβλήματος

Στο πρόβλημα "Μπουκάλια νερού" μας δίνονται δύο τιμές, δηλαδή "numBottle" που θα αποθηκεύσουν τον συνολικό αριθμό μπουκαλιών νερού πλήρους και "numExchange" που θα αποθηκεύσουν τον συνολικό αριθμό κενών μπουκαλιών νερού που μπορούμε να ανταλλάξουμε κάθε φορά και να πάρουμε ένα πλήρες μπουκαλι ΝΕΡΟΥ.

Μετά το πόσιμο νερό από ένα γεμάτο μπουκάλι νερό μετατρέπεται σε ένα άδειο μπουκάλι νερό. Ο στόχος μας είναι να μάθουμε τον μέγιστο αριθμό πλήρων μπουκαλιών νερού που μπορούμε να πιούμε.

Παράδειγμα

numBottles = 15, numExchange = 4
19

Επεξήγηση:

Λύση Leetcode μπουκαλιών νερό

Πρώτος γύρος: ποτό 15 μπουκάλια νερό δίνει 15 άδεια μπουκάλια.

Δεύτερος γύρος: από αυτά τα 15 μπουκάλια νερό παίρνουμε 3 πλήρη μπουκάλια νερό και αφήνουμε με 3 κενά μπουκάλια. Ποτό 3 φιάλες νερού που αφήσαμε τώρα με συνολικά 6 άδειες φιάλες.

Τρίτος γύρος: από αυτά τα 6 μπουκάλια νερό παίρνουμε 1 πλήρες μπουκάλι νερό και αφήνουμε με 2 άδεια μπουκάλια. Πίνετε 1 μπουκάλια νερό που αφήσαμε τώρα με συνολικά 3 κενά μπουκάλια.

Απαιτείται τουλάχιστον 4 μπουκάλια για την ανταλλαγή της φιάλης, δεν μπορούμε πλέον να αγοράσουμε ένα πλήρες μπουκάλι νερό. Έτσι, ο μέγιστος αριθμός μπουκαλιών νερού που μπορούμε να πιούμε είναι 15 + 3 + 1 = 19.

Προσέγγιση για τη λύση Leetcode μπουκαλιών νερό

Η βασική προσέγγιση για την επίλυση του προβλήματος είναι να κάνουμε ό, τι θέτουν οι ερωτήσεις.

  1. Πίνετε όλα τα γεμάτα μπουκάλια νερό και στη συνέχεια μετατρέπεται σε άδεια μπουκάλια νερού.
  2. Από όλα τα άδεια μπουκάλια νερό αγοράστε πλήρη μπουκάλια νερό.
  3. Επαναλάβετε αυτά τα βήματα έως ότου δεν μπορούμε να αγοράσουμε ένα πλήρες μπουκάλι νερό από ένα άδειο μπουκάλι νερό.
  4. Επιστρέψτε τον συνολικό αριθμό των πλήρων μπουκαλιών νερό που καταναλώσαμε κατά τη διάρκεια της διαδικασίας.

Μπορούμε να βελτιώσουμε το περίπλοκο της λύσης κάνοντας μερικές παρατηρήσεις:

  1. Έχουμε τον αριθμό μπουκαλιών πλήρους νερού numBottle, οπότε αυτός θα είναι ο ελάχιστος αριθμός πλήρων μπουκαλιών νερού που μπορούμε να πιούμε.
  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 μπουκαλιών νερό

Χρόνος πολυπλοκότητας

Η χρονική πολυπλοκότητα του παραπάνω κώδικα είναι Ο (1).

Διαστημικότητα

Η πολυπλοκότητα του παραπάνω κώδικα είναι Ο (1) γιατί χρησιμοποιούμε μόνο μια μεταβλητή για να αποθηκεύσουμε την απάντηση.

αναφορές