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