เซตย่อยที่หารมากที่สุดใน C++

สมมติว่าเรามีชุดของจำนวนเต็มบวกที่แตกต่างกัน เราต้องหาเซตย่อยที่ใหญ่ที่สุดเพื่อให้ทุกคู่เช่น (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 array

• สร้างสองอาร์เรย์ len และพาร์ขนาด n เริ่มต้น len โดย 1 และพาร์ด้วย 0

• สำหรับฉันอยู่ในช่วง 1 ถึง n – 1

  • พาร์[i] :=ฉัน

  • สำหรับ j ในช่วง 0 ถึง i – 1

    • ถ้า nums[i] mod nums[j] =0 และ len[j] + 1> len[i] แล้ว

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

      • พาร์[i] :=j

  • ถ้า len[j]> retLen แล้ว retLen :=len[i] และ endpoint :=i

• ใส่ nums[endPoint] ลงใน ret

• ในขณะที่จุดสิ้นสุดไม่เหมือนกับ 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, ]