数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的最大可整除子集
假设我们有一组不同的正整数，我们需要找到一个最大的子集，使得该子集中的每一对元素 (Si, Sj) 都满足：Si mod Sj = 0 或 Sj mod Si = 0。
所以如果输入类似 [1,2,3]，则可能的结果可能是 [1,2] 或 [1,3]
为了解决这个问题，我们将遵循以下步骤 -
创建一个数组 ret，设置 endpoint := 0，retLen := 1，n := nums 的大小
如果 n 为 0，则返回空集
对 nums 数组进行排序
创建两个大小为 n 的数组 len 和 par，将 len 初始化为 1，par 初始化为 0
对于 i 的范围从 1 到 n – 1
par[i] := i
对于 j 的范围从 0 到 i – 1
如果 nums[i] mod nums[j] = 0 且 len[j] + 1 > len[i]，则
len[i] := len[j] + 1
par[i] := j
如果 len[j] > retLen，则 retLen := len[i] 且 endpoint := i
将 nums[endPoint] 插入 ret
当 endpoint 不等于 par[endPoint] 时
endpoint := par[endPoint]
将 nums[endPoint] 插入 ret
反转列表 ret 并返回 ret
示例（C++）
让我们看看下面的实现以获得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
vector <int> ret;
int endPoint = 0;
int retLen = 1;
int n = nums.size();
if(!n) return {};
sort(nums.begin(), nums.end());
vector <int> len(n, 1);
vector <int> par(n, 0);
for(int i = 1; i < n; i++){
par[i] = i;
for(int j = 0; j < i; j++){
if(nums[i] % nums[j] == 0 && len[j] + 1 > len[i]){
len[i] = len[j] + 1;
par[i] = j;
}
}
if(len[i] > retLen){
retLen = len[i];
endPoint = i;
}
}
ret.push_back(nums[endPoint]);
while(endPoint != par[endPoint]){
endPoint = par[endPoint];
ret.push_back(nums[endPoint]);
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3};
print_vector(ob.largestDivisibleSubset(v));
}输入
[1,2,3]
输出
[1, 2, ]
更新于: 2020-05-02
76 次浏览
广告