专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
2024年10月11号，上海格力汽车科技有限公司成立，注册资本2000万人民币，最大股东是珠海格力智能装备有限公司。经营范围含汽车零部件研发，汽车零部件及配件制造，工业机器人制造，工业机器人销售等。
对此网友质疑：格力跨界造车，但电动汽车的核心在于电池、电机和电控，这三大件格力是否有技术储备？毕竟跟空调还是差挺多的。
还有网友说：2000万够干嘛，研发一个轮子都够呛。不过2000万对于造车来说确实非常少。我在企查查上查了下小米汽车的注册资本是1000000万元人民币，蔚来汽车是300000万美元，基本上都是上百亿。
而格力2千万的注册资本估计勉强能招20个年薪百万的高级工程师，关键20个人在一年以内也造不出车啊，超过一年工资又不够发了。不过网友的评论也是相当幽默，基本都是调侃，大家可以看下。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第368题：最大整除子集。
问题描述
来源：LeetCode第368题
难度：中等
给你一个由无重复正整数组成的集合 nums ，请你找出并返回其中最大的整 除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
1，answer[i] % answer[j] == 0 ，或
2，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 * 10^9
nums 中的所有整数互不相同
问题分析
这题让找出最长的整除子集，注意这里是子集，不是子序列，所以我们可以对数组进行 排序 ，这样这题就变成了我们前面讲的 。按照前面那题的思路就可以解这道题了。
这里定义dp[i]表示以第 i 个元素为结尾的最长整除子集长度，如果nums[i]能被nums[j]整除(j
但这题让返回的是子集，而不是子集的长度，所有我们还需要记录选择的过程，使用一个变量path来记录。
JAVA：
public List largestDivisibleSubset (int[] nums) {
Arrays.sort(nums);// 先对数组进行排序
int n = nums.length;
int[] dp = new int[n];
int[] path = new int[n];// 记录最大整除子序列的下标
Arrays.fill(dp, 1); // 初始化数组dp的每个值为1
Arrays.fill(path, -1);// 初始 -1 。
int max = 1;// 记录最大整除子集的长度
int maxIndex = 0;// 记录最大整除子集中最后一个元素的下标
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
// 记录路径，表示最大整除子集中 i 前面一个是 j
path[i] = j;
}
}
// 如果找到更大的子集，就记录最大的
if (dp[i] > max) {
max = dp[i];// 最大整除子集长度
maxIndex = i;// 最大整除子集最后一个元素的位置
}
}
// prev很类似于链表，每一个都是记录前一个的位置
List
res = new ArrayList<>(); while (maxIndex != - 1) { res.add(nums[maxIndex]); maxIndex = path[maxIndex]; } return res; }C++：
public:
vector
largestDivisibleSubset(vector
&nums) { sort(nums.begin(), nums.end());// 先对数组进行排序 int n = nums.size(); vector
dp(n, 1); vector
path(n, -1);// 记录最大整除子序列的下标 int max = 1;// 记录最大整除子集的长度 int maxIndex = 0;// 记录最大整除子集中最后一个元素的下标 for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; // 记录路径，表示最大整除子集中 i 前面一个是 j path[i] = j; } } // 如果找到更大的子集，就记录最大的 if (dp[i] > max) { max = dp[i];// 最大整除子集长度 maxIndex = i;// 最大整除子集最后一个元素的位置 } } // prev很类似于链表，每一个都是记录前一个的位置 vector
res; while (maxIndex != -1) { res.push_back(nums[maxIndex]); maxIndex = path[maxIndex]; } return res; }
Python：
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
nums.sort()# 先对数组进行排序
n = len(nums)
dp = [1] * n
path = [-1] * n #记录最大整除子序列的下标
max_len = 1 #记录最大整除子集的长度
max_index = 0 #记录最大整除子集中最后一个元素的下标
for i in range(1, n):
for j in range(i):
if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
path[i] = j #记录路径，表示最大整除子集中 i 前面一个是 j
# 如果找到更大的子集，就记录最大的
if dp[i] > max_len:
max_len = dp[i] #最大整除子集长度
max_index = i # 最大整除子集最后一个元素的位置
res = []
# prev很类似于链表，每一个都是记录前一个的位置
while max_index != -1:
res.append(nums[max_index])
max_index = path[max_index]
return res笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴