Open

Leetcode自分用解答メモ[Explore - Queue & Stack]

17

leetcodeを説いていて、自分の回答とかsolutionを読んで実装したやつとか詰まったとことかメモしとく

チャプターごとにスクラップで記録して、終わったらアーカイブする。

https://leetcode.com/explore/learn/card/queue-stack/228/first-in-first-out-data-structure/1337/

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()

https://leetcode.com/explore/learn/card/queue-stack/228/first-in-first-out-data-structure/1395/
tailを周回のたびにいちいち先頭へ戻すのではなく、tail = (tail + 1) % size;で計算できる
isFull()
 public boolean isFull() {
        return ((tail + 1) % size) == head;
    }

このようにかける。なるほど。

https://leetcode.com/explore/learn/card/queue-stack/228/first-in-first-out-data-structure/1368/
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型になってしまう。

https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1373/

マス目のボードで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のような比較が必要なくなる。

https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1374/

最初こんな感じで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)

https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1375/

鍵の暗証番号にたどり着くために目盛りをずらす最短回数を求める。引数として与えられた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
    }
}

https://leetcode.com/problems/open-the-lock/solution/

Time Complexity
O(N^2 ∗A^N +D)となる。

隣接する組み合わせの計算がN^2になるのが少し理解し難かったが、2Nの組み合わせごとに、stringをconstructするのにN時間かかるということらしい。

https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1371/

初見で解けず。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分木となみなし、割り切れる階層(深さ)が見つかるまで幅優先探索を繰り返す。

https://leetcode.com/explore/learn/card/queue-stack/230/usage-stack/1360/

最小値を取り出すメソッド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つに分ける方法なども感心したが省略。

https://leetcode.com/explore/learn/card/queue-stack/230/usage-stack/1361/

括弧の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
    }
}

https://leetcode.com/explore/learn/card/queue-stack/230/usage-stack/1363/

自力で解けずに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を挿入していけば良いところだった。前から逐次的に解を導いていくと思い込んでしまっていたのが敗因

https://leetcode.com/explore/learn/card/queue-stack/230/usage-stack/1394/

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
    }
}

https://leetcode.com/explore/learn/card/queue-stack/232/practical-application-stack/1380/

他の章でも見た問題。

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に変えていくというのがおしゃれと思った記憶

https://leetcode.com/explore/learn/card/queue-stack/232/practical-application-stack/1392/

グラフのコピー問題
最初の実装

/**
 * 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処理を実行してしまうのでこの場合使えない。

https://leetcode.com/explore/learn/card/queue-stack/232/practical-application-stack/1389/

ついさっきみていた問題とほぼ同じような問題でタイムリーだった

https://zenn.dev/nekoniki/scraps/f02a1c8d7ad3b3#comment-fae3fa971e5b60
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次元配列で行える。

https://leetcode.com/explore/learn/card/queue-stack/239/conclusion/1386/

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)となる。

償却計算量という概念が初めてだった。

https://www.madopro.net/entry/2016/06/28/184743

平均計算量に似た概念だが、連続して行なった場合という前提での一回の計算量、ということらしい。popの瞬間的な最悪計算量はO(n)だが、連続した場合の一回あたりはO(1)に収束する。なるほど。

https://leetcode.com/explore/learn/card/queue-stack/239/conclusion/1387/

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)の実装になってしまっていた

https://leetcode.com/explore/learn/card/queue-stack/239/conclusion/1379/

自分の実装(再帰)。結構時間かかってしまった。

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)
ログインするとコメントできます