[PYTHON] Lassen Sie Code Day 31 von vorne beginnen "581. Kürzestes unsortiertes kontinuierliches Subarray"

Ü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 30 ab Null "234. Palindrome Linked List"

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

Twitter Ich mache es.

Problem

581. Shortest Unsorted Continuous Subarray Der Schwierigkeitsgrad ist einfach. Auszug aus den 100 beliebtesten Fragen.

Das Problem erhält ein Array von ganzen Zahlen. Wenn Sie dieses Array in aufsteigender Reihenfolge sortieren, suchen Sie ein zusammenhängendes Unterarray, das das gesamte Array in aufsteigender Reihenfolge sortieren kann. Das Problem besteht darin, das kürzeste Unterarray unter ihnen zu finden und seine Länge zurückzugeben.

Betrachten wir ein Beispiel.

Example 1: Input: [2, 6, 4, 8, 10, 9, 15] Output: 5 Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Wenn Sie dies sortieren, wird das gesamte Array in aufsteigender Reihenfolge organisiert. Das kürzeste Unterarray reicht von "6" bis "9", sodass die Anzahl der Elemente erfasst und 5 zurückgegeben wird.

Lösung

Bereiten Sie die sortierte Variable vor, die Variable "start", die das Element von Anfang an abruft, und die Variable "last", die das Element vom Ende abruft. Wenn die Werte des sortierten Arrays und des ursprünglichen Arrays nicht übereinstimmen, wird der Index dieses Elements festgelegt. Ersatz für "Start". Tun Sie dies auch für "last", und die Differenz +1 ist die Länge der erforderlichen Anzahl von Elementen.

Schließlich haben wir eine Funktion implementiert, die "last --start + 1" zurückgibt, wenn "last-start" gilt, andernfalls "0".

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        start = last = 0
        num = sorted(nums)
        for i in range(len(nums)):
            if nums[i] != num[i]:
                start = i
                break
        for i in range(len(nums)-1,-1,-1):
            if nums[i] != num[i]:
                last = i
                break
        return last - start + 1 if last - start else 0
# Runtime: 196 ms, faster than 98.85% of Python3 online submissions for Shortest Unsorted Continuous Subarray.
# Memory Usage: 15.2 MB, less than 5.00% of Python3 online submissions for Shortest Unsorted Continuous Subarray.

Es war eine ziemlich einfache Idee, aber sie ist besser als ich erwartet hatte. Die Anzahl der Fragen, die mir am besten gefallen haben, hat erheblich abgenommen, daher denke ich, dass sie in Zukunft nur noch mittel sein werden.

In Bezug auf Hard weiß ich nicht, ob es richtig gelöst werden kann, aber ich werde es lösen, wenn es eine Gelegenheit gibt.

Recommended Posts

Lassen Sie Code Day 31 von vorne beginnen "581. Kürzestes unsortiertes kontinuierliches Subarray"
Lassen Sie Code Day75 von vorne beginnen "15.3 Sum"
Lassen Sie Code Day 29 "46. Permutationen" von vorne beginnen
Lassen Sie Code Day 65 "560. Subarray Sum Equals K" von vorne beginnen
Lassen Sie Code Day 27 "101. Symmetric Tree" von vorne beginnen
Lassen Sie Code Day 41 "394. Decode String" ab Null
Lassen Sie Code Day 25 "70. Climbing Stairs" von vorne beginnen
Lassen Sie Code Day69 von vorne beginnen "279. Perfect Squares"
Lassen Sie Code Day 34 von vorne beginnen "118. Pascals Dreieck"
Lassen Sie Code Day85 von vorne beginnen "6. Zick-Zack-Konvertierung"
Lassen Sie Code Day20 von vorne beginnen "134. Tankstelle"
Lassen Sie Code Day18 ab Null "53. Maximum Subarray"
Lassen Sie Code Day 88 "139. Word Break" von vorne beginnen
Lassen Sie Code Day 28 "198. House Robber" von vorne beginnen
Lassen Sie Code Day 39 "494. Target Sum" von vorne beginnen
Lassen Sie Code Day 36 "155. Min Stack" von vorne beginnen
Lassen Sie Code Tag 17 "169. Mehrheitselement" von vorne beginnen
Lassen Sie Code Tag 33 "1. Zwei Summe" ab Null
Lassen Sie Code Day8 ab Null "1302. Deepest Leaves Sum"
Lassen Sie Code Tag 22 ab Null "141. Linked List Cycle"
Lassen Sie Code Tag 30 von vorne beginnen "234. Palindrome Linked List"
Lassen Sie Code Day 32 "437. Path Sum III" von vorne beginnen
Lassen Sie Code Day68 von vorne beginnen "709. In Kleinbuchstaben"
Lassen Sie Code Tag 26 von vorne beginnen "94. Binary Tree Inorder Traversal"
Lassen Sie Code Day 46 von Grund auf neu beginnen "406. Rekonstruktion der Warteschlange nach Höhe"
Lassen Sie Code Day 38 von vorne beginnen "208. Implementieren Sie Trie (Präfixbaum)"
Lassen Sie Code Day3 ab Null "1313. Decompress Run-Length Encoded List"
Lassen Sie Code Day4 von vorne beginnen "938. Range Sum of BST"
Lassen Sie Code Day 77 "1502. Kann arithmetische Fortschritte von der Sequenz machen" ab Null
Lassen Sie Code Day 76 von vorne beginnen "3. Längste Teilzeichenfolge ohne Wiederholung von Zeichen"
Lassen Sie Code Day58 ab Null "20. Gültige Klammern"
Lassen Sie Code Day16 von vorne beginnen "344. Reverse String"
Lassen Sie Code Day49 ab Null "1323. Maximum 69 Number".
Lassen Sie Code Day89 "62. Unique Paths" ab Null
Lassen Sie Code Tag 55 "22. Klammern erzeugen" ab Null
Lassen Sie Code Tag 13 "338. Bits zählen" ab Null
Lassen Sie Code Day71 ab Null "1496. Pfadkreuzung"
Lassen Sie Code Tag 61 "7. Reverse Integer" ab Null
Lassen Sie Code Tag 82 "392. Ist Folge" ab Null
Lassen Sie Code Day51 "647. Palindromic Substrings" ab Null
Lassen Sie Code Tag 50 "739. Tägliche Temperaturen" ab Null
Lassen Sie Code Day15 ab Null "283. Nullen verschieben"
Lassen Sie Code Day14 ab Null "136. Single Number"
Lassen Sie Code Day 9 "701. In einen binären Suchbaum einfügen" von vorne beginnen
Lassen Sie Code Day 80 "703. Kth größtes Element in einem Stream" von vorne beginnen
Lassen Sie Code Day 66 "438. Alle Anagramme in einer Zeichenfolge finden" von vorne beginnen
Lassen Sie Code Day 43 von vorne beginnen "5. Längster palindromischer Teilstring"
Lassen Sie Code Day 42 "2. Add Two Numbers" von vorne beginnen
Lassen Sie Code Day57 ab Null "35. Search Insert Position"
Lassen Sie Code Day47 von vorne beginnen "14. Längstes gemeinsames Präfix"
Lassen Sie Code Day78 von vorne beginnen "206. Reverse Linked List"
Lassen Sie Code Day 90 von vorne beginnen "101 1. Kapazität zum Versenden von Paketen innerhalb von D Tagen"
Lassen Sie Code Day 44 "543. Durchmesser des Binärbaums" von vorne beginnen
Lassen Sie Code Tag 64 ab Null "287. Finden Sie die doppelte Nummer"
Lassen Sie Code Day 84 ab Null "142. Linked List Cycle II"
Lassen Sie Code Day24 ab Null "21. Zwei sortierte Listen zusammenführen"
Lassen Sie Code Day12 von vorne beginnen "617. Zwei binäre Bäume zusammenführen"
Lassen Sie Code Day2 von vorne beginnen "1108. IP-Adresse löschen"
Lassen Sie Code Day70 ab Null "295. Median aus Datenstrom suchen"
Lassen Sie Code Day81 "347. Top K Frequent Elements" ab Null
Lassen Sie Code Day48 ab Null "26. Duplikate aus sortiertem Array entfernen"