Lösung:Beste Zeit zum Kaufen und Verkaufen von Aktien mit Transaktionsgebühr

Dies ist Teil einer Reihe von Leetcode-Lösungserklärungen (Index). Wenn Ihnen diese Lösung gefallen hat oder Sie sie nützlich fanden, Gefällt mir bitte dieser Beitrag und/oder hochstimmen mein Lösungsbeitrag in Leetcodes Foren.

Leetcode-Problem Nr. 714 (Mittel ):Beste Zeit zum Kaufen und Verkaufen von Aktien mit Transaktionsgebühr

Beschreibung:


(Gehe zu :Lösungsidee || Code :JavaScript | Python | Java | C++ )

Beispiele:

Einschränkungen:

Idee:


(Gehe zu :Problembeschreibung || Code :JavaScript | Python | Java | C++ )

Dieses Problem ist eine Einführung in die Zustandsmaschine Logik. Um es zu lösen, können wir die zwei möglichen unterschiedlichen Seinszustände betrachten:keinen Vorrat haben und bereit sein zu kaufen (Kaufen ) und Aktien besitzen und zum Verkauf bereit sein (Verkaufen ).

Wir müssen nur die Preise durchlaufen (P ) und den bestmöglichen Wert für diese beiden Seinszustände für jeden Tag im Auge behalten. Die Schwierigkeit besteht darin, dass sich die Gleise der beiden Staaten regelmäßig kreuzen.

Betrachten wir zum Beispiel den Zustand der Bereitschaft, Aktien nach dieser Iteration zu kaufen (Kauf ), kann erreicht werden, indem Sie heute bereit sind zu kaufen und nichts zu tun, ODER Sie kann erreicht werden, indem Sie heute verkaufsbereit sind und verkaufen (mit der zusätzlichen Gebühr [F ]). Wir müssen nur dasjenige auswählen, das den besten Wert liefert.

Dasselbe gilt für den Verkauf Zustand. Das neue Verkaufen Zustand ist das bessere Ergebnis zwischen den vorherigen Verkäufen Zustand ohne Aktion und den vorherigen Kauf Staat mit einem Aktienkauf heute.

Wir sollten unsere Anfangswerte für den Kauf manuell festlegen und verkaufen um den ersten Tag zu berücksichtigen und von dort aus zu iterieren.

Da die Gebühr nur einmal pro Kauf-/Verkaufspaar erhoben wird, können wir sie technisch auf beiden Seiten berücksichtigen, da wir den Kauf immer zurückgeben wollen Zustand, keine ausstehenden Aktien mehr zu verkaufen.

Frage:Sollten wir uns Gedanken über die Aktualisierung des Kaufs machen, bevor wir ihn in der zweiten Gleichung verwenden?
Rein rechnerisch ist es immer nur ein guter Tag, um oder zu kaufen verkaufen; es kann nicht beides sein.

Betrachten Sie die möglichen Situationen:In der ersten Gleichung, wenn der alte Kauf größer ist als Verkauf + P[i] - F , dann das neue Kaufen wird dasselbe wie das alte Kaufen sein , also gibt es keine Änderung für die zweite Gleichung.

Aber was ist, wenn kaufen Änderungen? Nehmen wir ein Beispiel:

  if:  buy = 10, P[i] = 4, F = 0
then:  newBuy = max(10, sell + 4 - 0)
       newSell = max(sell, newBuy - 4)

  if:  sell <= 6                          // For values of sell less than 7
then:  newBuy = max(10, <=10)             // the old buy will still be largest
       newBuy = buy                       // so there's no problem

  if:  sell > 6                           // If sell is greater than 6
then:  newBuy = max(10, >6 + 4)           // then buy will change
       newBuy = sell + 4                  // so we might have a problem

  if:  newBuy = sell + 4                  // But here we see that sell cannot
then:  newSell = max(sell, sell + 4 - 4)  // possibly change when buy does

Jeder positive Wert für F im obigen Beispiel würde nur den Wert von newBuy senken , was es nur so machen würde, dass newBuy - P[i] konnte nicht einmal verkaufen aber immer niedriger sein.

Implementierung:

Der Code für alle vier Sprachen ist nahezu identisch.

Javascript-Code:


(Gehe zu :Problembeschreibung || Lösungsidee )

var maxProfit = function(P, F) {
    let len = P.length, buying = 0, selling = -P[0]
    for (let i = 1; i < len; i++) {
        buying = Math.max(buying, selling + P[i] - F)
        selling = Math.max(selling, buying - P[i])
    }
    return buying
};

Python-Code:


(Gehe zu :Problembeschreibung || Lösungsidee )

class Solution:
    def maxProfit(self, P: List[int], F: int) -> int:
        buying, selling = 0, -P[0]
        for i in range(1, len(P)):
            buying = max(buying, selling + P[i] - F)
            selling = max(selling, buying - P[i])
        return buying

Java-Code:


(Gehe zu :Problembeschreibung || Lösungsidee )

class Solution {
    public int maxProfit(int[] P, int F) {
        int len = P.length, buying = 0, selling = -P[0];
        for (int i = 1; i < len; i++) {
            buying = Math.max(buying, selling + P[i] - F);
            selling = Math.max(selling, buying - P[i]);
        }
        return buying;
    }
}

C++-Code:


(Gehe zu :Problembeschreibung || Lösungsidee )

class Solution {
public:
    int maxProfit(vector<int>& P, int F) {
        int len = P.size(), buying = 0, selling = -P[0];
        for (int i = 1; i < len; i++) {
            buying = max(buying, selling + P[i] - F);
            selling = max(selling, buying - P[i]);
        }
        return buying;
    }
};