[Powered by Google Translate] [Seminar: Texniki Müsahibələr] [Kenny Yu, Harvard Universiteti] [Bu CS50 edir.] [CS50.TV] Salam hər kəs, mən Kenny edirəm. Hal-hazırda kiçik öyrənilməsi kompüter edirəm. , Mən keçmiş CS TF oldum və mən bir underclassman olanda mən bu idi arzulayıram Mən bu seminar verirəm niyə və ki. Belə ki, mən onu zövq ümid edirik. Bu seminar, texniki müsahibələr haqqında və bütün resursları, bu link əldə edə bilərsiniz Burada bu link, ehtiyatların bir neçə. Mən bir neçə problemlər, əslində, problemlərin bir siyahısını etdi. Biz ipuçları tapa bilərsiniz Həmçinin ümumi ehtiyatları səhifə müsahibə üçün hazırlamaq üçün necə, Əgər faktiki müsahibə zamanı nə etməlidir haqqında məsləhətlər, həmçinin gələcək sened üçün problemləri və ehtiyatları yaxınlaşmaq necə. Bu, bütün online. Və yalnız bu seminar, bir disclaimer, giriş üçün bu kimi lazımdır - Sizin müsahibə hazırlıq bu siyahı ilə məhdudlaşmır bilməz. Bu yalnız bir guide deməkdir və siz mütləq, mən duz bir taxıl ilə demək hər şey almaq lazımdır həm də mən sizin müsahibə hazırlanmasında sizə kömək etmək üçün istifadə hər şey istifadə edin. I növbəti bir neçə slaydlar vasitəsilə sürətləndirmək üçün gedirəm biz faktiki Case əldə edə bilərsiniz. Bir proqram engineering postion üçün müsahibə strukturu, adətən 30 dən 45 dəqiqə, şirkət olaraq çox el. Tez-tez bir ağ board kodlaşdırma olacaq. Belə ki, bu kimi, lakin tez-tez kiçik miqyaslı bir ağ board. Bir telefon müsahibəsi qarşılaşdıqda, siz yəqin ki, istifadə edəcəyik collabedit və ya Google Doc ya onlar sizin kodlaşdırma canlı görə bilərsiniz Siz telefon müsahibə keçirilir etdiyiniz zaman. Müsahibə özü adətən 2 və ya 3 problemləri kompüter elm bilik test. Və demək olar ki, mütləq kodlaşdırma iştirak edəcək. Görürsünüz ki, sualların növləri adətən data strukturları və alqoritmlər var. Və problemlər bu cür etməklə, onlar kimi, xahiş edirik ki, nə zaman və məkan mürəkkəbliyi, böyük O nədir? Tez-tez onlar da yüksək səviyyəli suallar, belə bir sistem layihələndirilməsi necə sizin kodu salınması olardı? Nə interfeys, nə dərsləri, sizin sistem nə modulları var, və bu necə birlikdə qarşılıqlı edirsiniz? Belə data strukturları və alqoritmlər, həmçinin dizayn sistemi. Biz Case üçün dalış əvvəl bəzi ümumi ipuçları. Mən ən əhəmiyyətli qayda həmişə yüksək səslə düşünür ola düşünürəm. Müsahibə sizin düşüncə prosesi off göstərmək üçün şans olması ehtimal edilir. Müsahib ölçmek üçün müsahibə nöqtəsi necə düşünürsünüz və necə bir problem keçir. Edə bilərsiniz ən pis şey, bütün müsahibə boyunca ola səssiz edir. Bu yalnız heç bir yaxşı. Bir sual verilir, siz həmçinin sual başa əmin etmək istəyirəm. Belə ki, öz sözləri ilə geri sual təkrar və cəhd hərtərəfli bir neçə sadə test hallarda iş Siz sual başa əmin etmək. Bir neçə test hallarda vasitəsilə iş də bu problemi həll etmək üçün necə bir intuisiya verəcək. Siz hətta bir neçə nümunələri siz bu problemi həll kömək tapmaq bilər. Onların böyük tip incidir əldə edir. Incidir almaq etməyin. Müsahibələr çətin, lakin siz edə bilərsiniz ən pis şey, səssiz olmaqla yanaşı, aşkar incidir edilir. Siz Müsahib ki, təəssürat vermək istəmirəm. Bir şey ki, - belə ki, bir çox insanlar, onlar müsahibə getmək zaman, onlar, ilk ən yaxşı həll tapmağa cəhd zaman, həqiqətən, bir glaringly Aşkar həll adətən var. Bu yavaş ola bilər, bu səmərəsiz ola bilər, lakin yalnız göstərməlidir yalnız belə daha yaxşı işləmək üçün bir başlanğıc nöqtəsi var. Həmçinin, həll işarə baxımından yavaş böyük O zaman mürəkkəbliyi və ya kosmik mürəkkəbliyi, siz anlamaq ki, Müsahib nümayiş olunacaq bu məsələlər kodu yazarkən. Belə ki, ilk sadə alqoritmi ilə gəlmək qorxma və sonra orada daha yaxşı işləyir. Hər hansı sual, bu günə qədər? Okay. Belə edək ilk problem dalış. "N integers bir sıra nəzərə alaraq, array shuffles bir funksiya yazmaq n integers bütün permutations bərabər güman ki, belə yerdə. " Və mövcud bir təsadüfi tam generator var güman yarısı üçündür, 0-dan i bir sıra bir tamsayı yaradır. Hər kəs bu suala anlamaq varmı? Mən sizə n integers bir sıra vermək, sizə shuffle onu istəyirik. Mənim kataloqu, mən nə demək nümayiş bir neçə proqramları yazdı. Mən, shuffle 20 elementlər bir sıra gedirəm -10 ildən +9 üçün və sizə bu kimi bir siyahı çıxış etmək istəyirəm. Belə ki, bu mənim sıralanır giriş array və mən sizə shuffle onu istəyirik. Biz bunu edəcəyik. Hər kəs sual anlamaq varmı? Okay. Belə ki, siz qalmışdır. Bəzi fikirlər var? Siz n ^ 2, n log n, n kimi bunu edə bilərəmmi? Təklif açın. Okay. Emmy təklif Belə bir fikir, ilk 0-dan 20-a təsadüfi sayı, təsadüfi tam, bir sıra hesablamaq edir. Belə ki, bizim array 20 uzunluğu daşımır. 20 elementlər bizim sxemdə, bu giriş array edir. Və indi, onun təklif, yeni bir sıra yaratmaq Bu çıxış array olacaq. Və i Rand ilə geri əsasında - i idi ki,, 17, deyək ilk mövqeyi 17-ci element surəti. İndi silmək lazımdır - biz burada bütün elementləri keçmək lazımdır artıq biz sonunda bir boşluq və ortada heç bir deşik var. İndi biz prosesi təkrar edin. İndi 0 və 19 arasında yeni bir təsadüfi tam seçin. Biz burada yeni bir i var və biz bu mövqeyi bu element surəti. Sonra biz artıq maddələr keçmək və biz tam yeni array qədər biz prosesi təkrar edin. Bu alqoritm run zaman nədir? Yaxşı, bu təsiri hesab edək. Biz hər bir element dəyişir. Biz bu i aradan qaldırılması zaman, biz sola sonra bütün elementlər dəyişir. Və bir O (n) dəyəri çünki biz ilk element aradan əgər? Belə ki, hər bir aradan qaldırılması üçün, biz aradan qaldırılması - hər qaldırılması, bir O (n) əməliyyat götürür biz kaldırma n yana, bu O (n ^ 2) shuffle gətirib çıxarır. Okay. Belə ki, yaxşı bir başlanğıc. Yaxşı başlanğıc. Digər bir təklif isə Knuth shuffle kimi tanınan bir şey istifadə etmək və ya Fisher-Yates shuffle. Və həqiqətən xətti vaxt shuffle var. Və fikir çox oxşardır. Yenə biz daxil array var amma yerinə giriş / çıxış üçün iki seriallarda istifadə, biz qarışdırılmış hissəsi takip serialın ilk hissəsi istifadə və biz takip, sonra biz unshuffled hissəsi bizim serialın istirahət buraxın. Belə ki, burada nə demək deyil. Biz başlamaq - biz bir i seçin 0-dan 20-bir sıra. Bizim cari göstərici birinci index işarə edir. Biz bəzi i burada seçmək və indi dəyişdirmək. Bu 5 idi və bu 4 Belə ki, əgər nəticəsində array burada 5 burada və 4 olacaq. İndi biz burada bir marker unutmayın. Sol hər şey qarışdırılmış olunur və sağ hər şeyi unshuffled olunur. İndi biz prosesi təkrar edə bilərsiniz. Biz indi 1 və 20 arasında bir təsadüfi index seçin. Belə ki, i burada yeni güman edirlər. İndi biz burada cari yeni mövqe ilə bu i dəyişdirmək. Beləliklə, biz bu kimi geri və irəli dəyişdirmə yoxdur. Mənə daha konkret etmək kodu getirsin. Biz i bizim seçimi ilə başlamaq - i 0 bərabər biz başlamaq, biz təsadüfi yeri j seçin bu serialın unshuffled hissəsi, i, n-1. Mən burada oldum Belə ki, burada və array qalan arasında təsadüfi index seçmək və biz dəyişdirmək. Bu shuffle sizin array üçün lazım olan bütün kodu. Hər hansı sual? Yaxşı, bir sual lazım, niyə bu doğru deyil? Niyə hər permutation bərabər güman edir? Və mən, bu sübut ilə getməyəcək lakin kompüter çox problemləri induksiya vasitəsilə sübut edilə bilər. Necə bir çox induksiya ilə tanış var? Okay. Cool. Belə ki, sadə induksiya bu alqoritm düzgünlüyünü sübut edə bilər Sizin induksiya fərziyyə ola bilər yerləşir, güman mənim shuffle hər permutation bərabər ehtimal qaytarır qədər ilk i elementləri. İndi, i + 1 düşünün. Biz index j dəyişdirmək üçün seçin yolu ilə, , sonra ətraflı işləmək - bu səbəb Bu alqoritm qaytarır niyə ən azı bir tam sübut bərabər ehtimal ehtimal hər permutation. Bütün hüquqlar, növbəti problem. Belə ki, "mənfi sıfır, postive integers bir sıra verilir maksimum məbləği hesablayır bir funksiya yazmaq daxil array hər hansı continueous subarray edir. " Burada, məsələn, bütün nömrələri müsbət olduğu zaman, sonra hazırda ən yaxşı seçim bütün array etməkdir. 1, 2, 3, 4, 10 bərabərdir. Orada bəzi neqativ zaman, Bu halda biz yalnız ilk iki istəyirəm -1 və / və ya -3 seçilməsi bizim məbləğin aşağı gətirmək olacaq. Bəzən biz serialın ortasında başlamaq ola bilər. Bəzən biz heç bir şey seçə istəyirəm bir şey deyil yaxşı deyil. Və bəzən, payız etmək daha yaxşıdır sonra şey super böyük deyil. Belə ki, hər hansı bir fikir? (Tələbə, anlaşılmaz) >> Bəli. Mən -1 etmirlər düşünək. Sonra da mən 1000 və 20,000 seçin və ya yalnız 3 milyard seçin. Yaxşı, ən yaxşı seçim bütün nömrələri iştirak edir. Bu -1, mənfi olmasına baxmayaraq, bütün məbləğ mən -1 etmək deyil, daha yaxşıdır. Mən əvvəl qeyd ipuçlarını biri aydın aşkar etmək idi ilk və brute force həlli. Bu problem də brute force həlli nədir? Evet? [Jane] Bəli, mən brute force həll edirəm bütün mümkün birləşməsi (anlaşılmaz) əlavə olardı. [Yu] Okay. Belə ki, Jane ideyası hər cür iştirak edir - Mən paraphrasing Ben - hər mümkün davamlı subarray almaq üçün, onun məbləği hesablamaq, sonra bütün mümkün davamlı subarrays maksimum edirlər. Nə benzersiz mənim giriş array bir subarray müəyyən? Nə iki şey lazımdır, kimi? Evet? (Tələbə, anlaşılmaz) >> hüququ. A aşağı göstərici və üst bound indeksi bağlı benzersiz davamlı subarray müəyyənləşdirir. [Qadın tələbə] Biz bu unikal ədəd bir sıra var qiymətləndirilməsi edirmi? [Yu] No ona sual Beləliklə, biz array fərz edilir - bizim array bütün unikal nömrə və cavab yoxdur. Biz sonra brute force həlli, başlanğıc / son göstəriciləri istifadə edin benzersiz bizim davamlı subarray müəyyənləşdirir. Biz bütün mümkün start entries üçün təkrarlamaq Beləliklə, əgər, və bütün son entries üçün> və ya = başlamaq və > Zero. Yalnız -5 etmirlər. Burada həmçinin 0 olacaq. Evet? (Tələbə, anlaşılmaz) [Yu] Oh, sorry, bu -3 edir. Bu 2-dir, belə ki, bu -3 edir. Okay. Belə -4 ki, mövqe bitirmək üçün maksimal subarray nə -4 olduğu? Zero. Biri? 1, 5, 8. İndi -2 olduğu yer üzrə son olmalıdır. Belə ki, 6, 5, 7, və son bir 4. Bu mənim entries ki, hər şeyi Mən bu göstəricilərin hər bitmelidir olduğu transformasiya problem üçün, sonra mənim final cavab yalnız, arasında sweep almaq və maksimum edirlər. Belə ki, bu halda 8 deyil. Bu, maksimal subarray bu göstərici bitir o deməkdir ki, və əvvəl bir yerdə başladı. Hər kəs bu transformasiya subarray anlamaq varmı? Okay. Yaxşı, bu üçün təkrar həyata rəqəm imkan verir. Nin yalnız ilk bir neçə entries hesab edək. Belə ki, burada, 8 0, 0, 0, 1, 5 idi. Və sonra burada bir -2 idi ki, 6 yerə gətirdi. Mən vəziyyəti giriş zəng əgər i subproblem (i) necə bir əvvəlki subproblem cavab istifadə edə bilərsiniz bu subproblem cavab? Mən baxsaq, bu giriş, deyək. Necə baxaraq cavab 6 hesablamaq olar Bu array və bu serialın əvvəlki subproblems cavab birləşməsi? Bəli? [Qadın tələbə] Siz xərclər array almaq mövqeyi sağ əvvəl, 8 belə və sonra cari subproblem əlavə edin. [Yu], onun təklif bu iki ədəd baxmaq edir Bu sayı və bu nömrəsini. Beləliklə, bu 8 subproblem üçün cavab (1 - i) aiddir. Və beni daxil array A. zəng edək Mövqe i başa çatır ki, maksimal subarray tapmaq üçün, Mən iki seçim var: mən ya subarray davam edə bilər ki əvvəlki index başa çatıb, ya yeni bir sıra başlayın. Mən əvvəlki göstərici ilə başlayan subarray davam olsaydı sonra mən nail maksimum məbləği əvvəlki subproblem üçün cavab üstəgəl cari array giriş. Amma, mən də, yeni subarray başlayan seçim bu halda məbləğ 0 deyil. 1, üstəgəl cari array giriş - Belə cavab 0 max, subproblem i edir. Bu residiv mənada edirmi? Bizim təkrar, biz yalnız aşkar kimi, subproblem i deyil ki, əvvəlki subproblem maksimum plus mənim cari array giriş bərabərdir olan əvvəlki subarray davam deməkdir və ya 0, mənim cari index yeni subarray başlamaq. Və bir dəfə biz final cavab sonra, həllər bu cədvəl tikilib, yalnız subproblem array arasında xətti sweep etmək və maksimum edirlər. Bu yalnız nə dəqiq təzahürüdür. Yəni biz yeni bir subproblem dizi, subproblems yaradır. İlk giriş 0 və ya ilk giriş, bu iki maksimum ya edir. Və subproblems qalan biz yalnız aşkar dəqiq təkrar istifadə edin. İndi bizim subproblems array maksimum hesablamaq və son cavab var. Belə ki, necə çox yer biz bu alqoritm istifadə edir? Yalnız CS50 qəbul etdik, onda çox yer müzakirə ola bilər. Bəli, qeyd üçün bir şey ölçüsü n burada malloc adlı edir. Ki, siz nə təklif edir? Bu alqoritm linear space istifadə edir. Biz daha yaxşı edə bilərəmmi? Siz yekun cavab hesablamaq üçün lazımsız olduğunu qeyd edən bir şey var mı? Hərhalda daha yaxşı sual olunur, nə məlumat biz sonuna bütün yol keçirmək lazım deyil? İndi biz bu iki xətləri baxsaq, biz yalnız, əvvəlki subproblem qayğı və biz yalnız biz heç belə uzaq gördüm maksimum qayğı. Son cavab hesablamaq üçün biz bütün array ehtiyac yoxdur. Biz son sayı, keçən iki ədəd yalnız lazımdır. Maksimum üçün subproblem dizi, və son sayı üçün son sayı. Belə ki, əslində, biz birlikdə bu loops fitil bilər və xətti kosmosdan daimi yer gedin. Kömək edib, bu günə qədər burada subproblem, bizim subproblem array rolu əvəz edir. Belə ki, cari məbləği, bu günə qədər, əvvəlki subproblem cavab deyil. Və edib, bu günə qədər bizim maks yer tutur. Biz boyunca getmək kimi Biz maksimum hesablamaq. Və biz, daimi məkanına linear space getmək və biz subarray problemin həll xətti var. Suallara bu cür bir müsahibə zamanı əldə edəcək. Vaxt mürəkkəblik nədir; yer mürəkkəblik nədir? Daha yaxşı edə bilərəmmi? Ətrafında saxlamaq lazımsız olan şeylər var? Mən sizə öz almaq lazımdır ki, təhlillərini ön plana keçirmək bunu Bu problemləri çalışırıq kimi. Həmişə "Mən daha yaxşı edə bilərəmmi?", Özünüz xahiş edilə Əslində, biz bu daha yaxşı edə bilər? Bir oyun sual Sort. Sizə lazımdır, çünki Siz bilməz ən azı problemin daxil oxuyun. Lazımdır ki, ən azı problem üçün giriş oxumaq Beləliklə siz, xətti zaman daha yaxşı edə bilməz deməkdir ki, və daimi yer daha yaxşı edə bilməz. Belə ki, bu, əslində, bu problemin ən yaxşı həlli. Suallar? Okay. Fond bazarı problemi: "Müsbət, sıfır və ya mənfi n integers, bir sıra nəzərə alaraq, ki, n gün ərzində fond qiyməti təmsil Siz edə bilərsiniz maksimum mənfəət hesablamaq üçün bir funksiyası yazmaq Bu n gün ərzində düz 1 fond alış-satış ki, verilmiş. " Əslində, biz, aşağı almaq yüksək satış istəyirəm. Və biz edə bilər yaxşı gəlir anlamaq istəyirəm. Mənim tip geri gedir, nə dərhal aydın, sadə cavab, ancaq yavaş var? Bəli? (Tələbə, anlaşılmaz) >> Bəli. >> Beləliklə, siz yalnız baxmayaraq getmək və fond qiymətləri görünür zaman hər bir nöqtəsi, (anlaşılmaz). [Yu] Okay, belə ki, onun həlli - kompüter öz təklif ən aşağı və ən yüksək hesablanması mütləq iş deyil ən yüksək və ən aşağı əvvəl baş bilər, çünki. Belə ki, bu problemin brute force həlli nədir? Mən benzersiz mən etmək mənfəət müəyyən etmək üçün lazım olan iki şey var? Sağ. The brute force həlli - oh, belə ki, Corc təklifini biz yalnız iki gün lazımdır benzersiz bu iki gün mənfəəti birbaşa müəyyən etmək. Belə ki, biz almaq / satmaq istədiyiniz hər cüt hesablamaq mənfi və ya müsbət və ya sıfır ola biləcək mənfəət, hesablamaq. Biz gün bütün cüt üzərində iterating sonra olun ki, maksimum mənfəət hesablamaq. Yəni bizim final cavab olacaq. Və həlli yoxdur, çünki, O (n ^ 2) olmaq n iki cüt seçmək olacaq - siz son gün arasında seçə bilərsiniz ki, gün. OK, belə ki, mən burada brute force həlli getmək niyyətində deyiləm. Mən n log n həll olduğunu demək gedirəm. Hal-hazırda n log n nə alqoritm bilirik? Bu oyun sual deyil. Sort Birleştirme. Birleştirme sort, n log n və əslində, bu problemin həlli yollarından biri istifadə adlı fikir birləşmə sort cür, ümumiyyətlə, bölmək və qalib. Aşağıdakı kimi Və fikirdir. Siz yaxşı alış hesablamaq / sol yarısında cüt satmaq istəyirik. Yalnız iki gün ərzində ilk n, edə bilərsiniz ən yaxşı mənfəət tapın. Sonra, ən yaxşı alış oompute / sağ yarısında cüt satmaq istəyirəm iki gün ərzində belə son n. İndi isə sual necə geri birlikdə bu həllərin birləşməsi yoxdur, var? Bəli? (Tələbə, anlaşılmaz) Okay. >> Mənə bir şəkil çəkmək imkan verir. Bəli? (George, anlaşılmaz) Məhz >>. George həll dəqiq hüququdur. Onun təklif edir, birinci, ən yaxşı alış / satış cüt hesablamaq və sol yarım baş ki, sol, sol zəng edək. Best hüququ yarısında baş verir ki, cüt almaq / satmaq. Biz yalnız bu iki ədəd müqayisədə Lakin biz işin itkin etdiyiniz Burada almaq və sağ yarısında yerdə satmaq yerləşir. Biz sol yarısında almaq, sağ yarısında satmaq. Və həm yarıya indirir yayılır ki, ən yaxşı alış / satış cüt hesablamaq üçün ən yaxşı yol burada minimum hesablamaq və burada maksimum hesablamaq üçün və fərq edir. Alış / satış cüt yalnız burada olduğu iki hallarda Belə ki, yalnız burada, və ya hər iki yarıya indirir bu üç ədəd tərəfindən müəyyən edilir. , Geri birlikdə bizim həllərin daxil etmək üçün bizim alqoritm Beləliklə biz yaxşı alış / satış cüt hesablamaq istəyirəm biz sol yarım almaq və sağ yarım satmaq yerləşir. Və bunu ən yaxşı yolu, ilk yarısında ən aşağı qiymət hesablamaq üçün ən doğru yarısında qiymət və fərq edir. Ortaya çıxan üç mənfəət, bu üç ədəd, siz üç maksimum almaq və bu ilk və son gün ərzində edə bilərsiniz ən yaxşı mənfəət var. Burada mühüm xətləri qırmızı yerləşirsiniz. Bu sol yarısında cavab hesablamaq üçün rekursiv çağırışdır. Bu hüququ yarısında cavab hesablamaq üçün rekursiv çağırışdır. Bu iki loops müvafiq olaraq, sol və sağ yarım üzrə min və max hesablamaq. İndi mən, həm də yarıya indirir əhatə edən mənfəət hesablamaq və yekun cavab bu üç maksimum deyil. Okay. Belə ki, əmin, biz bir alqoritm var, amma daha böyük sual Bu zaman mürəkkəblik nədir? Mən birləşmə cür qeyd səbəbi bu formada cavab bölmək ki, iki və daha sonra geri birlikdə bizim həllərin birləşmə dəqiq birləşməsi növ formasıdır. Mənə müddəti ilə gedək. Biz addımların sayı bir funksiyası t (n) müəyyən edin n gün, iki recursive zənglər hər t (n / 2), başa gedir və bu zənglər iki var. İndi, sol yarısının minimum hesablamaq lazımdır Mən n / 2 dəfə, üstəgəl sağ yarım maksimum nə bilər. Belə ki, bu yalnız n. Və sonra bir daimi iş plus. Bu təkrarlanma tənliklər dəqiq birləşməsi sort üçün təkrarlanma tənliklər edir. Və biz bütün növ birləşmə n log n zaman bilirik. Buna görə də, bizim alqoritmi də log n vaxt n. Bu iteration mənada edirmi? Bu yalnız qısa bir recap: T (n) maksimum mənfəət hesablamaq üçün addımlar sayı n gün ərzində. Biz recursive zəng parçalanması yolu , ilk n / 2 gün bizim həll zəng edir ki, bir zəng, var və sonra ikinci yarısında yenidən zəng. Belə ki, iki zəng var. Və sonra biz xətti vaxt edə bilərsiniz ki, sol yarısında bir minimum tapmaq biz xətti vaxt edə bilərsiniz olan sağ yarısı maksimum tapa bilərsiniz. Belə ki, n / 2 + n / 2 yalnız n. Sonra biz hesab edirik kimi bəzi daimi iş var. Bu təkrarlanma tənliklər dəqiq birləşməsi sort üçün təkrarlanma tənliklər edir. Beləliklə, bizim shuffle alqoritm da n n daxil edin. Belə ki, necə çox yer biz istifadə olunur? Nin kodu geri edək. Daha yaxşı bir sual, nə çox yığını çərçivəsində biz heç bir anda var olunur? Biz recursion istifadə etdiyiniz ildən, yığını çərçivəsində sayı bizim kosmik istifadə müəyyənləşdirir. Nin n = 8 hesab edək. Biz, 8 shuffle zəng ilk dörd entries haqqında shuffle zəng edəcək ilk iki entries bir shuffle zəng edəcək. Belə ki, bizim yığını deyil - bu, bizim yığını deyil. Və sonra biz, 1 təkrar shuffle zəng və bizim əsas işi nədir, biz dərhal qayıtmaq. Biz heç bu çox yığını çərçivəsində daha çox var? No biz bir sehr etmək hər zaman olduğundan, shuffle bir recursive sehr, biz yarısında bizim ölçüsü bölmək. Biz heç bir anda var yığını çərçivəsində maksimum sayı Beləliklə log n yığını çərçivəsində əmri edir. Hər bir yığını çərçivəsində daimi yer var alan və buna görə də ümumi məbləği biz heç istifadə sahəsi maksimum O (Giriş n) sahibidir Ü n gün sayı. İndi, həmişə özünüzü xahiş, "biz daha yaxşı edə bilərəmmi?" Və xüsusilə də, biz artıq həll etdik bir problem bu azalda bilər? A ipucu: yalnız əvvəl iki digər problemləri müzakirə, və shuffle olacaq deyil. Biz maksimal subarray problem bu fond bazarında problem çevirə bilərsiniz. Biz bunu edə bilər? Əgər biri? Emmy? (Emmy, anlaşılmaz) [Yu] Exactly. Maksimal subarray problem Belə ki, biz davamlı subarray bir məbləğ üçün arıyorsanız. Və səhmlərinin problem üçün Emmy təklifi, dəyişikliklər və ya deltalar hesab edir. Bu bir şəkil - Bu fond qiymət, lakin biz hər ardıcıl gün arasında fərq etdi olduqda - biz maksimum qiyməti maksimum mənfəət biz edə bilər ki Burada almaq və burada satmaq əgər. Amma nin davamlı baxaq - nin subarray problem baxaq. Odur ki, biz edə bilər - burada burada gedən, biz bir müsbət dəyişiklik var və sonra burada buradan gedən bir mənfi dəyişiklik yoxdur. Amma sonra biz böyük bir müsbət dəyişiklik buradan burada gedir. Bu bizim son mənfəət əldə etmək yekunlaşdırmaq istəyirəm ki, dəyişikliklər var. Sonra daha çox mənfi dəyişikliklər burada var. Bizim maksimal subarray problem bizim fond problem azaldılması üçün əsas gün arasında deltalar hesab edir. Belə ki, biz, deltalar adlı yeni array yaratmaq , 0 olmaq üçün ilk giriş başlamaq və sonra hər delta (i), fərq ki, qoy mənim giriş array (i) və array (i - 1). Sonra biz maksimal subarray üçün adi prosedur zəng bir delta-nin array keçən. Və maksimal subarray xətti vaxt, çünki və bu azalma, bu delta array yaradılması bu prosesi, da xətti dəfə sonra səhmlər üçün yekun həlli O (n) iş plus O (n) iş hələ də O (n) əsəridir. Belə ki, biz problemin xətti vaxt həll var. Hər kəs bu transformasiya anlamaq varmı? Həmişə var ki, ümumiyyətlə, yaxşı bir fikir siz gördükdə yeni bir problem azaltmaq üçün cəhd edir. Bir köhnə problem tanış görünür, köhnə problem onu ​​azaldılması çalışırıq. Və siz köhnə problem istifadə etdiyiniz bütün vasitələrdən istifadə edə bilər, əgər yeni problem həll etsin. Belə ki, bükmək üçün texniki müsahibələr çətin olunur. Bu problemlər yəqin ki, daha çətin problemlər bəzi Bir müsahibəsində görə bilərsiniz ki, Mən yalnız əhatə edən bütün problemləri başa düşmürəm, əgər ki, tamam. Bu daha çətin problemlər bəzi. Təcrübə, təcrübə, təcrübə. Mən sədəqə problemlər bir çox verdi, belə ki, mütləq o oldu. Və müsahibələr uğurlar. Bütün ehtiyatları, bu link yerləşdirilir və mənim böyük dostlarından biri, istehza texniki müsahibələr bunu təklif etdi siz maraqlı etdiyiniz əgər, e-poçt e-poçt ünvanı Yao Will. Bir sualınız varsa, mənə verə bilərsiniz. Uşaqlar texniki müsahibələr bağlı konkret sual yoxdur və ya biz bu günə qədər gördüm hər hansı bir problem? Okay. Bəli, müsahibələr uğurlar. [CS50.TV]