Səhmlər almaq və satmaq üçün ən yaxşı vaxt

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Cisco DE Şou eBay Expedia Facebook Goldman Sachs google JP Morgan microsoft Morgan Stanley Kahin PayPal Kvalifikasiya Samsung VMware
Geyim Dinamik proqramlaşdırmaBaxılıb 91

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.

Problem bəyanat

Problem "Səhm alqı-satqısı üçün ən yaxşı vaxt" sizə verildiyini bildirir array n uzunluğunun qiymətləri, burada ith element anbar qiymətini ith günündə saxlayır.
Yalnız bir əməliyyat edə biləriksə, yəni bir gündə alıb başqa bir gündə satmaq üçün qazanılan maksimum qazanc nə qədər olacaq.

misal

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

Alqoritm

Səhmimizi on gün alsaq, maksimum mənfəət, i + 1-dən n-ə qədər olan gündə bir hissə satmaqla qazanılır, belə ki, gün səhmlərin maksimum qiymətinə sahib olsun və qiymət [i].
Qiymətləri nəzərdən keçirin = {7, 1, 5, 3, 6, 4}

Səhmlər almaq və satmaq üçün ən yaxşı vaxtPin
Beləliklə, maksimum mənfəət 2-ci gün səhm alıb 5-ci gündə satmaqla qazanılır, maksimum qazanc 5-dir.

Səhm almaq və satmaq üçün ən yaxşı vaxt üçün sadəlövh yanaşma

Yuxarıda göstərilən alqoritmi tətbiq etmək üçün sadəlövh yanaşma, biri alış günü üçün, digəri isə qarşıdakı günlərdə maksimum mənfəət tapmaq üçün iki iç içə döngə işlədir.

Saxta Kod

int maxProfit = -infinity;
for (int i = 0; i < n; i++) {
  int costPrice = price[i];
  int max = -infinity;
  // Finding the maximum stock price greater than costPrice on upcoming days
  for (int j = i + 1; j < n; j++) {
    if (prices[j] > costPrice) {
      max = maximum(max, a[j]);
    }
  }
  int profit = 0;
  if (max != -infinity) {
    profit = max - costPrice;
  }
  maxProfit = maximum(maxProfit, profit);
}

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n ^ 2), çünki səhm alqı-satqısı üçün günü seçmək üçün iki iç içə döngədən istifadə edirik. Beləliklə zamanın mürəkkəbliyi poltnomialdır.

Kosmik Mürəkkəblik

O (1), çünki hər hansı bir məlumat quruluşundakı hər bir elementlə əlaqəli bir məlumat saxlamırıq. Biz yalnız daimi məkandan istifadə etmişik. Beləliklə kosmik mürəkkəblik xətti olur.
burada n - massivdəki elementlərin sayı.

Səhmləri almaq və satmaq üçün ən yaxşı vaxt üçün optimal yanaşma

Daha yaxşı bir yanaşma bir array ith elementi indiki maksimum dəyəri saxlayır qiymətləri dizi i + 1-dən n-ə. Yəni sadəlövh yanaşmada daxili yuva halqasının gördüyü işi əvvəlcədən hesablayırıq. Beləliklə, daxili iç içə döngəni birbaşa maksimumu taparaq əvəz edə bilərik. Əvvəlcədən hesablama alqoritmi aşağıdakı qaydada işləyir.

  1. Ölçüsü maxSP ölçülü bir sıra yaradın qiymətləri massivi və dəyişən max və onu minimum dəyər kimi başladın.
  2. Son indeksdən başlayın qiymətləri serial.
    1. Qiymətlər [i] maksimumdan böyükdürsə
      1. Maksimum qiymətləri [i] olaraq yeniləyin və minimum dəyər olaraq maxSP [i] olun
    2. Qiymətlər [i] maksimumdan böyük deyilsə, başqa bir şeydir
      1. MaxSP [i] = max. Yeniləyin
  3. Əvvəlcədən hesablamadan sonra sadəlövh yanaşmanı izləyirik və yeni yaratdığımız maxSP dizisini istifadə edərək daxili iç içə döngəni əvəz edirik.

Saxta Kod

// Pre computation
int max = -infinity;
for (int i = n - 1; i >= 0; i--) {
  if (prices[i] > max) {
    max = prices[i];
    maxSP[i] = -infinity;
  } else {
    maxSP[i] = max;
  }
}
// Do as in naive approach
int maxProfit = -infinity;
for (int i = 0; i < n; i++) {
  int costPrice = prices[i];
  // Rather than using a loop to calculate max, we can directly get it from maxSP array
  int max = maxSP[i];
  int profit = 0;
  if (max != -infinity) {
    profit = max - costPrice;
  }
  maxProfit = maximum(maxProfit, profit);
}

Kodu

Səhm almaq və satmaq üçün ən yaxşı vaxt üçün Java kodu problemi

import java.util.Scanner;

class BestTimetoBuyandSellStock {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // Prices array
        int prices[] = new int[]{7, 1, 5, 3, 6, 4};

        // Calculating the max profit
        int ans = maxProfit(prices, prices.length);

        // Print the answer
        System.out.println(ans);
    }

    private static int maxProfit(int[] prices, int n) {
        int maxSP[] = new int[n];
        int max = Integer.MIN_VALUE;

        // Construct the maxSP array
        for (int i = n - 1; i >= 0; i--) {
            if (prices[i] > max) {
                max = prices[i];
                maxSP[i] = Integer.MIN_VALUE;
            } else {
                maxSP[i] = max;
            }
        }

        int profit = 0;
        for (int i = 0; i < n; i++) {
            if (maxSP[i] != Integer.MIN_VALUE) {
                profit = Math.max(profit, maxSP[i] - prices[i]);
            }
        }

        // Return profit
        return profit;
    }
}
5

Səhm almaq və satmaq üçün ən yaxşı vaxt üçün C ++ kodu

#include <bits/stdc++.h>
using namespace std;

int maxProfit(int *prices, int n) {
    int maxSP[n];
    int max = INT_MIN;
    
    // Construct the maxSP array
    for (int i = n - 1; i >= 0; i--) {
        if (prices[i] > max) {
            max = prices[i];
            maxSP[i] = INT_MIN;
        } else {
            maxSP[i] = max;
        }
    }
    
    int profit = 0;
    for (int i = 0; i < n; i++) {
        if (maxSP[i] != INT_MIN) {
            profit = std::max(profit, maxSP[i] - prices[i]);
        }
    }
    
    // Return profit
    return profit;
}

int main() {
    // Prices array
    int prices[] = {7, 1, 5, 3, 6, 4};
    
    // Calculating the max profit
    int ans = maxProfit(prices, sizeof(prices) / sizeof(prices[0]));
    
    // Print the answer
    cout<<ans<<endl;
    return 0;
}
5

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n), maksimum qazancın hesablanması və hesablanması zamanı massivin n elementini keçdiyimiz kimi. Zamanın mürəkkəbliyi xətti.

Kosmik Mürəkkəblik

O (n), çünki hesablama zamanı cari gündən sonrakı bir gündə maksimum satış qiymətini saxlayırdıq. Dizidəki bütün elementlər üçün saxlanıldığı üçün. Məkan mürəkkəbliyi də xətti.
burada n - massivdəki elementlərin sayı.

Crack Sistemi Dizayn Müsahibələri
Translate »