Re: [閒聊] 每日LeetCode已回收
※ 引述 《Rushia (みけねこ的鼻屎)》 之銘言：
:
: https://leetcode.com/problems/largest-divisible-subset/description
: 368. Largest Divisible Subset
: 給你一個陣列nums，找出由他的元素組成的最大子集合，所有元素滿足
: nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0，如果有多個解返回任意一個。
→
02/09 14:57,
02/09 14:57
思路：
1.同第一篇，但是不存最大的子集合有哪些元素，只存
當前最大子集合大小 => dp[i]
目前最大的子集合的"最大元素"和"集合大小"
2.我們知道最佳集合的最大元素和集合大小之後，只要當前最大值滿足
「可被整除」且「dp[i] = maxSize」就表示這個元素是包含在最大子集合，
把該數字加入解集合就可以回溯出最大子集合。
Java Code：
---------------------------------------------------------
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int[] dp = new int[n];
int maxVal = nums[0], maxSize = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
if (dp[i] > maxSize) {
maxSize = dp[i];
maxVal = nums[i];
}
}
List<Integer> res = new ArrayList<>();
for (int i = n - 1; i >= 0; i--) {
if (dp[i] == maxSize && maxVal % nums[i] == 0) {
maxSize--;
maxVal = nums[i];
res.add(nums[i]);
}
}
return res;
}
}
---------------------------------------------------------
Beats99.83% 供參
--
https://i.imgur.com/hhXzZJ3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707462623.A.086.html
※ 編輯: Rushia (122.100.73.13 臺灣), 02/09/2024 15:11:20
推
02/09 15:11,
1年前
, 1F
02/09 15:11, 1F
推
02/09 15:15,
1年前
, 2F
02/09 15:15, 2F
推
02/09 15:16,
1年前
, 3F
02/09 15:16, 3F
推
02/09 15:52,
1年前
, 4F
02/09 15:52, 4F
討論串 (同標題文章)
完整討論串 (本文為第 666 之 719 篇)：