가장 많은 수의 캔디를 가진 아이들 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 아마존 블룸버그 게시물에서
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 35

“가장 많은 사탕을 가진 아이들”문제에서 우리는 어떤 아이들이 가지고있는 초콜릿의 수를 나타내는 정수 배열과 어떤 식 으로든 배포 할 수있는 추가 사탕을 제공받습니다. 이제 다음을 찾아야합니다.

  • 모든 어린이가 가장 많은 수의 초콜릿을 가질 수 있습니까? 배포 후(과반수 또는 공동)?

이 가능성을 부울 벡터의 형태로 출력해야합니다.

Array = {1 , 4 , 5 , 6 , 7}
Extra = 5
false true true true true

설명

첫 번째 아이: 다 줘도 첫 번째 자녀에게 추가 사탕, 6 개 미만의 사탕 <7 (5 번째 자녀). 그래서 우리는 그릇된 그것을 위해.

둘째 아이: 우리는 모두를 이 아이에게 추가 사탕을 9 > 7 (다섯 번째 자녀). 그래서 우리는 참된 그것을 위해.

마찬가지로, 세 번째, 네 번째, 다섯 번째 아이의 경우 최적의 분배 후 가장 많은 수의 사탕을 가질 수 있음을 쉽게 알 수 있습니다.

접근 (Greedy)

문제에서 우리는 여분의 사탕을 배포하기위한 우리의 선택과 무관합니다. 그만큼 최적의 어떤 아이를 위해 결정하는 방법은 여분의 사탕을 모두주고 필요한 상태를 확인하는 것입니다. 고려할 사항에 대한 결과를 찾아야합니다. i 번째 아이. 이제, 그것에 줄 수있는 사탕의 최대 양은 총 추가 사탕과 같습니다.

따라서 소유 할 수있는 사탕의 총 수는 i 번째 child = a [i] + 추가 사탕. 이 값이 최대 요소보다 큰 경우 정렬 분배하기 전에 우리는이 아이가 분배 후 가장 많은 사탕을 가질 수 있다는 결론을 내릴 수 있습니다. 우리는 모든 여분의 사탕을 i 번째 이 접근 방식은 탐욕스러운.

가장 많은 수의 캔디를 가진 아이들 Leetcode 솔루션

암호알고리즘

  1. 배열의 최대 값을 찾아서 다음과 같이 저장하십시오. 맥스캔디
  2. 부울 초기화 결과 정렬
  3. 배열의 시작부터 끝까지 루프를 실행합니다.
    1. 현재 사탕 수가 i 번째 어린이 + 추가 사탕은 이상인 maxCandies :
      1. 이 자식의 결과를 다음과 같이 설정하십시오. 참된, 그릇된 그렇지 않으면
  4. 결과 인쇄

사탕 수가 가장 많은 어린이를 찾기위한 알고리즘 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

vector <bool> kidsWithCandies(vector <int> &candies , int extraCandies)
{
    int n = candies.size() , maxCandies = 0;
    for(int i = 0 ; i < n ; i++)
        if(candies[i] > maxCandies)
            maxCandies = candies[i];


    vector <bool> result(n);
    for(int i = 0 ; i < n ; i++)
        result[i] = (candies[i] + extraCandies >= maxCandies);

    return result;
}


int main()
{
    vector <int> candies = {1 , 4 , 5 , 6 , 7};
    int extraCandies = 5;
    for(bool x : kidsWithCandies(candies , extraCandies))
        cout << (x ? "true" : "false") << " ";
    cout << '\n';
    return 0;
}

자바 프로그램

class kids_with_candies
{
    public static void main(String args[])
    {
        int[] candies = {1 , 4 , 5 , 6 , 7};
        int extraCandies = 5;
        for(boolean x : kidsWithCandies(candies , extraCandies))
            System.out.print(x + " ");
    }


    static boolean[] kidsWithCandies(int[] candies , int extraCandies)
    {
        int n = candies.length , maxCandies = 0;
        for(int i = 0 ; i < n ; i++)
            if(candies[i] > maxCandies)
                maxCandies = candies[i];

        boolean[] result = new boolean[n];

        for(int i = 0 ; i < n ; i++)
            result[i] = (candies[i] + extraCandies >= maxCandies);

        return result;
    }
}
false true true true true

가장 많은 사탕을 가진 아이를 찾는 복잡성 분석

시간 복잡성

의 위에), N = 배열의 크기. 전체 배열을 한 번 횡단하면서.

공간 복잡성

의 위에), 모든 자식의 결과를 별도의 배열에 저장합니다.

코멘트를 남겨

Translate »