LeetCode

LeetCode-方法论-stack

20, 1021, 1019, 155，921，

#20 valid parenthese

  • 问题描述

    对于string S，判断是否是合法的括号对儿。

    如：

    1
    2
    {[()]()}()  合法
    {()]       不合法

  • 思路

    遍历s：

    1. 如果s[i]是左括号“(”，“[”, “{”，则入栈stack.push(s[i])。

    2. 如果是右括号，如果栈为空，表示第一个就不合法，结束。否则，记录栈顶元素curr=stack.top()，后出栈顶元素stack.pop()。

    3. 根据匹配规则，得到curr应该是什么，用match表示。然后匹配：看实际curr是否与应该match相同。若相同，继续遍历，否则不合法，结束。

      关键：判断当前元素应该是什么，与实际是什么，是否一致。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    bool matchParenthese(string S){
           stack<char> stack;
           // 遍历每一个字符
           for(int i=0; i<S.size(); i++){
               // 如果是'(', 入栈
               if(S[i] == '(' || S[i] == '[' || S[i] == '{' )
                   stack.push(S[i]);
               // 如果是')'：
               else {
                   // 如果栈开始就为空，则不合法
                   if(stack.size() == 0) return false;
                   // 得到栈顶元素 “实际”是啥
                   char curr = stack.top();
                   stack.pop();
                   // 匹配原则 得到“应该”是啥
                   char match;
                   if (S[i] == ')') match = '(';
                   else if(S[i] == ']') match = '[';
                   else if(S[i] == '}') match = '{';
                       
                   // 这时才开始匹配 “实际”与“应该”一致否
                   if(curr != match) return false;
               }
           }
           if(stack.size() != 0) 
               return false;
           return true;
    }

这个问题是stack 的经典应用。

#1021 remove outermost parentheses

  • 问题描述

    括号对儿是和法的。对于输入，返回输出：

    1
    2
    3
    4
    5
    6
    7
    8
    Input: "(()())(())"
    Ouput: "()()()"
    Explanation: 
    The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
    After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

    Input: "()()"
    Output: ""

  • 思路

    1. 第一步，遍历S，将每一对儿最外层的括号的右括号的Index记录在arr中，（初始化的arr中有个-1）。例：

      1
      2
      S:     ( ( (  ) ) )  ( ( ) ( )  )
      index: 0 1 2  3 4 5  6 7 8 9 10 11

      根据描述，返回arr: [-1, 5, 11]。因为0~5是第一对儿最外层括号，6~11是第二对儿最外层括号。

    2. 第二步，对arr中的前n-1个元素，取arr[i]+2和arr[i+1]-1之间的 所有对应的S中的元素。结束。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    string removeOutermostParentheses(string S){
           vector<int> arr;
           arr.push_back(-1);
           // the 1st step
           stack<char> stack;
           for(int i=0;i<S.size(); i++){
               if(S[i] == '(')
                   stack.push(S[i]);
               else{
                   stack.pop();
                   // 当stack为空，表示一组匹配结束，记录结束的index
                   if(stack.size()==0)
                       arr.push_back(i);
               }
           }
           // the 2nd step
           string resS;
           for(int i=0; i<arr.size()-1; i++){
               int start = arr[i]+2;
               int end = arr[i+1]-1;
               if(start>=end) continue;
               // 将outermost括号内的所有内用append到resS中
               for(int j=start; j<=end; j++){
                   resS+=S[j];
               }
           }
           return resS;
    }

#1019 next greater nodes in linked list

  • 问题描述

    看下面这个例子：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Input: [2,7,4,3,5]
    Output: [7,0,5,5,0]

    解释：
    对于2，其后第一个比他大的是7
    对于7，气候第一个比他大的没有，0
    对于4，其后第一个比他大的是5
    对于3，其后第一个比他大的是5
    对于5，为最后一个元素，其后没有比他大的，0
    所以返回[7,0,5,5,0]

  • 思路

  • 实现

#155 Min Stack

  • 描述 

    1
    Design a stack that supports push(), pop(), top(), and retrieving the minimum element in constant time: getMin().

  • 逻辑
    在这个类中，使用两个stack。一个mystack正常工作，另一个min记录栈mystack目前的最小值，保证min中的栈顶元素是最小的，而且min从栈顶到栈底元素大小递增。比如min： 底|3|2|1 ... |顶。并且始终保持min的性质始终不变。

    特点：使用两个stack，一个正常工作，引入另一个使得整个stack类有了其他功能。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    class MinStack{
    private:
        stack<int> mystack;  // 提供stack正常的功能。
        stack<int> min;   // 记录最小值。
    public:
        MinStack(){};
        ~MinStack(){};

        void push(int x){
            mystack.push(x);
            // 只要待处理元素小于min的top元素，
            // min也要push进这个元素，
            // 保证min的top为当前mystack的最小值
            if(min.empty() || x<=min.top())
                min.push(x);
        }

        int top(){
            return mystack.top();   
        }

        int getMin(){
            return min.top();   
        }
        bool empty(){
            return mystack.empty();
        }

        // 当mystack.top() == min.top()时，两个stack都要pop()
        // 保证min的top为当前mystack的最小值。
        void pop(){
            if(mystack.top() == min.top())
                min.pop();
            mystack.pop();
        }
    };

#921 Minimum Add to Make Parentheses Valid

  • 描述

    添加最少的括号，使得括号字符串有效，例子：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Input: "())"
    Output: 1


    Input: "((("
    Output: 3


    Input: "()"
    Output: 0

  • 逻辑

    使用栈：

    遍历S，遇到'('入站，遇到')'出站，表示有一对是匹配的，并将记录匹配对数的count+1。遍历完后，只需要：S.length()-2*count。的结果。

    还可以不使用栈。其实栈的作用只是记录'('，所以可以只是用一个int变量来记录。如此空间复杂度从O(N)变为O(1)。

    所有思路中一定有一个是适用于所有情况的，所以如果一个思路中有很多情况不能满足，思路不对。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
       // use stack
       int minAddToMakeValid(string S){
    	stack<int> stack;
    	int count=0;
           for(int i=0;i<S.size(); i++){
               if(S[i] == '(')
                   stack.push(S[i]);

               else if(S[i] == ')'){
                   if(!stack.empty()){
                       stack.pop();
    				count++;
                   }   
               }
           }
           return S.length()-2*count;
    }
       // No stack
       int minAddToMakeValid(string S){
    	int left_p=0;
    	int count=0;
           for(int i=0;i<S.size(); i++){
               if(S[i] == '(')
                   left_p++;

               else if(S[i] == ')'){
                   if(left_p!=0){
                       left_p--;;
    				count++;
                   }   
               }
           }
           return S.length()-2*count;
    }