തുടർച്ചയായ ലീറ്റ്കോഡ് പരിഹാരം വരെ കല്ലുകൾ നീക്കുന്നു


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ഫേസ്ബുക്ക്
ബ്രെയിന്റീസർ

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

ഈ പ്രശ്‌നത്തിൽ, a, b, c എന്നീ സ്ഥാനങ്ങളിൽ ഞങ്ങൾക്ക് മൂന്ന് കല്ലുകൾ നൽകിയിരിക്കുന്നു. ഇനിപ്പറയുന്ന ഘട്ടം ഒന്നോ അതിലധികമോ തവണ നടത്തിക്കൊണ്ട് ഞങ്ങൾ അവയെ തുടർച്ചയായി ആക്കണം.
ഓരോ ഘട്ടത്തിലും, ഞങ്ങൾ ഒരു ഇടത് കല്ല് അല്ലെങ്കിൽ വലത് കല്ല് തിരഞ്ഞെടുത്ത് ഇടത് നിന്ന് വലത് കല്ലിന്റെ പരിധിയിൽ എവിടെയെങ്കിലും ഇടും.
ചിത്രം പിന്തുടർന്ന് ഇത് മികച്ച രീതിയിൽ നിൽക്കാം:
തുടർച്ചയായ ലീറ്റ്കോഡ് പരിഹാരം വരെ കല്ലുകൾ നീക്കുന്നു
ഈ കല്ലുകൾ തുടർച്ചയായി നിർമ്മിക്കുന്നതിന് അത്തരം നടപടികളുടെ ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ എണ്ണം ഞങ്ങൾ ഉത്തരം നൽകണം.

ഉദാഹരണം

a = 1, b = 2, c = 5
[1,2]

വിശദീകരണം: കല്ല് 5 ൽ നിന്ന് 3 ലേക്ക് നീക്കുക, അല്ലെങ്കിൽ കല്ല് 5 ൽ നിന്ന് 4 ലേക്ക് 3 ലേക്ക് നീക്കുക.

a = 4, b = 3, c = 2
[0,0]

ഞങ്ങൾക്ക് ഒരു നീക്കവും നടത്താൻ കഴിയില്ല.

a = 3, b = 5, c = 1
[1,2]

കല്ല് 1 മുതൽ 4 വരെ നീക്കുക; അല്ലെങ്കിൽ കല്ല് 1 മുതൽ 2 വരെ 4 ലേക്ക് നീക്കുക.

സമീപനം

ആദ്യം പരമാവധി ഘട്ടങ്ങൾ എങ്ങനെ കണക്കാക്കാം എന്നതിനെക്കുറിച്ച് സംസാരിക്കാം. അതിരുകടന്ന രണ്ട് കല്ലുകളും 1 യൂണിറ്റ് നടുക്ക് കല്ലിനടുത്ത് വരുമ്പോൾ മാത്രമേ നീക്കങ്ങളുടെ എണ്ണം പരമാവധി ഉണ്ടാകൂ എന്ന് നമുക്ക് പറയാനാവില്ല.
അങ്ങനെ ഇടത് കല്ലിനും മധ്യ കല്ലിനുമിടയിലുള്ള സ്ഥാനങ്ങളുടെ എണ്ണം + മധ്യ കല്ലിനും വലത് കല്ലിനുമിടയിലുള്ള സ്ഥാനങ്ങളുടെ എണ്ണം തുടർച്ചയായുള്ള ഞങ്ങളുടെ പരമാവധി ഘട്ടങ്ങളായിരിക്കും.
തുടർച്ചയായ ലീറ്റ്കോഡ് പരിഹാരം വരെ കല്ലുകൾ നീക്കുന്നു
ഏറ്റവും കുറഞ്ഞ ഘട്ടങ്ങൾ എങ്ങനെ കണക്കാക്കാം എന്നതാണ് ഇപ്പോൾ പ്രധാന പ്രശ്നം. ഇനിപ്പറയുന്നവ മനസിലാക്കിക്കൊണ്ട് നമുക്ക് മിനിമം കണ്ടെത്താനാകും അവസ്ഥ.
ഇടത് കല്ലിനും മധ്യ കല്ലിനുമിടയിലുള്ള സ്ഥാനങ്ങളുടെ എണ്ണം lspace എന്നും മധ്യ കല്ലിനും വലത് കല്ലിനുമിടയിലുള്ള സ്ഥാനങ്ങളുടെ എണ്ണം rspace എന്നും വിളിക്കാം.
ഈ കല്ലുകളുടെ പ്രാരംഭ സ്ഥാനത്തെക്കുറിച്ച് ഇനിപ്പറയുന്ന 4 സാഹചര്യങ്ങളിൽ ഒന്ന് മാത്രമേ പറയാൻ കഴിയൂ.

1. കല്ലുകൾ ഇതിനകം തുടർച്ചയായി അതായത് lspace = 0 ഉം rspace = 0 ഉം ആണെങ്കിൽ min_steps = 0.

തുടർച്ചയായ ലീറ്റ്കോഡ് പരിഹാരം വരെ കല്ലുകൾ നീക്കുന്നു2. മൂന്ന് കല്ലുകളിൽ രണ്ടെണ്ണം തുടർച്ചയായി ഉണ്ടെങ്കിൽ, അതായത് lspace = 0 അല്ലെങ്കിൽ rspace = 0 ആണെങ്കിൽ, നമുക്ക് ഏറ്റവും കൂടുതൽ കല്ല് നടു കല്ലിന് സമീപം വെറും 1 ഘട്ടത്തിൽ ഇടാം, അങ്ങനെ min_steps = 1.

ബ്രെയിന്റീസർ3. മൂന്ന് കല്ലുകളിൽ രണ്ടെണ്ണം തമ്മിലുള്ള ഇടം 1 ആണെങ്കിൽ lspace = 1 അല്ലെങ്കിൽ rspace = 1 ആണെങ്കിൽ. അതിനുശേഷം, ഏറ്റവും അടുത്തുള്ള രണ്ട് കല്ലുകൾക്കിടയിൽ (അടുത്തുള്ള കല്ലുകൾക്കിടയിൽ ഒരു സ്ഥാനം മാത്രമേ ഉള്ളൂ എന്നത് ശ്രദ്ധിക്കുക) ഒരൊറ്റ ഘട്ടത്തിൽ ഇടാം.
അതിനാൽ, അവയെ തുടർച്ചയായി നിർമ്മിക്കുന്നത് വെറും 1 ഘട്ടത്തിൽ സംഭവിക്കാം. അങ്ങനെ, min_steps = 1.

ബ്രെയിന്റീസർ4. അങ്ങേയറ്റത്തെ കല്ലുകൾ ഒരു പടി വീതം നടുക്ക് കല്ലുകളിൽ ഇടാം. അങ്ങനെ, min_steps = 1 + 1 = 1.
തുടർച്ചയായ ലീറ്റ്കോഡ് പരിഹാരം വരെ കല്ലുകൾ നീക്കുന്നു

നടപ്പിലാക്കൽ

തുടർച്ചയായ ലീറ്റ്കോഡ് പരിഹാരം വരെ കല്ലുകൾ നീക്കുന്നതിനുള്ള സി ++ പ്രോഗ്രാം

#include <bits/stdc++.h>
using namespace std;
vector<int> numMovesStones(int a, int b, int c) 
{
    int left=min(a,min(b,c));
    int right=max(a,max(b,c));
    int mid=(a!=left && a!=right )?a:(b!=left && b!=right)?b:c;
    int lspace=mid-left-1;
    int rspace=right-mid-1;
    int max=lspace+rspace,min=0;
    if(lspace==0 && rspace==0)min=0;
    else if(lspace==0 || rspace==0)min=1;
    else if(lspace==1 || rspace==1)min=1;
    else min=2;
    vector<int> ans{min,max};
    return ans;
}
int main()
{
   vector<int>ans=numMovesStones(1,2,5);
   cout<<ans[0]<<" "<<ans[1]<<endl;
}
1 2

തുടർച്ചയായ ലീറ്റ്കോഡ് പരിഹാരം വരെ കല്ലുകൾ നീക്കുന്നതിനുള്ള ജാവ പ്രോഗ്രാം

#include <bits/stdc++.h>
using namespace std;
vector<int> numMovesStones(int a, int b, int c) 
{
    int left=min(a,min(b,c));
    int right=max(a,max(b,c));
    int mid=(a!=left && a!=right )?a:(b!=left && b!=right)?b:c;
    int lspace=mid-left-1;
    int rspace=right-mid-1;
    int max=lspace+rspace,min=0;
    if(lspace==0 && rspace==0)min=0;
    else if(lspace==0 || rspace==0)min=1;
    else if(lspace==1 || rspace==1)min=1;
    else min=2;
    vector<int> ans{min,max};
    return ans;
}
int main()
{
   vector<int>ans=numMovesStones(1,2,5);
   cout<<ans[0]<<" "<<ans[1]<<endl;
}
1 2

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

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

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

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

O (1): ഇടത്, വലത്, lspace, വലുപ്പം 2 ന്റെ അൻ‌സ് അറേ പോലുള്ള വേരിയബിളുകൾ‌ക്ക് പുറമെ, ഞങ്ങൾ‌ അധിക സ്ഥലമൊന്നും സൃഷ്ടിച്ചിട്ടില്ല, അതിനാൽ‌ സ്ഥല സങ്കീർ‌ണ്ണതയും O (1) ആണ്.