Birja LeetCode Həllini almaq və satmaq üçün ən yaxşı vaxt


Tez-tez soruşulur Çiy kərpic Amazon alma BlackRock Bloomberg ByteDance Cisco Citadel Expedia Facebook Goldman Sachs google JPMorgan microsoft Netflix Nvidia Kahin Paytm Salesforce XidmətNow Snapchat Über Viza VMware Yahoo Zoho
LeetCode LeetCodeSolutions Riot OyunlarBaxılıb 37

Problem bəyanat

Birja LeetCode Həllini Almaq və Satmaq üçün Ən Yaxşı Vaxt – “Səhm almaq və satmaq üçün ən yaxşı vaxt” bildirir ki, Sizə qiymətlər sırası verilir, burada qiymətlər[i] verilmiş bir səhmin onuncu gündə qiymətidir.

Bir səhm almaq üçün bir gün seçərək və gələcəkdə həmin səhmi satmaq üçün başqa bir gün seçərək qazancınızı maksimuma çatdırmaq istəyirsiniz.

Bu əməliyyatdan əldə edə biləcəyiniz maksimum gəliri qaytarın. Heç bir qazanc əldə edə bilmirsinizsə, 0 qaytarın.

Misal:

Birja LeetCode Həllini almaq və satmaq üçün ən yaxşı vaxt

prices = [7,1,5,3,6,4]
5

Explanation:

Siz 2-ci gündə (qiymət = 1) alıb, 5-ci gündə sata bilərsiniz (qiymət = 6), mənfəət = 6-1 = 5.

Qeyd etmək vacibdir ki, 2-ci gündə alış və 1-ci gündə satışa icazə verilmir, çünki satışdan əvvəl satın almalısınız.

prices = [7,6,4,3,1]
 0

Explanation:

Bu vəziyyətdə heç bir əməliyyat baş vermir və maksimum mənfəət = 0.

Brute Force Həll

Idea:

Hər j-ci gün biz onu satıb-satmayacağımızı yoxlayacağıq, maksimum nə olacaq gəlir j-ci gündən əvvəl alsaq.

Kodu

Səhmlərin alınması və satışı üçün ən yaxşı vaxtın C++ proqramı:

#include <bits/stdc++.h>
using namespace std;
 
int maxProfit(vector<int> &prices)
{
   int n = prices.size();
   int answer = 0;
   for (int i = 0; i < n; i++)
   {
       for (int j = i + 1; j < n; j++)
       {
           answer = max(answer, prices[j] - prices[i]);
       }
   }
   return answer;
}
int main()
{
   vector<int> prices = {7, 1, 5, 3, 6, 4};
   cout << maxProfit(prices) << endl;
   return 0;
}
5

Səhm almaq və satmaq üçün ən yaxşı vaxtın JAVA proqramı:

public class TutorialCup
{
   public static int maxProfit(int[] prices)
   {
       int n = prices.length;
       int answer = 0;
       for (int i = 0; i < n; i++)
       {
           for (int j = i + 1; j < n; j++)
           {
               answer=Math.max(answer, prices[j] - prices[i]);
           }
       }
       return answer;
   }
   public static void main(String[] args) {
 
   int[] prices = {7, 1, 5, 3, 6, 4};
   System.out.println(maxProfit(prices));
   }
}
5

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O(N^2)-dir, çünki biz bütün kodlar üzərindən keçirik massiv cütləri.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki biz heç bir əlavə yerdən istifadə etmirik.

Optimallaşdırılmış Həll

Idea:

Hər j-ci element üçün biz tapacağıq minimum element ondan əvvəl, belə ki, j-ci element üçün ən yaxşı cütü düzəldək.

Kodu

Səhmlərin alınması və satışı üçün ən yaxşı vaxtın C++ proqramı:

#include <bits/stdc++.h>
using namespace std;
 
int maxProfit(vector<int> &prices)
{
   int answer = 0;
   int mi = INT_MAX;
   for (auto ele : prices)
   {
       answer = max(answer, ele - mi);
       mi = min(mi, ele);
   }
   return answer;
}
int main()
{
   vector<int> prices = {7, 1, 5, 3, 6, 4};
   cout << maxProfit(prices) << endl;
   return 0;
}
5

Səhm almaq və satmaq üçün ən yaxşı vaxtın JAVA proqramı:

public class TutorialCup
{
   public static int maxProfit(int[] prices) {
        int answer = 0;
  int n=prices.length;
  int mi = Integer.MAX_VALUE;
  for (int i=0;i<n;i++)
  {
    answer = Math.max(answer, prices[i] - mi);
    mi = Math.min(mi,prices[i]);
  }
  return answer;
    }
   public static void main(String[] args) {
   int[] prices = {7, 1, 5, 3, 6, 4};
   System.out.println(maxProfit(prices));
   }
}
5

Üçün Mürəkkəblik Təhlili Səhmlər almaq və satmaq üçün ən yaxşı vaxt LeetCode Həlli

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O(N)-dir, çünki biz üzərindən keçirik array yalnız bir dəfə.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki biz heç bir əlavə yerdən istifadə etmirik.

References: https://en.wikipedia.org/wiki/Brute-force_search

https://download.java.net/java/GA/jdk14/docs/api/java.base/java/lang/reflect/Array.html

Şərh yaz

Translate »
1