Open31
Leetcode自分用解答メモ[October LeetCoding Challenge 2021]
リアルにサーモン
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)
}
}
動的計画法でイテレーションで実装する場合
リアルにサーモン
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による解法のケースは多々あるので引き出しに持っておきたい
リアルにサーモン
数字の配列が与えられ、その数字分右にジャンプできるという制約下で最初から最後まで辿り着けるかの判定。
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)スペースで解ける。
リアルにサーモン
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はかかっていた...
リアルにサーモン
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で求めるなどもある。
リアルにサーモン
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)時間かつ答え以外のメモリ使用はゼロで解ける
リアルにサーモン
文字のマトリックスからある文字列を見つけられか求める。
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つだけ保持し、更新していくだけである。
リアルにサーモン
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)時間で求められる。
リアルにサーモン
トライ木の実装
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)
*/
与えられた単語群の中から、文字で埋まったマトリックスに存在するものだけを求める。
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
}
}
単語群でトライ木を作ったのち、バックトラッキングで求める。
この実装ではできていないが、バックトラック時そのノードがリーフノードだった場合すでに到達済みということで、バックトラックを続けずにそのリーフノードを削除していくことで時間を最適化できる。
リアルにサーモン
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で桁を埋める、という実装
リアルにサーモン
二分木の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を更新していく。
再帰関数の返り値ではそのノードをルートとした時の高さ(左子と右子のうち高い方の高さ)を返していく。
リアルにサーモン
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
}
}
二分探索を用いる。
リアルにサーモン
二分探索木を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)
}
}
そのノードより値の小さいノードが左に、値が大きいノードは右に属するという二分探索木の性質を利用し、リミットを引数に渡す再帰関数で構築する。
リアルにサーモン
平方数のみの足し算の合計値である数を作るときに最も少ない平方数の個数で実現した時の個数を求める。
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)
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の書き方やコンパイルの問題??
リアルにサーモン
木が与えられ、あるノードから下階層にのみ辿っていけるという条件のパスのなかで合計値が特定の値になるパスの存在する数を求める。
/**
* 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
}
}
そこまでの合計値を引数に渡しつつ再帰的に。
リアルにサーモン
ツリーとある数字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で。
リアルにサーモン
ある数列に含まれる各要素について、もう一つの数列におけるその要素の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)で求められる。
リアルにサーモン
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, 二分探索のやり方で解く時の起点として与えられている
リアルにサーモン
文字列を単語単位でリバースする。
object Solution {
def reverseWords(s: String): String = {
s.trim.split("\\s+").reverse.mkString(" ")
}
}
組み込み関数と正規表現で
リアルにサーモン
ランダムに要素を取り出せるセットのようなデータ構造を定義する
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)を使って実装する方が楽
リアルにサーモン
ある文字列が与えられ、文字ごとの出現順に並べ替える。
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も最初の実装と比べて半分程度になっており、効果は大きかった
リアルにサーモン
ある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
}
}
ツリーの性質を使っていないが、一番素直に解いた。
Approach 2: Binary search
/**
* 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)時間
リアルにサーモン
二分木を反転させる。
/**
* 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
}
}
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?に取り組んだがうまくいかなかった。
リアルにサーモン
数字の配列が与えられ、合計が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を使う、より効率的で直感的
リアルにサーモン
空と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)になる。
リアルにサーモン
文字列において、重複している部分文字列のうち最長のものを求める。
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
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
リアルにサーモン
数列から、右側にそれより小さい数しか存在しない要素のインデックスを返す。
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
}
}