Re: [閒聊] 每日LeetCode已回收
https://leetcode.com/problems/largest-divisible-subset/description
368. Largest Divisible Subset
給你一個陣列nums，找出由他的元素組成的最大子集合，所有元素滿足
nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0，如果有多個解返回任意一個。
思路：
1.首先把陣列排序，這樣在判斷是否滿足的時候只需要後面的除前面。
2.明顯動態規劃，令 dp[i] 為把 i 位置當結尾的最大子集合，每個子集合初始化為
{nums[i]}。
3.遍歷所有 i 前面的最大子集合，如果滿足 nums[i] % nums[j] == 0 表示 nums[i]
可以加入到 dp[j] 的最大子集合變成一個更大的子集合，令 dp[i] 為這些子集合中
大小最大的。
4.在算的時候用 dp[i] 去更新 res。
Java Code：
-----------------------------------------
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
List<Integer> res = new ArrayList<>();
List<Integer>[] dp = new List[n];
for (int i = 0; i < n; i++) {
dp[i] = new ArrayList<>();
dp[i].add(nums[i]);
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && dp[j].size() + 1 >
dp[i].size()) {
List<Integer> list = new ArrayList<>(dp[j]);
list.add(nums[i]);
dp[i] = list;
}
}
if (dp[i].size() > res.size()) {
res = dp[i];
}
}
return res;
}
}
-----------------------------------------
--
https://i.imgur.com/PIoxddO.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707452722.A.8FB.html
※ 編輯: Rushia (122.100.73.13 臺灣), 02/09/2024 12:26:22
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 664 之 719 篇)：