Leetcode längste gültige Klammern
Link hier
Ich werde eine Lösung in Python und C ++ aufnehmen, und Sie können eine überprüfen. Ich bin hauptsächlich daran interessiert, den C ++ - Code zu überprüfen, was ich kürzlich gelernt habe. Wer C ++ nicht kennt, kann Python-Code überprüfen. Beide Lösungen haben eine ähnliche Logik, sodass die Überprüfung für beide gilt.
Problemstellung
Wenn eine Zeichenfolge nur die Zeichen '(' und ')' enthält, ermitteln Sie die Länge des längsten gültigen (wohlgeformten) Teilstrings in Klammern.
Beispiel 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Beispiel 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
Beispiel 3:
Input: s = ""
Output: 0
Beispiel 4:
Input: s = "(()()()"
Output: 6
Beispiel 5:
Input: s = "((())((((())))"
Output: 8
Beide Lösungen sind Oⁿ und bestehen alle Testfälle einschließlich des Zeitlimits. Sie benötigen jedoch mehr Zeit als erwartet, insbesondere die c ++ - Version, obwohl beide dieselbe Logik verwenden. Ich muss die Zeit vorrangig verbessern.
longest_parentheses.py
def check_longest(s):
opened = []
closed = []
cum_distance = 0
max_distance = 0
for i, ss in enumerate(s):
if ss == ')':
if opened:
closed.append((opened.pop(), i))
if ss == '(':
opened.append(i)
closed = set(sum(closed, ()))
for j in range(len(s)):
if j in closed:
cum_distance += 1
else:
cum_distance = 0
max_distance = max(max_distance, cum_distance)
return max_distance
if __name__ == '__main__':
print(check_longest(')((()()()()'))
Statistiken:
Runtime: 272 ms, faster than 5.14% of Python3 online submissions for Longest Valid Parentheses.
Memory Usage: 15.5 MB, less than 6.57% of Python3 online submissions for Longest Valid Parentheses.
longest_parentheses.h
#ifndef LEETCODE_LONGEST_PARENTHESES_H
#define LEETCODE_LONGEST_PARENTHESES_H
#include <string_view>
int calculate_distance(size_t p_size, const std::vector<size_t> &closed);
int get_longest(const std::string_view &s);
#endif //LEETCODE_LONGEST_PARENTHESES_H
longest_parentheses.cpp
#include "longest_parentheses.h"
#include <vector>
#include <iostream>
int calculate_distance(size_t p_size, const std::vector<size_t> &closed) {
int cum_distance = 0;
int max_distance = 0;
for (size_t i = 0; i < p_size; ++i) {
if (std::find(closed.begin(), closed.end(), i) != closed.end()) {
cum_distance++;
} else {
cum_distance = 0;
}
max_distance = std::max(max_distance, cum_distance);
}
return max_distance;
}
int get_longest(const std::string_view &s) {
std::vector<size_t> opened, closed;
for (size_t i = 0; i < s.size(); ++i) {
auto ss = s[i];
if (ss == ')') {
if (!opened.empty()) {
closed.push_back({opened.back()});
closed.push_back(i);
opened.pop_back();
}
}
if (ss == '(') {
opened.push_back(i);
}
}
return calculate_distance(s.size(), closed);
}
int main() {
std::cout << get_longest(")()())");
}
Statistiken:
Runtime: 1276 ms, faster than 5.09% of C++ online submissions for Longest Valid Parentheses.
Memory Usage: 9.3 MB, less than 5.04% of C++ online submissions for Longest Valid Parentheses.
Antworten
Hier sind einige Dinge, die Ihnen helfen können, Ihr Programm zu verbessern.
C ++ - Version
Verwenden Sie alle erforderlichen #includes
Der Typ std::vector<size_t>wird in der Definition von calculate_distance()in der Header-Datei verwendet, #include <vector>fehlt jedoch in der Liste der dort enthaltenen Includes. Wird auch std::max()verwendet, #include <algorithm>fehlt aber in der .cppDatei.
Minimieren Sie die Schnittstelle
Die .hDatei ist eine Deklaration der Schnittstelle zu Ihrer Software. Das .cppist die Implementierung dieser Schnittstelle. Es ist eine gute Entwurfspraxis, die Schnittstelle auf das zu minimieren, was von externen Programmen benötigt wird. Aus diesem Grund würde ich die calculate_distance()Funktion aus dem Header entfernen .
Machen Sie lokale Funktionen static
Mit der oben empfohlenen kleineren Schnittstelle wird die calculate_distanceFunktion zu einem Implementierungsdetail, das nur in der .cppDatei verwendet wird. Aus diesem Grund sollte es so gemacht werden, staticdass der Compiler weiß, dass es sicher ist, die Funktion zu integrieren.
Verwenden Sie eine switchstatt einer Reihe von ifAnweisungen
Der Code enthält derzeit Folgendes:
for (size_t i = 0; i < s.size(); ++i) {
auto ss = s[i];
if (ss == ')') {
if (!opened.empty()) {
closed.push_back({opened.back()});
closed.push_back(i);
opened.pop_back();
}
}
if (ss == '(') {
opened.push_back(i);
}
}
Es wäre etwas schneller und leichter zu lesen, wenn es stattdessen so geschrieben wäre:
for (size_t i = 0; i < s.size(); ++i) {
switch(s[i]) {
case ')':
if (!opened.empty()) {
closed.push_back({opened.back()});
closed.push_back(i);
opened.pop_back();
}
break;
case '(':
opened.push_back(i);
break;
}
}
Seien Sie vorsichtig mit signierten oder nicht signierten
Was würde es bedeuten, wenn calculate_distanceeine negative Zahl zurückgegeben würde? Es hat wahrscheinlich keine vernünftige Interpretation, daher würde ich empfehlen, eine unsignedMenge gegenüber einer signierten zurückzusenden int.
Schreiben Sie Testfunktionen
Sie haben in der Beschreibung des Problems einige Tests eingegeben, aber es wäre gut, ein vollständiges Testskript zu schreiben, um die Funktion auszuführen. Für solche Dinge verwende ich gerne ein Testobjekt. Hier ist der, den ich für diesen Code geschrieben habe:
class ParenTest {
public:
ParenTest(std::string_view input, unsigned longest)
: input{input}
, longest{longest}
{}
unsigned operator()() const {
return static_cast<unsigned>(get_longest(input));
}
bool test() const {
return longest == operator()();
}
friend std::ostream& operator<<(std::ostream& out, const ParenTest& test) {
auto calculated = test();
return out << (calculated == test.longest ? "ok " : "BAD ")
<< "\"" << test.input << "\", " << test.longest << ", got " << calculated << "\n";
}
private:
std::string_view input;
unsigned longest;
};
Hier sind einige Testvektoren und eine mainRoutine:
int main(int argc, char* argv[]) {
static const std::vector<ParenTest> tests{
{ "(()", 2 },
{ ")()())", 4 },
{ "", 0 },
{ "(()()()", 6 },
{ "((())((((())))", 8 },
{ "(())(())(()))", 12 },
{ "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))", 12 },
{ "(())(())(()))(())(())(())(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
{ "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
{ "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))"
"(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
};
for (const auto &test : tests) {
std::cout << test;
}
}
Um sowohl die Richtigkeit zu gewährleisten als auch das Timing zu verbessern, habe ich meine Stoppuhr-Vorlage verwendet . Die endgültige Version von mainsieht folgendermaßen aus:
#include "longest_parentheses.h"
#include "stopwatch.h"
#include <string_view>
#include <iostream>
#include <vector>
// the ParenTest class goes here
int main(int argc, char* argv[]) {
static const std::vector<ParenTest> tests{
{ "(()", 2 },
{ ")()())", 4 },
{ "", 0 },
{ "(()()()", 6 },
{ "((())((((())))", 8 },
{ "(())(())(()))", 12 },
{ "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))", 12 },
{ "(())(())(()))(())(())(())(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
{ "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
{ "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))"
"(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
};
for (const auto &test : tests) {
std::cout << test;
}
if (argc != 2) {
std::cout << "Usage: " << argv[0] << " num_trials\n";
return 1;
}
auto iterations = std::stoul(argv[1]);
Stopwatch<> timer{};
bool valid{true}
for (auto i{iterations}; i; --i) {
valid &= tests.back().test();
}
auto elapsed{timer.stop()};
if (!valid) {
std::cout << "The program failed!\n";
return 2;
}
std::cout << iterations << " trials took " << elapsed << " microseconds\n"
" for an average of " << elapsed/iterations << " microseconds/trial\n";
}
Verwenden Sie einen besseren Algorithmus
Der vorhandene Code ist nicht so schlecht, aber nicht so effizient wie er sein könnte. Auf meinem Computer mit dem oben gezeigten Code und mit einer Million Versuchen dauert es 5,66 Mikrosekunden pro Aufruf get_longest()der längsten Testeingabe, die auch die letzte des Satzes ist. Wir können es besser machen. Hier ist eine alternative Routine, die a verwendet std::vector, um jeden Start zu verfolgen (, wenn er auftritt, aber auch die Berechnung der Spannweitenlänge, wenn er auf jeden Abschluss trifft ). So habe ich es gemacht:
unsigned get_longest(const std::string_view& in) {
struct Span {
std::size_t begin;
std::size_t end;
Span(std::size_t begin, std::size_t end)
: begin{begin}
, end{end}
{}
std::size_t len() const {
return end - begin + 1;
}
bool is_strictly_enclosing(const Span& other) const {
return other.begin - begin == 1 &&
end - other.end == 1;
}
bool is_contiguous_with(const Span& other) const {
return begin - other.end == 1;
}
};
std::vector<std::size_t> parenmatch;
std::vector<Span> spans;
std::size_t longest{0};
for (std::size_t i{0}; i < in.size(); ++i) {
switch(in[i]) {
case '(':
parenmatch.push_back(i);
break;
case ')':
if (!parenmatch.empty()) {
Span curr_span{parenmatch.back(), i};
parenmatch.pop_back();
if (!spans.empty() && curr_span.is_strictly_enclosing(spans.back())) {
// destroy the last one
spans.pop_back();
}
if (!spans.empty() && curr_span.is_contiguous_with(spans.back())) {
// merge the contiguous spans
spans.back().end = curr_span.end;
} else {
spans.push_back(curr_span);
}
longest = std::max(longest, spans.back().len());
}
break;
default:
parenmatch.clear();
spans.clear();
}
}
return longest;
}
Es gibt wahrscheinlich noch Raum für Verbesserungen, aber so funktioniert das. Erstens verfolgt es jede Spanübereinstimmende und verschachtelte Klammer. So ()würde eine solche Spanne entsprechen, wie würde (()). Der Code verwendet is_strictly_enclosing, um diese zu testen. In beispielsweise wird (())das innere Paar zuerst gefunden und hätte eine Spanne von {1,2}. Das äußere Paar wird zuletzt gefunden und hat eine Spanne von {0,3}. Wenn wir die Logik untersuchen, ist jetzt klar, wonach dieser Code sucht:
bool is_strictly_enclosing(const Span& other) const {
return other.begin - begin == 1 &&
end - other.end == 1;
}
Zweitens gibt es den Fall von übereinstimmenden, aber nicht verschachtelten Klammern wie ()()oder (())(). Auch hier verwenden wir eine Mitgliedsfunktion von Span:
bool is_contiguous_with(const Span& other) const {
return begin - other.end == 1;
}
Mit diesem Code erhalten wir den folgenden Zeitbericht:
1000000 Versuche dauerten 562299 Mikrosekunden für durchschnittlich 0,562299 Mikrosekunden / Versuch
Diese Version des Codes ist also ungefähr 10x schneller. Beachten Sie auch, dass fehlerhafte Eingaben korrekt verarbeitet werden, z. B. ((*))durch Berichterstellung 0für eine solche Zeichenfolge.
Python-Version
Verwendung eliffür sich gegenseitig ausschließende Bedingungen
Die Prüfung für die Eröffnung wird (verwendet, ifaber es wäre sinnvoller, sie elifhier zu verwenden , da nur die beiden Fälle (entweder (oder )) berücksichtigt werden. Wenn Sie nur diese eine Änderung vornehmen, wird jede Iteration (unter Verwendung derselben sehr langen Zeichenfolge wie im C ++ - Code) von 74,167 Mikrosekunden auf 72,444 Mikrosekunden gelöscht.
Aktualisieren Sie keine unveränderten Werte
Der Code hat derzeit folgende Reihenfolge:
for j in range(len(s)):
if j in closed:
cum_distance += 1
else:
cum_distance = 0
max_distance = max(max_distance, cum_distance)
Ein kurzer Blick auf den Code bestätigt, dass max_distancenur dann ein neuer Wert erhalten werden kann, wenn die ifAnweisung wahr ist. Verschieben Sie also die Zeile dorthin. Dies verringert die Zeit auf 71,680 Mikrosekunden.
Verwenden Sie einen schnelleren Algorithmus
Was in der C ++ - Version funktioniert, funktioniert wieder in Python. Hier ist eine Python-Version des obigen Algorithmus:
def get_longest(s):
parenmatch = []
spans = []
longest = 0
for i, ss in enumerate(s):
if ss == '(':
parenmatch.append(i)
elif ss == ')':
if parenmatch:
curr_span = (parenmatch.pop(), i)
if spans and spans[-1][0] - curr_span[0] == 1 and curr_span[1] - spans[-1][1] == 1:
spans.pop()
if spans and curr_span[0] - spans[-1][1] == 1:
spans[-1] = (spans[-1][0], curr_span[1])
else:
spans.append(curr_span)
longest = max(longest, spans[-1][1] - spans[-1][0] + 1)
return longest
Diesmal ist der Unterschied nicht so dramatisch und die Zeit für diese Funktion beträgt 64,562 Mikrosekunden.