Leetcode tanda kurung valid terpanjang
Saya akan menyertakan solusi dengan Python dan C ++ dan Anda dapat memeriksanya. Saya sangat tertarik untuk meninjau kode C ++ yang merupakan hal yang baru saya pelajari; mereka yang tidak tahu C ++ dapat meninjau kode Python. Kedua solusi memiliki logika yang serupa, jadi peninjauan akan berlaku untuk keduanya.
Pernyataan masalah
Diberikan string yang hanya berisi karakter '(' dan ')', temukan panjang substring tanda kurung terpanjang yang valid (dibentuk dengan baik).
Contoh 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Contoh 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
Contoh 3:
Input: s = ""
Output: 0
Contoh 4:
Input: s = "(()()()"
Output: 6
Contoh 5:
Input: s = "((())((((())))"
Output: 8
Kedua solusi adalah Oⁿ dan lulus semua kasus uji termasuk batas waktu namun, mereka memakan waktu lebih dari yang saya harapkan, khususnya versi c ++ meskipun keduanya berbagi logika yang sama. Saya perlu meningkatkan waktu sebagai prioritas.
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(')((()()()()'))
Statistik:
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(")()())");
}
Statistik:
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.
Jawaban
Berikut beberapa hal yang dapat membantu Anda meningkatkan program Anda.
Versi C ++
Gunakan semua yang diperlukan #includes
Jenis std::vector<size_t>ini digunakan dalam definisi calculate_distance()di file header, tetapi #include <vector>hilang dari daftar yang disertakan di sana. Juga, std::max()digunakan, tetapi #include <algorithm>hilang dari .cppfile.
Minimalkan antarmuka
The .hfile adalah deklarasi dari antarmuka untuk perangkat lunak Anda. Ini .cppadalah implementasi dari antarmuka itu. Ini adalah praktik desain yang baik untuk meminimalkan antarmuka hanya yang dibutuhkan oleh program luar. Untuk alasan itu, saya akan menghapus calculate_distance()fungsi dari header.
Jadikan fungsi lokal static
Dengan antarmuka yang lebih kecil seperti yang disarankan di atas, calculate_distancefungsi tersebut menjadi detail implementasi yang hanya digunakan di dalam .cppfile. Oleh karena itu, ini harus dibuat staticagar kompiler tahu bahwa fungsi tersebut aman untuk disebariskan.
Gunakan switchdaripada serangkaian ifpernyataan
Kode saat ini berisi ini:
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);
}
}
Ini akan menjadi sedikit lebih cepat dan sedikit lebih mudah untuk dibaca jika ditulis seperti ini:
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;
}
}
Hati-hati dengan yang ditandatangani vs. tidak ditandatangani
Apa artinya jika calculate_distancemengembalikan angka negatif? Ini mungkin tidak memiliki interpretasi yang masuk akal, jadi untuk alasan itu, saya akan merekomendasikan untuk mengembalikan unsignedkuantitas versus yang ditandatangani int.
Tulis fungsi pengujian
Anda telah memberikan beberapa masukan pengujian dalam deskripsi masalah, tetapi sebaiknya tulis skrip pengujian lengkap untuk menjalankan fungsinya. Untuk hal semacam ini, saya cenderung suka menggunakan benda uji. Inilah yang saya tulis untuk kode ini:
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;
};
Sekarang inilah beberapa vektor uji dan mainrutinitas:
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;
}
}
Untuk memastikan kebenaran dan juga melakukan beberapa pengaturan waktu, saya telah menggunakan template stopwatch saya . Versi terakhir mainterlihat seperti ini:
#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";
}
Gunakan algoritma yang lebih baik
Kode yang ada tidak terlalu buruk, tetapi tidak seefisien mungkin. Di mesin saya dengan kode yang ditunjukkan di atas dan dengan satu juta percobaan, dibutuhkan 5,66 mikrodetik per pemanggilan get_longest()pada input tes terpanjang, yang juga merupakan yang terakhir dari set. Kami bisa lebih baik. Berikut adalah rutinitas alternatif yang menggunakan a std::vectoruntuk melacak setiap awal (saat terjadi, tetapi juga melakukan perhitungan panjang bentang saat bertemu setiap penutupan ). Begini cara saya melakukannya:
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;
}
Mungkin masih ada ruang untuk perbaikan, tapi begini cara kerjanya. Pertama, ini melacak setiap Spantanda kurung yang cocok dan bertingkat. Jadi ()akan sesuai dengan rentang seperti itu, seperti akan (()). Kode yang digunakan is_strictly_enclosinguntuk menguji ini. Sebagai contoh, dalam (()), pasangan dalam ditemukan pertama kali dan akan memiliki rentang {1,2}. Pasangan luar ditemukan terakhir dan memiliki rentang {0,3}. Jika kita memeriksa logikanya, sekarang jelas apa yang dicari kode ini:
bool is_strictly_enclosing(const Span& other) const {
return other.begin - begin == 1 &&
end - other.end == 1;
}
Kedua, ada kasus pencocokan tetapi tanda kurung tidak bertingkat seperti ()()atau (())(). Di sini sekali lagi, kami menggunakan fungsi anggota Span:
bool is_contiguous_with(const Span& other) const {
return begin - other.end == 1;
}
Dengan menggunakan kode ini, kami mendapatkan laporan waktu berikut:
Percobaan 1000000 membutuhkan 562299 mikrodetik untuk rata-rata 0,562299 mikrodetik / percobaan
Jadi versi kode ini 10x lebih cepat. Perhatikan juga, bahwa itu dengan benar menangani input yang salah format seperti ((*))dengan melaporkan 0string seperti itu.
Versi Python
Gunakan elifuntuk kondisi yang saling eksklusif
Pemeriksaan untuk pembukaan (menggunakan iftetapi akan lebih masuk akal untuk digunakan di elifsini karena dua kasus (baik (atau )) adalah satu-satunya yang dipertimbangkan. Membuat hanya satu perubahan ini akan menurunkan setiap iterasi (menggunakan string yang sangat panjang seperti pada kode C ++) dari 74,167 mikrodetik menjadi 72,444 mikrodetik.
Jangan perbarui nilai yang tidak berubah
Kode saat ini memiliki urutan ini:
for j in range(len(s)):
if j in closed:
cum_distance += 1
else:
cum_distance = 0
max_distance = max(max_distance, cum_distance)
Melihat sekilas kode akan memverifikasi bahwa max_distancehanya bisa mendapatkan nilai baru jika ifpernyataan itu benar, jadi mari kita pindahkan baris ke sana. Ini menurunkan waktu menjadi 71,680 mikrodetik.
Gunakan algoritma yang lebih cepat
Sekali lagi, apa yang berfungsi di versi C ++ juga berfungsi dengan Python. Berikut adalah versi algoritma Python di atas:
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
Kali ini, perbedaannya tidak terlalu dramatis, dan waktu untuk fungsi ini adalah 64,562 mikrodetik.