Ҳаракат кардани сангҳо то ҳалли пайдарпайи Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Facebook
Brainteaser

Изҳороти мушкилот

Дар ин масъала, дар мавқеъҳои 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 ва шумораи ҷойҳо байни санги миёна ва санги рост rspace номида шавад.
Дар бораи мавқеи ибтидоии ин сангҳо танҳо 4 ҳолати зеринро гуфтан мумкин аст.

1. Агар сангҳо аллакай пай дар пай бошанд, яъне lspace = 0 ва rspace = 0, пас min_steps = 0.

Ҳаракат кардани сангҳо то ҳалли пайдарпайи Leetcode2. Агар дигаре аз се санг пай дар пай бошад, агар дигаре lspace = 0 ё rspace = 0 бошад, дар сурате, ки мо метавонем танҳо аксари сангҳоро дар наздикии санги миёна танҳо дар 1 қадам гузошта, мин_степс = 1 созем.

Brainteaser3. Дигар аст, агар фосила байни ҳардуи ин се санг 1 бошад, яъне агар lspace = 1 ё rspace = 1. Пас, санги дуртарро дар байни ду санги наздик гузоштан мумкин аст (қайд кунед, ки сангҳои наздик байни онҳо танҳо як мавқеъ доранд) танҳо дар як қадам.
Аз ин рӯ, пай дар пай сохтани онҳо метавонад танҳо дар 1 қадам сурат гирад. Ҳамин тавр, min_steps = 1.

Brainteaser4. Сангҳои ҳарду шадидро метавонанд ба ҳамсояи сангҳои мобайнӣ ҳар як қадам 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

Мураккабии вақт

О (1): Мо танҳо изҳороти оддии шартиро дар алгоритми худ истифода кардем. Ҳамин тавр, мураккабии вақт O (1) мебошад.

Мураккабии фазо 

О (1): Ба ғайр аз тағирёбандаҳо, ба монанди чап, рост, lspace, массиви андозаи 2 ва ғайра, мо ягон фазои иловагӣ ба вуҷуд наовардем, бинобар ин мураккабии фазо низ O (1) аст.