資訊專(zhuān)欄INFORMATION COLUMN
摘要：讓數(shù)組從小到大排序。因?yàn)槿绻粋€(gè)數(shù)能被加到這個(gè)中的話(huà)，說(shuō)明這個(gè)數(shù)能被這個(gè)中的最大的數(shù)整除。同樣可以用一個(gè)數(shù)組來(lái)記錄之前搜索過(guò)的。，表示的是我們搜索的路徑是從到。初始化這個(gè)位置是頭結(jié)點(diǎn)。說(shuō)明是，并沒(méi)有是當(dāng)前最大的里的最大值。
LeetCode[368] Largest Divisible Subset
DPGiven a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si
% Sj = 0 or Sj % Si = 0.If there are multiple solutions, return any subset is fine.
Example 1:
nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok) Example 2:
nums: [1,2,4,8]
Result: [1,2,4,8]
復(fù)雜度
O(N^2),O(N)
思路
先要sort這個(gè)數(shù)組。讓數(shù)組從小到大排序。因?yàn)槿绻粋€(gè)數(shù)能被加到這個(gè)list中的話(huà)，說(shuō)明這個(gè)數(shù)能被這個(gè)list中的最大的數(shù)整除。所以需要先sortlist。
同樣可以用一個(gè)數(shù)組來(lái)記錄之前搜索過(guò)的path。prev[i] = j，表示的是我們搜索的路徑是從j到i。同樣用來(lái)保存搜索路徑的方法還有，用一個(gè)list然后進(jìn)行backtracking，也可以用來(lái)記錄。
同樣的應(yīng)用還可以用在union find上面。
代碼
public ListlargestDivisibleSubset(int[] nums) { List res = new ArrayList (); if(nums == null || nums.length == 0) return res; int[] dp = new int[nums.length]; // 保留一個(gè)數(shù)組的里面的數(shù)的Path的方法，可以用數(shù)組存index這樣做。 int[] prev = new int[nums.length]; Arrays.sort(nums); int max = 0, index = 0; for (int i = 0; i < nums.length; i++){ dp[i] = 1; // 初始化這個(gè)位置是頭結(jié)點(diǎn)。說(shuō)明prev是-1，并沒(méi)有parent node. prev[i] = -1; for (int j = i - 1; j >= 0; j--){ if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]){ dp[i] = dp[j] + 1; prev[i] = j; } } // dp[i]是當(dāng)前最大的subset里的最大值。 if (dp[i] > max){ max = dp[i]; index = i; } } while (index != -1){ res.add(nums[index]); index = prev[index]; } return res; }
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65219.html
摘要：題目要求假設(shè)有一組值唯一的正整數(shù)數(shù)組，找到元素最多的一個(gè)子數(shù)組，這個(gè)子數(shù)組中的任選兩個(gè)元素都可以構(gòu)成或。只要這個(gè)數(shù)字是前面數(shù)字的倍數(shù)，則構(gòu)成的數(shù)組的長(zhǎng)度則是之前數(shù)字構(gòu)成最長(zhǎng)子數(shù)組加一。 題目要求 Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj)...
368. Largest Divisible Subset 題目鏈接：https://leetcode.com/problems... dp記錄最大的長(zhǎng)度，加parent指針存路徑。dp方程是：dp[i] = max(dp[j]) + 1, if nums[i]%nums[j] == 0 public class Solution { public List largestDivisibl...
摘要：題目解答參考的里的解法，核心思想從小到大，每一位數(shù)都能被比他大的數(shù)整除。對(duì)于從后往前看，找出每一個(gè)可以被它整除的數(shù)的數(shù)組，并更新它作為從這里開(kāi)始，往后最大的，記錄下最大數(shù)組開(kāi)始的地方，并把下一個(gè)數(shù)記在里找出最長(zhǎng)的這個(gè)數(shù)組中的每一個(gè)數(shù) 題目：Given a set of distinct positive integers, find the largest subset such th...
摘要：復(fù)雜度思路考慮對(duì)于每一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，能組成的的。那么并且所以我們需要兩個(gè)返回值，一個(gè)是這個(gè)是不是，另一個(gè)是當(dāng)前的能組成的最大的值。代碼這個(gè)能構(gòu)成一個(gè)這個(gè)不能構(gòu)成一個(gè) LeetCode[333] Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary SearchTree (B...
摘要：深度優(yōu)先搜索復(fù)雜度時(shí)間空間遞歸棧空間思路這道題可以轉(zhuǎn)化為一個(gè)類(lèi)似二叉樹(shù)的深度優(yōu)先搜索。另外需要先排序以滿(mǎn)足題目要求。新的集合要一個(gè)新的，防止修改引用。 Subset I Given a set of distinct integers, nums, return all possible subsets. Note: Elements in a subset must be in n...
閱讀 3067·2021-11-25 09:43
閱讀 1042·2021-11-24 10:22
閱讀 1372·2021-09-22 15:26
閱讀 697·2019-08-30 15:44
閱讀 2475·2019-08-29 16:33
閱讀 3715·2019-08-26 18:42
閱讀 929·2019-08-23 18:07
閱讀 1845·2019-08-23 17:55
