ሊከፋፈሉ የሚችሉ ጥንዶች ቆጠራ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ ማሂንድራ ኮምቪቫ በ Oracle
ሰልፍ ተለዋዋጭ ፕሮግራም ሃሽ ሃምሽንግ

ሊከፋፈሉ የሚችሉ ጥንዶች ከቃለ-መጠይቁ ተወዳጅ ችግር አንዱ ነው ፡፡ ይህ ችግር በቃለ መጠይቆች ላይ ያሉ የችሎታ ክህሎቶችን እንደ ድርድር እና ሃሽ-ካርታዎች ባሉ ርዕሶች ላይ ዕውቀትን ለመፈተሽ በቂ ነው ፡፡

የችግር መግለጫ

የመምረጥ ተሰጥቶናል ልዩ አዎንታዊ ቁጥሮች።

ምን ለማግኘት?

በንዑስ ክፍል ውስጥ እያንዳንዱ ንጥረ ነገር አንድ ደንብ ይከተላል ፡፡

  1. ንጥረ ነገር (i)% ንጥረ ነገር (j) = 0
  2. ንጥረ ነገር (j)% ንጥረ ነገር (i) = 0

ማለትም እያንዳንዱ ንጥረ ነገር ሌላውን አካል ይከፍላል።

አቀራረብ -1

የደስታ ኃይል

መለስተኛ ጥንዶችን ለመቁጠር የጃቫ ኮድ

class Solution 
{
    public int largestDivisibleSubset(int[] nums) 
    {
    int count=0;
    for(int i=0;i<nums.length;i++)
    {
        for(int j=i+1;j<nums.length;j++)
        {
            if(nums[i]%nums[j]==0 || nums[j]%nums[i]==0)
                count++;
        }
    }
    return count;
    }
}

መለኮታዊ ጥንዶችን ለመቁጠር የ C ++ ኮድ

class Solution
{
public:
    int largestDivisibleSubset(vector<int>& nums) 
    {
    vector<int>data;
    int count=0;
    for(int i=0;i<nums.size();i++)
    {
        for(int j=i+1;j<nums.size();j++)
        {
            if(nums[i]%nums[j]==0 || nums[j]%nums[i]==0)
                count++;
        }
    }
    return count;
    }
};
[1,2,3,9]
3

የጊዜ ውስብስብነት = ኦ (n ^ 2)

ለምን?

  • ከላይ በተጠቀሰው ኮድ ውስጥ ሁለት ቀለበቶች ይሰራሉ
  • በመጀመሪያ የመጀመሪያውን ንጥረ-ነገር (ኦ) ን በመያዝ በድርድሩ ላይ የሚሄድ ሉፕ
  • በሁለተኛ ደረጃ ፣ የመጀመሪያውን ዑደት ውስጥ እየሮጠ ያለው ዑደት ሁለተኛውን ንጥረ-ነገር ይይዛል (O)
  • ለማጠቃለል ያህል ፣ የጊዜ ውስብስብነት (O n 2) እንጨርሳለን

የቦታ ውስብስብነት = ኦ (1)

ትንሽ ማስተካከያ

ከሁሉም ንዑስ ክፍሎች ትልቁን የሚከፋፍል ንዑስ ክፍል እንዲመልሱ ቢጠየቁስ?

ከዚያ የተወሰኑ ተከታታይ ጥንዶችን ለመቁጠር እና እንዲሁም ከቃለ መጠይቁ ለመሸሽ ሊያስቡ ይችላሉ !. አይጨነቁ ፣ እኔ ማድረግ እና መፍትሄውን ለመረዳት በቀለሉ ጀርባዎን አግኝቻለሁ ፡፡ በመጀመሪያ አቀራረብን በሚጠቀሙባቸው አራት ቀላል ደረጃዎች እከፍላለሁ ዲፒ.

  • በመጀመሪያ ድርድርን መደርደር
  • ድርድርን መደርደር የድርድሩ ክፍፍሎች በፊቱ እንዲታዩ ያረጋግጣል
  • በሁለተኛ ደረጃ ፣ የድርድር ቆጠራ ይፍጠሩ
  • የቆጠራ ድርድር ያጋጠሙትን ቁጥር አካፋዮች ቁጥር ያከማቻል
  • ትልቁን ንዑስ ክፍል እንደፈለግን በ ውስጥ እናልፋለን ብዛት ትልቁን ትልቁን አግኝ
  • በሶስተኛ ደረጃ ከኤለመንቱ ውስጥ ንዑስ ክፍሎቹን በማጠናቀቅ አካፋዮችን እንጨምራለን

አንድ ነጠላ ስዕል ለሺ ቃላት እንደሚናገር እንደ እኔ በስዕል ተመሳሳይ ልስጥ

ሊከፋፈሉ የሚችሉ ጥንዶች ማጠቃለያ
ሊከፋፈሉ የሚችሉ ጥንዶች ማጠቃለያ

የጃቫ ኮድ

class Solution
{
    public List<Integer> largestDivisibleSubset(int[] nums) 
    {
        Arrays.sort(nums);
        List<Integer>lisa=new ArrayList<Integer>();
        if(nums.length==0)
            return lisa;
        int count[]=new int[nums.length];
        int max=Integer.MIN_VALUE;
        Arrays.fill(count,1);
        for(int i=1;i<nums.length;i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(nums[i]%nums[j]==0)
                    count[i]=Math.max(count[i],count[j]+1);
            }
        }
        int maxid=0;
        for(int i=1;i<nums.length;i++)
        {
            if(count[i]>count[maxid])
            {
                maxid = count[i] > count[maxid] ? i : maxid;
            }
        }
        int temp=nums[maxid];
        int curr=count[maxid];
        for(int i=maxid;i>=0;i--)
        {
            System.out.println(nums[i]+" "+temp+" "+count[i]);
            if(temp%nums[i]==0 && count[i]==curr)
            {
                lisa.add(nums[i]);
                temp=nums[i];
                curr--;
            }
        }
        return lisa;
    }
}

ሲ ++ ኮድ

class Solution
{
public:
    int maxs(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end()); 
        vector<int>lisa;
        if(nums.size()==0)
            return lisa;
        vector<int>count(nums.size(),1);
        for(int i=1;i<nums.size();i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(nums[i]%nums[j]==0)
                    count[i]=maxs(count[i],count[j]+1);
            }
        }
        int maxid=0;
        for(int i=1;i<nums.size();i++)
        {
            if(count[i]>count[maxid])
            {
                maxid = count[i] > count[maxid] ? i : maxid;
            }
        }
        int temp=nums[maxid];
        int curr=count[maxid];
        for(int i=maxid;i>=0;i--)
        {
            if(temp%nums[i]==0 && count[i]==curr)
            {
                lisa.push_back(nums[i]);
                temp=nums[i];
                curr--;
            }
        }
        return lisa;
    }
};

ለተለያዩ ጥንዶች ውስብስብነት ትንተና

የተፈጠረው የጊዜ ውስብስብነት = ኦ (n ^ 2)

እኛ የምንፈልገው ቦታ = O (n)

የተጠቀሰው ጊዜ እና የቦታ ውስብስብ ነገሮች እንዴት እንደደረስን መፍረስ

የቦታ ውስብስብነት

  • ሁለት ተጨማሪ ቦታዎችን እንፈጥራለን
  • ውጤቱን ለማከማቸት የመጀመሪያ-ድርድር
  • ከፍተኛው የድርድር ርዝመት - የግብዓት ድርድር ርዝመት = O (n)
  • የንዑስ ክፍሎችን ርዝመት ለማከማቸት ሁለተኛ-ድርድር
  • የድርድር ርዝመት-የግብዓት ድርድር = O (n)

የጊዜ ውስብስብነት

  • በመጀመሪያ ደረጃ ድርድርን ለመደርደር የተደረገው ጊዜ = O (n log n)
  • በሁለተኛ ደረጃ ፣ ንዑስ ንጣፎችን ለማግኘት የተደረገው ጊዜ = O (n ^ 2)
  • እንዴት?
  • ሁለት ቀለበቶችን እናካሂዳለን ፡፡
  • የውጪው ዑደት እያንዳንዱን ንጥረ ነገር ከድርድሩ ግምት ውስጥ ያስገባል
  • የውስጠኛው ዑደት የአከፋፋዮችን ቁጥር ለመጨመር ይረዳል
  • በመጨረሻም ፣ ይህ ሁሉ ወደ O ውስብስብነት ይመራል (n ^ 2) + O (nlogn)
  • N ^ 2 ትልቅ መሆን የጠቅላላው ችግር ጊዜ ውስብስብ ያደርገዋል O (n ^ 2)