लगातार Leetcode समाधान सम्म स्टोन्स सार्दै


कठिनाई तह सजिलो
बारम्बार सोधिन्छ फेसबुक
Brainteaser

समस्या वक्तव्य

यस समस्यामा हामीलाई तीन, स्टोन दिइन्छ स्थानहरू ए, बी र सीमा। हामीले तिनीहरूलाई क्रमश: निम्न चरणहरू एक वा बढी पटक प्रदर्शन गर्नुपर्नेछ।
प्रत्येक चरणमा, हामी एउटा देब्रे ढु stone्गा वा दायाँ ढु stone्गा छान्नेछौं र बायाँदेखि दायाँ ढु stone्गाको दायरा बीचको बीचमा राख्नेछौं।
निम्न चित्रको आधारमा यसलाई अझ राम्रोसँग खडा गरौं:
लगातार Leetcode समाधान सम्म स्टोन्स सार्दै
हामी यी दुबै न्यूनतम र अधिकतम संख्यामा यी चरणहरूको लगातार बनाउनको लागि उत्तर दिन सक्छौं।

उदाहरणका

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

स्पष्टीकरण: to देखि from मा ढु Move्गा सार्नुहोस्, वा ढु to्गा 5 देखि to देखि move सम्म सार्नुहोस्।

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

हामी कुनै चाल बनाउन सक्दैनौं।

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

१ देखि from मा ढु stone्गा सार्नुहोस्; वा ढु to्गालाई १ देखि २ देखि move मा सार्नुहोस्।

दृष्टिकोण

पहिले कसरी अधिकतम चरणहरू गणना गर्ने बारेमा कुरा गरौं। के हामी केवल यो भन्न सक्दैनौं कि चालहरूको संख्या अधिकतम हुन्छ केवल जब चरममा रहेका दुई ढु stones्गाहरू मध्य एकाईद्वारा मध्य ढु stone्गाको नजिक आउँछन्।
यसैले बायाँ ढु stone्गा र मध्य ढु stone्गाको बिचको अवस्थाहरूको संख्या + मध्य पत्थर र दायाँ ढु stone्गाको बिचको स्थितिको संख्या तिनीहरूलाई क्रमशः बनाउनको लागि हाम्रो अधिकतम संख्याको हुनेछ।
लगातार Leetcode समाधान सम्म स्टोन्स सार्दै
अब मुख्य समस्या भनेको चरणहरूको न्यूनतम संख्याको हिसाब कसरी गर्ने। हामी निम्नलाई बुझेर न्यूनतम फेला पार्न सक्छौं अवस्था.
बायाँ ढु stone्गा र मध्य पत्थर बिचको स्थानको नम्बर कल गरौं र मध्य पत्थर र दायाँ ढु stone्गाको बिचको अवस्थाहरुको संख्या rspace हो।
यी पत्थरोंको प्रारम्भिक अवस्थाको बारेमा केवल 4 अवस्थामध्ये एउटा मात्र भन्न सकिन्छ।

१. यदि ढु stones्गाहरू पहिले नै क्रमशः अर्थात् lspace = ० र rspace = ० छन् भने मिनेट_स्पेस = ०।

लगातार Leetcode समाधान सम्म स्टोन्स सार्दै२. यदि तीनवटा मध्ये दुई ढु consec्गा लगातार छन् भने, यदि lspace = ० वा rspace = ० भने हामी केवल १ चरणमा मिड ढु near्गा नजिकै धेरै ढु stone्गाहरू राख्न सक्छौं यस प्रकार min_steps = १।

BrainteaserSe. अन्यथा तीन ढु stones्गा मध्ये कुनै दुई बीचको खाली स्थान १ हो भने lspace = १ वा rspace = १। त्यसो भए, सबैभन्दा टाढा ढु stone्गा दुई नजिक ढु stones्गा बीच राख्न सकिन्छ (ध्यान दिनुहोस् कि नजिक ढु stones्गाको बीचमा ती मध्ये एउटा स्थिति हुन्छ) केवल एक चरणमा।
तसर्थ, तिनीहरूलाई लगातार बनाउने मात्र १ चरणमा हुन सक्छ। यसैले, min_steps = १।

BrainteaserSe. अन्यथा दुबै चरममा ढु stones्गालाई मध्य ढु stones्गाको छिमेकीमा प्रत्येक १ पाइलाले राख्न सकिन्छ। यसैले, min_steps = 4 + 1 = 1।
लगातार Leetcode समाधान सम्म स्टोन्स सार्दै

कार्यान्वयन

सी ++ लगातार स्टोभ्स सार्नको लागि लगातार लीटकोड समाधानको लागि कार्यक्रम

#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

लगातार Leetcode समाधान सम्म ढुones्गाहरू सार्नको लागि जाभा कार्यक्रम

#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

लगातार Leetcode समाधान सम्म स्टोन्स सार्नको लागि जटिलता विश्लेषण

समय जटिलता

O (१): हामीले भर्खरै हाम्रो एल्गोरिथ्ममा सरल ससर्त कथनहरू प्रयोग गरेका छौं। यसैले, समय जटिलता ओ (१) हो।

ठाउँ जटिलता 

O (१): बाँया, दायाँ, lspace, आकार २ को एरिज एरेभरीएबलहरू बाहेक, हामीले कुनै अतिरिक्त ठाउँ सिर्जना गरेका छैनौं त्यसैले अन्तरिक्ष जटिलता पनि O (१) हो।