የሁሉም ጎዶሎ ርዝመት ርዝመት ሱባራይስ ሌትኮድ መፍትሔ ድምር


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ LinkedIn
ሰልፍ

የችግሩ መግለጫ

በዚህ ችግር ውስጥ አዎንታዊ የቁጥር ቁጥሮች ይሰጣቸዋል። የተሰጠው ድርድር ሁሉንም ሊሆኑ የማይችሉ ርዝመት ያላቸው ንዑስ ድምርዎችን አንድ ነጠላ ቁጥርን ማስላት እና መመለስ አለብን። አንድ ንዑስ ሰርጓጅ የ ‹ተያያዥ› ተከታይነት ነው ደርድር.

ለምሳሌ

arr = [1,4,2,5,3]
58

ማብራሪያ:

ያልተለመዱ እና ያልተለመዱ ድምር ጥቃቅን ንዑስ ርዕሶች-
[1] = 1 ፣ [4] = 4 ፣ [2] = 2 ፣ [5] = 5 ፣ 3] = 3 ፣ [1,4,2] = 7 ፣ [4,2,5] = 11 ፣ [2,5,3] = 10 ፣ [1,4,2,5,3] = 15
እነዚህን ሁሉ አንድ ላይ ስናክል 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58 እናገኛለን

arr = [1,2]
3

ማብራሪያ:

ያልተለመዱ ርዝመት ያላቸው 2 ንዑስ ክፍሎች ፣ [1] እና [2] ብቻ ናቸው። የእነሱ ድምር 3 ነው።

አቀራረብ (የጭካኔ ኃይል)

ይህንን ችግር በጭካኔ በሀይል ለመፍታት ፣ ለሁሉም ያልተለመዱ ርዝመት ንዑስ ርዕሶች መሄድ እና አጠቃላይ ድምርን ማስላት እና መመለስ ብቻ እንደሆነ ከችግሩ ማየት በጣም ቀላል ነው ፡፡
ቀላል እርምጃዎችን በመከተል ይህንን ተግባራዊ ማድረግ እንችላለን-

1. ተለዋዋጭ ይፍጠሩ ድምር ጠቅላላ ድምርን ለማከማቸት.
2. ለሚጀምሩ ለሁሉም ያልተለመዱ ርዝመት subarrays አንድ ለ loop ያሂዱ ብቻ= 1 እና እሴቱን በ 2 እየጨመሩ ይቀጥሉ ብቻ <= n (የድርድሩ መጠን)።
3. በዚህ ሉፕ ውስጥ ፣ አሂድ ሀ መዞር ለንዑስ ክፍሉ መነሻ ቦታ ከ i = 0 እስከ i = n-len
4. ከላይ በተጠቀሰው ዑደት ውስጥ መረጃ ጠቋሚው ከ i የሚጀምር እና በ i + ላይ የሚያልቅ ለዚህ ንዑስ ክፍል አንድ ቀለበት ያካሂዱብቻ-1 እና የዚህን ንዑስ ክፍል ሁሉንም አካላት ያክሉ።
5. በመጨረሻ ተመላሽ ያድርጉ ድምር.

ለሁሉም ጎዶሎዊ ርዝመት ሱባራይስ ሌትኮድ መፍትሔ ድምር መተግበር

C ++ ፕሮግራም

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

የጃቫ ፕሮግራም

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

የሁሉም ጎዶሎ ርዝመት የሱባሪዎች ሌትኮድ መፍትሔ ድምር ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n ^ 3) እያንዳንዱ ቀለበት በሚከተሉት ጊዜያት በሚሠራበት ጎጆ ውስጥ ሶስት ቀለበቶችን በተጠቀመ መልክ ተጠቅመናል-
የመጀመሪያ ዙር n / 2 ጊዜ እየሄደ ነው።
ሁለተኛ ዙር እየሄደ ነው (n-ብቻ) ጊዜያት ፣ የት ብቻ 1,3,4 ነው ፣…።
ሦስተኛው ሉፕ እየሄደ ነው ብቻ ጊዜ.
ጠቅላላ ጊዜ ይሆናል (n / 2) * (n-ብቻ)*ብቻ. ስለዚህ የጊዜ ውስብስብነት የላይኛው ወሰን O (n ^ 3) ይሆናል n የተሰጠው ድርድር መጠን የት ነው?

የቦታ ውስብስብነት 

ኦ (1) የቦታ ውስብስብነት ቋሚ ነው።

አቀራረብ (ጊዜ የተመቻቸ)

ከዚህ ማየት እንደምንችለው ከላይ ከፍ ያለ የኃይል መፍትሄ የ O (n ^ 3) የጊዜ ውስብስብነት አለው ፡፡ ከላይ ባቀረብነው አካሄድ ውስጥ ለተለያዩ ንዑስ መርሃግብሮች አንድ ጊዜ ተመሳሳይ ንጥረ ነገር እየጨመርን ስለሆነ ይህንን መቀነስ እንችላለን። አንድ የተወሰነ አካል ስንት ጊዜ እንደጨመረ ወይም በጠቅላላው ድምር ላይ መጨመር እንደሚገባ የምናውቅ ከሆነ ከኦ (n ^ 3) እስከ O (n) ያለውን የጊዜ ውስብስብነት መቀነስ እንችላለን።

እኛ ሁሉንም ንዑስ ክፍልፋዮች (እንኳን እና ያልተለመደ ርዝመት) ከወሰድን በዚያ ሁኔታ ውስጥ በመረጃ ጠቋሚ ላይ አንድ የተወሰነ ንጥረ ነገር የሚከሰትበት የመነሻ ኢንዴክስ ከእኔ ጋር እኩል በሆነ እና በሁሉም ደረጃዎች ውስጥ እንደሚከሰት መተንተን እንችላለን ፣ እና የማጠናቀቂያ መረጃ ጠቋሚ ከእኔ ጋር እኩል ነው .

ስለዚህ እኛ arr [i] (0-ኢንዴክስ) የያዙት የእነዚያ subarrays ጠቅላላ ብዛት ከ (i + 1) * (ni) ጋር እኩል ይሆናል ማለት እንችላለን።
ይህ እሴት x እንዲሆን ያድርጉ።
ከነዚህ ውስጥ (x + 1) / 2 ያልተለመደ ርዝመት ያላቸው subarrays አሉ arr [i] ን ይ containsል።
እና arr / i ን የያዘ የ x / 2 ርዝመት ርዝመት ንዑስ ርዕሶች።
ስለሆነም በመፍትሔያችን ውስጥ በድምሩ አንድ [i] (x + 1) / 2 ጊዜ አስተዋፅዖ ያደርጋል።

ይህንን በቀላል ምሳሌ ማየት እንችላለን-

አር = [1, 2, 3, 4, 5 ይስጥ]

የሁሉም ጎዶሎ ርዝመት ርዝመት ሱባራይስ ሌትኮድ መፍትሔ ድምር

ስለሆነም የእያንዳንዱ ንጥረ ነገር አስተዋፅኦ ያልተለመደ ነው subarrays = arr [i] * ((i + 1) * (ni) +1) / 2.
ይህ አንድ ነጠላ ዑደት በመጠቀም ሊከናወን ይችላል ስለሆነም ከዚህ ጊዜ የዚህ መፍትሔ ውስብስብነት መስመራዊ ይሆናል ፡፡

ለሁሉም ጎዶሎዊ ርዝመት ሱባራይስ ሌትኮድ መፍትሔ ድምር መተግበር

C ++ ፕሮግራም

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int i=0;i<n;i++)
    {
        int contribution= ((i+1)*(n-i) +1)/2;
        sum+= contribution* arr[i];
    }

    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

የጃቫ ፕሮግራም

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int i=0;i<n;i++)
    {
        int contribution= ((i+1)*(n-i) +1)/2;
        sum+= contribution* arr[i];
    }

    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

የሁሉም ጎዶሎ ርዝመት የሱባሪዎች ሌትኮድ መፍትሔ ድምር ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n): እያንዳንዱን የድርጅት ክፍል አንድ ጊዜ ብቻ ስናቋርጥ ፣ አሁን ውስብስብነት ኦ (n) ይሆናል። የተሰጠው ድርድር መጠን n የት ነው?

የቦታ ውስብስብነት 

ኦ (1) ምንም ተጨማሪ ማህደረ ትውስታ አልተጠቀምንም ፣ ስለሆነም የቦታ ውስብስብነት ቋሚ ይሆናል።