leetcode 의 회전 효과 적 인 괄호 문제 시리즈

오늘 의 leetcode 는 매일 1111 문제 입 니 다. 유효한 괄호 의 깊이 입 니 다.제목 을 보지 않 고 제목 만 보면 우 리 는 몇 가지 문 제 를 풀 수 있다.1. 유효한 괄호 는 무엇 입 니까?2 유효한 괄호 는 어떻게 끼 워 넣 습 니까?괄호 류 문 제 는 대부분 학생 들 이 스 택 이라는 데이터 구 조 를 공부 할 때 했 을 것 이다.본 고 는 뜯 어 낸 두 문제 에 따라 괄호 문 제 를 시리즈 로 해석 하고 자 한다.
유효한 괄호
'(', ')', '{', '}', '[', ']' 만 포함 하 는 문자열 을 지정 하여 문자열 이 올 바른 지 판단 합 니 다.
유효한 문자열 만족:
왼쪽 괄호 는 같은 유형의 오른쪽 괄호 로 닫 아야 합 니 다.왼쪽 괄호 는 반드시 정확 한 순서 로 닫 아야 한다.빈 문자열 은 유효한 문자열 로 여 겨 질 수 있 습 니 다.
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/valid-parentheses 저작권 은 인터넷 에 귀속 된다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
문제 풀이 의 사고 방향.
앞에서 도 말씀 드 렸 듯 이 데이터 구조 스 택 을 공부 할 때 부대 예 제 는 유효 괄호 입 니 다.스 택 구 조 를 사용 할 때 매번 열 리 는 기 호 를 만 날 때마다 (, [, {시 스 택 에 직접 들 어가 고 닫 힌 기 호 를 만 났 을 때, 즉),} 스 택 꼭대기 요 소 를 비교 합 니 다.

닫 힌 기 호 를 만 났 을 때 스 택 에 요소 가 없 으 면 효과 적 인 괄호 가 아 닙 니 다.

닫 힌 기 호 를 만 났 을 때 스 택 상단 요소 가 일치 하지 않 으 면 유효 괄호 가 아 닙 니 다.

그래서 기 호 를 창고 에 넣 고 창고 에서 나 오 는 작업 만 합 니 다.

Go 버 전 코드
시간 복잡 도: O (n) 공간 복잡 도: O (n) 실행 시: 0 ms 메모리 소모: 2 MB

func isValid(s string) bool {
//                      
	if s=="" {
        return true
    }
    if s[0]==')' || s[0]==']' ||s[0]=='}' {
        return false
    }
    var c []byte//     
    symbol := map[byte]byte{
        ')' : '(',
        ']' : '[',
        '}' : '{',
    }
    for _,value := range s {
        clen := len(c)
        if clen>0 {
            if _,ok := symbol[byte(value)];ok {
                if c[clen-1]==symbol[byte(value)] {
                    c = c[:clen-1]//  
                    continue
                }
            }
        }
        c = append(c,byte(value))//  
    }
    return len(c)==0
}

유효한 괄호 깊이
유효한 괄호 문자열 은 "(" 와 ")" 로 만 구성 되 며 다음 과 같은 몇 가지 조건 중 하나 에 부합 합 니 다.
빈 문자열 연결 은 AB (A 와 B 연결) 로 기록 할 수 있 습 니 다. 그 중에서 A 와 B 는 모두 유효한 괄호 문자열 로 구성 되 어 있 습 니 다. (A) 로 기록 할 수 있 습 니 다. 그 중에서 A 는 유효한 괄호 문자열 과 유사 합 니 다. 우 리 는 임의의 유효한 괄호 문자열 s 의 깊이 depth (S) 를 정의 할 수 있 습 니 다.
s 가 비어 있 을 때 depth (") = 0 s 가 A 와 B 로 연 결 될 때 depth (A + B) = max (depth (A), depth (B). 그 중에서 A 와 B 는 모두 유효한 괄호 문자열 s 가 포 함 된 상황 이 고 depth (" + A + ") = 1 + depth (A) 이다. 그 중에서 A 는 유효한 괄호 문자열 이다. 예 를 들 어", "()", "() () () () () ()") "는 모두 유효한 괄호 문자열 이 고 포 함 된 깊이 는 각각 0, 1, 2 이 며") "(") ")" 이다."()" 와 모두 유효한 괄호 문자열 이 아 닙 니 다.
유효한 괄호 문자열 seq 를 드 립 니 다. 교차 하지 않 는 두 개의 하위 서열 A 와 B 로 나 누고 A 와 B 는 유효한 괄호 문자열 의 정 의 를 만족 시 킵 니 다 (주의: A. length + B. length = seq. length).
현재, 그 중에서 유효한 괄호 문자열 A 와 B 를 선택 하여 max (depth (A), depth (B) 의 가능 한 값 을 최소 화해 야 합 니 다.
반환 길 이 는 seq. length 답 배열 answer 입 니 다. A 또는 B 를 선택 하 는 인 코딩 규칙 은: seq [i] 가 A 의 일부분 이 라면 answer [i] = 0 입 니 다. 그렇지 않 으 면 answer [i] = 1 입 니 다. 여러 개의 요 구 를 만족 시 키 는 답 이 존재 하 더 라 도 하나만 되 돌려 주 십시오. 예제 1:

  ：seq = "(()())"
  ：[0,1,1,1,1,0]

예시 2:

  ：seq = "()(())()"
  ：[0,0,0,1,1,0,1,1]

알림:

1 <= text.size <= 10000

출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings 저작권 은 리베이트 네트워크 의 소유 입 니 다. 상업 전 재 는 정부 에 연락 하여 권한 을 부여 하 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
문제 풀이 의 사고 방향.
효과 적 인 괄호 문제 의 밑받침 이 있 을 것 이 라 고 믿 습 니 다. 여러분 들 은 문 제 를 빨리 읽 을 수 있 을 것 입 니 다. 효과 적 인 괄호 를 바탕 으로 본 문 제 는 깊이 를 더 하 는 조건 을 추 가 했 습 니 다. 스 택 이라는 문제 풀이 방식 을 제외 하고 공식 문 제 는 규칙 적 인 해법 을 찾 아 보 는 것 도 우수 하 니 추천 합 니 다.
창고 로 문 제 를 풀다
다음 그림 은 공식 문제 풀이 에서 찾 아 온 것 입 니 다. 본 문 제 는 유효한 괄호 열 을 두 개의 유효한 괄호 열 로 나 누고 max (depth (A), depth (B) 의 가능 한 값 을 최소 화 하려 고 하기 때 문 입 니 다. 즉, 두 개의 문자열 의 끼 워 넣 기 깊이 를 가능 한 한 같 게 하려 는 것 입 니 다.
사고방식 은 삽입 깊이 를 반 으로 나 누고 A 열 은 삽입 깊이 를 홀수 로 차지 하 며 B 열 은 삽입 깊이 를 짝수 로 차지한다.

       ( ( ) ( ( ) ) ( ) )
       0 1 2 3 4 5 6 7 8 9
       1 2 2 2 3 3 2 2 2 1 

  ：LeetCode-Solution
  ：https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/solution/you-xiao-gua-hao-de-qian-tao-shen-du-by-leetcode-s/
  ：  （LeetCode）
        。             ，          。

시간 복잡 도: O (n) 공간 복잡 도: O (1) 실행 시: 0 ms 메모리 소모: 3.7 MB

func maxDepthAfterSplit(seq string) []int {
    var ans []int//         
    d := 0//    
    for _,v := range seq {
        if v == '(' {
            d += 1
            ans = append(ans, 1-d%2)
        } 
        if v == ')' {
            ans = append(ans, 1-d%2)
            d -= 1
        } 
    }
    return ans
}

규칙 적 인 방법 을 찾 아 문 제 를 풀다.

       ( ( ) ( ( ) ) ( ) )
       0 1 2 3 4 5 6 7 8 9
       1 2 2 2 3 3 2 2 2 1 

아니면 이 그림?

왼쪽 괄호 (아래 표 시 된 번 호 는 끼 워 넣 은 깊이 의 패 리 티 와 반대

오른쪽 괄호) 의 아래 표 시 된 번 호 는 끼 워 넣 은 깊이 의 패 리 티 와 같 습 니 다

정책 은:

아래 표 시 된 번 호 는 홀수 입 니 다. (그 내장 깊이 는 짝수 이 고 B 에 게 분 배 됩 니 다.

아래 표 시 된 번 호 는 짝수 (, 끼 워 넣 은 깊이 는 홀수 로 A 에 게 분 배 됩 니 다.

아래 표 시 된 번 호 는 홀수 입 니 다. 그 내장 깊이 는 홀수 이 고 A 에 게 분 배 됩 니 다.

아래 표 시 된 번 호 는 짝수 입 니 다. 그 내장 깊이 는 짝수 이 고 B 에 게 분 배 됩 니 다.

규칙 증명:
임의의 왼쪽 괄호 에 대해 서 는 X 로 표시 되 어 있 으 며, 앞 에 있 는 왼쪽 괄호 는 L 개 이 고, 앞 에 있 는 오른쪽 괄호 는 R 개가 있다.

  
X = L+R   //     0  
    Y 
Y = L-R+1

L + R 과 L - R 패 리 티 가 같 기 때문에 아래 표 시 는 깊이 Y 패 리 티 와 반대 입 니 다. 오른쪽 괄호 의 아래 표 시 는 깊이 패 리 티 와 같 음 을 증명 할 수 있 습 니 다.
시간 복잡 도: O (n) 공간 복잡 도: O (1) 실행 시: 0 ms 메모리 소모: 3.7 MB

func maxDepthAfterSplit(seq string) []int {
    var ans []int
    
    for k,v := range seq {
        if v == '(' {
            ans = append(ans, k%2)
        } else {
            ans = append(ans, 1-k%2)
        }
    }
    return ans
}

총결산
유효한 괄호 의 두 문 제 를 풀 면 프로 그래 밍 에서 모듈 화 된 사상 이 있 습 니 다. 유효한 괄호 의 판정 을 하나의 모듈 로 바 꾸 고 깊이 라 는 새로운 장면 이 있 을 때 모듈 + 새로운 장면 의 판단 을 재 활용 하면 됩 니 다.