Leetcode의 가장 긴 유효한 괄호
여기에 링크
저는 Python과 C ++로 된 솔루션을 포함 할 것이며 하나를 검토 할 수 있습니다. 저는 최근에 배우기 시작한 C ++ 코드를 검토하는 데 주로 관심이 있습니다. C ++를 모르는 사람들은 Python 코드를 검토 할 수 있습니다. 두 솔루션 모두 유사한 논리를 공유하므로 검토가 둘 중 하나에 적용됩니다.
문제 설명
'('및 ')'문자 만 포함 된 문자열이 주어지면 가장 긴 유효한 (잘 구성된) 괄호 하위 문자열의 길이를 찾습니다.
예 1 :
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
예 2 :
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
예 3 :
Input: s = ""
Output: 0
예 4 :
Input: s = "(()()()"
Output: 6
예 5 :
Input: s = "((())((((())))"
Output: 8
두 솔루션 모두 Oⁿ이며 시간 제한을 포함한 모든 테스트 케이스를 통과했지만 예상보다 시간이 더 걸리고 있습니다. 특히 C ++ 버전은 둘 다 동일한 논리를 공유하지만 더욱 그렇습니다. 우선적으로 시간을 개선해야합니다.
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(')((()()()()'))
통계 :
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(")()())");
}
통계 :
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.
답변
다음은 프로그램을 개선하는 데 도움이되는 몇 가지 사항입니다.
C ++ 버전
필요한 모든 #includes 사용
유형 std::vector<size_t>은 calculate_distance()헤더 파일 의 정의에 사용 되지만 #include <vector>포함 목록에서 누락되었습니다. 또한 std::max()사용되지만 파일 #include <algorithm>에서 누락되었습니다 .cpp.
인터페이스 최소화
이 .h파일은 소프트웨어 에 대한 인터페이스 선언입니다 . 이 인터페이스 .cpp의 구현 입니다. 인터페이스를 외부 프로그램에 필요한 것으로 최소화하는 것이 좋은 디자인 관행입니다. calculate_distance()따라서 헤더 에서 함수를 제거합니다 .
지역 기능 만들기 static
위에서 언급 한 것처럼 더 작은 인터페이스를 사용하면 calculate_distance함수가 .cpp파일 내에서만 사용되는 구현 세부 정보가 됩니다. static따라서 컴파일러가 함수를 인라인하는 것이 안전하다는 것을 알 수 있도록 만들어야합니다 .
switch일련의 if진술 보다는 사용
현재 코드에는 다음이 포함됩니다.
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);
}
}
다음과 같이 작성하면 조금 더 빠르고 읽기가 더 쉬울 것입니다.
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;
}
}
서명 된 것과 서명되지 않은 것에주의하십시오.
calculate_distance음수를 반환 하면 무엇을 의미 합니까? 아마도 현명한 해석이 없을 것이므로 그 이유 때문에 unsigned서명 된 int.
테스트 함수 작성
문제 설명에 테스트 입력을 제공했지만 기능을 실행하기 위해 전체 테스트 스크립트를 작성하는 것이 좋습니다. 이런 경우에는 테스트 개체를 사용하는 경향이 있습니다. 이 코드를 위해 작성한 코드는 다음과 같습니다.
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;
};
이제 몇 가지 테스트 벡터와 main루틴이 있습니다.
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;
}
}
정확성을 보장하고 시간을 측정하기 위해 스톱워치 템플릿을 사용했습니다 . 의 최종 버전은 main다음과 같습니다.
#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";
}
더 나은 알고리즘 사용
기존 코드는 그렇게 나쁘지는 않지만 가능한 한 효율적이지 않습니다. 위에 표시된 코드와 백만 번의 시도가있는 내 컴퓨터 get_longest()에서 가장 긴 테스트 입력에 대한 호출 당 5.66 마이크로 초가 걸리며 , 이는 집합의 마지막이기도합니다. 우리는 더 잘할 수 있습니다. 다음은를 사용 std::vector하여 시작 (되는 각 시작 을 추적 하지만 각 종료가 발생할 때 스팬 길이를 계산 하는 대체 루틴입니다 ). 내가 한 방법은 다음과 같습니다.
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;
}
여전히 개선의 여지가 있지만 이것이 작동하는 방법은 다음과 같습니다. 첫째, Span일치하는 각 괄호와 중첩 된 괄호 를 추적 합니다. 그래서 ()마찬가지로 같은 기간에 해당 될 것이다 (()). 코드는이 is_strictly_enclosing를 테스트하는 데 사용 합니다. 예를 들어에서 (())내부 쌍이 먼저 발견되고 범위가 {1,2}. 외부 쌍은 마지막으로 발견되며 범위는 {0,3}. 논리를 살펴보면이 코드가 무엇을 찾고 있는지 명확하게 알 수 있습니다.
bool is_strictly_enclosing(const Span& other) const {
return other.begin - begin == 1 &&
end - other.end == 1;
}
둘째, 매칭되지만, 비 - 중첩 괄호 경우가 ()()하거나 (())(). 여기서도 다음과 같은 멤버 함수를 사용합니다 Span.
bool is_contiguous_with(const Span& other) const {
return begin - other.end == 1;
}
이 코드를 사용하여 다음 타이밍 보고서를 얻습니다.
1000000 회 시도는 평균 0.562299 마이크로 초 / 시행 동안 562299 마이크로 초가 걸렸습니다.
따라서이 버전의 코드는 약 10 배 더 빠릅니다. 또한 이러한 문자열에 대한 ((*))보고 와 같은 잘못된 입력을 올바르게 처리 0합니다.
Python 버전
를 사용하여 elif상호 배타적 인 조건
오프닝에 대한 검사 (는 사용 if하지만 elif두 가지 경우 ( (또는 ))가 고려되는 유일한 경우이기 때문에 여기 에서 사용하는 것이 더 합리적 입니다. 이렇게 한 번만 변경하면 각 반복 (C ++ 코드에서와 동일한 매우 긴 문자열 사용)이 74.167 마이크로 초에서 72.444 마이크로 초로 감소합니다.
변경되지 않은 값은 업데이트하지 마십시오.
현재 코드에는 다음과 같은 순서가 있습니다.
for j in range(len(s)):
if j in closed:
cum_distance += 1
else:
cum_distance = 0
max_distance = max(max_distance, cum_distance)
코드를 간략히 살펴보면 문이 참일 max_distance때만 새 값을 얻을 수 있는지 확인할 수 if있으므로 행을 거기로 이동해 보겠습니다. 이렇게하면 시간이 71.680 마이크로 초로 떨어집니다.
더 빠른 알고리즘 사용
다시 한 번, C ++ 버전에서 작동하는 것은 Python에서도 작동합니다. 위의 알고리즘의 Python 버전은 다음과 같습니다.
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
이번에는 차이가 크지 않으며이 기능의 시간은 64.562 마이크로 초입니다.