Leetcode paréntesis válidos más largos
Incluiré una solución en Python y C ++ y puedes revisar una. Lo que más me interesa es revisar el código C ++, que es algo que comencé a aprender recientemente; aquellos que no conocen C ++ pueden revisar el código Python. Ambas soluciones comparten una lógica similar, por lo que la revisión se aplicará a ambas.
Planteamiento del problema
Dada una cadena que contenga solo los caracteres '(' y ')', encuentre la longitud de la subcadena de paréntesis válida más larga (bien formada).
Ejemplo 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Ejemplo 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
Ejemplo 3:
Input: s = ""
Output: 0
Ejemplo 4:
Input: s = "(()()()"
Output: 6
Ejemplo 5:
Input: s = "((())((((())))"
Output: 8
Ambas soluciones son Oⁿ y pasan todos los casos de prueba, incluido el límite de tiempo, sin embargo, están tomando más tiempo del que esperaba, especialmente la versión c ++, aunque ambas comparten la misma lógica. Necesito mejorar el tiempo como prioridad.
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(')((()()()()'))
Estadísticas:
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(")()())");
}
Estadísticas:
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.
Respuestas
Estas son algunas cosas que pueden ayudarlo a mejorar su programa.
Versión C ++
Utilice todos los #includes requeridos
El tipo std::vector<size_t>se usa en la definición de calculate_distance()en el archivo de encabezado, pero #include <vector>falta en la lista de incluye allí. También std::max()se utiliza, pero #include <algorithm>falta en el .cpparchivo.
Minimizar la interfaz
El .harchivo es una declaración de la interfaz de su software. El .cppes la aplicación de esa interfaz. Es una buena práctica de diseño minimizar la interfaz a la que necesitan los programas externos. Por esa razón, eliminaría la calculate_distance()función del encabezado.
Hacer funciones locales static
Con la interfaz más pequeña como se propuso anteriormente, la calculate_distancefunción se convierte en un detalle de implementación que se usa solo dentro del .cpparchivo. Por esa razón, debe hacerse staticpara que el compilador sepa que es seguro incorporar la función.
Utilice una switchserie de ifdeclaraciones en lugar de una
El código contiene actualmente esto:
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);
}
}
Sería un poco más rápido y un poco más fácil de leer si se escribiera así:
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;
}
}
Tenga cuidado con firmado vs. sin firmar
¿Qué significaría si calculate_distancedevuelve un número negativo? Probablemente no tenga una interpretación sensata, así que por esa razón, recomendaría que devuelva una unsignedcantidad en lugar de una firmada int.
Escribir funciones de prueba
Ha proporcionado alguna entrada de prueba en la descripción del problema, pero sería bueno escribir una secuencia de comandos de prueba completa para ejercitar la función. Para este tipo de cosas, suelo usar un objeto de prueba. Aquí está el que escribí para este código:
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;
};
Ahora aquí hay algunos vectores de prueba y una mainrutina:
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;
}
}
Para asegurar la corrección y también hacer algo de sincronización, he usado mi plantilla de cronómetro . La versión final de se mainve así:
#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 mejor
El código existente no es tan malo, pero no es tan eficiente como podría ser. En mi máquina con el código que se muestra arriba y con un millón de pruebas, toma 5.66 microsegundos por invocación de get_longest()la entrada de prueba más larga, que también es la última del conjunto. Podemos hacerlo mejor. Aquí hay una rutina alternativa que usa un std::vectorpara realizar un seguimiento de cada uno de los inicios a (medida que ocurren, pero también realiza el cálculo de la longitud del tramo a medida que se encuentra con cada cierre ). Así es como lo hice:
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;
}
Probablemente todavía haya margen de mejora, pero así es como funciona. Primero, realiza un seguimiento de cada uno Spande los paréntesis anidados y coincidentes. Así ()correspondería a tal lapso, como lo haría (()). El código se utiliza is_strictly_enclosingpara probarlos. Como ejemplo, en (()), el par interno se encuentra primero y tendría un intervalo de {1,2}. El par exterior se encuentra en último lugar y tiene un intervalo de {0,3}. Si examinamos la lógica, ahora está claro lo que busca este código:
bool is_strictly_enclosing(const Span& other) const {
return other.begin - begin == 1 &&
end - other.end == 1;
}
En segundo lugar, está el caso de paréntesis coincidentes pero no anidados como ()()o (())(). Aquí nuevamente, usamos una función miembro de Span:
bool is_contiguous_with(const Span& other) const {
return begin - other.end == 1;
}
Usando este código, obtenemos el siguiente informe de tiempo:
1000000 ensayos tomaron 562299 microsegundos para un promedio de 0.562299 microsegundos / ensayo
Entonces, esta versión del código es aproximadamente 10 veces más rápida. Tenga en cuenta también que maneja correctamente la entrada con formato incorrecto, ((*))por ejemplo, informando 0para dicha cadena.
Versión de Python
Usar elifpara condiciones mutuamente excluyentes
El cheque para la apertura se (usa, ifpero tendría más sentido usarlo elifaquí porque los dos casos ( (o )) son los únicos considerados. Hacer solo este cambio reduce cada iteración (usando la misma cadena muy larga que en el código C ++) de 74.167 microsegundos a 72.444 microsegundos.
No actualice los valores que no han cambiado
El código actualmente tiene esta secuencia:
for j in range(len(s)):
if j in closed:
cum_distance += 1
else:
cum_distance = 0
max_distance = max(max_distance, cum_distance)
Un vistazo rápido al código verificará que max_distancesolo se puede obtener un nuevo valor si la ifdeclaración es verdadera, así que muevamos la línea allí. Esto reduce el tiempo a 71.680 microsegundos.
Utilice un algoritmo más rápido
Una vez más, lo que funciona en la versión C ++ también funciona en Python. Aquí hay una versión de Python del algoritmo anterior:
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
Esta vez, la diferencia no es tan dramática y el tiempo para esta función es de 64,562 microsegundos.