LeetCode 스 택, 대기 열, 우선 대기 열 테마 1: 스 택 과 대기 열 사용

이 부분 에서 우 리 는 '창고, 대열, 우선 대열' 을 소개 하기 시작 했다.스 택 과 대기 열 은 간단 한 데이터 구조 이지 만 이런 간단 한 데이터 구 조 를 사용 하여 해결 하 는 알고리즘 문제 가 반드시 간단 한 것 은 아니다.이 장 에서 우 리 는 앞으로 창고 와 대열 과 관련 된 알고리즘 문 제 를 탐색 할 것 이다.
스 택 과 대기 열의 사용, 스 택 과 대기 열 은 두 가지 기본 적 인 데이터 구조 입 니 다.Stack 이라는 기초 데이터 구조의 특징 은 후진 선 출 이라는 점 이 매우 중요 하 다 는 것 이다.다음은 LeetCode 20 번 문 제 를 보십시오.
예제: LeetCode 20 번 문제: 유효한 괄호
전송 문: 영문 주소: 20. Valid Parentheses, 중국어 주소: 20. 유효한 괄호.'(', ')', '{', '}', '[', ']' 만 포함 하 는 문자열 을 지정 하여 문자열 의 유효성 을 판단 합 니 다.
유효한 문자열 만족:

왼쪽 괄호 는 같은 유형의 오른쪽 괄호 로 닫 아야 한다.

왼쪽 괄호 는 반드시 정확 한 순서 로 닫 아야 한다.

빈 문자열 은 유효한 문자열 로 여 겨 질 수 있 습 니 다.
예시 1:

  : "()"
  : true

예시 2:

  : "()[]{}"
  : true

예시 3:

  : "(]"
  : false

예시 4:

  : "([)]"
  : false

예시 5:

  : "{[]}"
  : true

분석: 전형 적 인 응용, 괄호 일치 확인, 텍스트 편집기 에서 흔히 볼 수 있 는 기능 입 니 다.
빈 문자열 은 유효한 문자열 로 여 겨 질 수 있 습 니 다.
사고방식: 문제 자체 가 매우 쉽다.문자열 의 괄호 가 합 법 적 인지 판단 합 니 다.이 문자열 을 한 번 옮 겨 다 니 며 Stack 을 보조 공간 으로 사용 합 니 다.
일단 왼쪽 방향의 기 호 를 만나면 이 기 호 를 창고 에 밀어 넣 으 세 요.
오른쪽 방향의 기 호 를 만나면 창고 의 창고 꼭대기 요 소 를 창고 에서 꺼 내 면 일치 하 는 지 여 부 를 판단 해 야 한다.
Stack 에는 왼쪽 기호 만 저장 되 어 있 습 니 다: "{", "[", "("). 전체 방법 이 되 돌아 오기 전에 Stack 이 비어 있 는 지 여 부 를 판단 해 야 합 니 다. Stack 은 모두 왼쪽 괄호 로 되 어 있 을 수 있 기 때 문 입 니 다. 즉, 스 택 에 요소 가 있 는 경우 검 측 된 문자열 은 제목 에 부합 되 지 않 을 것 입 니 다.
나의 해답 (좀 번 거 로 워 보인다):
다음은 제 가 선생님 의 해법 에 따라 많은 해법 을 최적화 하지 않 은 것 을 썼 습 니 다.
Java 코드:

public class Solution {

    public boolean isValid(String s) {
        boolean isValid = false;
        Stack stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '{' || c == '(' || c == '[') {
                stack.push(c);
            }
            if (c == '}' || c == ')' || c == ']') {
                //     ，               
                if (stack.isEmpty()) {
                    return isValid;
                }
                Character popElement = stack.pop();
                Character match = null;
                if (c == '}') {
                    match = '{';
                }
                if (c == ']') {
                    match = '[';
                }
                if (c == ')') {
                    match = '(';
                }

                if (popElement != match) {
                    return isValid;
                }
            }
        }
        if (stack.isEmpty()) {
            isValid = true;
        }
        return isValid;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        boolean result = solution.isValid("8{90[s(d)f]44}33");
        System.out.println(result);
    }

}

설명: 마지막 단계:

if (stack.isEmpty()) {
    isValid = true;
}

무시 하기 쉬 우 니 유의 하 세 요.
스 택 을 배 울 때 전형 적 인 스 택 을 사용 하여 문 제 를 해결 하 는 것 도 배 웠 습 니 다. 우 리 는 왜 스 택 을 사용 하 는 지 생각해 야 합 니 다. 스 택 을 사용 하 는 이 유 는 포 함 된 관계 에서 스 택 꼭대기 요 소 를 통 해 가장 가 까 운 우리 가 처리 해 야 할 요 소 를 얻 을 수 있 습 니 다.
스 택 상단 요 소 는 포 함 된 계층 관계 에서 최근 에 일치 해 야 할 요 소 를 반영 합 니 다.
Python 코드:

# 20.      
#         '('，')'，'{'，'}'，'['，']'     ，         。
class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        d = ["()", "[]", "{}"]
        for i in range(0, len(s)):
            stack.append(s[i])
            if len(stack) >= 2 and stack[-2] + stack[-1] in d:
                stack.pop()
                stack.pop()
        return len(stack) == 0

연습 1: LeetCode 150 번 문제: 역 폴란드 식 값 구하 기
전송 문: 150. 역 폴란드 표현 식 값 구하 기.
역 폴란드 표현법 에 따라 표현 식 의 값 을 구하 세 요.
유효한 연산 자 는 +, -, *, / 를 포함한다. 각 연산 대상 은 정수 일 수도 있 고, 또 다른 역 폴란드 표현 식 일 수도 있다.
설명:

정수 나 누 기 는 정수 부분 만 보류한다.

역 폴란드 표현 식 을 지정 하 는 것 은 항상 유효 합 니 다. 다시 말 하면 표현 식 은 항상 유효 수 치 를 얻 을 수 있 고 0 으로 나 누 는 경 우 는 존재 하지 않 습 니 다.

예시 1:

  : ["2", "1", "+", "3", "*"]
  : 9
  : ((2 + 1) * 3) = 9

예시 2:

  : ["4", "13", "5", "/", "+"]
  : 6
  : (4 + (13 / 5)) = 6

예시 3:

  : ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
  : 22
  : 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Java 코드:

public class Solution {

    public int evalRPN(String[] tokens) {
        Stack stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String token = tokens[i];
            String pattern = "-?[0-9]+|[\\+\\-\\*/]";
            if (!token.matches(pattern)) {
                throw new RuntimeException("      ");
            }
            if (token.matches("-?[0-9]+")) {
                int num = Integer.valueOf(token);
                System.out.println(num);
                stack.push(num);
            }
            if (token.matches("[\\+\\-\\*/]")) {
                System.out.println("    " + token);
                if (stack.size() >= 2) {
                    int num1 = stack.pop();
                    int num2 = stack.pop();
                    int result = 0;
                    switch (token){
                        case "+":
                            result = num2 +num1;
                            break;
                        case "-":
                            result = num2 -num1;
                            break;
                        case "*":
                            result = num2 *num1;
                            break;
                        case "/":
                            result = num2 /num1;
                            break;
                    }
                    stack.push(result);
                }
            }
        }

        return stack.pop();
    }


    public static void main(String[] args) {
        String[] tokens = new String[]{"3", "-4", "+"};

        Solution solution = new Solution();
        int result = solution.evalRPN(tokens);
        System.out.println(result);
    }
}

문제 가 있 습 니 다: Time Limit Exceed. 그리고 저 는 위의 두 개의 System. out. println () 문 구 를 삭제 하면 A 가 지나 갑 니 다. 신기 하 니까 문 제 를 푸 는 것 은 규범 화 되 어야 합 니 다.
연습 2: LeetCode 71 번 문제: 경로 간소화
전송 문: 71. 경 로 를 간소화 합 니 다.
유 닉 스 스타일 로 파일 의 절대 경 로 를 보 여 줍 니 다. 간소화 하거나 규범 화 된 경로 로 바 꿔 야 합 니 다.
유 닉 스 스타일 의 파일 시스템 에서 한 점 . 은 현재 디 렉 터 리 자 체 를 표시 합 니 다. 또한 두 점 .. 은 디 렉 터 리 를 이전 단계 (부모 디 렉 터 리 지향) 로 전환 하 는 것 을 표시 합 니 다. 둘 다 복잡 한 상대 경로 의 구성 부분 일 수 있 습 니 다. 더 많은 정 보 는 Linux / 유 닉 스 의 절대 경로 vs 상대 경로 참조 하 십시오.
돌아 오 는 규범 경 로 는 항상 슬 래 쉬 / 로 시작 해 야 하 며, 두 디 렉 터 리 이름 사이 에는 슬 래 쉬 / 만 있어 야 합 니 다. 마지막 디 렉 터 리 이름 (존재 한다 면) 은 / 으로 끝 날 수 없습니다. 또한 규범 경 로 는 절대 경 로 를 나타 내 는 가장 짧 은 문자열 이 어야 합 니 다.
예시 1:

  ："/home/"
  ："/home"
  ：  ，             。

예시 2:

  ："/../"
  ："/"
  ：             ，             。

예시 3:

  ："/home//foo/"
  ："/home/foo"
  ：      ，               。

예시 4:

  ："/a/./b/../../c/"
  ："/c"

예시 5:

  ："/a/../../b/../c//.//"
  ："/c"

예시 6:

  ："/a//b////c/d//././/.."
  ："/a/b/c"

다음 과 같은 글 을 참고 하 였 습 니 다.http://blog.csdn.net/u012249528/article/details/46705867
Java 코드 구현:

public class Solution {

    public String simplifyPath(String path) {
        String result = "";
        String[] pathList = path.split("/");
        if (pathList.length == 0) {
            return "/";
        }

        Stack stack = new Stack<>();
        for (String p : pathList) {
            if ("".equals(p) || ".".equals(p)) {
                continue;
            }
            if ("..".equals(p)) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else { //             ，  
                stack.push(p);
            }
        }


        //          
        while (!stack.isEmpty()) {
            result = "/" + stack.pop() + result;
        }
        if ("".equals(result)) {
            result = "/";
        }
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        String path1 = "/home/";
        String result1 = solution.simplifyPath(path1);
        System.out.println(result1);


        String path2 = "/a/./b/../../c/";
        String result2 = solution.simplifyPath(path2);
        System.out.println(result2);


        String path3 = "/..";
        String result3 = solution.simplifyPath(path3);
        System.out.println(result3);

        String path4 = "/..";
        String result4 = solution.simplifyPath(path4);
        System.out.println(result4);

        String path5 = "/abc/def/.";
        String result5 = solution.simplifyPath(path5);
        System.out.println(result5);
    }
}

(이 절 완료)