Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

※ 引述 《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，如果有多個解返回任意一個。
→ oin1104: 可是n^2 贏70幾趴欸 這題還有其他解法嗎
思路：
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
推 JIWP: 大師
推 DJYOSHITAKA: 這個記法好猛 少一條陣列捏
推 oin1104: 大師
推 SecondRun: 大師