C ++中最大的可分割子集

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一组不同的正整数，我们必须找到最大子集，以使该子集中的每对像(Si,Sj)的元素都满足：Si mod Sj = 0或Sj mod Si = 0。

因此，如果输入像[1,2,3]，则可能的结果可能像[1,2]或[1,3]

为了解决这个问题，我们将遵循以下步骤-

  • 创建一个数组ret，设置端点：= 0，retLen：= 1，n：= nums的大小

  • 如果n为0，则返回空集

  • 排序nums数组

  • 创建大小为n的两个数组len和par，用1初始化len，用0初始化par

  • 当我在1到n – 1的范围内时

    • 如果nums [i] mod nums [j] = 0且len [j] + 1> len [i]，则

    • len [i]：= len [j] + 1

    • par [i]：= j

    • par [i]：= i

    • 对于0到i – 1范围内的j

    • 如果len [j]> retLen，则retLen：= len [i]和端点：= i

    • 将nums [endPoint]插入ret

    • 而端点与par [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, ]

    以上是 C ++中最大的可分割子集 的全部内容， 来源链接： utcz.com/z/354263.html

    回到顶部