સતત લેટકોડ સોલ્યુશન સુધી સ્ટોન્સ ખસેડવું


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે ફેસબુક
મગજ કા .નાર

સમસ્યા નિવેદન

આ સમસ્યામાં, અમને એ, બી અને સી પોઝિશન્સ પર ત્રણ પત્થરો આપવામાં આવે છે. આપણે તેમને નીચેના પગલામાં એક કે વધુ વખત સળંગ બનાવવું છે.
દરેક પગલામાં, અમે ડાબો પત્થર અથવા જમણો પથ્થર પસંદ કરીશું અને ક્યાંક ડાબીથી જમણા પથ્થરની રેન્જની વચ્ચે મૂકીશું.
ચાલો નીચેના ચિત્ર દ્વારા આને વધુ સારી રીતે ઉભા કરીએ:
સતત લેટકોડ સોલ્યુશન સુધી સ્ટોન્સ ખસેડવું
આ પથ્થરોને સતત બનાવવા માટે આપણે આવા ન્યુનત્તમ અને મહત્તમ સંખ્યા બંનેનો જવાબ આપવો પડશે.

ઉદાહરણ

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

સમજૂતી: પથ્થરને 5 થી 3 સુધી ખસેડો, અથવા પથ્થરને 5 થી 4 થી ખસેડો.

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

આપણે કોઈ ચાલ કરી શકતા નથી.

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

1 થી 4 માં પથ્થર ખસેડો; અથવા પત્થરને 1 થી 2 થી 4 સુધી ખસેડો.

અભિગમ

પ્રથમ ચાલો મહત્તમ પગલાઓની ગણતરી કેવી રીતે કરવી તે વિશે વાત કરીએ. શું આપણે એમ કહી શકીએ નહીં કે ચાલની સંખ્યા ત્યારે જ મહત્તમ હશે જ્યારે ચરમસીમાના બંને પત્થરો 1 એકમ દ્વારા મધ્ય પત્થરની નજીક આવશે.
આમ ડાબી પથ્થર અને મધ્ય પથ્થર વચ્ચેના સ્થાનોની સંખ્યા + મધ્ય પથ્થર અને જમણા પથ્થર વચ્ચેની સ્થિતિની સંખ્યા, તેમને સતત બનાવવા માટે અમારી મહત્તમ પગલાં હશે.
સતત લેટકોડ સોલ્યુશન સુધી સ્ટોન્સ ખસેડવું
હવે મુખ્ય સમસ્યા એ છે કે ન્યુનત્તમ પગલાઓની ગણતરી કેવી રીતે કરવી. આપણે નીચેની બાબતોને સમજીને ન્યૂનતમ શોધી શકીએ શરતો.
ચાલો ડાબા પથ્થર અને મધ્ય પથ્થર વચ્ચેની સ્થિતિની ક lલ લspસ્પેસ છે અને મધ્ય પથ્થર અને જમણા પથ્થર વચ્ચેના સ્થાનોની સંખ્યા આરએસપીસ છે.
આ પત્થરોની પ્રારંભિક સ્થિતિ વિશે નીચેની 4 પરિસ્થિતિમાંથી ફક્ત એક જ કહી શકાય.

1. જો પત્થરો પહેલેથી જ સળંગ હોય છે, જેમ કે lspace = 0 અને rspace = 0 તો મિનિટ_સ્ટેપ્સ = 0.

સતત લેટકોડ સોલ્યુશન સુધી સ્ટોન્સ ખસેડવું2. બાકી જો ત્રણમાંથી બે પથ્થરો સળંગ હોય એટલે કે જો lspace = 0 અથવા rspace = 0 હોય, તો આપણે ફક્ત એક પગથિયામાં મધ્ય પથ્થરની નજીકના ભાગમાં સૌથી વધુ પત્થર મૂકી શકીએ છીએ આમ મીન_સ્ટેપ્સ = 1.

મગજ કા .નારSe. બીજું જો ત્રણ પત્થરોમાંથી કોઈપણ બે વચ્ચેની જગ્યા 3 છે, જો lspace = 1 અથવા rspace = 1. પછી, એકદમ પગથિયામાં સૌથી નજીકના પથ્થરને નજીકના બે પથ્થરો (નોંધવું કે નજીકના પત્થરોની વચ્ચે ફક્ત એક જ સ્થિતિ છે) વચ્ચે મૂકી શકાય છે.
તેથી, તેમને સતત બનાવવું ફક્ત 1 પગલામાં થઈ શકે છે. આમ, મિનિટ_સ્ટેપ્સ = 1.

મગજ કા .નારSe. અન્ય બંને પથ્થરો પર પત્થરો મધ્ય પથ્થરોના પડોશીમાં દરેક 4 પગલું દ્વારા મૂકી શકાય છે. આમ, મિનિટ_સ્ટેપ્સ = 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

સતત લેટકોડ સોલ્યુશન સુધી સ્ટોન્સ ખસેડવાની જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (1): અમે અમારા અલ્ગોરિધમનમાં હમણાં જ સરળ શરતી વિધાનોનો ઉપયોગ કર્યો છે. આમ, સમય જટિલતા ઓ (1) છે.

અવકાશ જટિલતા 

ઓ (1): ડાબી, જમણી, lspace, કદ 2 ની અન્સ એરે જેવા ચલો સિવાય, આપણે કોઈ વધારાનું સ્થાન બનાવ્યું નથી, તેથી જગ્યાની જટિલતા પણ ઓ (1) છે.