前言
持续更新了
正文
问题来源
本问题来自leetcode上的368题。
问题描述
给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。
如果有多个目标子集，返回其中任何一个均可。
示例 1:
输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)
示例 2:
输入: x = 2, y = 6, z = 5
输出: False
分析：
类似并查集的思想，先讲讲并查集问题。啥假设a,b,c；a，b是朋友；a，c也是朋友；然后a,b,c可以分成一类。做法是初始化时，a，b，c都有一个lead指针指向自身，当有条关系a,b则将follower少的那个指向另外一个，即此时a的leader指针指向自身，b的leader指针指向a；当a，c关系时，会得到a的leader指针指向自身，c的leader指针指向a；当所有节点的递归lead都是同一个时，则可以认为他们是一个团体。
回到这道题，首先将原数组从大到小排序，有两个数字a，b，a在前b在后(b>a)若b mod a == 0，此时有个c数字，c大于a，b，若c mod b == 0，则 c mod a也一定等于0，所以可以直接记录最大的前置即可。
初始化情况，每个元素的前置都是自身，有自身元素的集合元素个数为1。
使用一个一维DP，其含义是题目要求的数组，DP[i]的含义是，从0~i位置满足题目的最长数组。初始化每个dp元素都为1。
使用一个一维parent，记录每个元素的前置，初始化情况，每个元素的前置都是自身。
先用i遍历每个数字，然后用j从后向前寻找能被nums[i]整除的数字，这样如果判断能整除的时候，再判断dp[i] < dp[j] + 1，即对于以i索引结尾的最长的数组是否变长了。在变长的情况下，需要更新dp[i]，同时使用parent[i]更新i的前面能整除的数字。另外还要统计对于整个数组最长的子数组长度。
知道了对于每个位置最长的子数组之后，我们也就知道了对于0~n区间内最长的满足题目条件的数组，最后需要再次遍历，使用parent就能把正儿个数组统计输出出来。因为这个最大的索引mx_index是对n而言的，所以输出是逆序的。
func largestDivisibleSubset(nums []int) []int {
if len(nums) == 0 {
return nil
}
sort.Ints(nums)
//fmt.Println(nums)
parent := make([]int, len(nums))
dp := make([]int, len(nums))
for i := 0; i < len(nums); i++ {
parent[i] = i
dp[i] = 1
}
cmax := 1
k := 0
for i := 1; i < len(nums); i++ {
for j := 0; j < i; j++ {
if nums[i] % nums[j] != 0 {
continue
}
if dp[j] + 1 > dp[i] {
dp[i] = dp[j] + 1
parent[i] = j
}
if dp[i] > cmax {
cmax = dp[i]
k = i
}
}
}
res := make([]int, 0, cmax)
for parent[k] != k {
res = append(res, nums[k])
k = parent[k]
}
res = append(res, nums[k])
return res
}
总结：
勤思考。
结语
不管怎么样好好加油。
