LeetCode135:Candy

제목:
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?
문제 해결 방법:
두 번 반복해서 그룹을 세면 된다
첫 번째: 현재 원소가 이전보다 크면 현재 아이가 얻은 사탕 수는 이전 아이의 사탕 수+1이고, 그렇지 않으면 사탕 수는 1이다
두 번째: 뒤에서 앞으로 스캔하면 현재 원소 i의 값이 i+1 위치의 값보다 크면 이들의 현재 사탕 수를 비교한다. 만약에 i아이가 얻은 사탕 수가 i+1아이가 얻은 사탕 수+1보다 크면 변하지 않는다. 그렇지 않으면 i아이의 사탕 수를 i+1아이의 사탕 수+1로 설정한다.
구현 코드:

#include <iostream>

#include <vector>

using namespace std;



class Solution {

public:

    int candy(vector<int> &ratings) {

        int len = ratings.size();

        if(len == 0 || len == 1)

            return len;

        int *c = new int[len];

        c[0] = 1;

        for(int i = 1; i < len; i++)

            if(ratings[i] > ratings[i-1])

                c[i] = c[i-1] + 1;

            else

                c[i] = 1;

        int minCandy = c[len-1];

        for(int i = len-2; i >= 0; i--)

        {

            if(ratings[i] > ratings[i+1])

                c[i] = max(c[i], c[i+1] + 1);

            minCandy += c[i];            

        }

        return minCandy;

        

    }

};



int main(void)

{

    int ratings[] = {5,8,2,4,9,5,4};

    int len = sizeof(ratings) / sizeof(ratings[0]);

    vector<int> ratVec(ratings, ratings+len);

    Solution solution;

    int ret = solution.candy(ratVec);

    cout<<ret<<endl;

    return 0;

}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)

이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

LeetCode135:Candy

좋은 웹페이지 즐겨찾기