Leetcode più lunghe parentesi valide
Includerò una soluzione in Python e C ++ e potrai esaminarne una. Sono principalmente interessato a rivedere il codice C ++ che è una cosa che ho iniziato a imparare di recente; chi non conosce il C ++ può rivedere il codice Python. Entrambe le soluzioni condividono una logica simile, quindi la revisione si applicherà a entrambe.
Dichiarazione problema
Data una stringa contenente solo i caratteri '(' e ')', trova la lunghezza della sottostringa di parentesi più lunga valida (ben formata).
Esempio 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Esempio 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
Esempio 3:
Input: s = ""
Output: 0
Esempio 4:
Input: s = "(()()()"
Output: 6
Esempio 5:
Input: s = "((())((((())))"
Output: 8
Entrambe le soluzioni sono Oⁿ e superano tutti i casi di test incluso il limite di tempo, tuttavia, richiedono più tempo di quanto mi aspettassi, specialmente la versione c ++ sebbene entrambe condividano la stessa logica. Devo migliorare il tempo come priorità.
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(')((()()()()'))
Statistiche:
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(")()())");
}
Statistiche:
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.
Risposte
Ecco alcune cose che possono aiutarti a migliorare il tuo programma.
Versione C ++
Utilizzare tutte le richieste #includes
Il tipo std::vector<size_t>viene utilizzato nella definizione di calculate_distance()nel file di intestazione, ma non #include <vector>è presente nell'elenco degli include. Inoltre, std::max()viene utilizzato, ma non #include <algorithm>è presente nel .cppfile.
Riduci a icona l'interfaccia
Il .hfile è una dichiarazione dell'interfaccia al tuo software. Il .cppè l' implementazione di tale interfaccia. È una buona pratica di progettazione ridurre al minimo l'interfaccia a ciò che è necessario per i programmi esterni. Per questo motivo, rimuoverei la calculate_distance()funzione dall'intestazione.
Crea funzioni locali static
Con l'interfaccia più piccola come sostenuto in precedenza, la calculate_distancefunzione diventa un dettaglio di implementazione utilizzato solo all'interno del .cppfile. Per questo motivo, dovrebbe essere fatto in staticmodo che il compilatore sappia che è sicuro incorporare la funzione.
Usa una switchpiuttosto che una serie di ifaffermazioni
Il codice attualmente contiene questo:
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);
}
}
Sarebbe un po 'più veloce e un po' più facile da leggere se invece fosse scritto così:
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;
}
}
Fai attenzione con firmato e non firmato
Cosa significherebbe se calculate_distancerestituisse un numero negativo? Probabilmente non ha un'interpretazione sensata, quindi per questo motivo, consiglierei di restituire una unsignedquantità rispetto a un firmato int.
Scrivi funzioni di test
Hai fornito un input di test nella descrizione del problema, ma sarebbe bene scrivere uno script di test completo per esercitare la funzione. Per questo genere di cose, tendo a utilizzare un oggetto di prova. Ecco quello che ho scritto per questo codice:
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;
};
Ora ecco alcuni vettori di test e una 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;
}
}
Per garantire sia la correttezza che il tempismo, ho utilizzato il mio modello di cronometro . La versione finale di mainassomiglia a questa:
#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";
}
Usa un algoritmo migliore
Il codice esistente non è poi così male, ma non è efficiente come potrebbe essere. Sulla mia macchina con il codice mostrato sopra e con un milione di prove, ci vogliono 5,66 microsecondi per invocazione get_longest()sull'input di test più lungo, che è anche l'ultimo del set. Possiamo fare di meglio. Ecco una routine alternativa che utilizza un std::vectorper tenere traccia di ciascuno degli avviamenti (man mano che si verificano, ma esegue anche il calcolo della lunghezza dello span quando incontra ogni chiusura ). Ecco come l'ho fatto:
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;
}
Probabilmente c'è ancora spazio per miglioramenti, ma ecco come funziona. Innanzitutto, tiene traccia di ciascuna Spandelle parentesi corrispondenti e nidificate. Quindi ()sarebbe corrispondere a tale intervallo, come sarebbe (()). Il codice utilizza is_strictly_enclosingper verificare questi. Ad esempio, in (()), la coppia interna viene trovata per prima e avrebbe un intervallo di {1,2}. La coppia esterna si trova per ultima e ha una durata di {0,3}. Se esaminiamo la logica, ora è chiaro cosa sta cercando questo codice:
bool is_strictly_enclosing(const Span& other) const {
return other.begin - begin == 1 &&
end - other.end == 1;
}
In secondo luogo, c'è il caso di parentesi corrispondenti ma non annidate come ()()o (())(). Anche in questo caso, utilizziamo una funzione membro di Span:
bool is_contiguous_with(const Span& other) const {
return begin - other.end == 1;
}
Utilizzando questo codice, otteniamo il seguente rapporto sui tempi:
1000000 prove hanno impiegato 562299 microsecondi per una media di 0,562299 microsecondi / prova
Quindi questa versione del codice è circa 10 volte più veloce. Notare anche che gestisce correttamente l'input non valido, ad esempio ((*))segnalando 0una stringa di questo tipo.
Versione Python
Utilizzare elifper condizioni che si escludono a vicenda
Il controllo per l'apertura (usa ifma avrebbe più senso usare elifqui perché i due casi (o (o )) sono gli unici considerati. Eseguendo solo questa modifica, ogni iterazione (utilizzando la stessa stringa molto lunga del codice C ++) diminuisce da 74,167 microsecondi a 72,444 microsecondi.
Non aggiornare i valori che sono rimasti invariati
Il codice attualmente ha questa sequenza:
for j in range(len(s)):
if j in closed:
cum_distance += 1
else:
cum_distance = 0
max_distance = max(max_distance, cum_distance)
Una rapida occhiata al codice verificherà che max_distancepuò ottenere un nuovo valore solo se l' ifaffermazione è vera, quindi spostiamo la riga lì. Questo riduce il tempo fino a 71,680 microsecondi.
Usa un algoritmo più veloce
Ancora una volta, ciò che funziona nella versione C ++ funziona anche in Python. Ecco una versione Python dell'algoritmo sopra:
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
Questa volta, la differenza non è così drammatica e il tempo per questa funzione è di 64,562 microsecondi.