ゼロから始めるLeetCode Day108「300. Longest Increasing Subsequence」

• 概要
• 問題
• 解法

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day107「98. Validate Binary Search Tree」

次回
ゼロから始めるLeetCode Day109「213. House Robber II」

Twitterやってます。

問題

300. Longest Increasing Subsequence
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、整列されていない整数の配列が与えられたとき、最も長く増加する部分列の長さを求めなさい、というものです。

Example:

Input: [10,9,2,5,3,7,101,18] Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

解法

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = [1]*len(nums)
        dp[-1] = 1
        for i in reversed(range(len(nums))):
            for j in range(i+1,len(nums)):
                if nums[i] < nums[j]:
                    dp[i] = max(dp[i],dp[j]+1)  
        return max(dp)
# Runtime: 1220 ms, faster than  44.36%  of  Python3  online submissions for  Longest Increasing Subsequence.
# Memory Usage: 14.1 MB, less than  28.52%  of  Python3  online submissions for  Longest Increasing Subsequence.

動的計画法で解きました。
二重にfor文を回しているので計算量はO(N^2)ですね。

それぞれの考え方としては、

[10,9,2,5,3,7,101,18]

一つ目のfor文でreversedで要素を逆順に取り出すのをfor文で回し、二つ目のfor文でi+1からnumsの範囲で回します。

この処理をテストケースの中で見てみると以下のようになります。

# nums[i]
101  
7  
7  
3  
3  
3  
5  
5  
5  
5  
2  
2  
2  
2  
2  
9  
9  
9  
9  
9  
9  
10  
10  
10  
10  
10  
10  
10

# nums[j]
18  
101  
18  
7  
101  
18  
3  
7  
101  
18  
5  
3  
7  
101  
18  
2  
5  
3  
7  
101  
18  
9  
2  
5  
3  
7  
101  
18

これらの大小を比較し仮にnums[j]がnums[i]よりも大きい場合、すなわち増加している場合は、用意したdpに代入し続けるときちんとそれぞれの増加する部分列の長さが入っていることが分かります。

# dp
[2, 2, 4, 3, 3, 2, 1, 1]

そして最終的にmax関数で最大値を抽出して返せば通ります。

YouTubeとか見てみると解説動画が多いのでいろんな動画を見てみましたが、やはりDPで解いている人が多い印象ですし、中にはDPの練習として非常に良い問題だと言っていたのでDPの練習をしたい人には良い問題かもしれません。

では今回はここまで。お疲れ様でした。