LeetCode: 5393. 획득 가능 한 최대 포인트 C 언어 버 전
제목: 카드 몇 장 이 한 줄 로 되 어 있 고 카드 마다 해당 하 는 포인트 가 있 습 니 다.포 인 트 는 정수 배열 의 cardpoints 에 의 해 제 시 됩 니 다.
매번 행동 할 때마다, 너 는 줄 의 시작 이나 끝 에서 카드 를 한 장 가 져 갈 수 있 으 며, 결국 너 는 마침 k 장의 카드 를 가 져 가 야 한다.
당신 의 포 인 트 는 당신 이 가지 고 있 는 모든 카드 의 포 인 트 를 합 친 것 입 니 다.
정수 배열 cardpoints 와 정수 k 를 드 리 겠 습 니 다. 얻 을 수 있 는 최대 포 인 트 를 되 돌려 주 십시오.
예시 1:
입력: cardpoints = [1, 2, 3, 4, 5, 6, 1], k = 3 출력: 12 설명: 첫 번 째 행동, 어떤 카드 를 가 져 오 든 당신 의 포 인 트 는 항상 1 입 니 다.하지만 맨 오른쪽 카드 를 먼저 들 면 포 인 트 를 최대 화 할 수 있 습 니 다.가장 좋 은 전략 은 오른쪽 에 있 는 세 장의 카드 를 들 고 최종 포 인 트 는 1 + 6 + 5 = 12 입 니 다.
풀이: 사실 이 문제 의 해법 은 아직도 많 습 니 다. 제 가 처음에 생각 한 것 은 i 가 0 에서 k 로 순환 한 다음 에 순환 안에 각각 두 개의 순환 을 쓰 는 것 입 니 다. 하 나 는 왼쪽 에서 i 개 수 를 더 하고 하 나 는 오른쪽 에서 k - i 개 수 를 더 하 는 것 입 니 다.그 다음 에 max 를 주 고 이 순환 에서 최대 치 를 찾 습 니 다. 그러나 이러한 시간 은 복잡 도가 매우 크 고 적당 한 O (K ^ 2) 이기 때문에 운행 후 시간 이 초과 되 었 습 니 다.그리고 개선 한 후에 이렇게 쓰 는 것 을 선택 하 세 요.
int maxScore(int* cardPoints, int cardPointsSize, int k)
{
int max = 0;
int i , j , x = 0;
//
int left[100000] = {0} , right[100000] = {0};
/* k ， */
if(cardPointsSize <= k)
{
for(i = 0 ; i < cardPointsSize ; i++ )
max = max + cardPoints[i];
return max;
}
/* ， */
if(k == 1)
return cardPoints[0] > cardPoints[cardPointsSize - 1] ? cardPoints[0] : cardPoints[cardPointsSize - 1];
j = 1;
/* 0 k */
for(i = 0 ; i <= k ; i++)
left[j++] = left[i] + cardPoints[i];
i = 1;
/* 0 k */
for(j = cardPointsSize - 1 ; j > cardPointsSize - 1 - k ; j--)
right[i++] = right[x++] + cardPoints[j];
/* i ， k-i ， */
for( i = 0 ; i <= k ; i++)
max = left[i] + right[k-i] > max ? left[i] + right[k-i] : max;
return max;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
