資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告