सलग लेटकोड सोल्यूशन पर्यंत स्टोन्स हलवित आहे


अडचण पातळी सोपे
वारंवार विचारले फेसबुक
ब्रेनटीझर

समस्या विधान

या समस्येमध्ये, आपल्याला अ, ब आणि सी या तीन स्थानांवर दगड दिले जातात. आम्हाला पुढील चरण एक किंवा अधिक वेळा करून सलग बनवावे लागेल.
प्रत्येक चरणात, आम्ही डावा दगड किंवा उजवा दगड निवडू आणि डावीकडून उजवीकडे दगडांच्या दरम्यान कुठेतरी ठेवू.
चला खालील चित्रानुसार हे चांगले उभे करूयाः
सलग लेटकोड सोल्यूशन पर्यंत स्टोन्स हलवित आहे
हे दगड सलग बनविण्यासाठी आम्हाला किमान आणि कमाल अशा दोन्ही चरणांचे उत्तर द्यावे लागेल.

उदाहरण

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

स्पष्टीकरणः stone ते from वर दगड हलवा किंवा दगड 5 ते to ते move वर हलवा.

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

आम्ही कोणतीही हालचाल करू शकत नाही.

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

1 ते 4 पर्यंत दगड हलवा; किंवा दगड 1 ते 2 ते 4 पर्यंत हलवा.

दृष्टीकोन

प्रथम जास्तीत जास्त चरणांची गणना कशी करावी याबद्दल चर्चा करूया. आम्ही इतकेच म्हणू शकत नाही की टोकाच्या दोन्ही दगड 1 युनिटद्वारे मध्यम दगडांच्या जवळ येतील तेव्हाच यानुरूपांची संख्या जास्तीत जास्त असेल.
अशा प्रकारे डावे दगड आणि मध्यम दगड यांच्या दरम्यान असलेल्या पोझिशन्सची संख्या + मध्य दगड आणि उजवा दगड यांच्यामधील स्थितीची संख्या ही त्यांची सलग करण्यासाठी आम्ही जास्तीत जास्त पायर्‍या असू शकतो.
सलग लेटकोड सोल्यूशन पर्यंत स्टोन्स हलवित आहे
आता मुख्य अडचण म्हणजे किमान चरणांची गणना कशी करावी. आम्ही खालील गोष्टी समजून घेऊन कमीतकमी शोधू शकतो परिस्थिती.
डावा दगड आणि मध्यम दगड यांच्यामधील स्थानांची संख्या lspace आणि मध्य दगड आणि उजवा दगड यांच्यामधील पोझिशन्सची संख्या आरपीएस आहे.
या दगडांच्या प्रारंभिक स्थितीबद्दल खालील 4 परिस्थितींपैकी फक्त एक परिस्थितीच सांगता येईल.

1. जर दगड आधीपासूनच सलग असतील म्हणजेच lspace = 0 आणि rspace = 0 तर min_steps = 0.

सलग लेटकोड सोल्यूशन पर्यंत स्टोन्स हलवित आहे२. जर अन्य तीन दगडांपैकी दोन दगड सलग असतील तर, जर स्पेस = ० किंवा आरएसपीस = ० असेल तर आपण फक्त मध्यभागी दगडाच्या जवळजवळ सर्वात जास्त दगड फक्त १ चरणात ठेवू शकतो अशा प्रकारे मि_स्टेप्स = १.

ब्रेनटीझर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) आहे.