Leetcode Чечимин ала турган монеталардын максималдуу саны


Кыйынчылык деңгээли орто
сорттоо

Көйгөйдү айтуу

“Сиз ала турган монеталардын максималдуу саны” көйгөйүндө бизге 3 * n үймөл монета берилет. Монетанын бул үймөгү сизге жана сиздин эки досуңуз Элис менен Бобго таратылышы керек. Монеталардын үймөлөрүн жайылтуу эрежелери төмөнкүчө:

  1. Сиз каалаган үч үймөктү тандайсыз.
  2. Ушул 3 үймөктүн ичинен Алис максималдуу монеталарды камтыган үймөктү алат.
  3. Экинчи максималдуу монеталарды камтыган үймөктү аласыз.
  4. Боб үймөктү эң аз монета менен алат.
  5. Бардык үйүлгөн монеталар бөлүштүрүлмөйүнчө, ушул кадамдарды кайталаңыз.

Жогоруда айтылган эрежелерди эске алып, сиз ала турган тыйындын максималдуу санын табышыбыз керек.

мисал

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

Explanation:

Үймөктөрдү төмөнкү жол менен тандайсыз:

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

Үймөлөрдү тандоонун мындай жолу максималдуу саны 18 тыйынды алууга түрткү берет.

Leetcode Чечимин ала турган монеталардын максималдуу санына болгон мамиле

Бул көйгөйдү чечүү үчүн, ар бир жолу 3 үймөктү тандап алуунун аркасында эң көп монеталарды алууга болот.

  • Боб үймөктү эң аз тыйын менен алат. Ошентип, ар бир жолу, биз калган бардык үймөктөрдүн ичинен тыйындарды тандап, анда минималдык саны бар. Бул Бобтун 3 * n үймөгүнөн эң аз монета менен бардык 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) анткени биз массивди иргеп жатабыз. Бул жерде n массивдин көлөмү.

Космостун татаалдыгы

Жогорудагы коддун мейкиндик татаалдыгы O (1) анткени биз жоопту сактоо үчүн өзгөрмө гана колдонобуз.

шилтемелер