1423. Maximum Points You Can Obtain from Cards

LeetCode medium original: C# #array #csharp #leetcode #math #medium #prefix-sum #two-pointers

선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.

LeetCode Static

Есть несколько карт, расположенных в ряд, и у каждой карты есть определенное количество очков. Очки представлены в виде целочисленного 배열а cardPoints.

За один шаг вы можете взять одну карту либо с начала, либо с конца ряда. Вы должны взять ровно k карт.

Ваш результат - это сумма очков взятых карт.

Дан 정수 배열 cardPoints и 정수 k, return максимальное количество очков, которое вы можете получить.

예제:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3

Output: 12

Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

C# 해법

매칭됨/원본

public class Solution {
    public int MaxScore(int[] cardPoints, int k) {
        int n = cardPoints.Length;
        int[] frontSetOfCards = new int[k + 1];
        int[] rearSetOfCards = new int[k + 1];
        
        for (int i = 0; i < k; ++i) {
            frontSetOfCards[i + 1] = cardPoints[i] + frontSetOfCards[i];
            rearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i];
        }
        
        int maxScore = 0;
        for (int i = 0; i <= k; ++i) {
            int currentScore = frontSetOfCards[i] + rearSetOfCards[k - i];
            maxScore = Math.Max(maxScore, currentScore);
        }
        
        return maxScore;
    }
}

C++ 해법

자동 초안, 제출 전 검토

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        vector<int>& frontSetOfCards = new int[k + 1];
        vector<int>& rearSetOfCards = new int[k + 1];
        
        for (int i = 0; i < k; ++i) {
            frontSetOfCards[i + 1] = cardPoints[i] + frontSetOfCards[i];
            rearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i];
        }
        
        int maxScore = 0;
        for (int i = 0; i <= k; ++i) {
            int currentScore = frontSetOfCards[i] + rearSetOfCards[k - i];
            maxScore = max(maxScore, currentScore);
        }
        
        return maxScore;
    }
}

Java 해법

자동 초안, 제출 전 검토

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int MaxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int[] frontSetOfCards = new int[k + 1];
        int[] rearSetOfCards = new int[k + 1];
        
        for (int i = 0; i < k; ++i) {
            frontSetOfCards[i + 1] = cardPoints[i] + frontSetOfCards[i];
            rearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i];
        }
        
        int maxScore = 0;
        for (int i = 0; i <= k; ++i) {
            int currentScore = frontSetOfCards[i] + rearSetOfCards[k - i];
            maxScore = Math.max(maxScore, currentScore);
        }
        
        return maxScore;
    }
}

Python 해법

매칭됨/원본

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        frontSetOfCards = [0] * (k + 1)
        rearSetOfCards = [0] * (k + 1)
        
        for i in range(k):
            frontSetOfCards[i + 1] = cardPoints[i] + frontSetOfCards[i]
            rearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i]
        
        maxScore = 0
        for i in range(k + 1):
            currentScore = frontSetOfCards[i] + rearSetOfCards[k - i]
            maxScore = max(maxScore, currentScore)
        
        return maxScore

Algorithm

Инициализируйте два 배열а размера k + 1, frontSetOfCards и rearSetOfCards, чтобы хранить суммы очков, полученных при выборе первых i карт и последних i карт в 배열е.

Рассчитайте префиксные суммы для первых k карт и последних k карт.

Итерируйте от 0 до k и вычисляйте возможное количество очков, выбирая i карт с начала 배열а и k - i карт с конца, обновляя maximum результат при необходимости.

😎

Vacancies for this task

활성 채용 with overlapping task tags are 표시됨.

전체 채용

아직 활성 채용이 없습니다.