LeetCode日本語修行10日目- [368-最大整除部分集合]
Largest Divisible Subset
参考：https://leetcode.com/problems/largest-divisible-subset/
問題の内容:
正の整数集合nums、それぞれの要素が相異、この中に(answer[i], answer[j])の条件を満足するような最大の部分集合answerを返す。
(answer[i], answer[j])の条件:
answer[i] % answer[j] == 0, または
answer[j] % answer[i] == 0
複数の解がある場合は、そのうちどちらも正しいです。
例:
例1:
Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.
例2:
Input: nums = [1,2,4,8]
Output: [1,2,4,8]
ヒント:
1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 109
All the integers in nums are unique.
このような問題は、基本的DPを使います。今回は
必要の条件は、現在の要素の最大整除部分集合 maxSizeを貰います。
たとえ：
1 2 4 6 8 9
1: 1 ->1
2: 1,2 -> 2
4: 1,2,4 -> 3
6: 1,2,6 -> 3
8: 1,2,4,8 -> 4
9: 1,9 -> 2
1 2 4 6 8 9
1 2 3 3 4 2
そして、最大の8の中に、必ず4,2,1を含めます。
if(nums[i] % nums[j] == 0 && nums[j] % nums[k] == 0){
nums[i] % nums[k] == 0
}
DPの形になりました。
貰ったmaxSizeを格納のdpArrayをトラバーサルして、maxSize対応のvalueを順番で渡す
class Solution {
fun largestDivisibleSubset(nums: IntArray): List<Int> {
var size = nums.size
var dpArray = IntArray(size){1}
var maxSize = 1
var maxValue = dpArray[0]
nums.sort()
for(i in 1 until size){
for(j in 0 until i){
if(nums[i] % nums[j] == 0){
dpArray[i] = Math.max(dpArray[i],dpArray[j]+1)
}
}
if(dpArray[i] > maxSize){
maxSize = dpArray[i]
maxValue = nums[i]
}
}
var answer: MutableList<Int> = mutableListOf()
if(maxSize == 1){
answer.add(nums[0])
return answer
}
var index = size-1
while(index >= 0 && maxSize > 0){
if(dpArray[index] == maxSize && maxValue % nums[index] == 0){
answer.add(nums[index])
maxValue = nums[index]
maxSize--
}
index--
}
return answer
}
}
Author And Source
この問題について(LeetCode日本語修行10日目- [368-最大整除部分集合]), 我々は、より多くの情報をここで見つけました https://qiita.com/Aethey/items/4427d3f1cfc64a3222d5著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .