എല്ലാ വിചിത്രമായ നീളം സബ്‌റേകളുടെ ലീറ്റ്‌കോഡ് പരിഹാരത്തിന്റെ ആകെത്തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ലിങ്ക്ഡ്
അറേ

ഉള്ളടക്ക പട്ടിക

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ പോസിറ്റീവ് സംഖ്യകളുടെ ഒരു നിര നൽകിയിരിക്കുന്നു. തന്നിരിക്കുന്ന അറേയുടെ സാധ്യമായ വിചിത്രമായ നീളമുള്ള സബ്‌റേകളുടെ ആകെത്തുക, ഒരൊറ്റ സംഖ്യ കണക്കാക്കുകയും തിരികെ നൽകുകയും വേണം. ന്റെ തുടർച്ചയായ തുടർച്ചയാണ് ഒരു സബ്‌റേ ശ്രേണി.

ഉദാഹരണം

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. ആരംഭിക്കുന്ന എല്ലാ വിചിത്ര നീളമുള്ള സബ്‌റേകൾക്കും ഒരു ഫോർ ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക ലെൻ= 1 എന്നിട്ട് മൂല്യം 2 വർദ്ധിപ്പിക്കുന്നത് തുടരുക ലെൻ <= n (അറേയുടെ വലുപ്പം).
3. ഈ ലൂപ്പിനുള്ളിൽ, a പ്രവർത്തിപ്പിക്കുക ലൂപ്പ് i = 0 മുതൽ i = n-len വരെയുള്ള സബ്‌റേയുടെ സ്ഥാനം ആരംഭിക്കുന്നതിന്.
4. മുകളിലുള്ള ലൂപ്പിനുള്ളിൽ, ഈ സബ്‌റേയ്‌ക്കായി ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക, അതിന്റെ സൂചിക i ൽ നിന്ന് ആരംഭിച്ച് i + ൽ അവസാനിക്കുന്നുലെൻ-1 കൂടാതെ ഈ സബ്‌റേയുടെ എല്ലാ ഘടകങ്ങളും ചേർക്കുക.
5. അവസാനം മടങ്ങുക തുക.

എല്ലാ വിചിത്രമായ നീളം സബ്‌റേയ്‌സ് ലീറ്റ്‌കോഡ് സൊല്യൂഷന്റെ ആകെത്തുക നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം

#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

എല്ലാ വിചിത്രമായ നീളം സബ്‌റേകളുടെ ലീറ്റ്‌കോഡ് പരിഹാരത്തിനായുള്ള സങ്കീർണ്ണ വിശകലനം

സമയ സങ്കീർണ്ണത

O (n ^ 3): ഓരോ ലൂപ്പും ഇനിപ്പറയുന്ന സമയങ്ങളിൽ പ്രവർത്തിക്കുന്ന നെസ്റ്റഡ് രൂപത്തിൽ ഞങ്ങൾ മൂന്ന് ലൂപ്പുകൾ ഉപയോഗിച്ചു:
ആദ്യ ലൂപ്പ് n / 2 തവണ പ്രവർത്തിക്കുന്നു.
രണ്ടാമത്തെ ലൂപ്പ് പ്രവർത്തിക്കുന്നു (n-ലെൻ) തവണ, എവിടെ ലെൻ 1,3,4,….
മൂന്നാമത്തെ ലൂപ്പ് പ്രവർത്തിക്കുന്നു ലെൻ തവണ.
ആകെ സമയം (n / 2) * (n-ലെൻ)*ലെൻ. അതിനാൽ സമയ സങ്കീർണ്ണതയുടെ മുകൾഭാഗം O (n ^ 3) ആയിരിക്കും, ഇവിടെ n എന്നത് തന്നിരിക്കുന്ന അറേയുടെ വലുപ്പമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1): ബഹിരാകാശ സങ്കീർണ്ണത സ്ഥിരമാണ്.

സമീപനം (സമയം ഒപ്റ്റിമൈസ് ചെയ്തു)

മുകളിലുള്ള ബ്ര ute ട്ട് ഫോഴ്‌സ് പരിഹാരത്തിന് O (n ^ 3) സമയ സങ്കീർണ്ണത ഉണ്ടെന്ന് നമുക്ക് കാണാൻ കഴിയും. നമുക്ക് ഇത് ചെറുതാക്കാം, കാരണം മുകളിലുള്ള സമീപനത്തിൽ ഞങ്ങൾ വ്യത്യസ്ത സബ്‌റേകൾക്കായി ഒരേ ഘടകം ഒന്നിലധികം തവണ ചേർക്കുന്നു. ഒരു പ്രത്യേക മൂലകം എത്ര തവണ ചേർത്തുവെന്ന് അല്ലെങ്കിൽ ആകെ തുകയിൽ ചേർക്കണമെന്ന് എങ്ങനെയെങ്കിലും നമുക്കറിയാമെങ്കിൽ, നമുക്ക് സമയ സങ്കീർണ്ണത O (n ^ 3) ൽ നിന്ന് O (n) ലേക്ക് കുറയ്ക്കാൻ കഴിയും.

എല്ലാ സബ്‌റേകളും (ഇരട്ട നീളവും ഇരട്ടയും) എടുക്കുകയാണെങ്കിൽ, അത്തരം സന്ദർഭത്തിൽ സൂചികയിലെ ഒരു പ്രത്യേക ഘടകം എല്ലാ സബ്‌റേകളിലും സംഭവിക്കും, അവയുടെ ആരംഭ സൂചിക എനിക്ക് തുല്യമായതിനേക്കാൾ കുറവാണ്, അവസാനിക്കുന്ന സൂചിക i ന് തുല്യമാണ് .

അതിനാൽ, അറ [i] (0-സൂചികയിലുള്ളത്) അടങ്ങിയിരിക്കുന്ന സബ്‌റേകളുടെ ആകെ എണ്ണം (i + 1) * (ni) ന് തുല്യമാണെന്ന് നമുക്ക് പറയാൻ കഴിയും.
ഈ മൂല്യം x ആയിരിക്കട്ടെ.
അവയിൽ (x + 1) / 2 ഒറ്റ നീളമുള്ള സബ്‌റേകളുണ്ട്, അതിൽ അറ [i] അടങ്ങിയിരിക്കുന്നു.
Ar [i] അടങ്ങിയിരിക്കുന്ന x / 2 ഇരട്ട നീളമുള്ള സബ്‌റേകളും.
അതിനാൽ ഞങ്ങളുടെ പരിഹാരത്തിലെ ആകെ തുകയിൽ ഒരു [i] (x + 1) / 2 തവണ സംഭാവന ചെയ്യും.

ലളിതമായ ഒരു ഉദാഹരണം ഉപയോഗിച്ച് നമുക്ക് ഇത് കാണാൻ കഴിയും:

Arr = [1, 2, 3, 4, 5]

എല്ലാ വിചിത്രമായ നീളം സബ്‌റേകളുടെ ലീറ്റ്‌കോഡ് പരിഹാരത്തിന്റെ ആകെത്തുക

അതിനാൽ ഓരോ മൂലകത്തിന്റെയും സംഭാവന വിചിത്രമായ സബ്‌റേകളിൽ = arr [i] * ((i + 1) * (ni) +1) / 2.
ഒരൊറ്റ ലൂപ്പ് ഉപയോഗിച്ച് ഇത് ചെയ്യാൻ കഴിയും, അതിനാൽ ഈ പരിഹാരത്തിന്റെ സമയ സങ്കീർണ്ണത രേഖീയമായിരിക്കും.

എല്ലാ വിചിത്രമായ നീളം സബ്‌റേയ്‌സ് ലീറ്റ്‌കോഡ് സൊല്യൂഷന്റെ ആകെത്തുക നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം

#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

എല്ലാ വിചിത്രമായ നീളം സബ്‌റേകളുടെ ലീറ്റ്‌കോഡ് പരിഹാരത്തിനായുള്ള സങ്കീർണ്ണ വിശകലനം

സമയ സങ്കീർണ്ണത

O (n): അറേയിലെ ഓരോ ഘടകങ്ങളും ഞങ്ങൾ ഒരു തവണ മാത്രം സഞ്ചരിക്കുമ്പോൾ, സമയ സങ്കീർണ്ണത O (n) ആയിരിക്കും. ഇവിടെ n എന്നത് തന്നിരിക്കുന്ന അറേയുടെ വലുപ്പമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1): ഞങ്ങൾ അധിക മെമ്മറിയൊന്നും ഉപയോഗിച്ചിട്ടില്ല, അതിനാൽ സ്ഥല സങ്കീർണ്ണത സ്ഥിരമായിരിക്കും.