Leetcode自分用解答メモ[Explore

リアルにサーモン 2021/11/27

数列とかける数の数列が与えられ、かける数ごとに数列の左か右のどちらかを選んで結果を加算していく操作を繰り返し、合計が最大になるときの最大値を求める。

object Solution {
    def maximumScore(nums: Array[Int], multipliers: Array[Int]): Int = {
        val n = nums.length
        val m = multipliers.length
        
        val dp = new Array[Array[Int]](m + 1)
        for (i <- 0 to m) dp(i) = new Array[Int](m + 1)
        
        for (i <- 1 to m) {
            val multiplier = multipliers(i - 1)
            for (j <- 0 to i) {
                val takeLeft = if (j == 0) Int.MinValue else dp(i - 1)(j - 1) + multiplier * nums(j - 1)
                
                var takeRight = if (j == i) Int.MinValue else dp(i - 1)(j) + multiplier * nums(n - 1 - (i - j - 1))
                dp(i)(j) = takeLeft.max(takeRight)
            }
            
            
        }
        
        dp(m).max
    }
}

少し苦労したが、multipliersの数と左から要素をとった数をパラメータとしてDPしていく。

リアルにサーモン 2021/12/01

コインの単位群が与えられ、ある合計値に達するために必要なコインの最小枚数を求める。

object Solution {
    import scala.collection.mutable
    def coinChange(coins: Array[Int], amount: Int): Int = {
        val memo = mutable.Map[Int, Int]()
        val minCoin = coins.min
        
        def loop(a: Int): Int = {
            if (a == 0) return 0
            if (a < 0) return -1
            
            if (!memo.contains(a)) {
                if (a < minCoin) memo(a) = -1
                else {
                    var changes = Int.MaxValue
                    coins.foreach(coin => {
                        val res = loop(a - coin)
                        if (0 <= res) {
                            changes = changes.min(res + 1)
                        }
                    })
                    
                    memo(a) = if (changes == Int.MaxValue) -1 else changes
                }
            }
            
            memo(a)
        }
        
        loop(amount)
    }
}

最初試しに貪欲法で解けるのではと思いやってみたがそんなことはなかった。
直感的なTopdown DPで。

リアルにサーモン 2021/12/01

ある文字列と単語群が与えられ、単語群の組み合わせで文字列を構成できるかどうかチェックする。

object Solution {
    import scala.collection.mutable
    def wordBreak(s: String, wordDict: List[String]): Boolean = {
        val n = s.length
        val wordSet = mutable.Set[String]()
        wordDict.foreach(word => wordSet += word)
        val memo = mutable.Map[Int, Boolean]()
        
        def loop(i: Int): Boolean = {
            if (n <= i) return true
            if (!memo.contains(i)) {
                val b = new StringBuilder
                for (j <- i until n) {
                    b += s.charAt(j)
                    if (wordSet.contains(b.toString)) {
                        if (loop(j + 1)) return true
                    }
                }
                memo(i) = false
            }
            
            memo(i)
        }
        
        loop(0)
    }
}

こちらもシンプルにトップダウンDPで。

リアルにサーモン 2021/12/01

数列から昇順の部分列の中で最長のものの長さを求める。

object Solution {
    import scala.collection.mutable
    def lengthOfLIS(nums: Array[Int]): Int = {
        val n = nums.length
        
        val dp = new Array[Int](n)
        dp(0) = 1
        for (i <- 1 until n) {
            var v = 1
            for (j <- 0 until i) {
                if (nums(j) < nums(i)) v = v.max(dp(j) + 1)
                dp(i) = v
            }
        }
        
        dp.max
    }
}

シンプルなDP、`O(N^2)`時間

### Approach 3: Improve With Binary Search

```scala
object Solution {
    import scala.collection.mutable
    def lengthOfLIS(nums: Array[Int]): Int = {
        val n = nums.length
        
        val sub = mutable.ArrayBuffer[Int]()
        sub += nums(0)
        
        def bs(a: Int): Int = {
            var left = 0
            var right = sub.length - 1
            while (left < right) {
                val mid = left + (right - left) / 2
                if (sub(mid) == a) return mid
                else if (sub(mid) < a) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            
            left
        }
        
        for (i <- 1 until n) {
            val num = nums(i)
            if (sub(sub.length - 1) < num) {
                sub += num
            } else {
                sub(bs(num)) = num
            }
        }
        
        sub.size
    }
}

こちらはDPとは関係ないが、
subによって現状の昇順部分列を管理する解法とバイナリサーチを組み合わせることでO(NlogN)で解くことが可能。
subは最長部分列を表すわけではないが、その個数は正しく反映している。

リアルにサーモン 2021/12/02

株の価格変動を表す数列が与えられ、一度に一つの株しか保持できずk回までのトランザクションを組めるという制約下で得られる最大利益を求める。

object Solution {
    def maxProfit(k: Int, prices: Array[Int]): Int = {
        val n = prices.length
        
        val dp = Array.ofDim[Int](k + 1, n + 1)
        
        for (i <- 1 to k) {
            for (j <- 1 to n) {
                var pro = dp(i - 1)(j).max(dp(i)(j - 1))
                var price = prices(j - 1)
                for (l <- j - 2 to 0 by -1) {
                    pro = pro.max(price - prices(l) + dp(i - 1)(l))
                }
                dp(i)(j) = pro
            }
        }
        
        // println(dp.map(_.toList).toList)
        dp(k)(n)
    }
}

なかなか難しい、これだと一応O(n^2k)? (余裕でACだが)

リアルにサーモン 2021/12/04

株の保有状態をパラメータに加えることで、O(nk)時間で求めることができる。

object Solution {
    def maxProfit(k: Int, prices: Array[Int]): Int = {
        val n = prices.length
        // 0: not hold
        // 1: hold
        val memo = new Array[Array[Array[Int]]](n)
        for (i <- 0 until n) {
            memo(i) = new Array[Array[Int]](k + 1)
            for (j <- 0 to k) {
                memo(i)(j) = new Array[Int](2)
            }
        }
        
        def dp(day: Int, remain: Int, hold: Int): Int = {
            if (day == n || remain == 0) return 0
            
            if (memo(day)(remain)(hold) == 0) {
                if (hold == 0) {
                    val buy = dp(day + 1, remain, 1) - prices(day)
                    val stay = dp(day + 1, remain, 0)
                    memo(day)(remain)(hold) = buy.max(stay)
                } else {
                    val sell = dp(day + 1, remain - 1, 0) + prices(day)
                    val stay = dp(day + 1, remain, 1)
                    memo(day)(remain)(hold) = sell.max(stay)
                }
            }
            
            memo(day)(remain)(hold)
        }
        
        
        dp(0, k, 0)
    }
}

トップダウンメモ化ver

リアルにサーモン 2021/12/06

コインを表す数列とある金額が与えられ、その金額を満たすためのコインの選び方が何通りあるか求める。

Approach 1: Dynamic Programming

object Solution {
    import scala.collection.mutable
    def change(amount: Int, coins: Array[Int]): Int = {
        val n = coins.length
        val dp = Array.ofDim[Int](n + 1, amount + 1)
        
        for (i <- 1 to n) {
            val coin = coins(i - 1)
            dp(i)(0) = 1
            for (j <- 1 to amount) {
                if (coin <= j) {
                    dp(i)(j) = dp(i - 1)(j) + dp(i)(j - coin)
                } else dp(i)(j) = dp(i - 1)(j)
            }
        }
        
        dp(n)(amount)
    }
}

苦戦しSolutionを見てしまった。amountとcoinsで順番にDPしていく。amountが0の時は1をセットして金額を順番に上げていくのがポイント。

リアルにサーモン 2021/12/06

object Solution {
    def numDecodings(s: String): Int = {
        val n = s.length
        val dp = new Array[Int](n + 1)
        
        if (s.charAt(0) == '0') return 0
        if (n == 1) return 1
        dp(0) = 1
        dp(1) = 1
        
        for (i <- 2 to n) {
            val c = s.charAt(i - 1)
            val prevC = s.charAt(i - 2)
            if (c == '0') {
                if (prevC != '1' && prevC != '2') return 0
                else dp(i) = dp(i - 2)
            } else {
                if (prevC == '1' || ((prevC == '2') && c.asDigit < 7)) {
                    dp(i) = dp(i - 1) + dp(i - 2)
                } else dp(i) = dp(i - 1)
            }
        }
        // println(dp.toList)
        dp(n)
    }
}

リアルにサーモン 2021/12/06に更新

サークルしている数列から、部分列の合計値の最大値を求める。

Approach 1: Next Array

object Solution {
    def maxSubarraySumCircular(nums: Array[Int]): Int = {
        val n = nums.length
        
        var ans = nums(0)
        var cur = nums(0)
        for (i <- 1 until n) {
            cur = nums(i) + 0.max(cur)
            ans = ans.max(cur)
        }
        
        cur = nums(n - 1)
        var rightMost = cur
        val suffixSum = new Array[Int](n)
        suffixSum(n - 1) = 0.max(cur)
        for (i <- n - 2 to 0 by -1) {
            cur += nums(i)
            rightMost = rightMost.max(cur)
            suffixSum(i) = rightMost
        }
        
        cur = 0
        var leftMost = 0
        for (i <- 0 until n - 2) {
            cur += nums(i)
            ans = ans.max(cur + suffixSum(i + 1))
            leftMost = leftMost.max(cur)
        }
        
        ans
    }
}

サークルしている部分については、素直に左からの最大値を右からの最大値で求めていく。

リアルにサーモン 2021/12/09

Approach 2: Prefix Sums + Monoqueue

object Solution {
    import scala.collection.mutable
    def maxSubarraySumCircular(nums: Array[Int]): Int = {
        val n = nums.length
        
        val P = new Array[Int](n * 2)
        P(0) = nums(0)
        for (i <- 1 until n * 2) {
            P(i) = P(i - 1) + nums(i % n)
        }
        
        var ans = nums(0)
        val deque = mutable.ArrayDeque[Int]()
        deque.append(0)
        
        for (i <- 1 until n * 2) {
            
            if (deque.head < i - n) {
                deque.removeHead(false)
            }
            
            ans = ans.max(P(i) - P(deque.head))
            
            while (deque.nonEmpty && P(i) <= P(deque.last)) {
                deque.removeLast(false)
            }
            
            deque.append(i)
        }
        
        ans
    }
}

リアルにサーモン 2021/12/13

文字列から最長の回文を見つける。
Brute ForceでもACはしたが、O(n^3)時間

Approach 3: Dynamic Programming

object Solution {
    def longestPalindrome(s: String): String = {
        val n = s.length
        
        val dp = new Array[Array[Boolean]](n)
        for (i <- 0 until n) dp(i) = new Array[Boolean](n)
        
        var start = 0
        var end = 0
        
        for (i <- n - 1 to 0 by -1) {
            for (j <- i until n) {
                dp(i)(j) = (s.charAt(i) == s.charAt(j)) && (j - i < 3 || dp(i + 1)(j - 1))
                if (dp(i)(j)) {
                    if (end - start < j - i + 1) {
                        start = i
                        end = j + 1
                    }
                }
            }
        }
        
        s.slice(start, end)
    }
}

先頭と末尾の文字列を比較することで、DPを活用できる。
O(n^2)時間

Approach 4: Expand Around Center

object Solution {
    def longestPalindrome(s: String): String = {
        val n = s.length
        
        if (n < 2) return s
        
        var start = 0
        var end = 0
        def check(_l: Int, _r: Int): Unit = {
            var l = _l
            var r = _r
            while (0 <= l && r < n && s.charAt(l) == s.charAt(r)) {
                l -= 1
                r += 1
            }
            
            if (end - start < r - l) {
                start = l + 1
                end = r
            }
        }
        
        for (i <- 0 until n) {
            check(i, i)
            check(i, i + 1)
        }
        
        s.slice(start, end)
    }
}

各文字ごとの、その文字が中心の場合と、その文字と次の文字が中心の場合を考えてtwo pointerで左右の伸びながらチェックしていけば良い、シンプルで綺麗。

リアルにサーモン 2021/12/13に更新

文字列1と2のinterleavingとして文字列3を表現できるかどうかを求める。

文字列1と2を個数が1以上変わらないように分割し、それらを順番に配置して文字列3を表現できれば、interleavingである。

object Solution {
    import scala.collection.mutable
    def isInterleave(s1: String, s2: String, s3: String): Boolean = {
        val n1 = s1.length
        val n2 = s2.length
        val n3 = s3.length
        
        if (n1 + n2 != n3) return false
        
        val memo = mutable.Map[State, Boolean]()
        def dp(i3: Int, i1: Int, n: Int, m: Int, isPrev1: Boolean): Boolean = {
            if (1 < (n - m).abs) return false
            
            if (i3 == n3) return true
            
            val state = State(i3, i1, n, m)
            if (!memo.contains(state)) {
                memo(state) = false
                val c3 = s3.charAt(i3)
                if (i1 < n1 && s1.charAt(i1) == c3) {
                    val nextN = if (isPrev1) n else n + 1
                    memo(state) = dp(i3 + 1, i1 + 1, nextN, m, true)
                    if (memo(state)) return true
                }
                
                val i2 = i3 - i1
                if (i2 < n2 && s2.charAt(i2) == c3) {
                    val nextM = if (isPrev1) m + 1 else m
                    memo(state) = dp(i3 + 1, i1, n, nextM, false)
                    // if (res1) return true
                }
            }
            
            memo(state)
        }
        
        dp(0, 0, 0, 0, true) || dp(0, 0, 0, 0, false)
    }
}

case class State(i3: Int, i1: Int, n: Int, m: Int)

順番にどちらの文字列から取得していくかをチェックしていくトップダウンのDPで。

修正ver

object Solution {
    import scala.collection.mutable
    def isInterleave(s1: String, s2: String, s3: String): Boolean = {
        val n1 = s1.length
        val n2 = s2.length
        val n3 = s3.length
        
        if (n1 + n2 != n3) return false
        
        val memo = mutable.Map[State, Boolean]()
        def dp(i3: Int, i1: Int): Boolean = {
            if (i3 == n3) return true
            
            val state = State(i3, i1)
            if (!memo.contains(state)) {
                memo(state) = false
                val c3 = s3.charAt(i3)
                if (i1 < n1 && s1.charAt(i1) == c3) {
                    memo(state) = dp(i3 + 1, i1 + 1)
                    if (memo(state)) return true
                }
                
                val i2 = i3 - i1
                if (i2 < n2 && s2.charAt(i2) == c3) {
                    memo(state) = dp(i3 + 1, i1)
                }
            }
            
            memo(state)
        }
        
        dp(0, 0)
    }
}

case class State(i3: Int, i1: Int)

interleavingを達成するには、自動的に各文字列のコンポーネントの数の差は1以下になる、よって無駄なスペースを利用していたので削除してAC

リアルにサーモン 2021/12/15

Approach 3: Using 2D Dynamic Programming

object Solution {
    import scala.collection.mutable
    def isInterleave(s1: String, s2: String, s3: String): Boolean = {
        val n1 = s1.length
        val n2 = s2.length
        val n3 = s3.length
        
        if (n1 + n2 != n3) return false
        
        val dp = Array.ofDim[Boolean](n1 + 1, n2 + 1)
        dp(0)(0) = true
        for (i <- 1 to n2) {
            if (s2.charAt(i - 1) == s3.charAt(i - 1) && dp(0)(i - 1)) {
                dp(0)(i) = true
            }
        }
        
        for (i <- 1 to n1) {
            if (s1.charAt(i - 1) == s3.charAt(i - 1) && dp(i - 1)(0)) {
                dp(i)(0) = true
            }
        }
        
        for (i <- 1 to n1) {
            val c1 = s1.charAt(i - 1)
            for (j <- 1 to n2) {
                val c2 = s2.charAt(j - 1)
                
                val c3 = s3.charAt(i + j - 1)
                
                dp(i)(j) = (c1 == c3 && dp(i - 1)(j)) || c2 == c3 && dp(i)(j - 1)
            }
        }
        
        dp(n1)(n2)
    }
}

この場合ボトムアップで解くには、s1のi番目までとs2のj番目まででs3の(i + j)番目までのprefixを構成できるか、をDPに格納し、各イテレートでその文字をまだ使っていない時の一つ前の結果と比較して埋めていく。

リアルにサーモン 2021/12/14

1から365までの日付を表す数列と1day,7day,30dayごとのパスのコストが与えられ、与えられた数列分の日付を満たすための最小の組み合わせのコスト和を求める。

object Solution {
    import scala.collection.mutable
    def mincostTickets(days: Array[Int], costs: Array[Int]): Int = {
        val n = days.length
        val sortedDays = days.sorted
        
        val memo = mutable.Map[Int, Int]()
        
        def dp(dayIdx: Int): Int = {
            if (dayIdx < 0) return 0
            if (n - 1 < dayIdx) return 0
            
            if (!memo.contains(dayIdx)) {
                val oneDayPass = costs(0) + dp(dayIdx + 1)
                
                val day = sortedDays(dayIdx)
                var weekDayPassIdx = -1
                var monthDayPassIdx = -1
                for (i <- dayIdx + 1 until n) {
                    if (weekDayPassIdx < 0 &&
                        7 <= sortedDays(i) - day) {
                        weekDayPassIdx = i
                    }
                    if (monthDayPassIdx < 0 &&
                        30 <= sortedDays(i) - day) {
                        monthDayPassIdx = i
                    }
                }
                
                val weekPass = costs(1) + dp(weekDayPassIdx)
                val monthPass = costs(2) + dp(monthDayPassIdx)
                
                memo(dayIdx) = oneDayPass.min(weekPass.min(monthPass))
            }
            
            memo(dayIdx)
        }
        
        dp(0)
    }
}

ボトムアップだと苦戦したがトップダウンに切り替えると行けた。

リアルにサーモン 2021/12/15

ダイスの側面数と数とターゲットの数字が与えられ、ターゲットに一致するようなダイスの目の合計数になるダイスの振り方の総数を求める。

object Solution {
    val MOD = scala.math.pow(10, 9).toInt + 7
    def numRollsToTarget(d: Int, f: Int, target: Int): Int = {
        val dp = Array.ofDim[Int](d + 1, target + 1)
        dp(0)(0) = 1
        
        for (i <- 1 to d) {
            for (j <- 1 to target) {
                for (k <- 1 to f.min(j)) {
                    dp(i)(j) += dp(i - 1)(j - k)
                    dp(i)(j) %= MOD
                }
            }
        }
        
        (dp(d)(target) % MOD).toInt
    }
}

前回はトップダウンで解いたので今回はBottom Upで。
ダイスの数 * targetの二次元配列を使う