Բառը[Թաքցնել][Ցուցադրում]
- 1. Ինչպե՞ս եք սահմանում զանգվածը:
- 2. Դինամիկ զանգվածներ. որո՞նք են դրանք: Ի՞նչն է դրանք առանձնացնում Հիմնական զանգվածներից:
- 3. Ինչպե՞ս են զանգվածը և բառարանը տարբերվում միմյանցից:
- 4. Թվարկե՛ք զանգվածների առավելություններն ու թերությունները:
- 5. Ինչի՞ն է վերաբերում «Sparse Array»-ը:
- 6. Ե՞րբ կընտրեիք կապակցված ցուցակը զանգվածի փոխարեն:
- 7. Ինչո՞վ է տարբերվում ինդեքսավորված զանգվածը ասոցիատիվ զանգվածից:
- 8. Ի՞նչ առավելություններ ունի Heap-ը տեսակավորված զանգվածների նկատմամբ:
- 9. Կարո՞ղ ենք զանգվածի չափը սահմանել բացասական:
- 10. Ինչպե՞ս եք գտնում բացակայող ամբողջ թիվը 1-ից 100 տարրանոց զանգվածում:
- 11. Ինչպե՞ս գտնել զանգվածի տարրի ինդեքսը:
- 12. Ինչպե՞ս կարելի է զանգվածից ազատվել կոնկրետ տարրից:
- 13. Ինչպե՞ս կարելի է ստուգել երկու զանգվածների հավասարությունը:
- 14. Երբ քննարկում ենք զանգվածները, ի՞նչ նկատի ունեք «Չափ» և «Բաժանորդագրություն» արտահայտություններով:
- Հարցազրույցի կոդավորման հարցեր
- 15. Փնտրեք մի զույգ զանգվածի մեջ, որն ունի նշված գումարը
- 16. Երկուական զանգվածների տեսակավորում գծային ժամանակով
- 17. Գտեք զանգվածի ամենամեծ երկու ինտ արտադրյալը:
- 18. Ինչպես տեղափոխել զանգվածի բոլոր զրոները մինչև վերջ
- 19. Ինչպես տեսակավորել զանգվածը երկու մուտքով, որոնք փոխարկվում են մեկ գործողության ընթացքում:
- 20. Ինչպես միավորել երկու տեսակավորված զանգվածները տեղում:
- 21. Ինչպե՞ս վերադասավորել իրերի զանգվածը փոփոխվող բարձր և ցածր դիրքերում:
- 22. Ինչպե՞ս զանգվածի յուրաքանչյուր տարր առանց բաժանման օպերատոր օգտագործելու փոխարինել զանգվածի յուրաքանչյուր տարրի արտադրյալով:
- 23. Գտի՛ր զանգվածի ամենատարօրինակ տարրը լոգարիթմական ժամանակում
- 24. Ինչպե՞ս ստանալ հաջորդ ավելի մեծ տարրը շրջանաձև զանգվածի յուրաքանչյուր տարրի համար:
- 25. Գտե՛ք զանգվածի ինվերսիայի թիվը:
- 26. Ո՞րն է անձրևաջրերի փակման խնդիրը:
- Եզրափակում
Կոդավորման հարցազրույցները պարունակում են մի շարք DSA հարցեր: Դուք պետք է հմուտ լինեք զանգվածների հետ, եթե պատրաստվում եք ձեր առաջիկա տեխնոլոգիական հարցազրույցին FAANG-ի կամ այլ Tier-1 տեխնոլոգիական բիզնեսի հետ:
Կոդավորման հարցազրույցների մեծ մասում այն երկրորդ տեղում է String-ին: Զանգվածը կապակցված տվյալների տարրերի խմբավորում է, որոնք պահվում են հիշողության մեջ միմյանց մոտ:
Քանի որ դրանք կապված են ծրագրավորման բոլոր լեզուների հետ, ինչպիսիք են C, C++, Java, Python, Perl և Ruby, դրանք ամենուր են: Շարունակեք կարդալ որոշ պրակտիկայի կոդավորման մարտահրավերների և հարցազրույցի հարցերի ու պատասխանների համար՝ հիմնված զանգվածների վրա:
Python-ը կօգտագործվի այս գրառման մեջ կոդավորման խնդիրները լուծելու համար, քանի որ այն պարզ է օգտագործելու, հասկանալի և պետք է ծանոթ լինի մեզանից շատերին:
Եկեք սկսենք.
1. Ինչպե՞ս եք սահմանում զանգվածը:
- Կապակցված տվյալների տեսակների խումբը զանգված է:
- Զանգվածները միշտ ֆիքսված են:
- Նույն տեսակի փոփոխականը պահվում է մի քանի վայրերում՝ զանգվածի օբյեկտների միջոցով:
- Պրիմիտիվ տեսակները և օբյեկտների հղումները երկուսն էլ համատեղելի են դրա հետ:
2. Դինամիկ զանգվածներ. որո՞նք են դրանք: Ի՞նչն է դրանք առանձնացնում Հիմնական զանգվածներից:
Դինամիկ զանգվածների (նաև կոչվում են աճեցվող զանգվածներ, չափափոխվող զանգվածներ, փոփոխվող զանգվածներ կամ ArrayLists-ը Java-ում) ապահովում են զգալի առավելություն:
Դուք միշտ պետք է նախապես իմանաք, թե քանի տարր կպահի ձեր զանգվածը, քանի որ զանգվածներն ունեն ֆիքսված չափ: Մյուս կողմից, դինամիկ զանգվածն աճում է, երբ դրան ավելացնում եք լրացուցիչ անդամներ, այնպես որ նախօրոք դրա ճշգրիտ չափը իմանալու կարիք չկա:
3. Ինչպե՞ս են զանգվածը և բառարանը տարբերվում միմյանցից:
Սա հարցազրույցի հարցերի հիման վրա հիմնված զանգված է, որը պարբերաբար տրվում է: Ստորև բերված են զանգվածների և բառարանների հիմնական տարբերությունները.
- Զանգվածը նմանատիպ տարրերի պատվիրված ցանկ է: Բառարանը, մյուս կողմից, ունի բանալի-արժեք զույգեր:
- Զանգվածի չափերը կարող են դինամիկ փոխվել: Նման դինամիկ գաղափարներ չկան բառարաններում։
- Զանգված օգտագործելուց առաջ պետք է նշել դրա չափը: Բառարանի չափսերը հարմարեցնելու կարիք չունեն:
- Օգտագործեք Redim հայտարարությունը, եթե ցանկանում եք ընդլայնել զանգվածի չափը: Բառարաններում տարրը կարող է ավելացվել առանց հայտարարագրի։
4. Թվարկե՛ք զանգվածների առավելություններն ու թերությունները:
Առավելությունները.
- Զանգվածները կարող են միաժամանակ դասավորել մի շարք տարրեր:
- այլ տվյալների կառուցվածքները, ինչպես կույտերը, հերթերը, կապակցված ցուցակները, ծառերը, գրաֆիկները և այլն, կարող են իրականացվել զանգվածում:
- Ցուցանիշը կարող է օգտագործվել զանգվածի տարրին հասնելու համար:
Թերությունները:
- Զանգվածի չափը պետք է նախապես հայտարարված լինի: Զանգվածի հայտարարագրման պահին մենք, այնուամենայնիվ, կարող ենք տեղյակ չլինել մեր պահանջած չափի մասին:
- Զանգվածի կառուցվածքը ստատիկ է: Դա ենթադրում է, որ զանգվածի չափը միշտ ֆիքսված է, և որ հիշողության բաշխումը չի կարող ավելացվել կամ նվազել:
5. Ինչի՞ն է վերաբերում «Sparse Array»-ը:
Նվազ զանգվածը տվյալների զանգված է, որն ունի զրոյական արժեքներով բազմաթիվ մուտքեր: Ի հակադրություն, խիտ զանգվածը պարունակում է իր տարրերի մեծ մասը ոչ զրոյական արժեքներով: Նվազ զանգվածի ինդեքսները, որոնք թվերը վերածում են օբյեկտների, կարող են ներառել բացեր: Համեմատած HashMap-ի հետ՝ դրանք ավելի արդյունավետ են հիշողության համար:
6. Ե՞րբ կընտրեիք կապակցված ցուցակը զանգվածի փոխարեն:
Զանգվածների փոխարեն կապված ցուցակներն օգտագործելիս հաշվի առեք.
- Պատահական մուտք ունենալու համար որևէ տարր պետք չէ:
- Այնտեղ, որտեղ ժամանակային կանխատեսելիությունը էական է, ձեզ անհրաժեշտ են մշտական ժամանակի տեղադրումներ և հեռացումներ ցուցակից:
- Առաջնահերթ հերթ ստեղծելու համար գուցե անհրաժեշտ լինի տարրեր տեղադրել ցուցակի կենտրոնում:
- Դուք պատկերացում չունեք, թե որքան երկար կլինի ցուցակը: Եթե զանգվածի չափը մեծանում է, դուք պետք է նորից հայտարարեք և կրկնօրինակեք հիշողությունը, ինչպես պարզ զանգվածների դեպքում:
7. Ինչո՞վ է տարբերվում ինդեքսավորված զանգվածը ասոցիատիվ զանգվածից:
Ասոցիատիվ և ինդեքսավորված զանգվածների միջև առաջնային տարբերությունները թվարկված են հետևյալ աղյուսակում:
- Բանալին-արժեք զույգը տեքստային կամ թվային ձևաչափով օգտագործվում է ասոցիատիվ զանգվածը տեսակավորելու համար: Ինդեքսավորված զանգվածի ստեղները բոլորը թվային են, և յուրաքանչյուր բանալի միացված է որոշակի արժեքի:
- Ասոցիատիվ զանգվածում բանալին կարող է լինել տող: Ինդեքսավորված զանգված՝ 0-ից սկսվող ամբողջ թվային ստեղներով:
- Երկու սյունակ աղյուսակը նմանակում է ասոցիատիվ զանգվածի վարքագիծը: Մեկ սյունակ աղյուսակի նման են ինդեքսավորված զանգվածները:
- Քարտեզները ասոցիատիվ զանգվածի տեսակ են: Ինդեքսային զանգվածը քարտեզ չէ:
8. Ի՞նչ առավելություններ ունի Heap-ը տեսակավորված զանգվածների նկատմամբ:
Տեսակավորված զանգվածների վրա կույտի օգտագործման ժամանակի արդյունավետությունը հիմնական առավելությունն է: Թեև կույտային գործողություններն ավելի արագ են, զանգվածի տեսակավորումը շատ ժամանակ է պահանջում: Կույտը կարող է հայտնաբերել ամենափոքր տարրը զգալիորեն ավելի արագ, քան զանգվածը կարող է տեսակավորվել:
Թվերի տրված հավաքածուն կարելի է դասավորել երկու եղանակներից մեկով՝ օգտագործելով Տեսակավորված զանգվածները: Մյուս կողմից, թվերի տվյալ հավաքածուի համար կարող է լինել մեկից ավելի պոտենցիալ կույտ:
9. Կարո՞ղ ենք զանգվածի չափը սահմանել բացասական:
Ոչ, մենք չենք կարող բացասական ամբողջ թիվ սահմանել որպես զանգվածի չափ: Կազմելու ժամանակի սխալ չի լինի, եթե հայտարարենք: Գործարկման ժամանակ մենք, այնուամենայնիվ, կհանդիպենք NegativeArraySizeException:
10. Ինչպե՞ս եք գտնում բացակայող ամբողջ թիվը 1-ից 100 տարրանոց զանգվածում:
Շարքի ընդհանուր գումարը կարելի է հաշվարկել՝ կիրառելով հետևյալ ֆունկցիան՝ n (n + 1) / 2
Այս ֆունկցիան կգործի միայն այն դեպքում, եթե զանգվածը չունի կրկնօրինակներ կամ բացակայում է մեկից ավելի ամբողջ թիվ: Անկախ նրանից, թե զանգվածը ունի կրկնօրինակ տարրեր, դուք կարող եք տեսակավորել զանգվածը՝ տեսնելու, թե արդյոք կան համարժեք տարրեր:
11. Ինչպե՞ս գտնել զանգվածի տարրի ինդեքսը:
Տարրի ինդեքսը կարելի է հայտնաբերել գծային կամ երկուական որոնման միջոցով: Քանի դեռ չի գտնում պահանջվող տարրի համընկնումը՝ գծային որոնման ֆունկցիան պտտվում է զանգվածի յուրաքանչյուր տարրի վրա: Այն վերադարձնում է ինդեքսը, երբ գտնում է համապատասխան տարրը: Հետևաբար, գծային որոնման ժամանակային բարդությունը O. (n) է: Ե՛վ տեսակավորված, և՛ չտեսակավորված զանգվածը կարող է օգտագործել գծային որոնում:
Օգտագործելով երկուական որոնում, որը շարունակաբար կիսում է զանգվածը կիսով չափ, մինչև միջակայքի միջինը համապատասխանի պահանջվող տարրին և տրամադրի ինդեքսը, դուք կարող եք ստանալ տարրի ինդեքսը, եթե զանգվածը տեսակավորված է: Հետևաբար, երկուական որոնման ժամանակային բարդությունը O. է (log n):
12. Ինչպե՞ս կարելի է զանգվածից ազատվել կոնկրետ տարրից:
Քանի որ դուք չեք կարող պարզապես ջնջել տարրերը սկզբնական զանգվածից, քանի որ դրանք ֆիքսված հավաքածուներ են սահմանված չափսով, հարցազրուցավարը փնտրում է, որ դուք առաջարկեք այլ մոտեցում և զբաղվեք հարցի բարձրացրած խնդրի հետ: Գործողության լավագույն միջոցը նոր զանգված ստեղծելն է՝ տարրը ջնջելու համար: Դուք կարող եք կրկնօրինակել տարրերը առաջին զանգվածից այս զանգվածում և ներառել միայն այն տարրը, որը ցանկանում եք ջնջել:
Մեկ այլ ռազմավարություն ներառում է զանգվածում թիրախային տարրը գտնելը և այնուհետև փոխել բոլոր տարրերի հերթականությունը, որոնք գտնվում են թիրախային տարրի աջ կողմում:
13. Ինչպե՞ս կարելի է ստուգել երկու զանգվածների հավասարությունը:
Նախ պետք է ստուգեք տրամադրված երկու զանգվածների երկարությունը: Երկու զանգվածների համապատասխան տարրերը համեմատվում են, երբ դրանց երկարությունները հավասար են: Երկու զանգվածները կհամարվեն հավասար: եթե յուրաքանչյուր համապատասխանության բաղադրիչների յուրաքանչյուր զույգ հավասար է: Այս մոտեցումը խորհուրդ չի տրվում ստուգել երկու զանգվածների հավասարությունը, եթե զանգվածները մեծ չափերով են, քանի որ դրա համար շատ ժամանակ կպահանջվի: Դուք կարող եք նաև օգտագործել Arrays դասում ներառված equals() մեթոդը, սակայն, եթե հարցազրուցավարը ձեզ խնդրում է համեմատել երկու զանգված՝ առանց ներկառուցված մեթոդների օգտագործման, այս եղանակը օգտակար կլինի:
14. Երբ քննարկում ենք զանգվածները, ի՞նչ նկատի ունեք «Չափ» և «Բաժանորդագրություն» արտահայտություններով:
Զանգվածի «չափը» ինդեքսների կամ ենթագրերի քանակն է, որոնք անհրաժեշտ են յուրաքանչյուր առանձին անդամի նույնականացման համար: Բաժանորդները և չափերը կարող են անհասկանալի լինել: Չափը թույլատրված ստեղների տիրույթի նկարագրությունն է, մինչդեռ բաժանորդը թիվ է: Զանգվածի յուրաքանչյուր չափման համար պահանջվում է ընդամենը մեկ ենթագիր:
Օրինակ՝ arr[10][5] զանգվածն ունի երկու չափսեր։ Չափսերը մեկի վրա 10, մյուսի վրա՝ 5։ Դրա բաղադրիչներին անդրադառնալու համար ձեզ հարկավոր է երկու բաժանորդ: Երկուսն էլ 0-ի և 4-ի միջև են. մեկը 0-ից 9-ի միջև, ներառյալ:
Հարցազրույցի կոդավորման հարցեր
15. Փնտրեք մի զույգ զանգվածի մեջ, որն ունի նշված գումարը
Օրինակ,
Մուտք:
- համարներ = [8, 7, 2, 5, 3, 1]
- թիրախ = 10
Արդյունք:
- Գտնվել է զույգ (8, 2)
- Or
- Գտնվել է զույգ (7, 3)
Մուտք:
- համարներ = [5, 2, 6, 8, 1, 9]
- թիրախ = 12
Արդյունք:
- Զույգը չի գտնվել
16. Երկուական զանգվածների տեսակավորում գծային ժամանակով
Տեսակավորել երկուական զանգվածը գծային ժամանակով և ֆիքսված տարածքում: Արդյունքը պետք է նախ ցուցադրի բոլոր զրոները, ապա բոլորը:
Օրինակ,
- Մուտքագրում՝ {1, 0, 1, 0, 1, 0, 0, 1 }
- Արդյունք՝ {0, 0, 0, 0, 1, 1, 1, 1 }
Պարզ մոտեցումը կլինի զանգվածի 0-երի ընդհանուր թիվը հաշվարկելը, ասենք k, և այնուհետև զանգվածի առաջին k ինդեքսները լրացնել 0-ով, իսկ մնացած ինդեքսները 1-ով: Որպես այլընտրանք, մենք կարող ենք հաշվարկել, թե քանի 1 է ընդհանուր թիվը: k զանգված, զանգվածի վերջին k ինդեքսները լրացրեք 1-ով, իսկ մնացած ցուցիչները թողեք 0-ով:
Տրված մոտեցումն ունի O(n) ժամանակի բարդություն և չի օգտագործում լրացուցիչ պահեստ, որտեղ n-ը մուտքագրման չափն է:
17. Գտեք զանգվածի ամենամեծ երկու ինտ արտադրյալը:
Գտե՛ք երկու թվերի ամենամեծ արտադրյալը ամբողջ թվով զանգվածում:
Մտածեք 10 3 5 6 2 զանգվածի մասին որպես օրինակ: (-10, -3) կամ (5, 6) զույգը ամենաբարձր արտադրյալն է:
Յուրաքանչյուր տարրի համակցության մասին մտածելը և դրանց արտադրանքը պարզելը հիմար մոտեցում է: Եթե ընթացիկ զույգի արտադրյալն ավելի մեծ է, քան մինչ այժմ ստացված առավելագույն արտադրանքը, թարմացրեք առավելագույն արտադրանքը: Վերջնական տպեք վերջնական արտադրանքի բաղադրիչները:
Վերոնշյալ լուծումը, որտեղ n-ը մուտքագրման քանակն է, ունի O(n2) ժամանակային բարդություն և այլևս տեղ չի զբաղեցնում:
18. Ինչպես տեղափոխել զանգվածի բոլոր զրոները մինչև վերջ
Տեղափոխեք ամբողջ թվով զանգվածի բոլոր զրոները մինչև վերջ: Պատասխանը պետք է խուսափի մշտական տարածության օգտագործումից և պահպանի զանգվածի բաղադրիչների հարաբերական կարգը:
Ներածում ՝ {1,2,3,0,8,0,4,7}
Արդյունքը կլինի {1,2,3,8,4,7,0,0}
Տեղադրեք տարրը զանգվածի հետևյալ հասանելի դիրքում, եթե ընթացիկ տարրը զրո չէ: Լրացրեք մնացած բոլոր ինդեքսները 0-ով, երբ զանգվածի բոլոր տարրերը մշակվեն:
Նախորդ լուծումն ունի O(n) ժամանակի բարդություն, որտեղ n-ը մուտքագրման չափն է:
19. Ինչպես տեսակավորել զանգվածը երկու մուտքով, որոնք փոխարկվում են մեկ գործողության ընթացքում:
Տեսակավորել զանգվածը գծային ժամանակում՝ հաշվի առնելով երկու փոխանակված տարրերը և զանգվածը՝ իր բոլոր տարրերով դասավորված աճման կարգով: Ձևացնել, որ զանգվածը կրկնօրինակներ չի պարունակում:
Մուտք՝ = [1,9,3,4,7,2] կամ [9,3,7,2,1,4] կամ [2,4,1,7,3,9]
Արդյունք՝ = [1,2,3,4,7,9]
Սկսած զանգվածի երկրորդ տարրից՝ նպատակն է համեմատել յուրաքանչյուր տարր իր նախորդի հետ: Վեճի դիրքը պահվում է՝ վերցնելով երկու ցուցիչ՝ x և y:
Թարմացրեք x-ը նախորդ տարրի ինդեքսին, իսկ y-ն՝ ընթացիկ տարրի ինդեքսին, եթե առաջինը մեծ է երկրորդից: Թարմացրեք y-ը ընթացիկ տարրի ինդեքսին, եթե պարզվի, որ նախորդ տարրը մեծ է ընթացիկ տարրից։
Ի վերջո, փոխեք տարրերը x և y ինդեքսներում, երբ ավարտենք յուրաքանչյուր հարակից զույգ տարրերի մշակումը:
Հաշվի առնելով այն հանգամանքը, որ վերոհիշյալ մեթոդը կատարում է n չափի մուտքային զանգվածի միայն մեկ սկանավորում, դրա ժամանակային բարդությունը O(n է): Լուծման համար լրացուցիչ սենյակ անհրաժեշտ չէ։
20. Ինչպես միավորել երկու տեսակավորված զանգվածները տեղում:
Միավորե՛ք X[] և Y[] զանգվածների տարրերը՝ յուրաքանչյուրը m և n չափերի երկու տեսակավորված զանգված՝ պահպանելով տեսակավորված հերթականությունը, այսինքն՝ X[]-ը լրացնելով առաջին m ամենափոքր տարրերով և Y[]-ով լրացնելով. մնացած տարրերը.
Եթե X[] զանգվածի տարրն արդեն ճիշտ դիրքում է (այսինքն՝ նա, որն ամենափոքրն է մնացած տարրերից), արհամարհեք այն. հակառակ դեպքում փոխարինեք այն ամենափոքր տարրով, որը նույնպես Y[]-ի առաջին անդամն է: Փոխանակումից հետո տեսակավորված հերթականությունը պահպանելու համար տարրը (այժմ՝ Y[0]-ում) տեղափոխեք իր ճիշտ տեղը՝ Y[]-ում:
Առաջին զանգվածի չափը m է, իսկ երկրորդ զանգվածի չափը n է, իսկ ժամանակի բարդությունը՝ O(mn):
21. Ինչպե՞ս վերադասավորել իրերի զանգվածը փոփոխվող բարձր և ցածր դիրքերում:
Վերադասավորեք ամբողջ թվային զանգվածն այնպես, որ յուրաքանչյուր հաջորդ անդամ մեծ լինի նախորդ և հաջորդ տարրերից: Ենթադրենք, որ զանգվածը չի ներառում կրկնօրինակ տարրեր:
Արդյունավետ մոտեցման համար անհրաժեշտ չէ զանգվածի տեսակավորումը կամ լրացուցիչ տարածք օգտագործելը: Պլանը սկզբից զանգվածի երկրորդ անդամն է և յուրաքանչյուր օղակի կրկնության համար երկուսով բարձրանալը:
Փոխեք բաղադրիչները, եթե վերջին տարրը գերազանցում է առաջինը: Նույն կերպ, փոխեք երկու տարրերը, եթե հետևյալ տարրը ավելի մեծ է, քան ընթացիկ տարրը: Ցանկալի զանգվածը, որը համապատասխանում է նշված սահմանափակումներին, մենք կստանանք հանգույցի վերջում:
22. Ինչպե՞ս զանգվածի յուրաքանչյուր տարր առանց բաժանման օպերատոր օգտագործելու փոխարինել զանգվածի յուրաքանչյուր տարրի արտադրյալով:
Առանց բաժանման օպերատորի օգտագործման, ամբողջ թվով զանգվածի յուրաքանչյուր տարր փոխարինեք մյուս բոլոր տարրերի արտադրյալով:
Գծային ժամանակի և հաստատուն տարածության մեջ մենք կարող ենք օգտագործել ռեկուրսիան այս խնդրի լուծման համար: Աջ ենթազանգվածի յուրաքանչյուր տարրի արտադրյալների ռեկուրսիվ հաշվարկը և ձախ ենթաշարքի արտադրյալը որպես ֆունկցիայի պարամետրեր փոխանցելը հասկացությունն է:
Ժամանակի բարդությունը O(n) է:
23. Գտի՛ր զանգվածի ամենատարօրինակ տարրը լոգարիթմական ժամանակում
Հաշվի առնելով ամբողջ թվային զանգվածը, որտեղ բոլոր անդամները, բացի մեկից, ունեն զույգ թվեր, խնդիրն այն է, թե քանի անգամ է հայտնվում այս մեկ տարրը: Գտեք տարօրինակ տարրը լոգարիթմական ժամանակում և հաստատուն տարածության մեջ, եթե նույն տարրերը զանգվածում զույգերով են հանդիպում, և երբեք չի կարող անընդմեջ լինել տվյալ տարրի երկու դեպքից ավելի:
XOR գործողությունը մեզ հնարավորություն է տալիս լուծել այս խնդիրը գծային ժամանակում: Նպատակը զանգվածի յուրաքանչյուր տարր XOR-ն է: Միայն կենտ առաջացող տարրերը մնում են այն բանից հետո, երբ զույգ տարրերը ջնջում են միմյանց:
Այս խնդիրը կարող է լուծվել նույնիսկ O(log(n)) ժամանակում:
24. Ինչպե՞ս ստանալ հաջորդ ավելի մեծ տարրը շրջանաձև զանգվածի յուրաքանչյուր տարրի համար:
Շրջանաձև ամբողջ զանգվածի յուրաքանչյուր տարրի համար հաջորդ ավելի մեծ տարրը պետք է գտնվի: Զանգվածի x տարրից հետո առաջին ավելի մեծ ամբողջ թիվը այդ տարրի հետագա մեծ տարրն է:
Աջից ձախ մենք կարող ենք գործել զանգվածի տարրերով: Նպատակը յուրաքանչյուր x տարրի համար պտույտ անելն է այնքան ժամանակ, մինչև կա՛մ կույտը դատարկվի, կա՛մ մենք դրա վերևում ունենանք ավելի բարձր տարր: Սահմանեք x-ի հաջորդ ավելի մեծ տարրը, որպեսզի այն հայտնվի բուրգի վերևում, երբ այն հայտնվում է:
25. Գտե՛ք զանգվածի ինվերսիայի թիվը:
Գտեք զանգվածի ինվերսիաների ընդհանուր թիվը: I j) զույգը նշվում է որպես A զանգվածի ինվերսիա, եթե ես j) և (A[i] > A[j]): Մենք պետք է հաշվենք դրանցից յուրաքանչյուր զույգ զանգվածում:
Զանգվածի բոլոր անդամները հաշվելը, որոնք նրանից քիչ են աջ կողմում, և արդյունքը ելքին ավելացնելը պարզ մոտեցում է:
Այս լուծումն ունի O(n2) բարդություն, որտեղ n-ը մուտքագրման չափն է:
26. Ո՞րն է անձրևաջրերի փակման խնդիրը:
Գտնել առավելագույն ջուրը, որը կարող է թակարդվել տվյալ հավաքածուի մեջ մեկ միավորի լայնությամբ, հայտնի է որպես «թակարդող անձրևի» խնդիր:
Նպատակն է որոշել ամենաբարձր բարը, որը կարող է տեղադրվել յուրաքանչյուր բարի ձախ և աջ կողմում: Ձախ և աջ տանող ձողերի նվազագույնը, ընթացիկ ձողի բարձրությունից պակաս, ջրի քանակն է, որը պահվում է յուրաքանչյուր ձողի վերևում:
Եզրափակում
Տվյալների կառուցվածքի այլ թեմաների համեմատ զանգվածներն ավելի պարզ են: Որպեսզի ace array հարցազրույցի հարցեր, դուք պետք է ունենալ հիմնարար պատկերացում զանգվածների.
Դուք պետք է լայնորեն վերանայեք զանգվածների հիմքերը, ներառյալ զանգվածի գործողությունները (զանգված հայտարարելուց/ստեղծելուց մինչև զանգվածի տարրերի մուտքը/փոփոխումը), ինչպես նաև ծրագրավորման հասկացությունները, ինչպիսիք են օղակները, ռեկուրսիան և հիմնական օպերատորները, որպեսզի հաջողությամբ պատասխանեք զանգվածի հարցազրույցի հարցերին: Խնդիրն ամբողջությամբ ճանաչել:
Դուք պետք է պարզաբանում փնտրեք, եթե ունեք հարցեր: Մտածեք հարցը ավելի կառավարելի մասերի բաժանելու մասին։ Նախքան ծրագրավորումը սկսելը, համոզվեք, որ մտքում ունեք ալգորիթմը. գրեք այն կամ պատկերացրեք այն հոսքի գծապատկերում: ապա սկսեք գրել կոդը:
Թողնել գրառում