0%

leetcode Largest Divisible Subset

leetcode Largest Divisible Subset

Given 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:

1
2
3
nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

1
2
3
nums: [1,2,4,8]

Result: [1,2,4,8]

题目地址:leetcode Largest Divisible Subset

题意:给定一个数组,求其中的一个最大子集,要求该子集中任意的两个元素满足 x % y ==0 或者 y % x==0

思路:其实和求最大上升子序列LIS差不多,只不过这题要求输出序列而已。

先把数组排好序。首先要明确,若a<b且b%a==0 ,  b <c 且 c%b==0那么必然有c%a==0

我们设dp[i] 为最大的子集长度,更新的时候保存上一个的下标即可。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
vector<int> ans;
if (nums.empty()) return ans;
sort(nums.begin(), nums.end());
int n = nums.size();
vector<int> dp(n, 1), index(n, -1);
int max_index=0, max_dp=1;
for (int i = 0; i < n; i++) {
for (int j = i - 1; j >=0 ; j--) {
if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
index[i] = j;
}
}
if (max_dp < dp[i]) {
max_dp = dp[i];
max_index = i;
}
}
for (int i = max_index; i != -1; i = index[i])
ans.push_back(nums[i]);
return ans;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> ans = new ArrayList<Integer>();
if (nums.length == 0) return ans;
Arrays.sort(nums);
int n = nums.length;
int[] dp = new int[n], index = new int[n];
Arrays.fill(dp, 1);
Arrays.fill(index, -1);
int max_index = 0, max_dp = 1;
for (int i = 0; i < n; i++) {
for (int j = i - 1 ; j >= 0 ; j--) {
if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
index[i] = j;
}
}
if (max_dp < dp[i]) {
max_dp = dp[i];
max_index = i;
}
}
for (int i = max_index; i != -1; i = index[i])
ans.add(nums[i]);
return ans;
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
def largestDivisibleSubset(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums: return []
nums.sort()
n = len(nums)
dp, index = [1] * n, [-1] * n
max_dp, max_index = 1, 0
for i in xrange(n):
for j in xrange(i-1,-1,-1):
if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
index[i] = j

if max_dp < dp[i]:
max_dp, max_index = dp[i], i

ans = []
while max_index != -1:
ans.append(nums[max_index])
max_index = index[max_index]
return ans


 

本题是leetcode 368 Largest Divisible Subset 题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~