Μέγιστος αριθμός κερμάτων που μπορείτε να λάβετε Λύση κωδικού Leetcode


Επίπεδο δυσκολίας Μέσον
Ταξινόμηση

Δήλωση προβλήματος

Στο πρόβλημα "Μέγιστος αριθμός νομισμάτων που μπορείτε να λάβετε" μας δίνεται 3 * n σωροί κερμάτων. Αυτοί οι σωροί του νομίσματος θα διανεμηθούν μεταξύ εσάς και των δύο φίλων σας Αλίκη και Μπομπ. Οι κανόνες για τη διανομή των σωρών των κερμάτων έχουν ως εξής:

  1. Θα επιλέξετε τρεις πασσάλους.
  2. Από αυτούς τους 3 σωρούς, η Άλις παίρνει το σωρό που περιέχει τα μέγιστα νομίσματα.
  3. Θα πάρετε το σωρό που περιέχει τα δεύτερα μέγιστα νομίσματα.
  4. Ο Μπομπ θα πάρει το σωρό με τον μικρότερο αριθμό κερμάτων.
  5. Επαναλάβετε αυτά τα βήματα μέχρι να μην διανεμηθούν όλοι οι σωροί νομισμάτων.

Ακολουθώντας τους παραπάνω κανόνες, πρέπει να βρούμε τον μέγιστο αριθμό κερμάτων που μπορείτε να πάρετε.

Παράδειγμα

piles = [9,8,7,6,5,1,2,3,4]
18

Επεξήγηση:

Θα επιλέξετε τους σωρούς με τον ακόλουθο τρόπο:

  • (9,8,1)
  • (7,6,2)
  • (5,4,3)

Αυτός ο τρόπος επιλογής πασσάλων θα σας οδηγήσει να λάβετε τον μέγιστο αριθμό νομισμάτων που είναι 18 νομίσματα.

Προσέγγιση για τον μέγιστο αριθμό νομισμάτων που μπορείτε να λάβετε Λύση κωδικού Leetcode

Για την επίλυση αυτού του προβλήματος, κάθε κόλπο βρίσκεται πίσω από τον τρόπο επιλογής 3 πασσάλων κάθε φορά που θα σας οδηγήσουν να λάβετε τον μέγιστο αριθμό κερμάτων.

  • Ο Μπομπ παίρνει το σωρό με τον μικρότερο αριθμό κερμάτων. Έτσι κάθε φορά θα επιλέγουμε έναν σωρό από όλους τους υπόλοιπους σωρούς που περιέχουν τον ελάχιστο αριθμό νομισμάτων. Θα διασφαλίσει ότι ο Μπομπ παίρνει όλους τους ν σωρούς με τον μικρότερο αριθμό νομισμάτων από 3 * n σωρούς.
  • Κάθε φορά θα επιλέγουμε δύο σωρούς από όλους τους υπόλοιπους σωρούς που περιέχουν τον μέγιστο αριθμό νομισμάτων. Η Άλις παίρνει το σωρό που περιέχει τα μέγιστα νομίσματα. Παίρνετε το σωρό με τον δεύτερο μέγιστο αριθμό κερμάτων.
  • Για να πάρουμε τους σωρούς με τον μέγιστο και τον ελάχιστο αριθμό νομισμάτων, θα το κάνουμε είδος ο πίνακας.
  • Η παρακάτω εικόνα εξηγεί την κατανομή των πασσάλων μεταξύ της Αλίκης, του Μπομπ και του Εσύ.

λύση leetcode στο μέγιστο αριθμό νομισμάτων που μπορείτε να λάβετε

Εκτέλεση

Κωδικός C ++ για τον μέγιστο αριθμό νομισμάτων που μπορείτε να λάβετε

#include <bits/stdc++.h> 
using namespace std; 
    int maxCoins(vector<int>& piles) {
     sort(piles.begin(),piles.end());
        int n=piles.size();
        int ans=0;
        for(int i=n/3;i<n;i=i+2)
            ans+=piles[i];
        return ans;
    }
int main() 
{ 
 vector<int> arr = { 9,8,7,6,5,1,2,3,4 }; 
 cout<<maxCoins(arr)<<endl; 
 return 0;
}
18

Κωδικός Java για το μέγιστο αριθμό νομισμάτων που μπορείτε να λάβετε

import java.util.Arrays; 
public class Tutorialcup {
    public static int  maxCoins(int[] piles) {
          Arrays.sort(piles);
        int res = 0, n = piles.length;
        for (int i = n / 3; i < n; i += 2)
            res += piles[i];
        return res;
    }
  public static void main(String[] args) {
    int [] arr = {9,8,7,6,5,1,2,3,4}; 
    int ans=  maxCoins(arr);
    System.out.println(ans);
  }
}
18

Ανάλυση πολυπλοκότητας του μέγιστου αριθμού νομισμάτων που μπορείτε να λάβετε Λύση κωδικού Leetcode

Χρόνος πολυπλοκότητας

Η χρονική πολυπλοκότητα του παραπάνω κώδικα είναι O (nlogn) γιατί ταξινομούμε τον πίνακα. Εδώ είναι το μέγεθος του πίνακα.

Διαστημικότητα

Η πολυπλοκότητα του παραπάνω κώδικα είναι Ο (1) γιατί χρησιμοποιούμε μόνο μια μεταβλητή για να αποθηκεύσουμε την απάντηση.

αναφορές