מאַקסימום נומער פון קאָינס איר קענען באַקומען לעעטקאָדע לייזונג


שוועריקייט לעוועל מיטל
סאָרטינג

פּראָבלעם דערקלערונג

אין די פּראָבלעם "מאַקסימום נומער פון קאָינס איר קענען באַקומען" מיר באַקומען 3 * ן מערידן פון קאָינס. די מערידן פון די מאַטבייע זאָל זיין פונאנדערגעטיילט צווישן איר און דיין צוויי פרענדז אַליס און באָב. כּללים פֿאַר די פאַרשפּרייטונג פון די מערידן פון די קאָינס זענען ווי גייט:

  1. איר וועט אויסקלייַבן קיין דריי מערידן.
  2. פֿון די 3 מערידן אַליס די הויפן כּולל די מאַקסימום קאָינס.
  3. איר וועט באַקומען די הויפן וואָס כּולל די רגע מאַקסימום קאָינס.
  4. באָב וועט באַקומען די הויפן מיט דער מינדסטער נומער פון קאָינס.
  5. איבערחזרן די סטעפּס ביז אַלע מערידן פון קאָינס זענען נישט פונאנדערגעטיילט.

לויט די אויבן כּללים, מיר דאַרפֿן צו געפֿינען די מאַקסימום נומער פון קאָינס.

בייַשפּיל

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

דערקלערונג:

איר וועט אויסקלייַבן די מערידן אויף די פאלגענדע וועג:

  • (קסנומקס)
  • (קסנומקס)
  • (קסנומקס)

דעם וועג פון הויפן סעלעקציע וועט פירן איר צו באַקומען די מאַקסימום נומער פון קאָינס וואָס איז 18 קאָינס.

צוגאַנג פֿאַר מאַקסימום נומער פון קאָינס איר קענען באַקומען Leetcode סאַלושאַן

צו סאָלווע דעם פּראָבלעם, אַלע קונץ ליגט הינטער די סעלעקציע פון ​​3 מערידז יעדער מאָל וואָס וועט פירן איר צו באַקומען די מאַקסימום נומער פון קאָינס.

  • באָב געץ די הויפן מיט די מינדסטער נומער פון קאָינס. אַזוי יעדער מאָל מיר וועלן קלייַבן אַ הויפן פון אַלע די רוען מערידן וואָס כּולל די מינימום נומער פון קאָינס. עס וועט ענשור אַז באָב באַקומען אַלע די N מערידן מיט די מינדסטער נומער פון קאָינס פֿון 3 * N מערידן.
  • יעדער מאָל מיר סעלעקטירן צוויי מערידן פון אַלע די רוען מערידן וואָס כּולל די מאַקסימום נומער פון קאָינס. אַליס געץ די הויפן וואָס כּולל די מאַקסימום קאָינס. איר באַקומען די הויפן מיט די רגע מאַקסימום נומער פון קאָינס.
  • אין סדר צו באַקומען די מערידן מיט די מאַקסימום און די מינימום נומער פון קאָינס סאָרט די מענגע.
  • די בילד געוויזן אונטן דערקלערט די פאַרשפּרייטונג פון מערידן צווישן אַליס, באָב און איר.

לעעטקאָדע לייזונג צו מאַקסימום נומער פון קאָינס איר קענען באַקומען

ימפּלעמענטאַטיאָן

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 איז די גרייס פון דעם מענגע.

אָרט קאַמפּלעקסיטי

די פּלאַץ קאַמפּלעקסיטי פון די אויבן קאָד איז אָ (1) ווייַל מיר נוצן בלויז אַ בייַטעוודיק צו קראָם ענטפֿערס.

רעפֿערענצן