抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

09 | 面试题:用队列实现栈&用栈实现队列

课程中提到的一个时间/算法复杂度的统计表

https://www.bigocheatsheet.com/

前置知识:栈:FILO 先入后出。队列:FIFO 先入先出

232. 用栈实现队列

解决办法:使用两个栈,一个输入栈,一个输出栈。规则:

  1. 先全部进入输入栈(先进入的在输入栈栈顶),输出时,先从输入栈一个个 pop 岀来进入输出栈(先进入的在输出栈栈顶)。接着从输出栈输出即可。
  2. 新加入元素时,需要先判断输出栈是否为空,不为空则先从输出栈输出,为空则重复步骤1。
class MyQueue() {

/** Initialize your data structure here. */
val inS = Stack<Int>()
val outS = Stack<Int>()

/** Push element x to the back of queue. */
fun push(x: Int) {
inS.push(x)
}

/** Removes the element from in front of queue and returns that element. */
fun pop(): Int {
if (outS.isNotEmpty()) {
return outS.pop()
}
while (inS.isNotEmpty()) {
outS.push(inS.pop())
}
return outS.pop()
}

/** Get the front element. */
fun peek(): Int {
if (outS.isNotEmpty()) {
return outS.peek()
}
while (inS.isNotEmpty()) {
outS.push(inS.pop())
}
return outS.peek()
}

/** Returns whether the queue is empty. */
fun empty(): Boolean {
return outS.empty() && inS.empty()
}

}

225. 用队列实现栈

解决方法一:使用双端队列,一个就可以。(头进头出)

class MyStack() {

/** Initialize your data structure here. */
val deque = LinkedList<Int>()

/** Push element x onto stack. */
fun push(x: Int) {
deque.push(x)
}

/** Removes the element on top of the stack and returns that element. */
fun pop(): Int {
return deque.removeFirst()
}

/** Get the top element. */
fun top(): Int {
return deque.peekFirst()
}

/** Returns whether the stack is empty. */
fun empty(): Boolean {
return deque.isEmpty()
}

}

解决方法二:使用单端队列(Jvm系 都是一个类),步骤:

  1. push 时:每次入队都需要循环调整,比如入队 1,2;循环调整 2,1;入队3,循环调整3,2,1。每次需要移动size-1 个元素。
  2. pop 时:尾出即可,
  3. top 时:使用 peek()即可
class MyStack() {

/** Initialize your data structure here. */
val deque = LinkedList<Int>()

/** Push element x onto stack. */
fun push(x: Int) {
deque.push(x)
for (i in 0 until deque.size - 1) {
deque.push(deque.removeLast())
}
}

/** Removes the element on top of the stack and returns that element. */
fun pop(): Int {
return deque.removeLast()
}

/** Get the top element. */
fun top(): Int {
return deque.peekLast()
}

/** Returns whether the stack is empty. */
fun empty(): Boolean {
return deque.isEmpty()
}

}

20. 有效的括号

解决方案一:使用栈进行匹配判断,规则如下:

  1. 如果是左括号,则入栈。
  2. 如果是右括号,则判断栈顶元素是否与其匹配。匹配则弹出栈顶元素,不匹配则直接无效。( Tips:匹配时可使用 map 进行键值配对)
  3. 全部匹配完成后,判断栈是否为空,不为空则无效。

Kotlin 代码:

class SomeSolution {
fun isValid(s: String): Boolean {
//optimization
if (s.length % 2 != 0) return false

val chars = s.toCharArray()
val stack = Stack<Char>()
val map = mapOf('(' to ')', '{' to '}', '[' to ']')
chars.forEach {
if (map.containsKey(it)) {
stack.push(it)
} else {
if (stack.isEmpty()) return false
if (map[stack.peek()] != it) {
return false
} else {
stack.pop()
}
}
}
return stack.isEmpty()
}
}

解决方案二:开心消消乐(效率低,不推荐)

class Solution {
fun isValid(s: String): Boolean {
var str = s
if (s.length % 2 != 0) return false
while (str.contains("()") || str.contains("{}") || str.contains("[]")) {
str = str.replace("()", "").replace("{}", "").replace("[]", "")
}
return str.isEmpty()
}
}


0条评论

发表评论