【leetcode】Candy
5658 단어 LeetCode
제목 설명:
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:
What is the minimum candies you must give?
원래 물문제를 찾아서 닦는 태도로 이 문제를 선택했는데 여러 가지 잘못이 답답해...(시작하는 태도 때문에 그런가 봐요.)쓸데없는 소리 하지 말고 문제를 봐라.
이 문제의 뜻은 정말 잘 모르겠어요. 처음에 제 이해는 n개의 번호마다 적어도 설탕을 하나씩 나누고, 순위가 높은 것은 순위보다 낮은 것이 많아서 위의 순서대로 하면 된다고 생각했어요. nlogn의 복잡도는 받아들일 수 있을 거예요.그래서 WA에 미치기 시작했다. 다음과 같은 두 가지 이유가 있다. 첫째, rating에 대한 이해가 잘못된 것이다. 사실 rating은 숫자가 작을수록 높아야 한다. 그리고 더욱 은밀한 것이 하나 있다. 바로 그 위에 있는 두 개의 requirement는 우리를 오도하기 쉽다. 둘째, 사실은 모든 rating이 높은 사람은 이웃보다 높아야 한다는 것이다.즉, 양쪽과 같은 우리에게 하나를 분배하면 된다는 것이다.
그러나 나중에 제목을 이해하고 시간이 초과되었는데 nlogn의 알고리즘이 아직 우수하지 않은 것 같아서 정렬을 버렸다.문제의 뜻을 정확히 이해하는 경우 바로 두 번 훑어보고 기록하면 된다.
여기에 몇 조의 테스트 데이터를 제시하고 이곳에 함께 걸려 있는 사람들도 도와준다.
case1:input:[2,3,2]
output:4
case2:input:[1,2,2,2,3,2,1]
output:11
코드는 다음과 같습니다.
1 class Solution {
2 public:
3 int candy(vector<int> &ratings) {
4 if(ratings.empty()){
5 return 0;
6 }
7 if(ratings.size()==1){
8 return 1;
9 }
10 int l=ratings.size();
11 int* temp=new int[l];
12 temp[0]=1;
13 for(int i=1;i<l;i++){
14 if(ratings[i]>ratings[i-1]){
15 temp[i]=temp[i-1]+1;
16 }
17 else{
18 temp[i]=1;
19 }
20 }
21
22 int ans=temp[l-1];
23 for(int i=l-2;i>=0;i--){
24 if(ratings[i]>ratings[i+1]&&temp[i+1]+1>temp[i]){
25 temp[i]=temp[i+1]+1;
26 }
27 ans+=temp[i];
28 }
29 return ans;
30 }
31 };이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
