20. Valid brackets

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

A valid string must meet the following requirements:

  1. An open parenthesis must be closed with a close parenthesis of the same type.
  2. The left parentheses must be closed in the correct order.

 

Example 1:

Input: s = "()" output: trueCopy the code

Example 2:

Input: s = "()[]{}" Output: trueCopy the code

Example 3:

Input: s = "(]" Output: falseCopy the code

Example 4:

Input: s = "([)]" Output: falseCopy the code

Example 5:

Input: s = "{[]}" Output: trueCopy the code

 

Tip:

  • 1 <= s.length <= 104
  • sOnly by brackets'[] {} ()'composition


            // when an open parenthesis is encountered, the corresponding close parenthesis is pushed onto the stack
          
           // Check if it matches the top element
     
        // Check whether the stack elements match

Copy the code

1047. Remove all adjacent duplicates from a string

Given a string S consisting of lowercase letters, the deduplication operation selects two adjacent and identical letters and deletes them.

The deduplication operation is repeated on S until the deletion cannot continue.

Returns the final string after all deduplication operations have been completed. The answer is guaranteed to be unique.

 

Example:

Input: "abbaca" Output: "ca" Explanation: For example, in "abbaca", we can delete "bb" because the two letters are adjacent and identical, this is the only duplicate item that can be deleted at this time. Then we get the string "aaca", where only "aa" can be deduplicated, so the final string is "ca".Copy the code

 

Tip:

  1. 1 <= S.length <= 20000
  2. SContains only lowercase English letters.

        // use res as a stack
       
        // top is the length of res
      
            // If top > 0, if the current character is equal to the character in the stack, pop the top character, and top--
           
            // otherwise, push the character to the stack and top++
     


Copy the code

150. Evaluation of inverse Pollan expressions

Evaluate the expression according to the inverse Polish notation.

Valid operators include +, -, *, and /. Each operand can be an integer or another inverse Polish expression.

 

Description:

  • Integer division preserves only integer parts.
  • Given the inverse Polish expression is always valid. In other words, the expression always yields a valid value and never has a divisor of 0.

 

Example 1:

Input: tokens = [" 2 ", "1", "+", "3", "*"] output: 9: the formula into common infix arithmetic expression is: ((2 + 1) * 3) = 9Copy the code

Example 2:

Input: tokens = "4", "13", "5", "/", "+"] output: 6: this formula into common infix arithmetic expression is: (4 +) = 6 (13/5)Copy the code

Example 3:

Input: tokens = [" 10 ", "6", "9", "3", "+", "11", "*", "/", "*", "17", "+", "5", "+"] output: 22 explanation: this formula into common infix arithmetic expression is: ((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 = 22Copy the code

 

Tip:

  • 1 <= tokens.length <= 104
  • tokens[i]Or an operator ("+","-","*" 或 "/"), or one in the range[- 200, 200]The integer

 

Inverse Polish expression:

An inverse Polish expression is an expression with a suffix, which means the operator is written after it.

  • The commonly used formula is an infix expression, such as1 plus 2 times 3 plus 4. 。
  • The inverse Polish expression of the formula is written as(1 2 +) (3 4 +) *) 。

The inverse Polish expression has two main advantages:

  • After removing the parentheses, the expression is unambiguous, even if the above formula is written1, 2, plus 3, 4, plus starThe correct result can also be calculated according to the order.
  • Suitable for stack operation: the number is pushed into the stack; When encountering an operator, the top two numbers on the stack are calculated and the result is pushed onto the stack.
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:}}}return stack.pop();
    }

Copy the code

232. Implement queues with stacks

You can implement a first-in, first-out queue using only two stacks. Queues should support all the operations that queues normally support (push, POP, peek, empty) :

Implement MyQueue class:

  • void push(int x)Push element X to the end of the queue
  • int pop()Removes and returns elements from the beginning of the queue
  • int peek()Returns the element at the beginning of the queue
  • boolean empty()If the queue is empty, returntrue; Otherwise, returnfalse

 

Description:

  • You can only use standard stack operations — that is, onlypush to top.peek/pop from top.size, andis emptyThe operation is legal.
  • Your language may not support stacks. You can use a list or a deque to simulate a stack, as long as it’s standard stack operations.

 

Advanced:

  • Can you achieve amortized time for each operationO(1)The queue? In other words, executenThe total time complexity of the operation isO(n), even though one of the operations may take a long time.

 

Example:

Input: [" MyQueue ", "push" and "push" and "peek", "pop", "empty"] [[], [1], [2], [], [], []] output: [null, null, null, 1, 1, false] MyQueue MyQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return falseCopy the code

 

Tip:

  • 1 <= x <= 9
  • Most call100 次 push,pop,peek 和 empty
  • Assume that all operations are valid (for example, an empty queue is not calledpoporpeekOperation)
class MyQueue {

  

    /** Initialize your data structure here. */
        // Take charge of the loading
        // Take charge of pushing the stack
    
    
    /** Push element x to the back of queue. */
 
    
    /** Removes the element from in front of queue and returns that element. */
    
    
    /** Get the front element. */
    
    
    /** Returns whether the queue is empty. */
   

    // If stack2 is empty, put all elements in Stack1 into Stack2
    
}

/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); * /

Copy the code

225. Implement stacks with queues

You can implement a last in, first out (LIFO) stack with just two queues and support all four operations of a normal stack (push, top, POP, and Empty).

Implement MyStack class:

  • void push(int x)Push element X to the top of the stack.
  • int pop()Removes and returns the top element of the stack.
  • int top()Returns the top element of the stack.
  • boolean empty()Returns if the stack is emptytrue; Otherwise, returnfalse 。

 

Note:

  • You can only use the basic operations of the queue — i.epush to back,peek/pop from front,size 和 is emptyThese operations.
  • Your language may not support queues. You can use a list or a deque to simulate a queue, as long as it’s standard queue operations.

 

Example:

Input: [" MyStack ", "push" and "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] output: [null, null, null, 2, 2, false] MyStack MyStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // Return 2 mystack.pop (); // Return 2 mystack.empty (); / / returns FalseCopy the code

 

Tip:

  • 1 <= x <= 9
  • Most call100 次 push,pop,top 和 empty
  • Each callpop 和 topMake sure the stack is not empty

 

Advanced: Can you implement a stack with O(1) amortized time for each operation? In other words, the total time complexity of performing n operations is O(n), even though one of them may take longer than the others. You can use more than two queues.


class MyStack {

     // Keep the same elements in the stack queue
     // Secondary queue

    /** Initialize your data structure here. */
   
    
    /** Push element x onto stack. */
  
          // Put it in the secondary queue first
          // Finally swap queue1 and queue2, placing all elements in Queue1
    }
    
    /** Removes the element on top of the stack and returns that element. */
     // Since the elements in Queue1 are the same as those in the stack, this and the following operations only look at Queue1
    
    
    /** Get the top element. */
   
    
    /** Returns whether the stack is empty. */
    
}

Copy the code

Maximum sliding window value

Given an integer array numS, there is a sliding window of size K ** that moves from the leftmost of the array to the rightmost of the array. You can only see k numbers in the sliding window. The sliding window moves only one bit to the right at a time.

Returns the maximum value in the sliding window.

 

Example 1:

Input: nums = [1, 3, 1, 3,5,3,6,7], k = 3 output:,3,5,5,6,7 [3] : The position of the sliding window Maximum -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- [1] 3-1-3 3 5 6 7 3 1 [3-1-3] 3 5 6 7 3 1 3 [1-3-5] 3 6 7 5 3-1/3-3 5 6 7 5 1 3 1-3 [5 3 6] 7 6 1 3 1-3 5 [3 6 7] 7Copy the code

Example 2:

Input: nums = [1], k = 1Copy the code

Example 3:

Input: nums = [1,-1], k = 1Copy the code

Example 4:

Input: nums = [9,11], k = 2 output: [11]Copy the code

Example 5:

Input: nums = [4,-2], k = 2 output: [4]Copy the code

 

Tip:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length


class Solution {
    
        // The array position that holds the maximum value of the current window ensures that the array position in the queue is sorted from largest to smallest
        
        // Result array
         
     
            If the first number is small, pop it one by one until it meets the requirement
             
            // Add the array subscript to the current value
            
            // Check whether the current queue head value is valid
            
            // Save the maximum value of the current window when the window length is k
         
}

Copy the code