做暧暧视频网站在线,wordpress注册侧边栏,网站广告怎样做,php7.3 wordpress给你一个由 无重复 正整数组成的集合 nums #xff0c;请你找出并返回其中最大的整除子集 answer #xff0c;子集中每一元素对 (answer[i], answer[j]) 都应当满足#xff1a; answer[i] % answer[j] 0 #xff0c;或 answer[j] % answer[i] 0 如果存在多个有效解子集请你找出并返回其中最大的整除子集 answer 子集中每一元素对 (answer[i], answer[j]) 都应当满足 answer[i] % answer[j] 0 或 answer[j] % answer[i] 0 如果存在多个有效解子集返回其中任何一个均可。
示例 1
输入nums [1,2,3] 输出[1,2] 解释[1,3] 也会被视为正确答案。 示例 2
输入nums [1,2,4,8] 输出[1,2,4,8]
提示
1 nums.length 1000 1 nums[i] 2 * 109 nums 中的所有整数 互不相同
解题思路
从小到大进行排序每次判断两个元素的整除关系时只需要枚举前面元素判断是否存在整除关系即可。 因为整除关系存在传递性例如12481616整除8以外同时也能整除能被8整除的元素例如 124 因此只需要一个一维数组记录当前元素能够整除元素的个数 状态转移方程为 for j,v:range nums[:i] {//遍历前面元素if nums[i]%v0dp[j]1dp[i]{//当前nums[j]可以被nums[i]整除dp[i]dp[j]1//因此与nums[j]有整除关系的与nums[i]也存在相同的整除关系 //加一是因为与nums[i]与nums[j]也存在整除关系}}
代码
func largestDivisibleSubset(nums []int) []int {sort.Ints(nums)n : len(nums)dp : make([]int, n)for i:range dp{dp[i]1}maxS,maxV:1,nums[0]for i : 1; i n; i {for j,v:range nums[:i] {if nums[i]%v0dp[j]1dp[i]{dp[i]dp[j]1}}if dp[i]maxS{maxS,maxVdp[i],nums[i]}}var res []intif maxS1{resappend(res,maxV)return res}for i : n-1; i 0 ; i-- {if maxS0maxV%nums[i]0dp[i]maxS{maxS--maxVnums[i]resappend(res,maxV)}}return res}
