Open31

Leetcode自分用解答メモ[October LeetCoding Challenge 2021]

https://leetcode.com/problems/longest-common-subsequence/

2つの文字列から、最長のsubsequenceを抜き出す。

Approach 2: Improved Memoization

object Solution {
    def longestCommonSubsequence(text1: String, text2: String): Int = {
        val memo = scala.collection.mutable.Map[(Int, Int), Int]()
        
        def loop(i1: Int, i2: Int): Int = {
            if (text1.length <= i1 || text2.length <= i2) return 0
            
            if (memo.contains((i1, i2))) return memo((i1, i2))
            
            var answer = 0
            if (text1.charAt(i1) == text2.charAt(i2)) {
                answer = 1 + loop(i1 + 1, i2 + 1)
            } else {
                answer = loop(i1 + 1, i2).max(loop(i1, i2 + 1))
            }
            
            memo((i1, i2)) = answer
            memo((i1, i2))
        }
        
        loop(0, 0)
    }
}

メモ化と再帰の実装、最初、再帰関数に渡す引数をString型としていちいちsliceして渡していくやり方だとメモリオーバーしてしまった。
各文字列を比べ、双方の最初の文字列が一致する場合とそれ以外で分岐して対処する。

Approach 4: Dynamic Programming with Space Optimization

object Solution {
    def longestCommonSubsequence(text1: String, text2: String): Int = {
        var prev = new Array[Int](text1.length + 1)
        
        for (i <- text2.length - 1 to 0 by -1) {
            val c = text2.charAt(i)
            
            val cur = new Array[Int](text1.length + 1)
            for (j <- text1.length - 1 to 0 by -1) {
                
                if (text1.charAt(j) == c) {
                    cur(j) = prev(j + 1) + 1
                } else {
                    cur(j) = cur(j + 1).max(prev(j))
                }
            }

            prev = cur
        }

        prev(0)
    }
}

動的計画法でイテレーションで実装する場合

https://leetcode.com/problems/dungeon-game/
object Solution {
    def calculateMinimumHP(dungeon: Array[Array[Int]]): Int = {
        val m = dungeon.length
        val n = dungeon(0).length
        val pq = scala.collection.mutable.PriorityQueue[Path]()(Ordering.by((_: Path).minHp))
        pq.enqueue(Path(Room(0, 0), dungeon(0)(0), dungeon(0)(0)))
        
        while (pq.nonEmpty) {
            val path = pq.dequeue
            val curRow = path.room.row
            val curCol = path.room.col
            
            if (curRow == m - 1 && curCol == n - 1) {
                if (0 < path.minHp) return 1
                else return -1 * path.minHp + 1
            }
            
            if (curRow < m - 1) {
                val curHp = path.curHp + dungeon(curRow + 1)(curCol)
                val minHp = path.minHp.min(curHp)
                pq.enqueue(Path(Room(curRow + 1, curCol), curHp, minHp))
            }
            
            if (curCol < n - 1) {
                val curHp2 = path.curHp + dungeon(curRow)(curCol + 1)
                val minHp2 = path.minHp.min(curHp2)
                pq.enqueue(Path(Room(curRow, curCol + 1), curHp2, minHp2))
            }
        }
        
        -1
    }
}

case class Room(row: Int, col: Int)
case class Path(room: Room, curHp: Int, minHp: Int)

ヒープを使いつつ素直な感じで実装してみたが、TLE

Approach 1: Dynamic Programming

object Solution {
    def calculateMinimumHP(dungeon: Array[Array[Int]]): Int = {
        val m = dungeon.length
        val n = dungeon(0).length
        val dp = new Array[Array[Int]](m)
        for (i <- 0 until m) dp(i) = new Array[Int](n)
        
        dp(m - 1)(n - 1) = if (0 < dungeon(m - 1)(n - 1)) 1 else -1 * dungeon(m - 1)(n - 1) + 1
        
        for (r <- m - 1 to 0 by -1) {
            for (c <- n - 1 to 0 by -1) {
                if (!(r == m - 1 && c == n - 1)) {
                    var hp = Int.MaxValue
                    if (r < m - 1) {
                        val add = dp(r + 1)(c) - dungeon(r)(c)
                        if (0 < add) hp = hp.min(add)
                        else hp = hp.min(1)
                    }
                    if (c < n - 1) {
                        val add = dp(r)(c + 1) - dungeon(r)(c)
                        if (0 < add) hp = hp.min(add)
                        else hp = hp.min(1)
                    }
                    dp(r)(c) = hp
                }
            }
        }
        
        dp(0)(0)
    }
}

右下の目的地から始めることで、動的計画法で解くことができる。
そのマス目に到達する上で保持しておかなければならないhpを保存していく。
そのマス目の右と下のマス目のdpの値と、そのマス目の変化の値からそのマス目に到達する時点で保持していなければならないhpが求まっていく。

逆順のDPによる解法のケースは多々あるので引き出しに持っておきたい

https://leetcode.com/problems/jump-game/

数字の配列が与えられ、その数字分右にジャンプできるという制約下で最初から最後まで辿り着けるかの判定。

object Solution {
    def canJump(nums: Array[Int]): Boolean = {
        val memo = scala.collection.mutable.Map[Int, Boolean]()
        val N = nums.length
        def dfs(i: Int): Boolean = {
            if (memo.contains(i)) return memo(i)
            if (N <= i) return false
            if (i == N - 1) return true
            val num = nums(i)
            if (num == 0) return false
            for (j <- 1 to num) {
                val next = i + j
                if (dfs(next)) return true
            }
            memo(i) = false
            memo(i)
        }
        
        dfs(0)
    }
}

メモ化を伴うDFSで5000ms以上かかったが一応Accepted

Approach 2: Dynamic Programming Top-down

object Solution {
    def canJump(nums: Array[Int]): Boolean = {
        val N = nums.length
        val dp = new Array[Boolean](N)
        dp(0) = true
        for (i <- 0 until N) {
            if (dp(i)) {
                for (j <- 1 to nums(i)) {
                    if (i + j < N) dp(i + j) = true
                }
            }
        }
        dp(N - 1)
    }
}

SolutionのApproach 2: Dynamic Programming Top-downというタイトルだけを見て実装、解説と一致しているかはわからないが、O(n^2)の解法にはなっている

Approach 4: Greedy

object Solution {
    def canJump(nums: Array[Int]): Boolean = {
        val N = nums.length
        var leftPos = N - 1
        for (i <- nums.length - 2 to 0 by -1) {
            val idx = (N - 1).min(i + nums(i))
            if (leftPos <= idx) leftPos = leftPos.min(i)
        }
        if (leftPos == 0) true
        else false
    }
}

ボトムアップのDPと捉えて右からイテレーションし、さらにその時点で最左に位置する末尾から到達可能ポジションだけを活用することでO(N)時間0(1)スペースで解ける。

https://leetcode.com/problems/island-perimeter/submissions/

0が水、1が陸地を表すマトリックスが与えられ、マトリックスにはただ一つ陸地続きの島が存在する。
島の周囲長を求める。

object Solution {
    def islandPerimeter(grid: Array[Array[Int]]): Int = {
        val m = grid.length
        val n = grid(0).length
        var count = 0
        for (row <- 0 until m) {
            for (col <- 0 until n) {
                if (grid(row)(col) == 1) {
                    if (row == 0 || grid(row - 1)(col) == 0) count += 1
                    if (col == 0 || grid(row)(col - 1) == 0) count += 1
                    if (row == m - 1 || grid(row + 1)(col) == 0) count += 1
                    if (col == n - 1 || grid(row)(col + 1) == 0) count += 1
                }
            }
        }
        count
    }
}

Approach 2: Better Counting

object Solution {
    def islandPerimeter(grid: Array[Array[Int]]): Int = {
        val m = grid.length
        val n = grid(0).length
        var count = 0
        for (row <- 0 until m) {
            for (col <- 0 until n) {
                if (grid(row)(col) == 1) {
                    count += 4
                    if (0 < row && grid(row - 1)(col) == 1) count -= 2
                    if (0 < col && grid(row)(col - 1) == 1) count -= 2
                }
            }
        }
        count
    }
}

左と上の値だけを調べて求めることができる、が、こちらの方がSubmission timeはかかっていた...

https://leetcode.com/problems/climbing-stairs/

1か2のどちらかを選ぶ操作を繰り返していき合計値がnになるような順列の数を求める。

object Solution {
    def climbStairs(n: Int): Int = {
        val memo = scala.collection.mutable.Map[Int, Int]()
        def loop(nn: Int): Int = {
            if (nn == 1) return 1
            if (nn == 2) return 2
            if (memo.contains(nn)) return memo(nn)
            memo(nn) = loop(nn - 1) + loop(nn - 2)
            memo(nn)
        }
        loop(n)
    }
}

フィボナッチ数列と同じような性質を利用してDPで求めるなどもある。

https://leetcode.com/problems/find-all-duplicates-in-an-array/

1からnまでの数字が1つか2つずつ格納された配列の中から、2つ格納されている要素を見つける

object Solution {
    def findDuplicates(nums: Array[Int]): List[Int] = {
        val set = scala.collection.mutable.Set[Int]()
        val ans = scala.collection.mutable.ListBuffer[Int]()
        nums.foreach(num => if (set.contains(num)) ans += num else set += num)
        ans.toList
    }
}

Approach 4: Mark Visited Elements in the Input Array itself

object Solution {
    def findDuplicates(nums: Array[Int]): List[Int] = {
        val ans = scala.collection.mutable.ListBuffer[Int]()
        for (i <- 0 until nums.length) {
            val num = nums(i).abs
            if (nums(num - 1) < 0) ans += num
            else nums(num - 1) = -1 * nums(num - 1)
        }
        ans.toList
    }
}

1からnまでの数字しか含まれないという性質を利用して、インプットの配列自体をフラグとして扱うことができる、イテレートし、その要素の数字のインデックスにある値の符号を入れ替える、再度その要素を確認した時に負だった場合は、一度訪問済みと判定し結果に加える。
O(N)時間かつ答え以外のメモリ使用はゼロで解ける

https://leetcode.com/problems/word-search/

文字のマトリックスからある文字列を見つけられか求める。

object Solution {
    def exist(board: Array[Array[Char]], word: String): Boolean = {
        val m = board.length
        val n = board(0).length
        val N = word.length
        
        val visited = scala.collection.mutable.Set[Grid]()
        def backtrack(grid: Grid, i: Int): Boolean = {
            if (word.charAt(i) == board(grid.row)(grid.col)) {
                if (i == N - 1) return true
                if (i < N - 1) {
                    visited += grid
                    val aroundGrids = around(grid)
                    aroundGrids.filter(!visited.contains(_)).foreach(g => {
                        if (backtrack(g, i + 1)) return true
                    })
                    visited -= grid
                }
            }
            false
        }
        
        def around(grid: Grid): Array[Grid] = {
            val buf = scala.collection.mutable.ArrayBuffer[Grid]()
            if (0 < grid.row) buf += Grid(grid.row - 1, grid.col)
            if (0 < grid.col) buf += Grid(grid.row, grid.col - 1)
            if (grid.row < m - 1) buf += Grid(grid.row + 1, grid.col)
            if (grid.col < n - 1) buf += Grid(grid.row, grid.col + 1)
            buf.toArray
        }
        
        for (row <- 0 until m) {
            for (col <- 0 until n) {
                visited.clear
                if (backtrack(Grid(row, col), 0)) return true
            }
        }
        
        false
    }
}

case class Grid(row: Int, col: Int)

典型的なバックトラッキングの問題という感じ。

ふと、深さ優先探索(DFS)との違いが気になって調べたところ、メモリ使用量の小さい深さ優先探索がバックトラックと呼ばれる、というような性質らしい。

バックトラッキングのアルゴリズムは、単に正しい解を得るまで可能な組み合わせを試していくだけであり、一種の深さ優先探索である。探索の際、ある組み合わせが解でなかったなら、探索木をたどって戻り別の組み合わせを試す。その組み合わせを試しても解でなかった場合、さらに探索木を戻り、新たな組み合わせを試す。探索木を全部サーチしたとき、探索は失敗して終了する。

バックトラックは一般に再帰呼び出し関数として実装される。一回の呼び出しでは1つの変数に値を設定(束縛)して、それ以外を自由な変数として再帰的に呼び出す。バックトラッキングは深さ優先探索に似ているが、メモリ使用量が少なく、現在の解の状態を1つだけ保持し、更新していくだけである。

https://ja.wikipedia.org/wiki/バックトラッキング

https://leetcode.com/problems/leftmost-column-with-at-least-a-one/

0か1で埋められたマトリックスが与えられ、各行は昇順に(つまり0は左側の列、1は右側の列に寄せられて)いるとする。
1が存在する列の中で最も左に位置する列のインデックスを求める。
マトリックスのグリッドの値はbinaryMatrix.get(row, col)というメソッドからしか求められず、1000回以上呼び出せない。
行と列の最大長はそれぞれ100まで。

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * class BinaryMatrix {
 *     def get(row: Int, col: Int): Int = {}
 *     def dimensions(): Array[Int] = {}
 * }
 */

object Solution {
    def leftMostColumnWithOne(binaryMatrix: BinaryMatrix): Int = {
        val dim = binaryMatrix.dimensions
        val m = dim(0)
        val n = dim(1)
        
        var left = 0
        var right = n - 1
        while (left < right) {
            val mid = left + (right - left) / 2
            var flag = false
            for (i <- 0 until m) {
                if (!flag && binaryMatrix.get(i, mid) == 1) flag = true
            }
            if (flag) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        
        // もしleftに1が存在しなければ、-1を返す
        var oneExists = false
        for (i <- 0 until m) {
            if (!oneExists && binaryMatrix.get(i, left) == 1) oneExists = true
        }
        if (!oneExists) return -1
        left
    }
}

二分探索を使えば制限の下で求められる。
Solutionでは各行ごとに二分探索をしていた。
O(MlogN)時間

Approach 3: Start at Top Right, Move Only Left and Down

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * class BinaryMatrix {
 *     def get(row: Int, col: Int): Int = {}
 *     def dimensions(): Array[Int] = {}
 * }
 */

object Solution {
    def leftMostColumnWithOne(binaryMatrix: BinaryMatrix): Int = {
        val dim = binaryMatrix.dimensions
        val m = dim(0)
        val n = dim(1)
        
        var row = 0
        var col = n - 1
        while (row < m) {
            if (binaryMatrix.get(row, col) == 1) {
                if (col == 0) return 0
                else {
                    col -= 1
                }
            } else {
                row += 1
            }
        }
        
        if (col == n - 1) -1
        else col + 1
    }
}

右上のグリッドから初めて左か下にしか動かさずに最後の行まで現在位置を遷移させていくことで、O(M+N)時間で求められる。

https://leetcode.com/problems/implement-trie-prefix-tree/

トライ木の実装

class Trie() {
    val children = scala.collection.mutable.Map[Char, Trie]()
    var isWord = false

    def insert(word: String) {
        var cur = this
        word.foreach(c => {
            if (!cur.children.contains(c)) cur.children(c) = new Trie()
            cur = cur.children(c)
        })
        cur.isWord = true
    }

    def search(word: String): Boolean = {
        var cur = this
        word.foreach(c => {
            if (!cur.children.contains(c)) return false
            cur = cur.children(c)
        })
        cur.isWord
    }

    def startsWith(prefix: String): Boolean = {
        var cur = this
        prefix.foreach(c => {
            if (!cur.children.contains(c)) return false
            cur = cur.children(c)
        })
        true
    }

}

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

https://leetcode.com/problems/word-search-ii/

与えられた単語群の中から、文字で埋まったマトリックスに存在するものだけを求める。

object Solution {
    def findWords(board: Array[Array[Char]], words: Array[String]): List[String] = {
        val trie = new Trie()
        words.foreach(trie.insert(_))
        
        val m = board.length
        val n = board(0).length
        
        def around(grid: Grid): Array[Grid] = {
            val buf = scala.collection.mutable.ArrayBuffer[Grid]()
            Array(
                Grid(grid.row - 1, grid.col),
                Grid(grid.row, grid.col - 1),
                Grid(grid.row + 1, grid.col),
                Grid(grid.row, grid.col + 1)
            ).foreach(g => {
                if (0 <= g.row && g.row < m && 0 <= g.col && g.col < n) buf += g
            })
            buf.toArray
        }
        
        val ans = scala.collection.mutable.ListBuffer[String]()
        val visited = scala.collection.mutable.Set[Grid]()
        var cur = trie
        var curStr = new scala.collection.mutable.StringBuilder
        def backtrack(grid: Grid): Unit = {
            val c = board(grid.row)(grid.col)
            if (cur.children.contains(c)) {
                val tmpCur = cur
                visited += grid
                cur = cur.children(c)
                curStr.append(c)
                if (cur.isWord) {
                    ans += curStr.toString
                    cur.isWord = false
                }
                
                around(grid).filter(!visited.contains(_)).foreach(g => {
                    backtrack(g)
                })
                cur = tmpCur
                curStr.deleteCharAt(curStr.length - 1)
                visited -= grid
            }
        }
        
        for (i <- 0 until m) {
            for (j <- 0 until n) {
                backtrack(Grid(i, j))
                visited.clear
            }
        }
        
        ans.toList
    }
}

case class Grid(row: Int, col: Int)

class Trie() {
    val children = scala.collection.mutable.Map[Char, Trie]()
    var isWord = false
    
    def insert(word: String) = {
        var cur = this
        word.foreach(c => {
            if (!cur.children.contains(c)) cur.children(c) = new Trie()
            cur = cur.children(c)
        })
        cur.isWord = true
    }
}

単語群でトライ木を作ったのち、バックトラッキングで求める。
この実装ではできていないが、バックトラック時そのノードがリーフノードだった場合すでに到達済みということで、バックトラックを続けずにそのリーフノードを削除していくことで時間を最適化できる。

https://leetcode.com/problems/bitwise-and-of-numbers-range/
object Solution {
    def rangeBitwiseAnd(left: Int, right: Int): Int = {
        if (left == right) return left
        var ans = left
        for (i <- left + 1 to right) ans = ans & i
        ans
    }
}

普通にビット演算を繰り返すだけで通ってしまったが、8000ms
leftが2147483647(Intの最大値)だった時にエラーが出たのでif (left == right) return leftを入れている。

本来この実装はTLEになるはずの模様、まあ当然か。

Approach 1: Bit Shift

object Solution {
    def rangeBitwiseAnd(left: Int, right: Int): Int = {
        var l = left
        var r = right
        var shift = 0
        while (l < r) {
          l >>= 1
          r >>= 1
          shift += 1
        }
        return l << shift
    }
}

ビット演算のANDの性質から、求める解は2つの数字の共通のprefixを求めたものになる(共通のprefix以下の桁において、順番に数が&演算される = 共通のprefix以下の桁はどちらかが0になるタイミングがあるため、結果全て0になる)

その性質を利用して、まず右シフトで共通prefixを求め、その後左シフトして0で桁を埋める、という実装

https://leetcode.com/problems/diameter-of-binary-tree/

二分木のdiameter(最長のノード間の距離)を求める。

/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 *   var value: Int = _value
 *   var left: TreeNode = _left
 *   var right: TreeNode = _right
 * }
 */
object Solution {
    def diameterOfBinaryTree(root: TreeNode): Int = {
        var d = 0
        def loop(node: TreeNode): Int = {
            if (node == null) return 0
            var left = 0
            if (node.left != null) left = loop(node.left)
            var right = 0
            if (node.right != null) right = loop(node.right)
            d = d.max(left + right)
            left.max(right) + 1
        }
        loop(root)
        d
    }
}

各パスはあるノードをルートとして媒介していると捉え、
各ノード毎に左子ノードと右子ノードの高さを求め、合計値でdiameterを更新していく。
再帰関数の返り値ではそのノードをルートとした時の高さ(左子と右子のうち高い方の高さ)を返していく。

https://leetcode.com/problems/guess-number-higher-or-lower/

1からnまでの数の中から選ばれた数を、その数と引数に与えた数の大小関係を返す関数def guess(num: Int)を使って導き出す。

/** 
 * The API guess is defined in the parent class.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * def guess(num: Int): Int = {}
 */

class Solution extends GuessGame {
    def guessNumber(n: Int): Int = {
        var left = 1
        var right = n
        while (true) {
            val mid = left + (right - left) / 2
            val g = guess(mid)
            if (g < 0) right = mid
            else if (g == 0) return mid
            else left = mid + 1
        }
        -1
    }
}

二分探索を用いる。

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

二分探索木をpreorderした値の配列からツリーを再構築する。

/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 *   var value: Int = _value
 *   var left: TreeNode = _left
 *   var right: TreeNode = _right
 * }
 */
object Solution {
    def bstFromPreorder(preorder: Array[Int]): TreeNode = {
        val N = preorder.length
        var cur = 0
        def loop(minLimit: Int, maxLimit: Int): TreeNode = {
            if (N - 1 < cur) return null
            val v = preorder(cur)
            if (v < minLimit || maxLimit < v) return null
            
            val node = TreeNode(v)
            cur += 1
            
            node.left = loop(minLimit, maxLimit.min(node.value))
            node.right = loop(minLimit.max(node.value), maxLimit)
            
            node
        }
        
        loop(Int.MinValue, Int.MaxValue)
    }
}

そのノードより値の小さいノードが左に、値が大きいノードは右に属するという二分探索木の性質を利用し、リミットを引数に渡す再帰関数で構築する。

https://leetcode.com/problems/perfect-squares/

平方数のみの足し算の合計値である数を作るときに最も少ない平方数の個数で実現した時の個数を求める。

object Solution {
    def numSquares(n: Int): Int = {
        val buf = scala.collection.mutable.ListBuffer[Int]()
        var cur = 1
        while (cur * cur <= n) {
            buf += cur * cur
            cur += 1
        }
        val list = buf.toList
        val N = list.length
        
        val map = scala.collection.mutable.Map[Int, Int]()
        var count = Int.MaxValue
        def dfs(rest: Int, c: Int): Unit = {
            if (count <= c) return
            else if (map.contains(rest) && map(rest) <= c) return
            else if (rest == 0) count = count.min(c)
            else if (rest < 4) count = count.min(c + rest)
            else {
                map(rest) = c
                for (i <- N - 1 to 0 by -1) {
                    val sq = list(i)
                    if (sq <= rest) dfs(rest - sq, c + 1)
                }
            }
        }
        
        dfs(n, 0)
        count
    }
}

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

ある銘柄の株価の変動を表す配列が与えられ、ベストな売り買いをした時の利益を求める。

object Solution {
    def maxProfit(prices: Array[Int]): Int = {
        if (prices.length == 1) return 0
        
        val N = prices.length
        val dp = new Array[Int](N)
        dp(N - 1) = 0
        dp(N - 2) = 0.max(prices(N - 1) - prices(N - 2))
        for (i <- N - 3 to 0 by -1) {
            val p = prices(i)
            
            var add = 0
            for (j <- i + 1 until N) {
                val pro = prices(j) - p

                val b = if (j + 2 < N) dp(j + 2) else 0
                add = add.max(pro + b)
            }
            
            dp(i) = dp(i + 1).max(add)
        }
        
        dp(0)
    }
}

最初メモ化 & 再帰で解こうとしたがメモリエラーに(実装の問題?)
DPに切り替え、何度か試行錯誤の後に。結構苦労した。

Approach 1: Dynamic Programming with State Machine

object Solution {
    def maxProfit(prices: Array[Int]): Int = {
        var sold = Int.MinValue
        var held = Int.MinValue
        var reset = 0
        
        prices.foreach(price => {
            val preSold = sold
            sold = held + price
            held = held.max(reset - price)
            reset = reset.max(preSold)
        })
        
        sold.max(reset)
    }
}

各株価ごとにsold, held, resetの3状態が存在するとしてState Machineを定義し、更新していくことでO(N)時間で求めることができる。

が、最初の自分の実装の方(O(N^2)のはず)がなぜかSubmit時TimeもMemoryも小さかった。Scalaの書き方やコンパイルの問題??

https://leetcode.com/problems/path-sum-iii/submissions/

木が与えられ、あるノードから下階層にのみ辿っていけるという条件のパスのなかで合計値が特定の値になるパスの存在する数を求める。

/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 *   var value: Int = _value
 *   var left: TreeNode = _left
 *   var right: TreeNode = _right
 * }
 */
object Solution {
    def pathSum(root: TreeNode, targetSum: Int): Int = {
        var count = 0
        
        def loop(node: TreeNode, sums: List[Int]): Unit = {
            if (node == null) return
            
            val newSums = node.value :: sums.map(sum => sum + node.value)
            count += newSums.filter(_ == targetSum).length
            
            loop(node.left, newSums)
            loop(node.right, newSums)
        }
        
        loop(root, List())
        
        count
    }
}

そこまでの合計値を引数に渡しつつ再帰的に。

https://leetcode.com/problems/cousins-in-binary-tree/

ツリーとある数字x, yが与えられ、x, yそれぞれの値を持つノードがcousinaであるかどうか(高さが同じで別の親を持つノード)を求める。

/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 *   var value: Int = _value
 *   var left: TreeNode = _left
 *   var right: TreeNode = _right
 * }
 */
object Solution {
    def isCousins(root: TreeNode, x: Int, y: Int): Boolean = {
        if (root.value == x || root.value == y) return false
        val queue = scala.collection.mutable.Queue[(TreeNode, TreeNode)]()
        
        queue.enqueue((root.left, root))
        queue.enqueue((root.right, root))
        
        while (queue.nonEmpty) {
            val size = queue.size
            
            var xParent = -1
            var yParent = -1
            for (i <- 0 until size) {
                val (node, parent) = queue.dequeue
                if (node != null) {
                    if (node.value == x) xParent = parent.value
                    if (node.value == y) yParent = parent.value
                    
                    queue.enqueue((node.left, node))
                    queue.enqueue((node.right, node))
                }
            }
            
            if (0 < xParent && 0 < yParent && xParent != yParent) return true
            if (0 < xParent || 0 < yParent) return false
        }
        
        false
    }
}

BFSで。

https://leetcode.com/problems/next-greater-element-i/

ある数列に含まれる各要素について、もう一つの数列におけるその要素のnext greater elementを求める。

object Solution {
    def nextGreaterElement(nums1: Array[Int], nums2: Array[Int]): Array[Int] = {
        val ans = scala.collection.mutable.ArrayBuffer[Int]()
        for (i <- 0 until nums1.length) {
            val num = nums1(i)
            var found = false
            var next = -1
            for (j <- 0 until nums2.length) {
                val num2 = nums2(j)
                if (found) {
                    if (next < 0 && num < num2) {
                        next = num2
                    }
                } else {
                    if (num == num2) found = true
                }
            }
            ans += next
        }
        ans.toArray
    }
}

Brute ForceでO(N^2)だがAccepted

Approach 3: Using Stack

object Solution {
    def nextGreaterElement(nums1: Array[Int], nums2: Array[Int]): Array[Int] = {
        val map = scala.collection.mutable.Map[Int, Int]()
        val stack = scala.collection.mutable.Stack[Int]()
        
        for (i <- 0 until nums2.length) {
            val num = nums2(i)
            while (stack.nonEmpty && stack.head < num) {
                map(stack.pop) = num
            }
            stack.push(num)
        }
        
        while (stack.nonEmpty) map(stack.pop) = -1
        
        val ans = scala.collection.mutable.ArrayBuffer[Int]()
        for (i <- 0 until nums1.length) ans += map(nums1(i))
        ans.toArray
    }
}

StackとMapを使うことでO(N)で解くことができる、感心。
Stackのhead要素より現在の要素が小さくなるまではheadを取り出してmapに格納する、を繰り返すことでnext greater elementがどれになるかをO(N)で求められる。

https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/

0と1(1は全て繋がっていて一つの領域しか存在しない)で構成されたマトリックスが与えられ、1を全て含むような直方形の面積を求める。

object Solution {
    def minArea(image: Array[Array[Char]], x: Int, y: Int): Int = {
        var leftMost = Int.MaxValue
        var upMost = Int.MaxValue
        var rightMost = Int.MinValue
        var lowMost = Int.MinValue
        
        val m = image.length
        val n = image(0).length
        for (i <- 0 until m) {
            for (j <- 0 until n) {
                if (image(i)(j) == '1') {
                    leftMost = leftMost.min(j)
                    rightMost = rightMost.max(j)
                    upMost = upMost.min(i)
                    lowMost = lowMost.max(i)
                }
            }
        }
        // println(leftMost)
        // println(rightMost)
        // println(upMost)
        // println(lowMost)
        (lowMost - upMost + 1) * (rightMost - leftMost + 1)
    }
}

なぜxとyで一つの1の点を示す引数が与えられたのかもわからず、一番単純に解いてacceptedにはなった

-> xとyはDFSやBFS, 二分探索のやり方で解く時の起点として与えられている

https://leetcode.com/problems/insert-delete-getrandom-o1/

ランダムに要素を取り出せるセットのようなデータ構造を定義する

class RandomizedSet() {
    val map = scala.collection.mutable.Map[Int, Int]()
    val arr = new Array[Int](200000)
    var tail = -1
    val r = new scala.util.Random

    def insert(`val`: Int): Boolean = {
        if (map.contains(`val`)) return false
        tail += 1
        arr(tail) = `val`
        map(`val`) = tail
        true
    }

    def remove(`val`: Int): Boolean = {
        if (!map.contains(`val`)) return false
        if (map(`val`) != tail) {
            arr(map(`val`)) = arr(tail)
            map(arr(tail)) = map(`val`)
        }
        tail -= 1
        map -= `val`
        
        true
    }

    def getRandom(): Int = {
        val idx = r.nextInt(tail + 1)
        arr(idx)
    }

}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(`val`)
 * var param_2 = obj.remove(`val`)
 * var param_3 = obj.getRandom()
 */

全ての操作をO(1)で行う必要があるということで、
mapと配列を使って。

arrayList(scalaで言うところのarrayBuffer)を使って実装する方が楽

https://leetcode.com/problems/sort-characters-by-frequency/

ある文字列が与えられ、文字ごとの出現順に並べ替える。

object Solution {
    def frequencySort(s: String): String = {
        val map = scala.collection.mutable.Map[Char, Int]()
        
        s.foreach(c => {
            if (!map.contains(c)) map(c) = 0
            map(c) += 1
        })
        
        val b = new StringBuilder
        map.toArray.sortBy(_._2).reverse.foreach {
            case (c, i) => for (j <- 0 until i) b.append(c)
        }
        
        b.result
    }
}

まずmapに各文字ごとの出現数を記録してソートし、並べ替えた。O(NlogN)時間

Approach 3: Multiset and Bucket Sort

object Solution {
    def frequencySort(s: String): String = {
        val map = scala.collection.mutable.Map[Char, Int]()
        
        s.foreach(c => {
            if (!map.contains(c)) map(c) = 0
            map(c) += 1
        })
        
        val maxCount = map.map(_._2).max
        val buckets = new Array[List[Char]](maxCount + 1)
        for (i <- 0 to maxCount) buckets(i) = List()
        
        map.foreach {
            case (c, i) => buckets(i) = c :: buckets(i)
        }
        
        val sb = new StringBuilder
        for (i <- buckets.length - 1 to 0 by -1) {
            buckets(i).foreach(c => {
                for (j <- 0 until i) sb.append(c)
            })
        }
        
        sb.result
    }
}

バケットソートを使うことでO(N)時間で解くことができる。
Submission Timeも最初の実装と比べて半分程度になっており、効果は大きかった

https://leetcode.com/problems/count-complete-tree-nodes/

あるcomplete binary treeのノードの数を求める。

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 *   var value: Int = _value
 *   var left: TreeNode = _left
 *   var right: TreeNode = _right
 * }
 */
object Solution {
    def countNodes(root: TreeNode): Int = {
        if (root == null) return 0
        
        countNodes(root.left) + countNodes(root.right) + 1
    }
}

ツリーの性質を使っていないが、一番素直に解いた。

/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 *   var value: Int = _value
 *   var left: TreeNode = _left
 *   var right: TreeNode = _right
 * }
 */
object Solution {
    def countNodes(root: TreeNode): Int = {
        if (root == null) return 0
        
        var d = 0
        var cur = root
        while (cur.left != null) {
            cur = cur.left
            d += 1
        }
        
        if (d == 0) return 1
        
        val lastNodesMaxCount = scala.math.pow(2, d).toInt
        
        def exists(idx: Int): Boolean = {
            var left = 0 
            var right = lastNodesMaxCount - 1
            var cur = root
            for (i <- 0 until d) {
                val mid = left + (right - left) / 2
                if (idx <= mid) {
                    cur = cur.left
                    right = mid
                } else {
                    cur = cur.right
                    left = mid + 1
                }
            }
            cur != null
        }
        
        var left = 0
        var right = lastNodesMaxCount - 1
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (exists(mid)) left = mid + 1
            else right = mid - 1
        }
        
        scala.math.pow(2, d).toInt - 1 + left
    }
}

最下段のノードの数だけ分ければ全体のノード数を求められるというcomplete binary treeの性質を利用して、二分探索を駆使して解く方法。
二分探索の中で二分探索を使うようなユニークな構造が見られる、O(logN)時間

https://leetcode.com/problems/invert-binary-tree/

二分木を反転させる。

/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 *   var value: Int = _value
 *   var left: TreeNode = _left
 *   var right: TreeNode = _right
 * }
 */
object Solution {
    def invertTree(root: TreeNode): TreeNode = {
        if (root == null) return null
        
        val l = root.left
        root.left = root.right
        root.right = l
        invertTree(root.left)
        invertTree(root.right)
        
        root
    }
}

https://leetcode.com/problems/sort-colors/

0と1と2で構成された配列を、昇順にならべかえる。

object Solution {
    def sortColors(nums: Array[Int]): Unit = {
        val N = nums.length
        
        def swap(x: Int, y: Int) = {
            val tmp = nums(x)
            nums(x) = nums(y)
            nums(y) = tmp
        }
        
        var l = 0
        while (nums(l) == 0 && l < N - 1) l += 1
        for (i <- l until N) {
            if (nums(i) == 0) {
                swap(i, l)
                l += 1
            }
        }
        
        var r = N - 1
        while (nums(r) == 2 && 0 < r) r -= 1
        for (i <- r to 0 by -1) {
            if (nums(i) == 2) {
                swap(i, r)
                r -= 1
            }
        }
    }
}

2回のイテレーションで0と2をそれぞれ左右に寄せる。
Follow up: Could you come up with a one-pass algorithm using only constant extra space?に取り組んだがうまくいかなかった。

https://leetcode.com/problems/3sum/

数字の配列が与えられ、合計が0になる3つの数字の組み合わせを列挙する。

object Solution {
    def threeSum(nums: Array[Int]): List[List[Int]] = {
        var N = nums.length
        val ans = scala.collection.mutable.Set[List[Int]]()
        
        var sortedNums = nums.sorted
        if (2 < nums.filter(_ == 0).length) {
            ans += List(0,0,0)
            sortedNums = (nums.filter(_ != 0) :+ 0).sorted
            N = sortedNums.length
        }
        
        def bs(target: Int, l: Int, r: Int): Int = {
            var left = l
            var right = r
            while (left < right) {
                val mid = left + (right - left) / 2
                val num = sortedNums(mid)
                if (target <= num) right = mid
                else left = mid + 1
            }
            if (sortedNums(left) == target) left
            else -1
        }
        
        for (i <- 0 until N - 2) {
            // val num1 = sortedNums(i)
            
            for (j <- i + 1 until N - 1) {
                val sum = sortedNums(i) + sortedNums(j)
                if (sum < 1) {
                    var k = bs(-1 * sum, j + 1, N - 1)
                    if (0 < k) {
                        val lastNum = sortedNums(k)
                        
                        while (k < N && sortedNums(k) == lastNum) {
                            ans += List(sortedNums(i), sortedNums(j), sortedNums(k))
                            k += 1
                        }
                    }
                }
            }
        }
        
        ans.toList
    }
}

BruteForceでやるとO(N^3)になるが、ソートと二分探索を使うことでO(N^2logN)にしている。
値が全て0の場合にTimeLimitになってしまったので、そのケースだけ対応している。0は1つ含まれるか3つ含まれるのどちらかのパターンしかない。

Approach 1: Two Pointers

object Solution {
    def threeSum(nums: Array[Int]): List[List[Int]] = {
        var N = nums.length
        val ans = scala.collection.mutable.Set[List[Int]]()
        val sortedNums = nums.sorted
        
        def twoSum(i: Int): Unit = {
            var lo = i + 1
            var hi = N - 1
            while (lo < hi) {
                val sum = sortedNums(i) + sortedNums(lo) + sortedNums(hi)
                if (0 < sum) hi -= 1
                else if (sum < 0) lo += 1
                else {
                    ans += List(sortedNums(i),
                                sortedNums(lo),
                                sortedNums(hi))
                    lo += 1
                }
            }
        }
        
        for (i <- 0 until N - 2) {
            if (i == 0 || sortedNums(i) != sortedNums(i - 1)) {
                twoSum(i)
            }
        }
        
        ans.toList
    }
}

ソートし2pointerを使う、より効率的で直感的

https://leetcode.com/problems/rotting-oranges/

空とflesh orangeとrotten orangeで構成されたマトリックスの全てのオレンジがrottenするまでの時間を求める。

object Solution {
    def orangesRotting(grid: Array[Array[Int]]): Int = {
        val m = grid.length
        val n = grid(0).length
        val queue = scala.collection.mutable.Queue[(Int, Int)]()
        var fleshCount = 0
        for (i <- 0 until m) {
            for (j <- 0 until n) {
                if (grid(i)(j) == 1) fleshCount += 1
                if (grid(i)(j) == 2) queue.enqueue((i, j))
            }
        }
        
        if (fleshCount == 0) return 0
        
        def adj(r: Int, c: Int): Array[(Int, Int)] = {
            val res = scala.collection.mutable.ArrayBuffer[(Int, Int)]()
            val ar = Array((-1, 0), (0, -1), (1, 0), (0, 1))
            for (i <- 0 until 4) {
                val a = ar(i)
                val newR = r + a._1
                val newC = c + a._2
                if (0 <= newR && newR < m && 0 <= newC && newC < n) {
                    res += ((newR, newC))
                }
            }
            res.toArray
        }
        
        val visited = scala.collection.mutable.Set[(Int, Int)]()
        var times = 0
        while (queue.nonEmpty) {
            val size = queue.size
            for (i <- 0 until size) {
                val p = queue.dequeue
                if (!visited.contains(p)) {
                    visited += p
                    if (grid(p._1)(p._2) == 1) {
                        fleshCount -= 1
                    }
                    if (grid(p._1)(p._2) != 0) {
                        adj(p._1, p._2).foreach(queue.enqueue(_))
                    }
                }
            }
            
            if (fleshCount == 0) return times
            times += 1
        }
        
        -1
    }
}

典型的なBFSの問題。

Approach 2: In-place BFS

普通のBFSでは、全てのグリッドが最初から2だった場合などqueueに積まれるデータの分があるのでSpace ComplexはO(N)になる。
rotten化した各gridにタイムスタンプを記録していき、毎度全てのgridを走査することでO(1)スペースで解くことができるが、その場合TimeはO(N^2)になる。

https://leetcode.com/problems/longest-duplicate-substring/

文字列において、重複している部分文字列のうち最長のものを求める。

object Solution {
    def longestDupSubstring(s: String): String = {
        val N = s.length
        if (s.toSet.size == 1) return s.slice(0, N - 1)
        val dp = new Array[String](N)
        dp(N - 1) = ""
        
        for (i <- N - 2 to 0 by -1) {
            val c = s.charAt(i)
            val prevLongest = dp(i + 1)
            var longest = ""
            for (j <- i + 1 until N) {
                val c2 = s.charAt(j)
                if (c == c2) {
                    var cur = j + 1
                    var curLongest = 0
                    val check = N.min(j + 1 + prevLongest.length)
                    var isContinue = true
                    while (cur < check && isContinue) {
                        val c3 = s.charAt(cur)
                        if (c3 == prevLongest.charAt(curLongest)) {
                            cur += 1
                            curLongest += 1
                        } else isContinue = false
                    }
                    if (longest.length < curLongest + 2) {
                        longest = s.slice(j, cur)
                    }
                }
            }
            
            dp(i) = longest
        }
        
        dp.sortBy(_.length).last
    }
}

O(N^3)なので違うだろうなーと思いつつ、submitで失敗したエッジケースに無理やり対応したところ4000msもかかってacceptedされてしまった。が、自分で独自にテストケースをセットして実行したところやはりタイムリミットになってしまう。

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

childポインタを持つ双方向連結リストを、childをnextに据えてflattenする。

/**
 * Definition for a Node.
 * class Node(var _value: Int) {
 *   var value: Int = _value
 *   var prev: Node = null
 *   var next: Node = null
 *   var child: Node = null
 * }
 */

object Solution {
    def flatten(head: Node): Node = {
        if (head == null) return null
    	val stack = scala.collection.mutable.Stack[Node]()
        val h = new Node(-1)
        var cur = h
        stack.push(head)
        
        while (stack.nonEmpty) {
            val node = stack.pop
            cur.next = node
            node.prev = cur
            cur = node
            if (node.next != null) stack.push(node.next)
            if (node.child != null) stack.push(node.child)
            node.child = null
        }
        
        h.next.prev = null
        h.next
    }
}

stackを使ったDFS

https://leetcode.com/problems/buildings-with-an-ocean-view/

数列から、右側にそれより小さい数しか存在しない要素のインデックスを返す。

object Solution {
    def findBuildings(heights: Array[Int]): Array[Int] = {
        val N = heights.length
        val buf = scala.collection.mutable.ArrayBuffer[Int]()
        var maxHeight = Int.MinValue
        for (i <- N - 1 to 0 by -1) {
            if (maxHeight < heights(i)) {
                buf += i
                maxHeight = heights(i)
            }
        }
        buf.toArray.reverse
    }
}
ログインするとコメントできます