This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.
105. Compare strings with backspace (backspace-string-compare)
The label
- The stack
- simple
The title
Leetcode portal
Let’s just open leetCode.
Given two strings S and T, when each is entered into a blank text editor, determine if the two are equal and return the result. # stands for backspace character.
Note: If you enter a backspace character for empty text, the text remains empty.
Input: S = "ab#c", T = "ad#c" output: true explanation: both S and T become "ac".Copy the codeInput: S = "ab##", T = "c#d#" output: trueCopy the codeBasic steps
Very simple, this problem can be solved by a stack, I think the following code is enough to explain the idea.
Writing implement
var backspaceCompare = function(s, t) {
const transStr = (str) = > {
let stack = []
str.split(' ').map(item= > {
if (item === The '#') {
stack.pop()
} else {
stack.push(item)
}
})
return stack.join(' ')}return transStr(s) === transStr(t)
};
let S = "ab#c", T = "ad#c"
console.log(backspaceCompare(S, T))
Copy the code106. Implementing queues with stacks (implement-queue-using-stacks)
The label
- Stack, queue,
- simple
The title
Leetcode portal
Let’s just open leetCode.
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) pushes element x to the end of the queue int pop() removes the element from the beginning of the queue and returns the element int peek() returns the element at the beginning of the queue Boolean empty() Returns true if the queue is empty; Otherwise, return false.
You can only use standard stack operations — that is, only push to Top, peek/ Pop from Top, size, and is empty are 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 implement queues with O(1) amortized time per operation? In other words, the total time complexity of performing n operations is O(n), even though one of them may take a long time.
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 codeThe basic idea
The problem sounds complicated, but it’s important to understand the problem, which is to use a double stack to simulate fifO in queues. The input stack and the output stack respectively handle the input and output, which are used to control the fifO, since the stack is first in and then out.
Writing implement
/** * Initialize your data structure here. */
var MyQueue = function() {
// Create two stacks to simulate
this.inStack = []
this.outStack = []
};
/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}* /
MyQueue.prototype.push = function(x) {
this.inStack.push(x)
};
/**
* Removes the element from in front of queue and returns that element.
* @return {number}* /
MyQueue.prototype.pop = function() {
// When the output stack is empty, the input stack element is pushed in
if ( this.outStack.length === 0) {
this.inStackToOutStack()
}
// output stack out of stack
return this.outStack.pop()
};
/**
* Get the front element.
* @return {number}* /
MyQueue.prototype.peek = function() {
if ( this.outStack.length === 0) {
this.inStackToOutStack()
}
// Get the top element of the stack, noting that the top is the last subscript position in the array
return this.outStack[this.outStack.length -1]};/**
* Returns whether the queue is empty.
* @return {boolean}* /
MyQueue.prototype.empty = function() {
return !this.inStack.length && !this.outStack.length
};
MyQueue.prototype.inStackToOutStack = function () {
while (this.inStack.length) {
this.outStack.push(this.inStack.pop())
}
}
/** * Your MyQueue object will be instantiated and called as such: * var obj = new MyQueue() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.peek() * var param_4 = obj.empty() * /
Copy the code107. Implementing queues (implement-stack-using-queues)
The label
- Stack, queue,
- simple
The title
Leetcode portal
Let’s just open leetCode.
You can implement a last in, first out (LIFO) stack with just two queues and support all four operations (push, top, POP, and Empty) of normal queues.
Implement MyStack class:
Void push(int x) pushes 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 true if the stack is empty; Otherwise, return false.
Note:
You can only use the basic operations of queues — namely push to Back, peek/ Pop from Front, size, and is empty. 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 codeThe basic idea
It may be easier to simulate a stack with a queue. When a push operation is performed, len of the current queue length is recorded and len of the current queue length is added to the queue. All the elements before the new elements are added to the queue are removed from the queue and then added to the queue.
Writing implement
var MyStack = function() {
this.queue = [];
};
/**
* Push element x onto stack.
* @param {number} x
* @return {void}* /
MyStack.prototype.push = function(x) {
// Record the current length
let len = this.queue.length;
this.queue.push(x);
for (let i = 0; i < len; i++) {
this.queue.push(this.queue.shift()); }};/**
* Removes the element on top of the stack and returns that element.
* @return {number}* /
MyStack.prototype.pop = function() {
return this.queue.shift();
};
/**
* Get the top element.
* @return {number}* /
MyStack.prototype.top = function() {
return this.queue[0];
};
/**
* Returns whether the stack is empty.
* @return {boolean}* /
MyStack.prototype.empty = function() {
return !this.queue.length;
};
/** * Your MyStack object will be instantiated and called as such: * var obj = new MyStack() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.top() * var param_4 = obj.empty() * /
Copy the codeIn addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series
If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions