មាតិកា[លាក់][បង្ហាញ]
- 1. តើអ្នកកំណត់ Array យ៉ាងដូចម្តេច?
- 2. ឌីណាមិកអារេ៖ តើវាជាអ្វី? តើអ្វីដែលកំណត់ពួកវាខុសពីអារេមូលដ្ឋាន?
- 3. តើអារេ និងវចនានុក្រមខុសគ្នាពីគ្នាទៅវិញទៅមកយ៉ាងដូចម្តេច?
- 4. រាយបញ្ជីអត្ថប្រយោជន៍ និងគុណវិបត្តិមួយចំនួននៃអារេ។
- 5. តើ “Sparse Array” សំដៅលើអ្វី?
- 6. តើនៅពេលណាដែលអ្នកជ្រើសរើសបញ្ជីដែលភ្ជាប់នៅលើអារេមួយ?
- 7. តើអ្វីជាភាពខុសគ្នានៃអារេដែលមានលិបិក្រមពីអារេសមាគម?
- 8. តើហេបមានគុណសម្បត្តិអ្វីខ្លះលើអារេដែលបានតម្រៀប?
- 9. តើយើងអាចកំណត់ទំហំនៃអារេទៅជាអវិជ្ជមានបានទេ?
- 10. តើអ្នកកំណត់ចំនួនគត់ដែលបាត់ក្នុងអារេធាតុពី 1 ដល់ 100 ដោយរបៀបណា?
- 11. តើអ្នកស្វែងរកលិបិក្រមនៃធាតុនៅក្នុងអារេដោយរបៀបណា?
- 12. តើអ្នកអាចកម្ចាត់ធាតុជាក់លាក់មួយចេញពីអារេដោយរបៀបណា?
- 13. តើសមភាពរបស់អារេពីរអាចផ្ទៀងផ្ទាត់បានដោយរបៀបណា?
- 14. នៅពេលយើងពិភាក្សាអំពីអារេ តើអ្នកមានន័យយ៉ាងណាចំពោះឃ្លា "វិមាត្រ" និង "អក្សរតូច"?
- សំណួរសំភាសន៍សរសេរកូដ
- 15. ស្វែងរកគូក្នុងអារេដែលមានផលបូកដែលបានបញ្ជាក់
- 16. ការតម្រៀបអារេប្រព័ន្ធគោលពីរជាមួយពេលវេលាលីនេអ៊ែរ
- 17. ស្វែងរកផលិតផល two-int ធំបំផុតក្នុងអារេមួយ។
- 18. របៀបប្តូរលេខសូន្យទាំងអស់របស់អារេទៅចុងបញ្ចប់
- 19. របៀបតម្រៀបអារេដែលមានធាតុពីរដែលត្រូវបានប្តូរក្នុងប្រតិបត្តិការមួយ។
- 20. របៀបផ្សំអារេដែលបានតម្រៀបពីរនៅនឹងកន្លែង។
- 21. តើធ្វើដូចម្តេចដើម្បីតម្រៀបអារេនៃធាតុនៅក្នុងទីតាំងខ្ពស់និងទាបជំនួស?
- 22. តើត្រូវជំនួសធាតុនីមួយៗនៃអារេដោយរបៀបណា ដោយមិនប្រើប្រយោគបែងចែកជាមួយផលិតផលនៃធាតុនីមួយៗក្នុងអារេ?
- 23. ស្វែងរកធាតុសេសបំផុតក្នុងអារេក្នុងពេលវេលាលោការីត
- 24. តើធ្វើដូចម្តេចដើម្បីទទួលបានធាតុធំជាបន្តបន្ទាប់សម្រាប់ធាតុនីមួយៗនៅក្នុងអារេរាងជារង្វង់?
- 25. ស្វែងរកចំនួនបញ្ច្រាសនៃអារេមួយ?
- 26. តើអ្វីទៅជាបញ្ហាទឹកភ្លៀង?
- សន្និដ្ឋាន
ការសំភាសន៍សរសេរកូដមានសំណួរ DSA ជាបន្តបន្ទាប់។ អ្នកគួរតែមានជំនាញជាមួយអារេ ប្រសិនបើអ្នកកំពុងត្រៀមខ្លួនសម្រាប់ការសម្ភាសន៍បច្ចេកវិទ្យានាពេលខាងមុខរបស់អ្នកជាមួយ FAANG ឬអាជីវកម្មបច្ចេកវិទ្យាលំដាប់ទី 1 ផ្សេងទៀត។
នៅក្នុងការសំភាសន៍សរសេរកូដភាគច្រើន វាស្ថិតនៅលំដាប់ទីពីរទៅ Strings ។ អារេគឺជាក្រុមនៃធាតុទិន្នន័យដែលទាក់ទងគ្នាដែលរក្សាទុកនៅជិតគ្នាទៅវិញទៅមកនៅក្នុងអង្គចងចាំ។
ដោយសារពួកវាត្រូវបានភ្ជាប់ទៅគ្រប់ភាសាសរសេរកម្មវិធីដូចជា C, C++, Java, Python, Perl និង Ruby ពួកវាមាននៅគ្រប់ទីកន្លែង។ បន្តអានសម្រាប់បញ្ហាប្រឈមក្នុងការសរសេរកូដមួយចំនួន និងសំណួរសម្ភាសន៍ និងចម្លើយដោយផ្អែកលើអារេ។
Python នឹងត្រូវបានប្រើនៅក្នុងការប្រកាសនេះដើម្បីដោះស្រាយបញ្ហាកូដដោយសារតែវាមានភាពសាមញ្ញក្នុងការប្រើ, យល់, និងត្រូវតែស្គាល់សម្រាប់យើងភាគច្រើន។
តោះចាប់ផ្ដើម។
1. តើអ្នកកំណត់ Array យ៉ាងដូចម្តេច?
- ក្រុមនៃប្រភេទទិន្នន័យដែលពាក់ព័ន្ធគឺជាអារេមួយ។
- អារេតែងតែត្រូវបានជួសជុល។
- ប្រភេទដូចគ្នានៃអថេរត្រូវបានរក្សាទុកនៅកន្លែងជាច្រើនដោយវត្ថុអារេ។
- ប្រភេទបឋម និងឯកសារយោងវត្ថុគឺត្រូវគ្នាជាមួយវា។
2. ឌីណាមិកអារេ៖ តើវាជាអ្វី? តើអ្វីដែលកំណត់ពួកវាខុសពីអារេមូលដ្ឋាន?
ការធ្វើមាត្រដ្ឋានដោយស្វ័យប្រវត្តិដែលអារេថាមវន្ត (ហៅផងដែរថាអារេដែលអាចពង្រីកបាន អារេដែលអាចផ្លាស់ប្តូរទំហំបាន អារេដែលអាចផ្លាស់ប្តូរបាន ឬអារេលីសក្នុងចាវ៉ា) ផ្តល់ជាអត្ថប្រយោជន៍យ៉ាងសំខាន់។
អ្នកត្រូវតែដឹងជានិច្ចថាតើអារេរបស់អ្នកនឹងផ្ទុកធាតុប៉ុន្មានជាមុន ព្រោះអារេមានទំហំថេរ។ ម្យ៉ាងវិញទៀត អារេថាមវន្ត លូតលាស់នៅពេលអ្នកបន្ថែមសមាជិកបន្ថែមទៅវា ដូច្នេះអ្នកមិនចាំបាច់ដឹងពីទំហំពិតប្រាកដរបស់វាជាមុនទេ។
3. តើអារេ និងវចនានុក្រមខុសគ្នាពីគ្នាទៅវិញទៅមកយ៉ាងដូចម្តេច?
នេះគឺជាអារេផ្អែកលើមូលដ្ឋាននៃសំណួរសម្ភាសន៍ដែលត្រូវបានសួរជាទៀងទាត់។ ខាងក្រោមនេះគឺជាភាពខុសគ្នាសំខាន់រវាងអារេ និងវចនានុក្រម៖
- អារេគឺជាបញ្ជីលំដាប់នៃធាតុស្រដៀងគ្នា។ ម្យ៉ាងវិញទៀត វចនានុក្រម មានគូតម្លៃសំខាន់ៗ។
- ទំហំអារេអាចផ្លាស់ប្តូរថាមវន្ត។ គំនិតថាមវន្តបែបនេះមិនមាននៅក្នុងវចនានុក្រមទេ។
- មុនពេលប្រើអារេ ទំហំរបស់វាត្រូវតែបញ្ជាក់។ ទំហំវចនានុក្រមមិនចាំបាច់ត្រូវបានប្ដូរតាមបំណងទេ។
- ប្រើសេចក្តីថ្លែងការណ៍ Redim ប្រសិនបើអ្នកចង់ពង្រីកទំហំរបស់អារេ។ នៅក្នុងវចនានុក្រម ធាតុមួយអាចត្រូវបានបន្ថែមដោយគ្មានការប្រកាស។
4. រាយបញ្ជីអត្ថប្រយោជន៍ និងគុណវិបត្តិមួយចំនួននៃអារេ។
គុណសម្បត្តិ:
- អារេអាចតម្រៀបធាតុមួយចំនួនក្នុងពេលដំណាលគ្នា។
- ផ្សេងទៀត រចនាសម្ព័ន្ធទិន្នន័យដូចជាជង់ ជួរ បញ្ជីភ្ជាប់ ដើមឈើ ក្រាហ្វ។ល។ អាចត្រូវបានអនុវត្តនៅក្នុងអារេមួយ។
- លិបិក្រមអាចត្រូវបានប្រើដើម្បីឈានដល់ធាតុនៃអារេមួយ។
គុណវិបត្តិ:
- ទំហំរបស់អារេត្រូវតែប្រកាសជាមុន។ នៅពេលនៃការប្រកាសអារេ យើងប្រហែលជាមិនដឹងពីទំហំដែលយើងត្រូវការនោះទេ។
- រចនាសម្ព័ន្ធនៃអារេគឺឋិតិវន្ត។ វាបង្កប់ន័យថាទំហំអារេតែងតែត្រូវបានជួសជុល ហើយការបែងចែកអង្គចងចាំមិនអាចបង្កើន ឬបន្ថយបានទេ។
5. តើ “Sparse Array” សំដៅលើអ្វី?
sparse array គឺជាអារេទិន្នន័យដែលមានធាតុជាច្រើនដែលមានតម្លៃសូន្យ។ ផ្ទុយទៅវិញ អារេក្រាស់មានធាតុភាគច្រើនរបស់វា ដែលមានតម្លៃមិនសូន្យ។ សន្ទស្សន៍នៃអារេ sparse ដែលបំប្លែងលេខទៅជាវត្ថុអាចរួមបញ្ចូលចន្លោះ។ បើប្រៀបធៀបទៅនឹង HashMap ពួកវាមានប្រសិទ្ធភាពការចងចាំជាង។
6. តើនៅពេលណាដែលអ្នកជ្រើសរើសបញ្ជីដែលភ្ជាប់នៅលើអារេមួយ?
នៅពេលប្រើបញ្ជីដែលបានភ្ជាប់ជំនួសឱ្យអារេ សូមពិចារណា៖
- អ្នកមិនត្រូវការធាតុណាមួយដើម្បីមានសិទ្ធិចូលប្រើដោយចៃដន្យទេ។
- កន្លែងណាដែលការទស្សន៍ទាយបណ្តោះអាសន្នគឺចាំបាច់ អ្នកត្រូវការការបញ្ចូល និងដកចេញពីបញ្ជីជាប្រចាំ។
- ដើម្បីបង្កើតជួរអាទិភាព អ្នកប្រហែលជាត្រូវដាក់ធាតុនៅកណ្តាលបញ្ជី។
- អ្នកមិនដឹងថាតើបញ្ជីនេះនឹងមានរយៈពេលប៉ុន្មាននោះទេ។ ប្រសិនបើទំហំអារេកើនឡើង អ្នកត្រូវតែប្រកាសឡើងវិញ និងចម្លងអង្គចងចាំ ដូចទៅនឹងអារេសាមញ្ញដែរ។
7. តើអ្វីជាភាពខុសគ្នានៃអារេដែលមានលិបិក្រមពីអារេសមាគម?
ភាពខុសគ្នាចម្បងរវាងអារេសហការ និងលិបិក្រមត្រូវបានរាយក្នុងតារាងខាងក្រោម។
- គូតម្លៃគន្លឹះក្នុងទម្រង់អត្ថបទ ឬជាលេខត្រូវបានប្រើដើម្បីតម្រៀបអារេពាក់ព័ន្ធ។ គ្រាប់ចុចរបស់អារេដែលបានធ្វើលិបិក្រមគឺជាលេខទាំងអស់ ហើយសោនីមួយៗត្រូវបានភ្ជាប់ទៅតម្លៃខុសគ្នា។
- ក្នុងអារេដែលទាក់ទងគ្នា គន្លឹះអាចជាខ្សែអក្សរ។ អារេដែលបានធ្វើលិបិក្រមជាមួយគ្រាប់ចុចចំនួនគត់ចាប់ផ្តើមពី 0 ។
- តារាងជួរឈរពីរធ្វើត្រាប់តាមឥរិយាបថនៃអារេសមាគម។ ស្រដៀងគ្នានឹងតារាងជួរឈរតែមួយត្រូវបានធ្វើលិបិក្រមអារេ។
- ផែនទីគឺជាប្រភេទអារេដែលពាក់ព័ន្ធ។ អារេលិបិក្រមមិនមែនជាផែនទីទេ។
8. តើហេបមានគុណសម្បត្តិអ្វីខ្លះលើអារេដែលបានតម្រៀប?
ប្រសិទ្ធភាពពេលវេលានៃការប្រើប្រាស់ Heap លើ Sorted Arrays គឺជាអត្ថប្រយោជន៍សំខាន់។ ខណៈពេលដែលប្រតិបត្តិការ heap កាន់តែលឿន ការតម្រៀបអារេត្រូវការពេលវេលាច្រើន។ គំនរអាចរកឃើញធាតុតូចបំផុត លឿនជាងអារេអាចត្រូវបានតម្រៀប។
ការប្រមូលលេខដែលបានផ្តល់ឱ្យអាចត្រូវបានរៀបចំតាមវិធីមួយក្នុងចំណោមវិធីពីរយ៉ាងដោយប្រើ Sorted Arrays ។ ម៉្យាងវិញទៀត សម្រាប់ការប្រមូលលេខដែលបានផ្តល់ឱ្យ អាចមានច្រើនជាងមួយ។
9. តើយើងអាចកំណត់ទំហំនៃអារេទៅជាអវិជ្ជមានបានទេ?
ទេ យើងមិនអាចកំណត់ចំនួនគត់អវិជ្ជមានជាទំហំនៃអារេបានទេ។ វានឹងមិនមានកំហុសពេលចងក្រងទេ ប្រសិនបើយើងប្រកាស។ នៅពេលដំណើរការ យើងនឹងជួបប្រទះ NegativeArraySizeException។
10. តើអ្នកកំណត់ចំនួនគត់ដែលបាត់ក្នុងអារេធាតុពី 1 ដល់ 100 ដោយរបៀបណា?
សរុបនៃស៊េរីអាចត្រូវបានគណនាដោយអនុវត្តមុខងារដូចខាងក្រោម: n (n + 1) / 2
លុះត្រាតែអារេមិនមានលេខស្ទួន ឬមានចំនួនគត់ច្រើនជាងមួយបាត់ ទើបមុខងារនេះដំណើរការ។ ថាតើអារេមួយមានធាតុស្ទួនទេ អ្នកអាចតម្រៀបអារេដើម្បីមើលថាតើមានធាតុណាមួយដែលសមមូល។
11. តើអ្នកស្វែងរកលិបិក្រមនៃធាតុនៅក្នុងអារេដោយរបៀបណា?
លិបិក្រមរបស់ធាតុអាចត្រូវបានរកឃើញតាមរយៈការស្វែងរកលីនេអ៊ែរ ឬប្រព័ន្ធគោលពីរ។ រហូតទាល់តែវារកឃើញការផ្គូផ្គងនៃធាតុដែលត្រូវការ មុខងារស្វែងរកលីនេអ៊ែរវិលជុំវិញធាតុនីមួយៗនៅក្នុងអារេមួយ។ វាត្រឡប់លិបិក្រមនៅពេលដែលវាកំណត់ទីតាំងធាតុដែលត្រូវគ្នា។ អាស្រ័យហេតុនេះ ភាពស្មុគស្មាញខាងបណ្ដោះអាសន្ននៃការស្វែងរកលីនេអ៊ែរគឺ O. (n) ។ ទាំងអារេដែលបានតម្រៀប និងអារេមិនតម្រៀបអាចប្រើការស្វែងរកលីនេអ៊ែរ។
ដោយប្រើការស្វែងរកប្រព័ន្ធគោលពីរ ដែលបន្តបែងចែកអារេជាពាក់កណ្តាលរហូតដល់មធ្យមនៃចន្លោះពេលត្រូវគ្នានឹងធាតុដែលត្រូវការ ហើយផ្តល់លិបិក្រម អ្នកអាចទទួលបានលិបិក្រមរបស់ធាតុ ប្រសិនបើអារេត្រូវបានតម្រៀប។ អាស្រ័យហេតុនេះ ភាពស្មុគស្មាញបណ្តោះអាសន្ននៃការស្វែងរកប្រព័ន្ធគោលពីរគឺ O. (log n)។
12. តើអ្នកអាចកម្ចាត់ធាតុជាក់លាក់មួយចេញពីអារេដោយរបៀបណា?
ដោយសារអ្នកមិនអាចលុបធាតុចេញពីអារេដើមបានទេ ដោយសារពួកវាជាសំណុំថេរជាមួយនឹងទំហំដែលបានកំណត់ អ្នកសម្ភាសន៍កំពុងស្វែងរកអ្នកឱ្យណែនាំវិធីសាស្រ្តផ្សេង និងដោះស្រាយបញ្ហាដែលសំណួរចោទឡើង។ សកម្មភាពដ៏ល្អបំផុតគឺបង្កើតអារេថ្មី ដើម្បីលុបធាតុមួយ។ អ្នកអាចចម្លងធាតុពីអារេទីមួយក្នុងអារេនេះ ហើយបញ្ចូលតែធាតុដែលអ្នកចង់លុបប៉ុណ្ណោះ។
យុទ្ធសាស្រ្តមួយផ្សេងទៀតពាក់ព័ន្ធនឹងការស្វែងរកធាតុគោលដៅនៅក្នុងអារេ ហើយបន្ទាប់មកបញ្ច្រាសលំដាប់នៃធាតុទាំងអស់ដែលនៅខាងស្តាំនៃធាតុគោលដៅ។
13. តើសមភាពរបស់អារេពីរអាចផ្ទៀងផ្ទាត់បានដោយរបៀបណា?
ដំបូងអ្នកត្រូវតែផ្ទៀងផ្ទាត់ប្រវែងនៃអារេដែលបានផ្តល់ទាំងពីរ។ ធាតុដែលត្រូវគ្នានៃអារេទាំងពីរត្រូវបានប្រៀបធៀបនៅពេលដែលប្រវែងរបស់វាស្មើគ្នា។ អារេទាំងពីរនឹងត្រូវបានចាត់ទុកថាស្មើគ្នា។ ប្រសិនបើគូនីមួយៗនៃសមាសធាតុនៅក្នុងរាល់ការឆ្លើយឆ្លងគឺស្មើគ្នា។ វិធីសាស្រ្តនេះមិនត្រូវបានណែនាំឱ្យពិនិត្យមើលសមភាពនៃអារេពីរទេ ប្រសិនបើអារេមានទំហំធំព្រោះវានឹងត្រូវការពេលវេលាច្រើន។ អ្នកក៏អាចប្រើវិធីសាស្ត្រ equals() ដែលរួមបញ្ចូលក្នុងថ្នាក់ Arrays ផងដែរ ទោះជាយ៉ាងណាក៏ដោយ ប្រសិនបើអ្នកសម្ភាសន៍សួរអ្នកឱ្យប្រៀបធៀប arrays ពីរដោយមិនប្រើវិធីដែលភ្ជាប់មកជាមួយ នោះវិធីនេះនឹងមានប្រយោជន៍។
14. នៅពេលយើងពិភាក្សាអំពីអារេ តើអ្នកមានន័យយ៉ាងណាចំពោះឃ្លា "វិមាត្រ" និង "អក្សរតូច"?
"វិមាត្រ" នៃអារេគឺជាចំនួននៃសន្ទស្សន៍ ឬអក្សរតូចដែលត្រូវការដើម្បីកំណត់អត្តសញ្ញាណសមាជិកនីមួយៗ។ ការជាវ និងទំហំអាចមិនច្បាស់លាស់។ វិមាត្រគឺជាការពិពណ៌នាអំពីជួរនៃសោដែលបានអនុញ្ញាត ចំណែកឯអក្សររងជាលេខ។ មានអក្សរតូចតែមួយប៉ុណ្ណោះដែលត្រូវការសម្រាប់វិមាត្រអារេនីមួយៗ។
ឧទាហរណ៍ អារេ អារេ[10][5] មានវិមាត្រពីរ។ ទំហំ 10 នៅលើមួយនិង 5 នៅលើផ្សេងទៀត។ ដើម្បីដោះស្រាយសមាសធាតុរបស់វា អ្នកត្រូវការ subscripts ពីរ។ ទាំងពីរគឺនៅចន្លោះ 0 និង 4; មួយរវាង 0 និង 9 រួមបញ្ចូល។
សំណួរសំភាសន៍សរសេរកូដ
15. ស្វែងរកគូក្នុងអារេដែលមានផលបូកដែលបានបញ្ជាក់
ឧទាហរណ៍,
បញ្ចូល:
- លេខ = [8, 7, 2, 5, 3, 1]
- គោលដៅ = ០
លទ្ធផល:
- បានរកឃើញគូ (8, 2)
- Or
- បានរកឃើញគូ (7, 3)
បញ្ចូល:
- លេខ = [5, 2, 6, 8, 1, 9]
- គោលដៅ = ០
លទ្ធផល:
- រកមិនឃើញគូទេ។
16. ការតម្រៀបអារេប្រព័ន្ធគោលពីរជាមួយពេលវេលាលីនេអ៊ែរ
តម្រៀបអារេប្រព័ន្ធគោលពីរក្នុងពេលវេលាលីនេអ៊ែរ និងក្នុងតំបន់ថេរ។ លទ្ធផលគួរតែបង្ហាញលេខសូន្យទាំងអស់ជាមុនសិន បន្ទាប់មកលេខទាំងអស់។
ឧទាហរណ៍,
- បញ្ចូល៖ { 1, 0, 1, 0, 1, 0, 0, 1 }
- លទ្ធផល៖ { 0, 0, 0, 0, 1, 1, 1, 1 }
វិធីសាស្រ្តត្រង់គឺដើម្បីគណនាចំនួនសរុបរបស់អារេ 0s និយាយថា k ហើយបន្ទាប់មកបំពេញសន្ទស្សន៍ k ដំបូងក្នុងអារេជាមួយ 0s និងសន្ទស្សន៍ដែលនៅសល់ជាមួយ 1។ ជាជម្រើសមួយ យើងអាចគណនាចំនួន 1s សរុបនៅក្នុង អារេ k បំពេញសន្ទស្សន៍ k ចុងក្រោយក្នុងអារេជាមួយ 1 ហើយទុកសន្ទស្សន៍ដែលនៅសល់ដោយ 0 ។
វិធីសាស្រ្តដែលបានផ្តល់ឱ្យមានភាពស្មុគស្មាញពេលវេលា O(n) ហើយមិនប្រើកន្លែងផ្ទុកបន្ថែមដែល n គឺជាទំហំនៃការបញ្ចូល។
17. ស្វែងរកផលិតផល two-int ធំបំផុតក្នុងអារេមួយ។
ស្វែងរកផលិតផលធំបំផុតនៃលេខពីរក្នុងអារេចំនួនគត់។
សូមគិតអំពីអារេ 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. តើត្រូវជំនួសធាតុនីមួយៗនៃអារេដោយរបៀបណា ដោយមិនប្រើប្រយោគបែងចែកជាមួយផលិតផលនៃធាតុនីមួយៗក្នុងអារេ?
ដោយមិនប្រើសញ្ញាប្រមាណវិធីបែងចែក ជំនួសធាតុនីមួយៗក្នុងអារេចំនួនគត់ជាមួយនឹងផលិតផលនៃធាតុផ្សេងទៀតទាំងអស់។
នៅក្នុងពេលវេលាលីនេអ៊ែរ និងចន្លោះថេរ យើងអាចប្រើប្រាស់ការហៅឡើងវិញដើម្បីដោះស្រាយបញ្ហានេះ។ ការគណនាឡើងវិញនូវផលិតផលនៃធាតុនីមួយៗនៅក្នុង subarray ខាងស្តាំ និងឆ្លងកាត់ផលិតផល subarray ខាងឆ្វេងដែលជាប៉ារ៉ាម៉ែត្រមុខងារគឺជាសញ្ញាណ។
ភាពស្មុគស្មាញនៃពេលវេលាគឺ O(n) ។
23. ស្វែងរកធាតុសេសបំផុតក្នុងអារេក្នុងពេលវេលាលោការីត
ដោយបានផ្តល់ឱ្យអារេចំនួនគត់ដែលសមាជិកទាំងអស់លើកលែងតែមួយមានចំនួនគូនៃការកើតឡើង បញ្ហាគឺដើម្បីកំណត់ថាតើធាតុមួយនេះលេចឡើងប៉ុន្មានដង។ ស្វែងរកធាតុដែលកើតឡើងសេសក្នុងពេលវេលាលោការីត និងចន្លោះថេរ ប្រសិនបើធាតុដូចគ្នាកើតឡើងជាគូក្នុងអារេ ហើយមិនអាចមានធាតុលើសពីពីរនៃធាតុដែលបានផ្តល់ឱ្យក្នុងមួយជួរបានទេ។
ប្រតិបត្តិការ XOR អនុញ្ញាតឱ្យយើងដោះស្រាយបញ្ហានេះក្នុងរយៈពេលលីនេអ៊ែរ។ គោលដៅគឺដើម្បី XOR រាល់ធាតុនៅក្នុងអារេ។ មានតែធាតុដែលកើតឡើងពីសេសប៉ុណ្ណោះដែលនៅមានបន្ទាប់ពីធាតុដែលកើតឡើងដដែលនោះលុបចោលគ្នា។
បញ្ហានេះអាចដោះស្រាយបានក្នុងរយៈពេល O(log(n))។
24. តើធ្វើដូចម្តេចដើម្បីទទួលបានធាតុធំជាបន្តបន្ទាប់សម្រាប់ធាតុនីមួយៗនៅក្នុងអារេរាងជារង្វង់?
ធាតុធំបន្ទាប់សម្រាប់ធាតុនីមួយៗនៅក្នុងអារេចំនួនគត់ដែលមានរាងជារង្វង់គួរតែស្ថិតនៅ។ ចំនួនគត់ធំជាងដំបូងបន្ទាប់ពីធាតុ x ក្នុងអារេ គឺជាធាតុធំជាបន្តបន្ទាប់នៃធាតុនោះ។
ពីស្តាំទៅឆ្វេង យើងអាចដំណើរការលើធាតុអារេ។ គោលដៅគឺរង្វិលជុំសម្រាប់ធាតុនីមួយៗ x រហូតដល់ជង់ទទេ ឬយើងមានធាតុខ្ពស់ជាងនៅលើវា។ កំណត់ធាតុធំបន្ទាប់នៃ x ដើម្បីបង្ហាញនៅលើកំពូលនៃជង់នៅពេលដែលវាកើតឡើង។
25. ស្វែងរកចំនួនបញ្ច្រាសនៃអារេមួយ?
ស្វែងរកចំនួនសរុបនៃការបញ្ច្រាសនៃអារេមួយ។ គូ I j) ត្រូវបានគេសំដៅថាជាការបញ្ច្រាសនៃអារេ A ប្រសិនបើ I j) និង (A[i]> A[j])។ យើងត្រូវរាប់រាល់គូទាំងនេះក្នុងអារេ។
ការរាប់សមាជិកអារេទាំងអស់ដែលមានចំនួនតិចជាងវាទៅខាងស្ដាំរបស់វា ហើយបន្ថែមលទ្ធផលទៅលទ្ធផលគឺជាវិធីសាស្រ្តត្រង់។
ដំណោះស្រាយនេះមានភាពស្មុគស្មាញ O(n2) ដែល n ជាទំហំនៃការបញ្ចូល។
26. តើអ្វីទៅជាបញ្ហាទឹកភ្លៀង?
ការស្វែងរកទឹកច្រើនបំផុតដែលអាចជាប់នៅក្នុងរបារដែលបានផ្តល់ឱ្យដែលមានទទឹងនៃឯកតានីមួយៗត្រូវបានគេស្គាល់ថាជាបញ្ហា "អន្ទាក់ទឹកភ្លៀង" ។
គោលដៅគឺដើម្បីកំណត់របារខ្ពស់បំផុតដែលអាចត្រូវបានដាក់នៅខាងឆ្វេងនិងខាងស្តាំនៃរបារនីមួយៗ។ អប្បបរមានៃរបារនាំមុខនៅខាងឆ្វេង និងខាងស្តាំ តិចជាងកម្ពស់នៃរបារបច្ចុប្បន្ន គឺជាបរិមាណទឹកដែលត្រូវបានរក្សាទុកនៅលើកំពូលនៃរបារនីមួយៗ។
សន្និដ្ឋាន
បើប្រៀបធៀបទៅនឹងប្រធានបទរចនាសម្ព័ន្ធទិន្នន័យផ្សេងទៀត អារេគឺសាមញ្ញជាង។ ដើម្បីសួរសំណួរសំភាសន៍អារេ អារេ អ្នកត្រូវមានការយល់ដឹងជាមូលដ្ឋានអំពីអារេ។
អ្នកគួរតែពិនិត្យមើលឱ្យបានទូលំទូលាយនូវមូលដ្ឋានគ្រឹះនៃអារេ រួមទាំងប្រតិបត្តិការអារេ (ពីការប្រកាស/បង្កើតអារេ ដល់ការចូលប្រើ/កែប្រែធាតុអារេ) ក៏ដូចជាគោលគំនិតនៃការសរសេរកម្មវិធីដូចជា រង្វិលជុំ ការហៅឡើងវិញ និងប្រតិបត្តិករមូលដ្ឋាន ដើម្បីឆ្លើយសំណួរសម្ភាសន៍អារេដោយជោគជ័យ។ ទទួលស្គាល់បញ្ហាទាំងស្រុង។
អ្នកគួរតែស្វែងរកការបំភ្លឺ ប្រសិនបើអ្នកមានសំណួរណាមួយ។ គិតអំពីការបែងចែកបញ្ហាទៅជាផ្នែកដែលអាចគ្រប់គ្រងបាន។ ត្រូវប្រាកដថាអ្នកមានក្បួនដោះស្រាយនៅក្នុងចិត្ត មុនពេលអ្នកចាប់ផ្តើមសរសេរកម្មវិធី។ សរសេរវាចុះ ឬមើលវានៅក្នុងគំនូសតាងលំហូរ។ បន្ទាប់មកចាប់ផ្តើមសរសេរកូដ។
សូមផ្ដល់យោបល់