Closed21
Leetcode自分用解答メモ[Explore - Queue & Stack]
リアルにサーモンleetcodeを説いていて、自分の回答とかsolutionを読んで実装したやつとか詰まったとことかメモしとく
チャプターごとにスクラップで記録して、終わったらアーカイブする。
リアルにサーモン
Circular Queueを実装する。
自分の実装
class MyCircularQueue(_k: Int) {
val arr = new Array[Int](_k)
var sI = -1
var eI = -1
def enQueue(value: Int): Boolean = {
if (isFull()) return false
if (eI + 1 < _k) {
arr(eI + 1) = value
eI += 1
}
else {
arr(0) = value
eI = 0
}
if (sI == -1) sI = 0
true
}
def deQueue(): Boolean = {
if (isEmpty()) return false
if (sI == eI) {
sI = -1
eI = -1
} else {
if (sI + 1 < _k) sI += 1
else sI = 0
}
true
}
def Front(): Int = {
if (isEmpty()) return -1
arr(sI)
}
def Rear(): Int = {
if (isEmpty()) return -1
arr(eI)
}
def isEmpty(): Boolean = {
if (sI == -1 && eI == -1) true
else false
}
def isFull(): Boolean = {
if (sI < eI) {
if (sI == 0 && eI == _k - 1) return true
}
if (eI < sI) {
if (sI - 1 == eI) return true
}
if (sI == eI && _k == 1) return true
false
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* var obj = new MyCircularQueue(k)
* var param_1 = obj.enQueue(value)
* var param_2 = obj.deQueue()
* var param_3 = obj.Front()
* var param_4 = obj.Rear()
* var param_5 = obj.isEmpty()
* var param_6 = obj.isFull()
tailを周回のたびにいちいち先頭へ戻すのではなく、tail = (tail + 1) % size;で計算できる
isFull()も
public boolean isFull() {
return ((tail + 1) % size) == head;
}
このようにかける。なるほど。
リアルにサーモン
class MovingAverage(_size: Int) {
/** Initialize your data structure here. */
val queue = scala.collection.mutable.Queue[Double]()
var sum: Double = 0
def next(`val`: Int): Double = {
if (_size <= queue.size) {
val t = queue.dequeue
sum -= t
}
queue.enqueue(`val`)
sum += `val`.toDouble
sum / queue.size
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* var obj = new MovingAverage(size)
* var param_1 = obj.next(`val`)
明示的にDouble型を指定しないと、商などは勝手に切り捨てられてInt型になってしまう。
リアルにサーモン
マス目のボードでgateからの最短距離を計算してセットする。
自分の実装
object Solution {
def wallsAndGates(rooms: Array[Array[Int]]): Unit = {
var visited = Array.empty[(Int, Int)]
val queue = scala.collection.mutable.Queue[(Int, Int)]()
def isVisited(r: Int, c: Int): Boolean = {
visited.exists(v => v._1 == r && v._2 == c)
}
def shouldUpdate(rr: Int, cc: Int): Boolean = {
if (rr < 0 || rooms.length <= rr || cc < 0 || rooms(rr).length <= cc) return false
if (isVisited(rr,cc)) return false
if (rooms(rr)(cc) == -1 || rooms(rr)(cc) == 0) return false
true
}
for (r <- 0 until rooms.length) {
val row = rooms(r)
for (c <- 0 until row.length) {
val root = row(c)
// gateだったら操作する
if (root == 0) {
queue.enqueue((r, c))
var d = 0
while (queue.nonEmpty) {
val size = queue.size
for (s <- 0 until size) {
val cur = queue.dequeue
visited :+= (cur)
rooms(cur._1)(cur._2) = List(rooms(cur._1)(cur._2), d).min
// 訪れておらず、かつ
// 範囲内であり、
// gateでもwallでもない
if (shouldUpdate(cur._1 - 1, cur._2)) queue.enqueue((cur._1 - 1, cur._2))
if (shouldUpdate(cur._1 + 1, cur._2)) queue.enqueue((cur._1 + 1, cur._2))
if (shouldUpdate(cur._1, cur._2 - 1)) queue.enqueue((cur._1, cur._2 - 1))
if (shouldUpdate(cur._1, cur._2 + 1)) queue.enqueue((cur._1, cur._2 + 1))
}
d += 1
}
}
// 初期化
visited = Array.empty[(Int, Int)]
queue.clear
}
}
}
}
各マス目をforで巡り、gateだった場合はそこから幅優先探索をして距離を更新する。
結構時間かかった。
Solutionを読んで
上の回答だと、gateの数×mn分の時間かかってしまう
最初にすべてのgateをqueueに投入し、1回キューから取り出すごとに周囲の隣接している点のみ更新していくことで、各マス目に1度ずつ訪れるようにすれば、 1×mnの時間で事足りる。
List(rooms(cur._1)(cur._2), d).minのような比較が必要なくなる。
リアルにサーモン
最初こんな感じでsubmitしたら、TimeLimit ErrorやMemory Errorになってしまっていた。
object Solution {
def numIslands(grid: Array[Array[Char]]): Int = {
var counter = 0
val visited = scala.collection.mutable.Set[Point]()
val queue = scala.collection.mutable.Queue[Point]()
val m = grid.length
val n = grid(0).length
def shouldEnqueue(p: Point): Boolean = {
if (p.m < 0 || m <= p.m || p.n < 0 || n <= p.n) return false
if (visited.contains(p)) return false
if (grid(p.m)(p.n).toString != "1") return false
true
}
def toLeft(p: Point) = Point(p.m - 1, p.n)
def toUp(p: Point) = Point(p.m, p.n - 1)
def toRight(p: Point) = Point(p.m + 1, p.n)
def toBottom(p: Point) = Point(p.m, p.n + 1)
for (y <- 0 until m) {
for (x <- 0 until n) {
val p = Point(y, x)
if (shouldEnqueue(p)) {
counter += 1
queue.enqueue(p)
while (queue.nonEmpty) {
val targetPoint = queue.dequeue
visited += targetPoint
if (shouldEnqueue(toLeft(targetPoint))) queue.enqueue(toLeft(targetPoint))
if (shouldEnqueue(toUp(targetPoint))) queue.enqueue(toUp(targetPoint))
if (shouldEnqueue(toRight(targetPoint))) queue.enqueue(toRight(targetPoint))
if (shouldEnqueue(toBottom(targetPoint))) queue.enqueue(toBottom(targetPoint))
}
}
}
}
counter
}
}
case class Point(m: Int, n: Int)
queueから取り出す際にvisitedに追加するのでは、一度訪れた場所を重複して巡回してしまうのが原因だった。enqueueの時点でvisitedの印をつけておく必要があった。。
object Solution {
def numIslands(grid: Array[Array[Char]]): Int = {
var counter = 0
val visited = scala.collection.mutable.Set[Point]()
val queue = scala.collection.mutable.Queue[Point]()
val m = grid.length
val n = grid(0).length
def shouldEnqueue(p: Point): Boolean = {
if (p.m < 0 || m <= p.m || p.n < 0 || n <= p.n) return false
if (visited.contains(p)) return false
if (grid(p.m)(p.n).toString != "1") return false
true
}
def toLeft(p: Point) = Point(p.m - 1, p.n)
def toUp(p: Point) = Point(p.m, p.n - 1)
def toRight(p: Point) = Point(p.m + 1, p.n)
def toBottom(p: Point) = Point(p.m, p.n + 1)
for (y <- 0 until m) {
for (x <- 0 until n) {
val p = Point(y, x)
if (shouldEnqueue(p)) {
counter += 1
queue.enqueue(p)
visited += p
while (queue.nonEmpty) {
val targetPoint = queue.dequeue
if (shouldEnqueue(toLeft(targetPoint))) {
queue.enqueue(toLeft(targetPoint))
visited += toLeft(targetPoint)
}
if (shouldEnqueue(toUp(targetPoint))) {
queue.enqueue(toUp(targetPoint))
visited += toUp(targetPoint)
}
if (shouldEnqueue(toRight(targetPoint))) {
queue.enqueue(toRight(targetPoint))
visited += toRight(targetPoint)
}
if (shouldEnqueue(toBottom(targetPoint))) {
queue.enqueue(toBottom(targetPoint))
visited += toBottom(targetPoint)
}
}
}
}
}
counter
}
}
case class Point(m: Int, n: Int)
鍵の暗証番号にたどり着くために目盛りをずらす最短回数を求める。引数として与えられたdeadendsに含まれる組み合わせは通ることができない。
自分で解法を思いつけず、Solutionのさわりを読む。各数字の組み合わせをグラフとしてみて、幅優先探索を用いて最短距離を求める。なるほど。。ということで実装
object Solution {
def openLock(deadends: Array[String], target: String): Int = {
val visited = scala.collection.mutable.Set[String]()
val queue = scala.collection.mutable.Queue[String]()
var mtn = 0
var ans = -1
def shouldEnqueue(t: String): Boolean = {
if (deadends.contains(t)) return false
if (visited.contains(t)) return false
true
}
def enqueueAround(l: String) = {
val splitted = l.split("")
var t = turnUp(splitted(0).toInt).toString + splitted(1) + splitted(2) + splitted(3)
if (shouldEnqueue(t)) {
queue.enqueue(t)
visited += t
}
t = turnDown(splitted(0).toInt).toString + splitted(1) + splitted(2) + splitted(3)
if (shouldEnqueue(t)) {
queue.enqueue(t)
visited += t
}
t = splitted(0) + turnUp(splitted(1).toInt).toString + splitted(2) + splitted(3)
if (shouldEnqueue(t)) {
queue.enqueue(t)
visited += t
}
t = splitted(0) + turnDown(splitted(1).toInt).toString + splitted(2) + splitted(3)
if (shouldEnqueue(t)) {
queue.enqueue(t)
visited += t
}
t = splitted(0) + splitted(1) + turnUp(splitted(2).toInt).toString + splitted(3)
if (shouldEnqueue(t)) {
queue.enqueue(t)
visited += t
}
t = splitted(0) + splitted(1) + turnDown(splitted(2).toInt).toString + splitted(3)
if (shouldEnqueue(t)) {
queue.enqueue(t)
visited += t
}
t = splitted(0) + splitted(1) + splitted(2) + turnUp(splitted(3).toInt).toString
if (shouldEnqueue(t)) {
queue.enqueue(t)
visited += t
}
t = splitted(0) + splitted(1) + splitted(2) + turnDown(splitted(3).toInt).toString
if (shouldEnqueue(t)) {
queue.enqueue(t)
visited += t
}
}
if (shouldEnqueue("0000")) queue.enqueue("0000")
while (queue.nonEmpty && ans == -1) {
val size = queue.size
for (x <- 0 until size) {
val lock = queue.dequeue
if (lock == target) ans = mtn
enqueueAround(lock)
}
mtn += 1
}
ans
}
def turnUp(i: Int): Int = {
if (i == 9) return 0
i + 1
}
def turnDown(i: Int): Int = {
if (i == 0) return 9
i - 1
}
}
Time Complexity
O(N^2 ∗A^N +D)となる。
隣接する組み合わせの計算がN^2になるのが少し理解し難かったが、2Nの組み合わせごとに、stringをconstructするのにN時間かかるということらしい。
リアルにサーモン
初見で解けず。Solutionを見ると最初はDPでの解法が紹介されていたのでとりあえず実装してみる。
Approach 2: Dynamic Programming
object Solution {
def numSquares(n: Int): Int = {
val squares = new Array[Int](scala.math.floor(scala.math.sqrt(n)).toInt)
for (x <- 1 to scala.math.floor(scala.math.sqrt(n)).toInt) {
squares(x - 1) = scala.math.pow(x.toInt, 2).toInt
}
val dp = new Array[Int](n + 1)
dp(0) = 0
def getMin(i: Int): Int = {
if (squares.contains(i)) return 1
var minV = Int.MaxValue
squares.filter(s => s < i).foreach(s => {
minV = List(dp(i - s) + 1, minV).min
})
minV
}
for (x <- 1 to n) {
dp(x) = getMin(x)
}
dp(n)
}
}
Approach 3: Greedy Enumeration
object Solution {
def numSquares(n: Int): Int = {
val squares = new Array[Int](scala.math.floor(scala.math.sqrt(n)).toInt)
for (x <- 1 to scala.math.floor(scala.math.sqrt(n)).toInt) {
squares(x - 1) = scala.math.pow(x.toInt, 2).toInt
}
def isDividedBy(v: Int, d: Int): Boolean = {
if (d == 1) return squares.contains(v)
squares.filter(_ < v).foreach(s => {
if (isDividedBy(v - s, d - 1)) return true
})
false
}
for (x <- 1 to n) if (isDividedBy(n, x)) return x
n
}
}
greedy algorithm(貪欲法)という用語が初見だった。Wikiによると
動的計画法と異なり保持する状態は常に一つであり、一度選択した要素を再考する事は無い。
とのことらしい。
Approach 4: Greedy + BFS (Breadth-First Search)
object Solution {
def numSquares(n: Int): Int = {
val squares = new Array[Int](scala.math.floor(scala.math.sqrt(n)).toInt)
for (x <- 1 to scala.math.floor(scala.math.sqrt(n)).toInt) {
squares(x - 1) = scala.math.pow(x.toInt, 2).toInt
}
var queue = scala.collection.mutable.Queue[Int]()
queue.enqueue(n)
var count = 0
var isFound = false
while (queue.nonEmpty && !isFound) {
count += 1
val size = queue.size
val nextQ = scala.collection.mutable.Queue[Int]()
for (x <- 0 until size) {
val v = queue.dequeue
if (squares.contains(v)) isFound = true
else squares.filter(_ < v).foreach(s => nextQ.enqueue(v - s))
}
queue = nextQ.distinct
}
count
}
}
さらに、やっと出てきたQueue & BFS。
approach 3のコールスタックの構造をN分木となみなし、割り切れる階層(深さ)が見つかるまで幅優先探索を繰り返す。
リアルにサーモン
最小値を取り出すメソッドgetMin()の実装付きのスタックの実装
最初の実装
class MinStack() {
/** initialize your data structure here. */
val data: Array[Int] = new Array[Int](10000)
var i = -1
def push(x: Int) {
i += 1
data(i) = x
}
def pop() {
i -= 1
}
def top(): Int = {
data(i)
}
def getMin(): Int = {
data.slice(0, i + 1).toList.min
}
}
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
よく考えず、こういう時arrayのサイズ固定でいいのかなーなんて思いながら実装してテストに通ってしまったが、Solutionを見た所そういうことではなかったらしい。getMin()はO(1)で行える必要がある。
Approach 1: Stack of Value/ Minimum Pairs
class MinStack() {
/** initialize your data structure here. */
val stack = scala.collection.mutable.Stack[(Int, Int)]()
def push(x: Int) {
stack.push((x, List(stack.headOption.getOrElse((Int.MaxValue, Int.MaxValue))._2, x).min))
}
def pop() {
stack.pop
}
def top(): Int = {
stack.head._1
}
def getMin(): Int = {
stack.head._2
}
}
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
こういうことだった。他stackを2つに分ける方法なども感心したが省略。
リアルにサーモン
括弧のvalid / invalidの判定。まさにStackという感じ。
object Solution {
def isValid(s: String): Boolean = {
val stack = scala.collection.mutable.Stack[String]()
s.split("").foreach(ss => {
if (ss == "(" || ss == "[" || ss == "{") stack.push(ss)
else {
if (stack.nonEmpty &&
(ss == ")" && stack.head == "("
|| ss == "]" && stack.head == "["
|| ss == "}" && stack.head == "{")) stack.pop
else stack.push(ss)
}
})
stack.isEmpty
}
}
自力で解けずにSolutionを見て実装。
object Solution {
def dailyTemperatures(T: Array[Int]): Array[Int] = {
val stack = scala.collection.mutable.Stack[Int]()
val output = new Array[Int](T.length)
for (x <- 0 until T.length) {
while (stack.nonEmpty && T(stack.head) < T(x)) {
val i = stack.pop
output(i) = (x - i)
}
stack.push(x)
}
output
}
}
inputと同じサイズの配列を用意して、indexごとにansを挿入していけば良いところだった。前から逐次的に解を導いていくと思い込んでしまっていたのが敗因
リアルにサーモン
Stackそのまま、みたいな問題
最初の実装
object Solution {
def evalRPN(tokens: Array[String]): Int = {
val stack = scala.collection.mutable.Stack[Int]()
tokens.foreach(t => {
t match {
case "+" => stack.push(stack.pop + stack.pop)
case "-" => stack.push(-stack.pop + stack.pop)
case "*" => stack.push(stack.pop * stack.pop)
case "/" => {
val v1 = stack.pop
val v2 = stack.pop
stack.push((v2 / v1).toInt)
}
case x => stack.push(x.toInt)
}
})
stack.pop
}
}
他の章でも見た問題。
object Solution {
def numIslands(grid: Array[Array[Char]]): Int = {
def dfs(p: Point): Unit = {
grid(p.m)(p.n) = 0.toChar
if (0 < p.m && grid(p.m - 1)(p.n).toString == "1") dfs(Point(p.m - 1, p.n))
if (p.m < grid.length - 1 && grid(p.m + 1)(p.n).toString == "1") dfs(Point(p.m + 1, p.n))
if (0 < p.n && grid(p.m)(p.n - 1).toString == "1") dfs(Point(p.m, p.n - 1))
if (p.n < grid(0).length - 1 && grid(p.m)(p.n + 1).toString == "1") dfs(Point(p.m, p.n + 1))
}
var count = 0
for (y <- 0 until grid.length) {
for (x <- 0 until grid(0).length) {
if (grid(y)(x).toString == "1") {
dfs(Point(y, x))
count += 1
}
}
}
count
}
}
case class Point(m: Int, n: Int)
visitedを使ってもいいが、訪問した点は0に変えていくというのがおしゃれと思った記憶
リアルにサーモン
グラフのコピー問題
最初の実装
/**
* Definition for a Node.
* class Node(var _value: Int) {
* var value: Int = _value
* var neighbors: List[Node] = List()
* }
*/
object Solution {
def cloneGraph(graph: Node): Node = {
if (graph == null) return null
val cache = collection.mutable.Map[Int, Node]()
def dfs(root: Node): Node = {
cache.get(root.value) match {
case Some(result) => result
case None => {
val node = new Node(root.value)
cache += (root.value -> node)
node.neighbors = root.neighbors.map(dfs(_))
node
}
}
}
dfs(graph)
}
}
dfsで解きはしたが、Stackを使うのがピンと来ず普通に再帰で。
-> と思ったらSolutionも同じだった。再帰を使うとプログラムの内部的にはStackを使ってますよ~的なことを前の章で書いてあったなそういえば。
scalaのmapのメソッドでgetOrElseUpdate()というのがあってぴったり使えそうだが、mapに追加する前にupdate処理を実行してしまうのでこの場合使えない。
リアルにサーモン
ついさっきみていた問題とほぼ同じような問題でタイムリーだった
object Solution {
def findTargetSumWays(nums: Array[Int], S: Int): Int = {
var counter = 0
def dfs(acc: Int, d: Array[Int]): Unit = {
if (d.isEmpty) {
if (acc == S) counter += 1
} else {
dfs(acc + d(0), d.drop(1))
dfs(acc - d(0), d.drop(1))
}
}
dfs(0, nums)
counter
}
}
ただ、Solutionを見た所これは強引なやり方でアルゴリズムとしてはあまり良くないらしい。O(2^n)
Approach 2: Recursion with Memoization
object Solution {
def findTargetSumWays(nums: Array[Int], S: Int): Int = {
val memo = Array.fill[Array[Int]](nums.length)(Array.fill[Int](2001)(Int.MinValue))
def dfs(sum: Int, d: Array[Int]): Int = {
if (d.isEmpty) {
if (sum == S) return 1
0
} else {
if (memo(nums.length - d.length)(sum + 1000) != Int.MinValue) return memo(nums.length - d.length)(sum + 1000)
val add = dfs(sum + d(0), d.drop(1))
val subtract = dfs(sum - d(0), d.drop(1))
memo(nums.length - d.length)(sum + 1000) = add + subtract
memo(nums.length - d.length)(sum + 1000)
}
}
dfs(0, nums)
}
}
メモ化。最初の実装では+と-の順序が入れ替わっただけで同じ計算を冗長に行なっているので、すでに計算した値をキャッシュしておき計算を省略する。
確かに早くなってる。
Approach 3: 2D Dynamic Programming
object Solution {
def findTargetSumWays(nums: Array[Int], S: Int): Int = {
val dp = Array.fill[Array[Int]](nums.length)(Array.fill[Int](2001)(0))
dp(0)(nums(0) + 1000) = 1
dp(0)(1000 - nums(0)) += 1
for (x <- 1 until nums.length) {
for (y <- -1000 to 1000) {
if (dp(x - 1)(y + 1000) != 0) {
dp(x)(y + nums(x) + 1000) += dp(x - 1)(y + 1000)
dp(x)(y - nums(x) + 1000) += dp(x - 1)(y + 1000)
}
}
}
if (S < 1001) dp(nums.length - 1)(S + 1000) else 0
}
}
2次元配列を使ったDPで解く。
組み合わせに使う数を1から一つずつ増やしていき、その前の数で算出された値を加算していく。
Approach 4: 1D Dynamic Programming
object Solution {
def findTargetSumWays(nums: Array[Int], S: Int): Int = {
var dp = Array.fill[Int](2001)(0)
dp(nums(0) + 1000) = 1
dp(1000 - nums(0)) += 1
for (x <- 1 until nums.length) {
val next = Array.fill[Int](2001)(0)
for (y <- -1000 to 1000) {
if (dp(y + 1000) != 0) {
next(y + nums(x) + 1000) += dp(y + 1000)
next(y - nums(x) + 1000) += dp(y + 1000)
}
}
dp = next
}
if (S < 1001) dp(S + 1000) else 0
}
}
今回のdpで必要なのは一つ前の値のみなので、1次元配列で行える。
リアルにサーモン
stackを2つだけ使ってqueueのデータ構造を作る。最初の実装。
class MyQueue() {
/** Initialize your data structure here. */
val stack1 = scala.collection.mutable.Stack[Int]()
val stack2 = scala.collection.mutable.Stack[Int]()
/** Push element x to the back of queue. */
def push(x: Int) {
if (stack1.nonEmpty) {
while (stack1.nonEmpty) stack2.push(stack1.pop)
stack1.push(x)
while (stack2.nonEmpty) stack1.push(stack2.pop)
} else stack1.push(x)
}
/** Removes the element from in front of queue and returns that element. */
def pop(): Int = {
stack1.pop
}
/** Get the front element. */
def peek(): Int = {
stack1.head
}
/** Returns whether the queue is empty. */
def empty(): Boolean = {
stack1.isEmpty
}
}
/**
* 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()
Approach #2 (Two Stacks) Push - O(1)O(1) per operation, Pop - Amortized O(1)O(1) per operation.
class MyQueue() {
/** Initialize your data structure here. */
val stack1 = scala.collection.mutable.Stack[Int]()
val stack2 = scala.collection.mutable.Stack[Int]()
var front = Int.MinValue
/** Push element x to the back of queue. */
def push(x: Int) {
if (stack1.isEmpty) front = x
stack1.push(x)
}
/** Removes the element from in front of queue and returns that element. */
def pop(): Int = {
if (stack2.isEmpty) while (stack1.nonEmpty) stack2.push(stack1.pop)
stack2.pop
}
/** Get the front element. */
def peek(): Int = {
if (stack2.nonEmpty) stack2.head else front
}
/** Returns whether the queue is empty. */
def empty(): Boolean = {
stack1.isEmpty && stack2.isEmpty
}
}
/**
* 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()
一つめの実装ではpushの計算量がO(n)となるが、こちらはpushがO(1)、popの償却計算量がO(1)となる。
償却計算量という概念が初めてだった。
平均計算量に似た概念だが、連続して行なった場合という前提での一回の計算量、ということらしい。popの瞬間的な最悪計算量はO(n)だが、連続した場合の一回あたりはO(1)に収束する。なるほど。
リアルにサーモン
Queueを使ってStackを実装
class MyStack() {
/** Initialize your data structure here. */
var front = Int.MinValue
val q1 = scala.collection.mutable.Queue[Int]()
val q2 = scala.collection.mutable.Queue[Int]()
val q3 = scala.collection.mutable.Queue[Int]()
var top_ = Int.MinValue
/** Push element x onto stack. */
def push(x: Int) {
q1.enqueue(x)
top_ = x
}
/** Removes the element on top of the stack and returns that element. */
def pop(): Int = {
if (q2.isEmpty && q3.isEmpty) {
while (q1.nonEmpty) {
if (q2.isEmpty) {
q2.enqueue(q1.dequeue)
while (q3.nonEmpty) q2.enqueue(q3.dequeue)
} else {
q3.enqueue(q1.dequeue)
while (q2.nonEmpty) q3.enqueue(q2.dequeue)
}
}
}
if (q2.nonEmpty) q2.dequeue else q3.dequeue
}
/** Get the top element. */
def top(): Int = {
if (q2.nonEmpty) return q2.head
if (q3.nonEmpty) return q3.head
top_
}
/** Returns whether the stack is empty. */
def empty(): Boolean = {
q1.isEmpty && q2.isEmpty && q3.isEmpty
}
}
/**
* 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()
*/
Follow-up: Can you implement the stack such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer. You can use more than two queues.
とあったのでそれを目指して書いてみたがSolutionにamortized O(1) time complexityの解答がなく合っているのか不明
-> O(N^2)または amortized O(N)の実装になってしまっていた
リアルにサーモン
自分の実装(再帰)。結構時間かかってしまった。
object Solution {
def decodeString(s: String): String = {
var ans = ""
var tmp = ""
var digit = ""
var brcCount = 0
val splitted = s.split("")
for (x <- 0 until splitted.length) {
val ch = splitted(x)
if (brcCount != 0) {
if (ch == "[") brcCount += 1
if (ch == "]") brcCount -= 1
if (brcCount == 0) {
val result = decodeString(tmp)
for (y <- 0 until digit.toInt) ans += result
digit = ""
tmp = ""
} else tmp += ch
} else {
if (ch.head.isDigit) digit += ch
else if (ch == "[") brcCount += 1
else ans += ch
}
}
ans
}
}
case class Bracket(digit: Int, idx: Int)
最初の実装
object Solution {
def floodFill(image: Array[Array[Int]], sr: Int, sc: Int, newColor: Int): Array[Array[Int]] = {
val i = image(sr)(sc)
if (i == newColor) return image
def loop(sR: Int, sC: Int): Unit = {
image(sR)(sC) = newColor
if (0 < sR && image(sR - 1)(sC) == i) loop(sR - 1, sC)
if (sR < image.length - 1 && image(sR + 1)(sC) == i) loop(sR + 1, sC)
if (0 < sC && image(sR)(sC - 1) == i) loop(sR, sC - 1)
if (sC < image(0).length - 1 && image(sR)(sC + 1) == i) loop(sR, sC + 1)
}
loop(sr, sc)
image
}
}
Solutionもdfsで似たようなものだったので次
リアルにサーモン
0,1のマトリクスをもっとも近くにある0からの距離で置き換える。
最初の実装。
object Solution {
def updateMatrix(matrix: Array[Array[Int]]): Array[Array[Int]] = {
val queue = scala.collection.mutable.Queue[Point]()
for (y <- 0 until matrix.length) {
for (x <- 0 until matrix(0).length) {
val point = Point(y, x)
if (matrix(point.r)(point.c) != 0) {
queue.enqueue(point)
var counter = 0
while (queue.nonEmpty) {
val size = queue.size
for (i <- 0 until size) {
if (queue.nonEmpty) {
val tp = queue.dequeue
if (matrix(tp.r)(tp.c) == 0) {
matrix(point.r)(point.c) = counter
queue.clear
} else {
if (0 < tp.r) queue.enqueue(Point(tp.r - 1, tp.c))
if (tp.r < matrix.length - 1) queue.enqueue(Point(tp.r + 1, tp.c))
if (0 < tp.c) queue.enqueue(Point(tp.r, tp.c - 1))
if (tp.c < matrix(0).length - 1) queue.enqueue(Point(tp.r, tp.c + 1))
}
}
}
counter += 1
}
}
}
}
matrix
}
}
case class Point(r: Int, c: Int)
各地点ごとに幅優先探索で求める。
が、これは同じ地点を重複して回るのでよくなさそう?(SubmissionのTimeを見ると特に遅くはないのだが)
Approach #2 Using BFS [Accepted]
Solutionで示されているBFSを使った方法。
object Solution {
def updateMatrix(matrix: Array[Array[Int]]): Array[Array[Int]] = {
val queue = scala.collection.mutable.Queue[Point]()
val dist = Array.ofDim[Int](matrix.length, matrix(0).length)
for (y <- 0 until matrix.length) {
for (x <- 0 until matrix(0).length) {
if (matrix(y)(x) == 0) {
queue.enqueue(Point(y, x))
} else {
dist(y)(x) = -1
}
}
}
while (queue.nonEmpty) {
val tp = queue.dequeue
val curD = dist(tp.r)(tp.c)
if (0 < tp.r && dist(tp.r - 1)(tp.c) == -1) {
dist(tp.r - 1)(tp.c) = curD + 1
queue.enqueue(Point(tp.r - 1, tp.c))
}
if (tp.r < dist.length - 1 && dist(tp.r + 1)(tp.c) == -1) {
dist(tp.r + 1)(tp.c) = curD + 1
queue.enqueue(Point(tp.r + 1, tp.c))
}
if (0 < tp.c && dist(tp.r)(tp.c - 1) == -1) {
dist(tp.r)(tp.c - 1) = curD + 1
queue.enqueue(Point(tp.r, tp.c - 1))
}
if (tp.c < dist(0).length - 1 && dist(tp.r)(tp.c + 1) == -1) {
dist(tp.r)(tp.c + 1) = curD + 1
queue.enqueue(Point(tp.r, tp.c + 1))
}
}
dist
}
}
case class Point(r: Int, c: Int)
最初に0の地点だけqueueに入れ、queueから取り出すたびに隣接地点を確認し未訪問だったら1を足して距離をセットする。全ての地点を1回しか訪れずO(r * c)で解ける。
Approach #3 DP Approach [Accepted]
object Solution {
def updateMatrix(matrix: Array[Array[Int]]): Array[Array[Int]] = {
val dist = Array.ofDim[Int](matrix.length, matrix(0).length)
for (y <- 0 until matrix.length) {
for (x <- 0 until matrix(0).length) {
dist(y)(x) = Int.MaxValue - 20
}
}
for (y <- 0 until matrix.length) {
for (x <- 0 until matrix(0).length) {
if (matrix(y)(x) == 0) dist(y)(x) = 0
else {
if (0 < y) dist(y)(x) = List(dist(y)(x), dist(y - 1)(x) + 1).min
if (0 < x) dist(y)(x) = List(dist(y)(x), dist(y)(x - 1) + 1).min
}
}
}
for (y <- matrix.length - 1 to 0 by -1) {
for (x <- matrix(0).length - 1 to 0 by -1) {
if (matrix(y)(x) == 0) dist(y)(x) = 0
else {
if (y < matrix.length - 1) dist(y)(x) = List(dist(y)(x), dist(y + 1)(x) + 1).min
if (x < matrix(0).length - 1) dist(y)(x) = List(dist(y)(x), dist(y)(x + 1) + 1).min
}
}
}
dist
}
}
case class Point(r: Int, c: Int)
DPを使った解法。
左上からだけでなく、その後右下からも巡回することで4方向を考慮してDPで解けるというのは単純ながらなるほどと思った。
リアルにサーモン
dfsで。
object Solution {
def canVisitAllRooms(rooms: List[List[Int]]): Boolean = {
val visited = collection.mutable.Set[Int]()
def dfs(r: Int): Unit = {
if (!visited.contains(r)) {
visited += r
rooms(r).foreach(key => if (!visited.contains(key)) dfs(key))
}
}
dfs(0)
for (x <- 0 until rooms.length) if (!visited.contains(x)) return false
true
}
}
Queue & Stackの章は完了したのでclose
このスクラップは2021/03/03にクローズされました