تحريك الأحجار حتى حل Leetcode المتتالي


مستوى الصعوبة سهل
كثيرا ما يطلب في Facebook
دعابة الدماغ

المشكلة بيان

في هذه المسألة ، لدينا ثلاثة أحجار في المواضع أ ، ب ، ج. علينا أن نجعلها متتالية من خلال تنفيذ الخطوة التالية مرة واحدة أو أكثر.
في كل خطوة ، سنختار حجرًا يسارًا أو حجرًا يمينًا ونضعه في مكان ما بين نطاق الحجر من اليسار إلى اليمين.
دعونا نقف هذا بشكل أفضل من خلال الصورة التالية:
تحريك الأحجار حتى حل Leetcode المتتالي
علينا الإجابة على كل من الحد الأدنى والحد الأقصى لعدد هذه الخطوات لجعل هذه الأحجار متتالية.

مثال

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.

الرسالة

لنتحدث أولاً عن كيفية حساب الحد الأقصى للخطوات. لا يمكننا أن نقول ببساطة أن عدد الحركات سيكون الحد الأقصى فقط عندما تقترب كلتا الحجارة في أقصى الحدود من الحجر الأوسط بمقدار وحدة واحدة.
وبالتالي فإن عدد المواضع بين الحجر الأيسر والحجر الأوسط + عدد الموضع بين الحجر الأوسط والحجر الأيمن سيكون الحد الأقصى لعدد الخطوات لجعلها متتالية.
تحريك الأحجار حتى حل Leetcode المتتالي
الآن المشكلة الرئيسية هي كيفية حساب الحد الأدنى لعدد الخطوات. يمكننا معرفة الحد الأدنى من خلال فهم ما يلي شروط.
دعنا نسمي عدد المواضع بين الحجر الأيسر والحجر الأوسط هو lspace وعدد المواضع بين الحجر الأوسط والحجر الأيمن هو rspace.
يمكن قول حالة واحدة فقط من الحالات الأربعة التالية عن الموضع الأولي لهذه الأحجار.

1. إذا كانت الأحجار متتالية بالفعل ، أي: lspace = 0 و rspace = 0 ، فإن min_steps = 0.

تحريك الأحجار حتى حل Leetcode المتتالي2. وإلا إذا كان اثنان من الأحجار الثلاثة متتاليتين ، أي إذا كانت lspace = 0 أو rspace = 0 ، فيمكننا ببساطة وضع معظم الأحجار بالقرب من منتصف الحجر في خطوة واحدة فقط ، وبالتالي فإن min_steps = 1.

دعابة الدماغ3. وإلا إذا كانت المسافة بين أي اثنين من الأحجار الثلاثة هي 1 ، أي إذا كانت lspace = 1 أو rspace = 1. بعد ذلك ، يمكن وضع أكبر عدد من الأحجار بين حجرين قريبين (لاحظ أن الأحجار القريبة لها موقع واحد فقط بينهما) في خطوة واحدة فقط.
ومن ثم ، فإن جعلها متتالية يمكن أن يحدث في خطوة واحدة فقط. وبالتالي ، min_steps = 1.

دعابة الدماغ4. عدا ذلك ، يمكن وضع الحجارة على طرفي الجار في منتصف الأحجار بخطوة واحدة لكل منها. وبالتالي ، فإن min_steps = 1 + 1 = 1.
تحريك الأحجار حتى حل Leetcode المتتالي

تطبيق

برنامج C ++ لنقل الأحجار حتى حل 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

برنامج Java لنقل الأحجار حتى حل 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 المتتالي

تعقيد الوقت

يا (1): لقد استخدمنا للتو عبارات شرطية بسيطة في خوارزمية لدينا. وبالتالي ، فإن تعقيد الوقت هو O (1).

تعقيد الفضاء 

يا (1): بصرف النظر عن المتغيرات مثل اليسار واليمين والمسافة ومصفوفة الحجم 2 وما إلى ذلك ، لم نخلق أي مساحة إضافية وبالتالي فإن تعقيد الفضاء هو O (1).