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:
- An open parenthesis must be closed with a close parenthesis of the same type.
- 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
s
Only 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 <= S.length <= 20000
S
Contains 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 as
1 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 written
1, 2, plus 3, 4, plus star
The 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 queueint pop()
Removes and returns elements from the beginning of the queueint peek()
Returns the element at the beginning of the queueboolean empty()
If the queue is empty, returntrue
; Otherwise, returnfalse
Description:
- You can only use standard stack operations — that is, only
push to top
.peek/pop from top
.size
, andis empty
The 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 operation
O(1)
The queue? In other words, executen
The 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 call
100
次push
,pop
,peek
和empty
- Assume that all operations are valid (for example, an empty queue is not called
pop
orpeek
Operation)
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.e
push to back
,peek/pop from front
,size
和is empty
These 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 call
100
次push
,pop
,top
和empty
- Each call
pop
和top
Make 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