Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.
Mündəricat
Problem bəyanat
“Səhm III almaq və satmaq üçün ən yaxşı vaxt” problemində, massivdəki hər elementin həmin gün verilmiş stokun qiymətini ehtiva etdiyi bir sıra verilir.
Tərifi əməliyyat bir hissə hissə almaq və o bir hissə satmaqdır.
Bizim vəzifəmiz aşağıdakı məhdudiyyətlər altında maksimum mənfəət tapmaqdır:
- əvvəlki hissəni satmamışıqsa yeni bir səhm ala bilmərik. yəni bir anda ən çox bir stoka sahib ola bilərik.
- ən çox iki əməliyyat edə bilərik.
misal
prices = [1,2,3,4,5]
4
Explanation: əldə edilə bilən maksimum mənfəət 4-dür. Əməliyyat detalı:
İlk gün: al
İkinci gün: istirahət
Üçüncü gün: istirahət
Dördüncü gün: istirahət
Beşinci gün: satmaq
Stock III Leetcode Solution almaq və satmaq üçün ən yaxşı vaxt üçün yanaşma
Bu problem daha çətin bir versiyadır Səhmlər almaq və satmaq üçün ən yaxşı vaxt. Beləliklə, bu problemə atlamadan əvvəl problemin asan versiyasını həll etməlisiniz.
Burada yalnız bir əməliyyat edə biləcəyimiz asan versiyaya nisbətən ən çox iki əməliyyat edə bilərik. bu, maksimum mənfəət verəcək şəkildə bir əməliyyat və ya iki əməliyyat deməkdir.
Problemin ən hiyləgər hissəsi ikinci əməliyyatı necə idarə etməkdir. Bu problemi görmək üçün perspektivimizi dəyişdirdikdən sonra bu problem bu problemin asan bir versiyasına çevrilə bilər.
ilk əməliyyatımızı 200 Rs qazancla tamamladığımızı deyək. (Bu hissə eynidir Səhmlər almaq və satmaq üçün ən yaxşı vaxt). Beləliklə, ilk əməliyyatdan sonra əlimizdə 200 Rs var.
İndi 500 Rs bir hissə almağa gedəndə. İstədiyimiz kimi düşünə bilərik, baxmayaraq ki, səhmlərin qiyməti 500 Rs-dir. Ancaq bizim üçün 300 Rs'dir, çünki onsuz da əlimizdə 200 Rs var və pulsuz əldə etdik. İndi ikinci əməliyyatı da xalis mənfəəti içimizdəki kimi maksimum dərəcədə artıracaq şəkildə edəcəyik Səhmlər almaq və satmaq üçün ən yaxşı vaxt problem.
Bu nümunədən yanaşma daha aydın olacaq:
Həyata keçirilməsi
Stock III almaq və satmaq üçün ən yaxşı vaxt üçün Java kodu
import java.util.Arrays;
public class Tutorialcup {
public static int maxProfit(int[] prices) {
int firstSell = 0;
int secondSell = 0;
int firstBuy = Integer.MAX_VALUE;
int secondBuy = Integer.MAX_VALUE;
for(int i = 0; i < prices.length; i++) {
int p = prices[i];
firstBuy = Math.min(firstBuy, p);
firstSell = Math.max(firstSell, p - firstBuy);
secondBuy = Math.min(secondBuy, p - firstSell);
secondSell = Math.max(secondSell, p - secondBuy);
}
return secondSell;
}
public static void main(String[] args) {
int [] arr = {1,2,3,4,5};
int ans= maxProfit(arr);
System.out.println(ans);
}
}
4
Stock III almaq və satmaq üçün ən yaxşı vaxt üçün C ++ kodu
#include <bits/stdc++.h>
using namespace std;
int maxProfit(vector<int>& prices) {
int firstSell = 0;//stores profit after one sell
int secondSell = 0;//stores profit after two sell
int firstBuy = INT_MAX;
int secondBuy = INT_MAX;
int n=prices.size();
for(int i=0;i<n;i++)
{
firstBuy=min(firstBuy,prices[i]);
firstSell=max(firstSell,prices[i]-firstBuy);
secondBuy=min(secondBuy,prices[i]-firstSell);
secondSell=max(secondSell,prices[i]-secondBuy);
}
return secondSell;
}
int main()
{
vector<int> arr = { 1,2,3,4,5 };
cout<<maxProfit(arr)<<endl;
return 0;
}
4
Fond III Leetcode Həlli almaq və satmaq üçün ən yaxşı vaxtın mürəkkəbliyinin təhlili
Zaman mürəkkəbliyi
Yuxarıdakı kodun zaman mürəkkəbliyi O (n) çünki qiymət massivini yalnız bir dəfə keçirik. Burada n qiymət massivinin uzunluğudur.
Kosmik mürəkkəblik
Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki yaddaşdan yalnız cavabı saxlamaq üçün istifadə edirik.
