Leetcode մրցույթ 296

Խնդիր 1

Min Max Game

Ձեզ տրվում է 0 ինդեքսավորված ամբողջ թվային զանգված nums, որի երկարությունը 2 հզորություն է:

Կիրառեք հետևյալ ալգորիթմը nums-ի վրա.

Թող n լինի nums-ի երկարությունը: Եթե ​​n == 1, ապա ավարտեք գործընթացը: Հակառակ դեպքում, ստեղծեք նոր 0-ինդեքսավորված newNumsn / 2 երկարությամբ ամբողջ թվային զանգված:

Յուրաքանչյուր զույգ i ինդեքսի համար, որտեղ 0 <= i < n / 2, նշանակեք newNums[i] արժեքը որպես min(nums[2 * i], nums[2 * i + 1]):

Յուրաքանչյուր կենտ i ինդեքսի համար, որտեղ 0 <= i < n / 2, նշանակել newNums[i] արժեքը որպես max(nums[2 * i], nums[2 * i + 1]):

Փոխարինել nums զանգվածը newNums-ով:

Կրկնեք ամբողջ գործընթացը՝ սկսած 1-ին քայլից:

Ալգորիթմը կիրառելուց հետո վերադարձրեք վերջին թիվը, որը մնում էnums-ում:

Մոտեցում

Լուծումը պարզ իրականացումն է, ինչպես նկարագրված է խնդրի մեջ:

• զույգ ինդեքսի համար մենք վերցնում ենք նվազագույնը nums[2*i] և nums[2*i + 1]
• կենտ ինդեքսի համար մենք վերցնում ենք առավելագույնը nums[2*i] և nums[2*i + 1]

Մենք դա անում ենք այնքան ժամանակ, քանի դեռ զանգվածում միայն մեկ թիվ կա:

Լուծում

Ժամանակի բարդություն՝ O(n)

Տիեզերական բարդություն՝ O(n)

Խնդիր 2

Բաժանման զանգված այնպիսին, որ առավելագույն տարբերությունը K է

Ձեզ տրվում է nums ամբողջ զանգված և k ամբողջ թիվ: Դուք կարող եք nums-ը բաժանել մեկ կամ ավելի ենթահաջորդությունների այնպես, որ nums-ի յուրաքանչյուր տարր հայտնվի ճիշտ ենթահերթականներից մեկում:

Վերադարձրեք նվազագույնենթահաջորդականությունների քանակը, որոնք անհրաժեշտ են այնպես, որ յուրաքանչյուր ենթահաջորդության առավելագույն և նվազագույն արժեքների տարբերությունը լինի առավելագույնըk:

ենթահաջորդականությունը այն հաջորդականությունն է, որը կարող է ստացվել մեկ այլ հաջորդականությունից՝ ջնջելով որոշ կամ ոչ մի տարրեր՝ առանց մնացած տարրերի հերթականությունը փոխելու:

Մոտեցում

Տարրերը խմբավորելու պայմանն է՝ առավելագույն և նվազագույն տարրերի միջև տարբերությունը պետք է լինի ≤ k: Մենք դասավորում ենք զանգվածը և օգտագործում ենք երկու ցուցիչի մոտեցում, ամրագրում ենք առաջին ցուցիչի դիրքը և տեղափոխում երկրորդ ցուցիչը այնքան ժամանակ, մինչև երկու ցուցիչների միջև եղած տարրերի տարբերությունը լինի ≤ k: Երբ պայմանը ձախողվում է, մենք թարմացնում ենք առաջին ցուցիչի դիրքը և կրկնում ենք գործընթացը: Ենթահաջորդությունների թիվը առաջին ցուցիչի թարմացման քանակն է:

Լուծում

Ժամանակի բարդություն՝ O(nlogn)

Տիեզերական բարդություն՝ O(1)

Խնդիր 3

Փոխարինել տարրերը զանգվածում

Ձեզ տրվում է 0 ինդեքսավորված զանգված nums, որը բաղկացած է n տարբերակ դրական ամբողջ թվերից: Կիրառեք m գործողությունները այս զանգվածի վրա, որտեղ ith գործողության մեջ operations[i][0] թիվը փոխարինում եք operations[i][1]-ով:

Երաշխավորված է, որ ith գործողության մեջ.

operations[i][0] կա nums-ում:

operations[i][1] nums-ում չկա:

Վերադարձրեք բոլոր գործողությունները կիրառելուց հետո ստացված զանգվածը:

Մոտեցում

Մենք պահպանում ենք արժեք՝ տվյալ զանգվածի յուրաքանչյուր տարրի համար ինդեքսավորելու համար: Յուրաքանչյուր թարմացման գործողության համար մենք գտնում ենք գործողության[i][0] ինդեքսը և թարմացնում արժեքը nums[operation[i][0]]-ում մինչև : գործողություն[i][1]և թարմացրեք նաև ինդեքսային քարտեզագրիչը:

Լուծում

Ժամանակի բարդություն՝ O(n)

Տիեզերական բարդություն՝ O(n)

Խնդիր 4

Տեքստային խմբագրի նախագծում

Նախագծեք տեքստային խմբագրիչ կուրսորով, որը կարող է անել հետևյալը.

Ավելացրեք տեքստ այն վայրում, որտեղ գտնվում է կուրսորը:

Ջնջել տեքստը այն վայրից, որտեղ գտնվում է կուրսորը (նմանացնելով backspace ստեղնը):

Տեղափոխեք կուրսորը ձախ կամ աջ:

Տեքստը ջնջելիս կջնջվեն միայն կուրսորից ձախ կողմում գտնվող նիշերը: Կուրսորը նույնպես կմնա իրական տեքստի մեջ և չի կարող տեղափոխվել դրանից այն կողմ: Ավելի ֆորմալ առումով, մենք ունենք, որ 0 <= cursor.position <= currentText.length-ը միշտ պահպանվում է:

Իրականացնել TextEditor դասը.

TextEditor() Նախնականացնում է օբյեկտը դատարկ տեքստով:

void addText(string text) Ավելացնում է text կուրսորը: Կուրսորն ավարտվում է text-ի աջ կողմում:

int deleteText(int k) Ջնջում է կուրսորի ձախ կողմում գտնվող k նիշերը: Վերադարձնում է իրականում ջնջված նիշերի թիվը:

string cursorLeft(int k) Կուրսորը k անգամ տեղափոխում է ձախ: Վերադարձնում է վերջին min(10, len) նիշերը կուրսորի ձախ կողմում, որտեղ len կուրսորից ձախ նիշերի թիվն է:

string cursorRight(int k) Կուրսորը k անգամ տեղափոխում է աջ: Վերադարձնում է վերջին min(10, len) նիշերը կուրսորի ձախ կողմում, որտեղ len կուրսորից ձախ նիշերի թիվն է:

Մոտեցում

Մենք կարող ենք օգտագործել երկու կույտ մոտեցում: lstack և rstack: Կուրսորը միշտ կլինի lstack-ի վերևում:

1. ԱվելացնելՏրված տեքստը կկցվի lstack-ին:
2. Ջնջել Մենք ջնջում ենք նիշերը lstack-ից մինչև k-ը հասնի 0-ի, իսկ lstack-ը դատարկ չէ:
3. Տեղափոխեք կուրսորը ձախ Կուրսորը տեղափոխեք ձախ իմաստով, վերևի ցուցիչը տեղափոխեք, որից ներքև, ոչ այլ ինչ է, քան տարրը lstack-ից դուրս հանելը: Բացված տարրերը կպահվեն rstack-ում:
4. Տեղափոխեք կուրսորը աջ Կուրսորը տեղափոխեք ճիշտ իմաստով, տեղափոխեք վերևի ցուցիչը, որի վերևում գտնվող ցուցիչը ոչ այլ ինչ է, քան տարրը rstack-ից դուրս հանելը: Բացված տարրերը կպահվեն lstack-ում:

Լուծում

Ժամանակի բարդություն. O(n), որտեղ n-ը ավելացված, ջնջված նիշերի կամ կուրսորը տեղափոխվող դիրքերի թիվն է:

Տիեզերքի բարդություն. O(n), որտեղ n-ը նիշերի ընդհանուր քանակն է, որոնք պահվում են կույտից որևէ մեկում:

Հուսով եմ, տղաներ, այս գրառումը ձեզ դուր եկավ:

Եթե ​​գտնում եք, որ դա օգտակար է, խնդրում ենք տարածել և ծափերը շատ գնահատելի են: 😄

Զգացեք ձեր հարցերը տալ մեկնաբանությունների բաժնում: