Քարեր տեղափոխելը մինչև հաջորդ Leetcode լուծումը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են facebook
Ինտելեկտուալ խաղ

Խնդիրի հայտարարություն

Այս խնդրում մեզ տրվում են երեք քարեր a, b և c դիրքերում: Մենք պետք է դրանք դարձնենք հաջորդական ՝ կատարելով հետևյալ քայլը մեկ կամ մի քանի անգամ:
Յուրաքանչյուր քայլում մենք կընտրենք ձախ կամ աջ քար և մի տեղ կդնենք ձախից աջ քարի միջակայքում:
Եկեք ավելի լավ կանգնենք սա ՝ հետևելով նկարին.
Քարեր տեղափոխելը մինչև հաջորդ 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:

Մոտեցում

Նախ խոսենք այն մասին, թե ինչպես կարելի է հաշվարկել առավելագույն քայլերը: Կարո՞ղ ենք պարզապես ասել, որ շարժումների քանակը առավելագույնը կլինի միայն այն դեպքում, երբ ծայրահեղ ծայրամասում գտնվող երկու քարերն էլ 1 միավորով մոտենան միջին քարին:
Այսպիսով, ձախ քարի և միջին քարի միջև դիրքերի քանակը + միջին քարի և աջ քարի միջև դիրքի քանակը կլինի մեր հաջորդականության համար մեր առավելագույն քայլերի քանակը:
Քարեր տեղափոխելը մինչև հաջորդ Leetcode լուծումը
Այժմ հիմնական խնդիրն այն է, թե ինչպես հաշվարկել քայլերի նվազագույն քանակը: Մենք կարող ենք նվազագույնը պարզել ՝ հասկանալով հետևյալը պայմաններ.
Եկեք զանգահարենք ձախ քարի և միջին քարի միջև դիրքերի քանակը lspace է, իսկ միջին քարի և աջ քարի միջև դիրքերի քանակը `տարածություն:
Հաջորդ 4 իրավիճակներից միայն մեկը կարելի է ասել այս քարերի նախնական դիրքի մասին:

1. Եթե քարերն արդեն հաջորդական են, այսինքն lspace = 0 և rspace = 0, ապա min_steps = 0:

Քարեր տեղափոխելը մինչև հաջորդ Leetcode լուծումը2. Այլապես, եթե երեք քարերից երկուսը հաջորդական են, այսինքն, եթե lspace = 0 կամ rspace = 0, ապա մենք կարող ենք պարզապես քարի մեծ մասը դնել միջին քարի վրա ընդամենը 1 քայլով, այդպիսով min_steps = 1:

Ինտելեկտուալ խաղ3. Ուրիշ, եթե երեք քարերից որևէ մեկի միջև տարածությունը 1 է, այսինքն, եթե lspace = 1 կամ rspace = 1: Այնուհետև ամենաքիչը քարը կարող է դրվել երկու մոտ քարերի արանքում (նշենք, որ քարերի մոտակայքում ընդամենը մեկ դիրք կա) միայն մեկ քայլով:
Հետևաբար, դրանք անընդմեջ դարձնելը կարող է տեղի ունենալ ընդամենը 1 քայլում: Այսպիսով, min_steps = 1:

Ինտելեկտուալ խաղ4. Ուրիշ ծայրերում գտնվող քարերը կարող են դրվել միջին քարերի հարևանությամբ `յուրաքանչյուրը 1 աստիճանով: Այսպիսով, min_steps = 1 + 1 = 2:
Քարեր տեղափոխելը մինչև հաջորդ 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 լուծումը

Timeամանակի բարդություն

O (1): Մենք պարզապես օգտագործել ենք պարզ պայմանական հայտարարություններ մեր ալգորիթմում: Այսպիսով, ժամանակի բարդությունը O է (1):

Տիեզերական բարդություն 

O (1): Բացի փոփոխականներից, ինչպիսիք են ձախը, աջը, lspace- ն, 2-ի չափի զանգվածը և այլն, մենք լրացուցիչ տարածք չենք ստեղծել, ուստի տարածության բարդությունը նույնպես O է (1):