물병 Leetcode 솔루션


난이도 쉽게
자주 묻는 질문 Microsoft
탐욕스러운

문제 설명

문제”Water Bottles”에는 전체 물병의 총 개수를 저장하는“numBottle”과 한 번에 교환 할 수있는 빈 물병의 총 개수를 저장하는“numExchange”라는 두 가지 값이 주어집니다. 물 병.

가득 찬 물병에서 물을 마신 후에는 빈 물병으로 바뀝니다. 우리의 임무는 우리가 마실 수있는 물병의 최대 개수를 찾는 것입니다.

numBottles = 15, numExchange = 4
19

설명 :

물병 Leetcode 솔루션

첫 번째 라운드: 음주 15 물병은 15 개의 빈 병을 제공합니다.

XNUMX 라운드 : 이 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

물병 용 자바 코드

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) 답을 저장하는 데 변수 만 사용하고 있기 때문입니다.

참조