Bրի շշեր Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Microsoft
Ագահ

Խնդրի հայտարարություն

«Bրի շշեր» խնդրում մեզ տրվում է երկու արժեք `« numBottle », որը կպահի լիարժեք ջրի շշերի ընդհանուր քանակը և« numExchange »- ը, որը կպահպանի ջրի դատարկ շշերի ընդհանուր քանակը, որոնք կարող ենք միաժամանակ փոխանակել և ստանալ ամբողջական քանակ: ջրի շիշ.

Լրիվ ջրի շշից ջուր խմելուց հետո այն վերածվում է դատարկ ջրի շշի: Մեր խնդիրն է պարզել լիարժեք ջրի շշերի առավելագույն քանակը, որոնք մենք կարող ենք խմել:

Օրինակ

numBottles = 15, numExchange = 4
19

Բացատրությունը.

Bրի շշեր Leetcode լուծում

Առաջին փուլ. խմել 15 ջրի շշերը տալիս են 15 դատարկ շիշ:

Երկրորդ փուլ. Այս 15 ջրի շշերից մենք ստանում ենք 3 լրիվ ջրի շիշ և մնում 3 դատարկ շիշ: Խմեք 3 ջրի շշեր մենք հիմա թողեցինք ընդհանուր առմամբ 6 դատարկ շիշ:

Երրորդ փուլ. Այս 6 ջրի շշերից մենք ստանում ենք 1 լրիվ ջրի շիշ և մնում 2 դատարկ շիշ: Խմեք 1 ջրի շիշ, որը մենք հիմա թողել ենք, ընդհանուր առմամբ 3 դատարկ շիշով:

Քանի որ շիշը փոխանակելու համար պահանջվում է առնվազն 4 շիշ, մենք այլևս չենք կարող լիարժեք ջրի շիշ գնել: Այսպիսով, ջրի շշերի առավելագույն քանակը, որ մենք կարող ենք խմել, դա է 15 + 3 + 1 = 19.

Bրի շշերի 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րի շշերի 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

Bրի շշերի բարդության վերլուծություն `լետկոդային լուծույթ

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է Ո (1)

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է Ո (1) քանի որ մենք պատասխանը պահելու համար օգտագործում ենք միայն փոփոխական:

Սայլակ