#LeetCode:368. Largest Divisible Subset

灆洢 2020-06-14 02:09:37

此題要從給予的數字集合中,找出一個可兩兩成為整除關係的最大子集合為何。

先將數字從小到大排好,接著利用動態規劃(Dynamic Programming)紀錄每個數字 i 若是以其當作子集合中最大數字的話,最多可以做出多大的互相兩兩整除的子集合的數量 count[i],則 \(count[i] = max(1, count[j_1] + 1, count[j_2] + 1, count[j_3] + 1, …), j_n \in \{ j_n < i \land j_n \mid i \}\),並且在找到最大值的時候也順便紀錄找到的 j 是哪個,這樣就可以在找到最大數量後,透過這個 j 回推出整個子集合有哪些元素。

Kotlin(256ms)

/*******************************************************
 * LeetCode 368. Largest Divisible Subset              *
 * Author: Maplewing [at] knightzone.studio            *
 * Version: 2020/06/14                                 *
 *******************************************************/
class Solution {
    fun largestDivisibleSubset(nums: IntArray): List<Int> {
        if (nums.size <= 1) return nums.toList()

        val sortedNumbers = nums.sorted()
        val divisibleSubsetCount = IntArray(sortedNumbers.size, { 1 })
        val previousElementIndexInSubset = IntArray(sortedNumbers.size, { it })

        var maxCount = 1
        var maxSubsetEndIndex = 0
        for (i in 1..sortedNumbers.lastIndex) {
            for (j in 0..i - 1) {
                if (sortedNumbers[i] % sortedNumbers[j] == 0) {
                    val count = divisibleSubsetCount[j] + 1
                    if (count > divisibleSubsetCount[i]) {
                        divisibleSubsetCount[i] = count
                        previousElementIndexInSubset[i] = j

                        if (count > maxCount) {
                            maxCount = count
                            maxSubsetEndIndex = i
                        }
                    }
                }
            }
        }

        var index = maxSubsetEndIndex
        var result = IntArray(maxCount)
        for (i in 0 until maxCount) {
            result[i] = sortedNumbers[index]
            index = previousElementIndexInSubset[index]
        }
        return result.reversed()
    }
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料