Überblick

Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.

Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.

Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.

Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.

Leetcode

Leet Code-Tabelle ab Null

Letztes Mal Leet Code Tag 17 "169. Mehrheitselement" ab Null

Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.

Problem

53. Maximum Subarray

Der Schwierigkeitsgrad ist einfach. Eine der 100 beliebtesten Fragen.

Angesichts des Nur-Ganzzahl-Arrays nums. Das Problem besteht darin, ein Unterarray in diesem Array mit einer maximalen Summe zu finden, die mindestens eine Zahl enthält, und die Summe zurückzugeben.

Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6

Wenn Sie beispielsweise alle aufeinander folgenden Elemente von "nums [3]" zu "nums [6]" hinzufügen, erhalten Sie 4 + (-1) + 2 + 1 = 6, was dem Maximalwert im Array entspricht. Es wird eine Berechnung sein.

Lösung

Ich bin ein Zub-Amateur über dynamische Planung, aber ich habe es zufällig gelesen. [Datenstruktur und Algorithmus (neues Engineering von Informationskommunikationssystemen) (Japanisch)](https://www.amazon.co.jp/%E3%83%87%E3%83%BC%E3%82%BF% E6% A7% 8B% E9% 80% A0% E3% 81% A8% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0-% E6% 96% B0% E3% 83% BB% E6% 83% 85% E5% A0% B1-% E9% 80% 9A% E4% BF% A1% E3% 82% B7% E3% 82% B9% E3% 83% 86% E3% 83% A0% E5% B7% A5% E5% AD% A6-% E4% BA% 94% E5% 8D% 81% E5% B5% 90-% E5% 81% A5% E5% A4% AB / dp / 4901683497) [Organisieren Sie typische DP-Muster (Dynamic Planning Method) Teil 1 ~ Knapsack DP ~](https://qiita.com/drken/items/a5e6fe22863b7992efdb#3-%E9%83%A8%E5%88 % 86% E5% 92% 8C% E5% 95% 8F% E9% A1% 8C% E3% 81% A8% E3% 81% 9D% E3% 81% AE% E5% BF% 9C% E7% 94% A8 % E3% 81% 9F% E3% 81% A1) Nun, es sieht nicht so aus, als ob es gelöst werden kann! ?? Ich dachte, also dachte ich darüber nach, während ich mich darauf bezog.

Bereiten Sie zunächst den Maximalwert "max_num" und die temporäre Variable "temp" vor. Ersetzen Sie die Elemente des Arrays so, dass sie von Anfang an geleckt werden. Wenn "temp" 0 oder mehr ist, vergleichen Sie es mit "max_num" und "temp", das größere wird "max_num" zugewiesen, andernfalls " 0 ist temp` zugeordnet. Wenn Sie versuchen, einen solchen Ablauf zu schreiben, sieht dieser wie folgt aus.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        temp = 0
        max_num = max(nums)
        for i in range(len(nums)):
            temp += nums[i]
            if temp >= 0:
                max_num = max(max_num,temp)
            else:
                temp = 0
        return max_num
# Runtime: 60 ms, faster than 93.50% of Python3 online submissions for Maximum Subarray.
# Memory Usage: 14.5 MB, less than 5.69% of Python3 online submissions for Maximum Subarray.

Ich habe nicht viel gelesen, weil ich ein Bild hatte, das die dynamische Planungsmethode schwer zu verstehen war, aber als ich es schrieb, schien es, dass das Gedächtnis effizienter und schneller gemacht werden kann, so dass es besser scheint, wieder hart zu lernen.

Wenn es eine gute Antwort gibt, werde ich sie hinzufügen.

[PYTHON] Lassen Sie Code Day18 ab Null "53. Maximum Subarray"

Überblick

Problem

Lösung