המספר המרבי של מטבעות שתוכלו לקבל פתרון 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 ערימות בכל פעם שיובילו אתכם להשיג את המספר המרבי של מטבעות.

  • בוב מקבל את הערימה עם מספר המטבעות הנמוך ביותר. כך שבכל פעם נבחר ערימה מתוך כל הערמות שנותרו המכילות את מספר המטבעות המינימלי. זה יבטיח שבוב יקבל את כל ערימות ה- n עם מספר המטבעות הנמוך ביותר מערימות 3 * n.
  • בכל פעם נבחר שתי ערימות מתוך כל הערמות שנותרו המכילות את המספר המרבי של מטבעות. אליס מקבלת את הערימה שמכילה את מקסימום המטבעות. אתה מקבל את הערימה עם המספר המרבי השני של מטבעות.
  • על מנת לקבל את הכלונסאות עם המספר המרבי והמינימלי של מטבעות, נעשה זאת sort המערך.
  • התמונה המוצגת למטה מסבירה את התפלגות הערימות בין אליס, בוב, ואתה.

פתרון 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) כי אנחנו ממיינים את המערך. כאן n הוא גודל המערך.

מורכבות חלל

מורכבות החלל של הקוד הנ"ל היא O (1) מכיוון שאנחנו משתמשים רק במשתנה לאחסון התשובה.

הפניות