Су бөтелкелері 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 ерітіндісі

Уақыт күрделілігі

Жоғарыда келтірілген кодтың уақыт күрделілігі O (1).

Ғарыштың күрделілігі

Жоғарыда аталған кодтың кеңістігінің күрделілігі мынада O (1) өйткені біз жауап сақтау үшін тек айнымалыны қолданамыз.

Әдебиеттер тізімі