1423. Maximum Points You Can Obtain from Cards

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

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

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

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

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

Дан số nguyên mảng cardPoints и số nguyên k, return максимальное количество очков, которое вы можете получить.

Ví dụ:

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# lời giải

đã khớp/gố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++ lời giải

bản nháp tự động, xem lại trước khi gửi

#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 lời giải

bản nháp tự động, xem lại trước khi gửi

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 lời giải

đã khớp/gốc

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

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

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

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

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.