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

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

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)
else hp = hp.min(1)
}
if (c < n - 1) {
val add = dp(r)(c + 1) - dungeon(r)(c)
else hp = hp.min(1)
}
dp(r)(c) = hp
}
}
}

dp(0)(0)
}
}
``````

そのマス目に到達する上で保持しておかなければならないhpを保存していく。
そのマス目の右と下のマス目のdpの値と、そのマス目の変化の値からそのマス目に到達する時点で保持していなければならないhpが求まっていく。

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

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回以上呼び出せない。

``````/**
* // 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
}
}
``````

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

leftが2147483647(Intの最大値)だった時にエラーが出たので`if (left == right) return left`を入れている。

### 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/

``````/**
* 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
}
}
``````

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

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

``````/**
* The API guess is defined in the parent class.
* @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/

``````/**
* 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
}
}
``````

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

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

for (j <- i + 1 until N) {
val pro = prices(j) - p

val b = if (j + 2 < N) dp(j + 2) else 0
}

}

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

が、最初の自分の実装の方(`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()
*/
``````

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

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/

``````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)`にしている。

### 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/

``````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) {
}
}
}

if (fleshCount == 0) return times
times += 1
}

-1
}
}
``````

### Approach 2: In-place BFS

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されてしまった。が、自分で独自にテストケースをセットして実行したところやはりタイムリミットになってしまう。

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

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