1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminarium: Techniczne Wywiady]

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Harvard University]

3
00:00:04,630 --> 00:00:08,910
[To jest CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Witam wszystkich, jestem Kenny. Jestem obecnie młodszy studiowania informatyki.

5
00:00:12,420 --> 00:00:17,310
Jestem byłym CS TF, i chciałbym mieć to, kiedy byłem Underclassman,

6
00:00:17,310 --> 00:00:19,380
i dlatego daję tym seminarium.

7
00:00:19,380 --> 00:00:21,370
Więc mam nadzieję, że się spodoba.

8
00:00:21,370 --> 00:00:23,470
To seminarium jest o technicznych wywiadów

9
00:00:23,470 --> 00:00:26,650
i wszystkie moje zasoby można znaleźć pod tym linkiem,

10
00:00:26,650 --> 00:00:32,350
ten link tutaj, kilka zasobów.

11
00:00:32,350 --> 00:00:36,550
Więc zrobiłem listę problemów, faktycznie, sporo problemów.

12
00:00:36,550 --> 00:00:40,800
Także ogólnie strona zasobów, gdzie możemy znaleźć wskazówki

13
00:00:40,800 --> 00:00:42,870
jak przygotować się do rozmowy kwalifikacyjnej

14
00:00:42,870 --> 00:00:46,470
wskazówek na temat tego, co należy zrobić w czasie rzeczywistym rozmowy,

15
00:00:46,470 --> 00:00:51,910
, jak również w jaki sposób podejść do problemów i zasobów w przyszłości.

16
00:00:51,910 --> 00:00:53,980
To wszystko online.

17
00:00:53,980 --> 00:00:58,290
I właśnie do przedmowa tego seminarium, zrzeczenie się,

18
00:00:58,290 --> 00:01:00,690
jak to nie powinno - przygotowań do rozmowy

19
00:01:00,690 --> 00:01:02,800
nie powinna być ograniczona do tej listy.

20
00:01:02,800 --> 00:01:04,750
To jest tylko ma być przewodnikiem,

21
00:01:04,750 --> 00:01:08,890
i powinno się brać wszystko, co mówię z przymrużeniem oka,

22
00:01:08,890 --> 00:01:14,620
ale również wykorzystać wszystko, co używane, aby pomóc Ci w przygotowaniu do rozmowy kwalifikacyjnej.

23
00:01:14,620 --> 00:01:16,400
>> Zamierzam przyspieszyć zmianę kilku następnych slajdach

24
00:01:16,400 --> 00:01:18,650
więc możemy dostać się do rzeczywistych studiów przypadków.

25
00:01:18,650 --> 00:01:23,630
Struktura wywiadzie dla postion inżynierii oprogramowania,

26
00:01:23,630 --> 00:01:26,320
zwykle jest to 30 do 45 minut,

27
00:01:26,320 --> 00:01:29,810
kilka rund, w zależności od firmy.

28
00:01:29,810 --> 00:01:33,090
Często będziesz kodowania na tablicy.

29
00:01:33,090 --> 00:01:35,960
Więc jak to biała tablica, ale często w mniejszej skali.

30
00:01:35,960 --> 00:01:38,540
Jeśli masz rozmowę telefoniczną, prawdopodobnie będziesz używać

31
00:01:38,540 --> 00:01:44,030
albo collabedit lub Google Doc, aby mogli zobaczyć żyjesz kodowania

32
00:01:44,030 --> 00:01:46,500
gdy jesteś przesłuchiwania przez telefon.

33
00:01:46,500 --> 00:01:48,490
Wywiad sam w sobie jest zazwyczaj 2 lub 3 problemy

34
00:01:48,490 --> 00:01:50,620
testuje swoją wiedzę informatyczną.

35
00:01:50,620 --> 00:01:54,490
I to prawie na pewno obejmować kodowania.

36
00:01:54,490 --> 00:01:59,540
Rodzaje pytań, na które będzie można zobaczyć zazwyczaj struktury danych i algorytmy.

37
00:01:59,540 --> 00:02:02,210
I czyniąc tego rodzaju problemów,

38
00:02:02,210 --> 00:02:07,830
poprosi cię, jak, to, co jest czas i złożoność przestrzeni, duży O?

39
00:02:07,830 --> 00:02:09,800
Często również zapytać nadrzędne pytania

40
00:02:09,800 --> 00:02:12,530
Tak więc, system projektowania,

41
00:02:12,530 --> 00:02:14,770
jak można ułożyć swój kod?

42
00:02:14,770 --> 00:02:18,370
Co interfejsy, jakie ćwiczenia, jakie moduły masz w systemie,

43
00:02:18,370 --> 00:02:20,900
i jak one współdziałają ze sobą?

44
00:02:20,900 --> 00:02:26,130
Więc struktury danych i algorytmy oraz systemy projektowania.

45
00:02:26,130 --> 00:02:29,180
>> Kilka ogólnych wskazówek Zanim zagłębimy się w naszych studiach przypadku.

46
00:02:29,180 --> 00:02:32,300
Myślę, że najważniejszą zasadą jest zawsze głośno myślę.

47
00:02:32,300 --> 00:02:36,980
Wywiad ma być Twoja szansa, aby pokazać swój proces myślenia.

48
00:02:36,980 --> 00:02:39,820
Punkt wywiadu jest wywiad, aby ocenić

49
00:02:39,820 --> 00:02:42,660
jak myślisz i jak można przejść przez problem.

50
00:02:42,660 --> 00:02:45,210
Najgorsze co można zrobić, to milczeć przez cały wywiad.

51
00:02:45,210 --> 00:02:50,090
To po prostu nie jest dobre.

52
00:02:50,090 --> 00:02:53,230
Kiedy dostaniesz pytanie, chcemy także upewnić się, że rozumiem pytanie.

53
00:02:53,230 --> 00:02:55,350
Więc powtórzyć pytanie z powrotem własnymi słowami

54
00:02:55,350 --> 00:02:58,920
i próba pracy gruntownych kilka prostych przypadków testowych

55
00:02:58,920 --> 00:03:01,530
upewnić się, że rozumiem pytanie.

56
00:03:01,530 --> 00:03:05,510
Praca przez kilka przypadków testowych udzielają też intuicję, w jaki sposób rozwiązać ten problem.

57
00:03:05,510 --> 00:03:11,210
Można nawet odkryć kilka wzorców, które pomogą Ci rozwiązać problem.

58
00:03:11,210 --> 00:03:14,500
Ich duża wskazówka jest nie denerwować.

59
00:03:14,500 --> 00:03:17,060
Nie sfrustrowani.

60
00:03:17,060 --> 00:03:19,060
Rozmowy są trudne, ale najgorsze, co można zrobić,

61
00:03:19,060 --> 00:03:23,330
oprócz tego, że milczy, należy wyraźnie sfrustrowany.

62
00:03:23,330 --> 00:03:27,410
Nie chcesz dać takie wrażenie na wywiad.

63
00:03:27,410 --> 00:03:33,960
Jedna rzecz, że - tak, wiele osób, gdy idą do wywiadu,

64
00:03:33,960 --> 00:03:37,150
próbują spróbować znaleźć najlepsze rozwiązanie pierwsze,

65
00:03:37,150 --> 00:03:39,950
kiedy tak naprawdę, to zwykle rażąco oczywiste rozwiązanie.

66
00:03:39,950 --> 00:03:43,500
To może być powolne, może być nieskuteczne, ale należy po prostu podać go,

67
00:03:43,500 --> 00:03:46,210
tak więc masz punkt wyjścia, z którego można pracować lepiej.

68
00:03:46,210 --> 00:03:48,270
Ponadto wskazuje się na rozwiązanie jest powolne, w zakresie

69
00:03:48,270 --> 00:03:52,160
duża złożoność O lub złożoność przestrzeni,

70
00:03:52,160 --> 00:03:54,450
będzie udowodnić, że rozumie ankietera

71
00:03:54,450 --> 00:03:57,510
te kwestie podczas pisania kodu.

72
00:03:57,510 --> 00:04:01,440
Więc nie bój się wymyślić najprostszym algorytmie

73
00:04:01,440 --> 00:04:04,950
i lepiej tam.

74
00:04:04,950 --> 00:04:09,810
Wszelkie pytania do tej pory? Okay.

75
00:04:09,810 --> 00:04:11,650
>> Warto więc zagłębić się nasz pierwszy problem.

76
00:04:11,650 --> 00:04:14,790
"Biorąc pod uwagę wartości całkowitych n, napisać funkcję tasuje tablicę

77
00:04:14,790 --> 00:04:20,209
w miejscu takim, że wszystkie permutacje liczb całkowitych n są jednakowo prawdopodobne. "

78
00:04:20,209 --> 00:04:23,470
I że masz dostępne losowy generator liczb całkowitych

79
00:04:23,470 --> 00:04:30,980
który generuje liczbę całkowitą w zakresie od 0 do i, zakres pół.

80
00:04:30,980 --> 00:04:32,970
Czy wszyscy rozumieją to pytanie?

81
00:04:32,970 --> 00:04:39,660
Daję ci tablicę liczb całkowitych n, i chcę Ci Shuffle to.

82
00:04:39,660 --> 00:04:46,050
W moim katalogu, napisałem kilka programów, aby wykazać, co mam na myśli.

83
00:04:46,050 --> 00:04:48,910
Idę shuffle tablicę 20 elementów,

84
00:04:48,910 --> 00:04:52,490
od -10 do +9,

85
00:04:52,490 --> 00:04:57,050
i chcę Ci wyeksportować listę takiego.

86
00:04:57,050 --> 00:05:02,890
Więc to jest mój posortowana tablica wejściowa, i chcę Ci Shuffle to.

87
00:05:02,890 --> 00:05:07,070
Zrobimy to jeszcze raz.

88
00:05:07,070 --> 00:05:13,780
Czy wszyscy rozumiem pytanie? Okay.

89
00:05:13,780 --> 00:05:16,730
Więc to zależy od Ciebie.

90
00:05:16,730 --> 00:05:21,220
Jakie są pomysły? Można to zrobić jak n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Otwarty na propozycje.

92
00:05:34,400 --> 00:05:37,730
Okay. Więc jeden pomysł, zaproponowany przez Emmy,

93
00:05:37,730 --> 00:05:45,300
jest najpierw obliczyć liczbę losową, losową liczbę całkowitą, w zakresie od 0 do 20.

94
00:05:45,300 --> 00:05:49,840
Więc zakładamy nasza tablica ma długość 20.

95
00:05:49,840 --> 00:05:54,800
W naszym schemacie 20 elementów,

96
00:05:54,800 --> 00:05:58,560
to jest nasza tablica wejściowa.

97
00:05:58,560 --> 00:06:04,590
I teraz, jej propozycja jest, aby utworzyć nową tablicę,

98
00:06:04,590 --> 00:06:08,440
więc będzie tablicy wyjściowej.

99
00:06:08,440 --> 00:06:12,880
I na podstawie i zwrócony przez rand -

100
00:06:12,880 --> 00:06:17,580
więc gdybym był, powiedzmy, 17,

101
00:06:17,580 --> 00:06:25,640
skopiować 17-gi element do pierwszej pozycji.

102
00:06:25,640 --> 00:06:30,300
Teraz musimy usunąć - musimy przenieść wszystkie elementy tutaj

103
00:06:30,300 --> 00:06:36,920
się tak, że mamy lukę na końcu i nie ma dziury w środku.

104
00:06:36,920 --> 00:06:39,860
A teraz mamy powtórzyć proces.

105
00:06:39,860 --> 00:06:46,360
Teraz możemy wybrać nowy losową liczbę całkowitą z przedziału od 0 do 19 lat.

106
00:06:46,360 --> 00:06:52,510
Mamy nowy I tu, i skopiować ten element do tej pozycji.

107
00:06:52,510 --> 00:07:00,960
Następnie przesunąć elementy nad i powtarzamy proces, aż mamy pełne nową tablicę.

108
00:07:00,960 --> 00:07:05,890
Co to jest czas pracy tego algorytmu?

109
00:07:05,890 --> 00:07:08,110
Cóż, brać pod uwagę wpływ tego.

110
00:07:08,110 --> 00:07:10,380
Przenoszeni jesteśmy każdy element.

111
00:07:10,380 --> 00:07:16,800
Gdy usuwamy to ja, my przenosimy wszystkie elementy po niej w lewo.

112
00:07:16,800 --> 00:07:21,600
I to O (n) kosztów

113
00:07:21,600 --> 00:07:26,100
bo co, jeśli usuwamy pierwszy element?

114
00:07:26,100 --> 00:07:29,670
Więc dla każdego wyprowadzenia, usuwamy -

115
00:07:29,670 --> 00:07:32,170
Każda przeprowadzka ponosi O (n) operacji,

116
00:07:32,170 --> 00:07:41,520
a ponieważ mamy n przeprowadzki, prowadzi to do (n ^ 2) O shuffle.

117
00:07:41,520 --> 00:07:49,550
Okay. Tak dobry start. Dobry początek.

118
00:07:49,550 --> 00:07:55,290
>> Kolejna propozycja to użyć czegoś znanego jako shuffle Knuth,

119
00:07:55,290 --> 00:07:57,540
lub Fisher-Yates shuffle.

120
00:07:57,540 --> 00:07:59,630
I to jest rzeczywiście liniowy Shuffle czas.

121
00:07:59,630 --> 00:08:02,200
A pomysł jest bardzo podobny.

122
00:08:02,200 --> 00:08:05,160
Znowu mamy tablicę wejście,

123
00:08:05,160 --> 00:08:08,580
ale zamiast dwóch tablic dla naszego wejścia / wyjścia,

124
00:08:08,580 --> 00:08:13,590
używamy pierwszą część tablicy do śledzenia naszego przetasowana porcji

125
00:08:13,590 --> 00:08:18,400
i śledzić, a potem zostawić resztę naszej tablicy na unshuffled porcji.

126
00:08:18,400 --> 00:08:24,330
Więc tutaj jest to, co mam na myśli. Zaczniemy - mamy wyboru i,

127
00:08:24,330 --> 00:08:30,910
tablicy od 0 do 20.

128
00:08:30,910 --> 00:08:36,150
Nasz obecny wskaźnik jest skierowany do pierwszego indeksu.

129
00:08:36,150 --> 00:08:39,590
Mamy do wyboru kilka i tu

130
00:08:39,590 --> 00:08:42,740
a teraz zamienić.

131
00:08:42,740 --> 00:08:47,690
Więc jeśli to było 5 i to było 4,

132
00:08:47,690 --> 00:08:57,150
array końcowy będzie miał 5 Tu i 4 tutaj.

133
00:08:57,150 --> 00:09:00,390
I teraz możemy zauważyć znacznik tutaj.

134
00:09:00,390 --> 00:09:05,770
Wszystko na lewo jest wymieszane,

135
00:09:05,770 --> 00:09:15,160
i wszystko, co do prawa jest unshuffled.

136
00:09:15,160 --> 00:09:17,260
I teraz możemy powtórzyć proces.

137
00:09:17,260 --> 00:09:25,210
Mamy do wyboru losowego indeksu pomiędzy 1 a 20 teraz.

138
00:09:25,210 --> 00:09:30,650
Więc załóżmy, że nasz nowy i jest tutaj.

139
00:09:30,650 --> 00:09:39,370
Teraz możemy zamienić to I z naszego aktualnego położenia nowego tutaj.

140
00:09:39,370 --> 00:09:44,790
Więc robimy swapping iz powrotem jak ten.

141
00:09:44,790 --> 00:09:51,630
Pozwól mi otworzyć kod, aby to bardziej konkretne.

142
00:09:51,630 --> 00:09:55,290
Zaczynamy z naszego wyboru i -

143
00:09:55,290 --> 00:09:58,370
zaczynamy i równa 0, możemy wybrać losowy j lokalizacji

144
00:09:58,370 --> 00:10:02,420
w unshuffled części tablicy, i do n-1.

145
00:10:02,420 --> 00:10:07,280
Więc jeśli jestem tutaj, wybrać losowy indeks pomiędzy tu i resztę tablicy,

146
00:10:07,280 --> 00:10:12,410
i swap.

147
00:10:12,410 --> 00:10:17,550
To jest cały kod niezbędny shuffle swoją tablicę.

148
00:10:17,550 --> 00:10:21,670
Masz pytanie?

149
00:10:21,670 --> 00:10:25,530
>> Cóż, trzeba było pytanie, dlaczego jest to prawidłowe?

150
00:10:25,530 --> 00:10:28,360
Dlaczego każda permutacja jednakowo prawdopodobne?

151
00:10:28,360 --> 00:10:30,410
I nie będzie przejść przez dowód tego,

152
00:10:30,410 --> 00:10:35,970
ale wiele problemów w informatyce można udowodnić przez indukcję.

153
00:10:35,970 --> 00:10:38,520
Jak wielu z was zna indukcji?

154
00:10:38,520 --> 00:10:40,590
Okay. Cool.

155
00:10:40,590 --> 00:10:43,610
Więc można udowodnić słuszność tego algorytmu przez prostą indukcję,

156
00:10:43,610 --> 00:10:49,540
gdzie hipoteza indukcyjna byłoby zakładać, że

157
00:10:49,540 --> 00:10:53,290
moja Shuffle zwraca każdy permutacji jednakowo prawdopodobne

158
00:10:53,290 --> 00:10:56,120
do pierwszych elementów i.

159
00:10:56,120 --> 00:10:58,300
Teraz rozważmy i + 1.

160
00:10:58,300 --> 00:11:02,550
A przy okazji możemy wybrać nasz j indeks swap,

161
00:11:02,550 --> 00:11:05,230
prowadzi to do - a potem opracować szczegóły,

162
00:11:05,230 --> 00:11:07,390
co najmniej pełny dowód, dlaczego ten algorytm zwraca

163
00:11:07,390 --> 00:11:12,800
każda permutacja z prawdopodobieństwem jednakowo prawdopodobne.

164
00:11:12,800 --> 00:11:15,940
>> Dobra, następny problem.

165
00:11:15,940 --> 00:11:19,170
Więc "podano tablicę liczb całkowitych, dodatnią, zero, ujemna,

166
00:11:19,170 --> 00:11:21,290
napisać funkcję obliczającą maksymalną kwotę

167
00:11:21,290 --> 00:11:24,720
każdego continueous subarray tablicy wejściowego ".

168
00:11:24,720 --> 00:11:28,370
Przykładem jest, w przypadku, gdy wszystkie liczby są pozytywne,

169
00:11:28,370 --> 00:11:31,320
następnie aktualnie najlepiej jest zabrać całą tablicę.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, jest równa 10.

171
00:11:34,690 --> 00:11:36,780
Gdy masz jakieś negatywy w tam,

172
00:11:36,780 --> 00:11:38,690
w tym przypadku chcemy tylko dwa pierwsze

173
00:11:38,690 --> 00:11:44,590
ponieważ wybór -1 i / lub -3 przyniesie naszą sumę dół.

174
00:11:44,590 --> 00:11:48,120
Czasami musimy zacząć w środku tablicy.

175
00:11:48,120 --> 00:11:53,500
Czasami chcemy wybrać w ogóle nic, to najlepiej nie brać nic.

176
00:11:53,500 --> 00:11:56,490
A czasem lepiej jest wziąć upadek,

177
00:11:56,490 --> 00:12:07,510
bo coś po niej jest super duży. Więc jakieś pomysły?

178
00:12:07,510 --> 00:12:10,970
(Student, niezrozumiały) >> Tak.

179
00:12:10,970 --> 00:12:13,560
Załóżmy, że nie biorę -1.

180
00:12:13,560 --> 00:12:16,170
Wtedy albo wybrać 1.000 i 20.000,

181
00:12:16,170 --> 00:12:18,630
lub po prostu wybierz 3 miliardy.

182
00:12:18,630 --> 00:12:20,760
Cóż, najlepiej jest podjąć wszystkie numery.

183
00:12:20,760 --> 00:12:24,350
Ten -1, mimo że negatywny,

184
00:12:24,350 --> 00:12:31,340
suma całości były lepsze niż nie podjąć -1.

185
00:12:31,340 --> 00:12:36,460
Więc jednym z porad, o których wspomniałem wcześniej było określenie wyraźnie oczywiste

186
00:12:36,460 --> 00:12:40,540
i brute force rozwiązanie pierwsze.

187
00:12:40,540 --> 00:12:44,340
Co to jest brute force w rozwiązanie tego problemu? Tak?

188
00:12:44,340 --> 00:12:46,890
[Jane] Cóż, myślę, że roztwór brute force

189
00:12:46,890 --> 00:12:52,600
byłoby dodać wszystkie możliwe kombinacje (niezrozumiałe).

190
00:12:52,600 --> 00:12:58,250
[Yu] Dobra. Więc pomysł Jane jest do podjęcia wszelkich możliwych -

191
00:12:58,250 --> 00:13:01,470
Jestem parafrazując - jest do podjęcia wszelkich możliwych ciągłego subarray,

192
00:13:01,470 --> 00:13:07,840
obliczyć jego sumę, a następnie podjąć maksymalnie wszystkie możliwe subarrays ciągłych.

193
00:13:07,840 --> 00:13:13,310
Co jednoznacznie identyfikuje subarray w mojej tablicy wejściowej?

194
00:13:13,310 --> 00:13:17,380
Podoba Ci się to, co dwie rzeczy są potrzebne? Tak?

195
00:13:17,380 --> 00:13:19,970
(Student, niezrozumiały) >> Racja.

196
00:13:19,970 --> 00:13:22,130
Dolna granica na indeksie i górnego indeksu związanego

197
00:13:22,130 --> 00:13:28,300
jednoznacznie określa ciągły subarray.

198
00:13:28,300 --> 00:13:31,400
[Studentka] Czy jesteśmy szacowania to tablica unikatowych numerów?

199
00:13:31,400 --> 00:13:34,280
[Yu] No więc jej pytanie jest, czy my zakładając naszą tablicę -

200
00:13:34,280 --> 00:13:39,000
to nasza tablica wszystkie unikatowe numery, a odpowiedź brzmi: nie.

201
00:13:39,000 --> 00:13:43,390
>> Jeśli używamy naszej brutalnej rozwiązanie siłowe, to start / end indeksy

202
00:13:43,390 --> 00:13:47,200
jednoznacznie określa nasz ciągły subarray.

203
00:13:47,200 --> 00:13:51,680
Jeśli więc iteracyjne dla wszystkich możliwych pozycji startowych,

204
00:13:51,680 --> 00:13:58,320
i wszystkich zapisów końcowych> lub = zacząć i <n,

205
00:13:58,320 --> 00:14:05,570
można obliczyć sumę, a następnie bierzemy maksymalną kwotę widzieliśmy do tej pory.

206
00:14:05,570 --> 00:14:07,880
Czy to jasne?

207
00:14:07,880 --> 00:14:12,230
Co to jest duże O z tego rozwiązania?

208
00:14:12,230 --> 00:14:16,660
Timewise.

209
00:14:16,660 --> 00:14:18,860
Nie dość n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Zauważ, że iteracyjne od 0 do n,

211
00:14:25,250 --> 00:14:27,520
tak że jest jeden dla pętli.

212
00:14:27,520 --> 00:14:35,120
Mamy iteracyjne ponownie od prawie początku do końca, drugi dla pętli.

213
00:14:35,120 --> 00:14:37,640
A teraz, w ciągu, musimy podsumować każdy wpis,

214
00:14:37,640 --> 00:14:43,810
tak że jest inny dla pętli. Więc mamy trzy zagnieżdżone pętle, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okay. Wykracza to jako punkt wyjścia.

216
00:14:46,560 --> 00:14:53,180
Nasze rozwiązanie jest nie gorsza niż n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Czy wszyscy rozumieją brute force rozwiązanie?

218
00:14:55,480 --> 00:14:59,950
>> Okay. Lepszym rozwiązaniem jest użycie pomysł o nazwie programowanie dynamiczne.

219
00:14:59,950 --> 00:15:03,040
Zażycie CS124, który jest Algorytmy i struktury danych,

220
00:15:03,040 --> 00:15:05,680
zostaniesz bardzo dobrze zaznajomieni z tej techniki.

221
00:15:05,680 --> 00:15:12,190
A pomysł, starają się budować rozwiązania mniejszych problemów w pierwszej kolejności.

222
00:15:12,190 --> 00:15:17,990
Co mam na myśli to, ale aktualnie nie martwić się o dwie rzeczy: początek i koniec.

223
00:15:17,990 --> 00:15:29,340
I to jest denerwujące. Co zrobić, jeśli możemy się pozbyć jednego z tych parametrów?

224
00:15:29,340 --> 00:15:32,650
Jednym z pomysłów jest - jesteśmy podany nasz oryginalny problem,

225
00:15:32,650 --> 00:15:37,470
znaleźć maksymalną wartość jakiejkolwiek subarray zakresu [O, N-1].

226
00:15:37,470 --> 00:15:47,400
A teraz mamy nowy subproblem, gdzie wiemy, w naszym indeksu i,

227
00:15:47,400 --> 00:15:52,520
wiemy, musimy stwierdzić, tam. Nasza subarray musi kończyć w bieżącym indeksie.

228
00:15:52,520 --> 00:15:57,640
Więc pozostała problemem jest to, w którym powinniśmy zacząć naszą subarray?

229
00:15:57,640 --> 00:16:05,160
Czy to ma sens? Okay.

230
00:16:05,160 --> 00:16:12,030
Tak już zakodowane ten fakt, i spójrzmy, co to oznacza.

231
00:16:12,030 --> 00:16:16,230
W codirectory, jest program o nazwie subarray,

232
00:16:16,230 --> 00:16:19,470
i ma liczbę pozycji,

233
00:16:19,470 --> 00:16:25,550
i zwraca maksymalną sumę subarray moim przetasowana listy.

234
00:16:25,550 --> 00:16:29,920
Tak więc, w tym przypadku, to nasza ilość subarray 3.

235
00:16:29,920 --> 00:16:34,850
I to podjęte tylko przy użyciu 2 i 1.

236
00:16:34,850 --> 00:16:38,050
Przyjrzyjmy się jeszcze raz. To także 3.

237
00:16:38,050 --> 00:16:40,950
Ale tym razem, zauważyć, jak dostaliśmy 3.

238
00:16:40,950 --> 00:16:46,690
Wzięliśmy - my po prostu wziąć się 3

239
00:16:46,690 --> 00:16:49,980
ponieważ jest otoczony z obu stron ujemnych,

240
00:16:49,980 --> 00:16:55,080
który przyniesie suma <3.

241
00:16:55,080 --> 00:16:57,820
Przyjrzyjmy się na 10 pozycji.

242
00:16:57,820 --> 00:17:03,200
Tym razem jest to 7, bierzemy wiodącą 3 i 4.

243
00:17:03,200 --> 00:17:09,450
Tym razem jest to 8, a my otrzymujemy, że, biorąc 1, 4 i 3.

244
00:17:09,450 --> 00:17:16,310
Tak, aby dać Ci intuicji, w jaki sposób możemy rozwiązać ten przekształcił problem,

245
00:17:16,310 --> 00:17:18,890
rzućmy okiem na subarray.

246
00:17:18,890 --> 00:17:23,460
Jesteśmy biorąc pod uwagę ten parametr tablica i wiemy, że odpowiedź jest 8.

247
00:17:23,460 --> 00:17:26,359
Bierzemy 1, 4 i 3.

248
00:17:26,359 --> 00:17:29,090
Ale spójrzmy na to, jak tak naprawdę mam to odpowiedź.

249
00:17:29,090 --> 00:17:34,160
Spójrzmy na maksymalnej subarray zakończonym na każdy z tych wskaźników.

250
00:17:34,160 --> 00:17:40,780
Co jest, że maksymalna subarray musi kończy się na pierwszej pozycji?

251
00:17:40,780 --> 00:17:46,310
[Student] Zero. >> Zero. Po prostu nie wziąć -5.

252
00:17:46,310 --> 00:17:50,210
Tutaj to będzie 0, jak również. Tak?

253
00:17:50,210 --> 00:17:56,470
(Student, niezrozumiały)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, przepraszam, to jest -3.

255
00:17:58,960 --> 00:18:03,220
Więc to jest 2, to jest -3.

256
00:18:03,220 --> 00:18:08,690
Okay. Więc -4, co maksymalna subarray zakończyć tę pozycję

257
00:18:08,690 --> 00:18:12,910
gdzie -4 jest? Zero.

258
00:18:12,910 --> 00:18:22,570
One? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
Teraz muszę kończyć w miejscu, gdzie jest na -2.

260
00:18:28,060 --> 00:18:39,330
Tak 6, 5, 7, a ostatni z nich jest 4.

261
00:18:39,330 --> 00:18:43,480
Wiedząc, że to są moje wpisy

262
00:18:43,480 --> 00:18:48,130
dla przekształconej problemu gdzie muszę zakończyć na każdym z tych wskaźników,

263
00:18:48,130 --> 00:18:51,410
wtedy moja ostateczna odpowiedź jest po prostu, wziąć rozmach całej,

264
00:18:51,410 --> 00:18:53,580
i wziąć maksymalną liczbę.

265
00:18:53,580 --> 00:18:55,620
Tak więc, w tym przypadku jest to 8.

266
00:18:55,620 --> 00:19:00,010
Oznacza to, że ilość subarray kończy w tym indeksie

267
00:19:00,010 --> 00:19:04,970
i zaczął gdzieś przed nim.

268
00:19:04,970 --> 00:19:09,630
Czy wszyscy rozumieją ten przekształcił subarray?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Cóż, dowiedzieć się nawrót do tego.

270
00:19:22,160 --> 00:19:27,990
Rozważmy tylko kilka pierwszych wpisów.

271
00:19:27,990 --> 00:19:35,930
Więc o to, 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
A potem było -2, oraz że przyniósł go do 6.

273
00:19:39,790 --> 00:19:50,800
Więc jeśli zadzwonię wpis w pozycji i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
jak można używać odpowiedź do poprzedniego subproblem

275
00:19:54,910 --> 00:19:59,360
aby odpowiedzieć na to subproblem?

276
00:19:59,360 --> 00:20:04,550
Gdy patrzę na, powiedzmy, ten wpis.

277
00:20:04,550 --> 00:20:09,190
Jak mogę obliczyć odpowiedź 6 patrząc na

278
00:20:09,190 --> 00:20:18,780
Połączenie tej tablicy i odpowiedź na poprzednie podzagadnień w tej tablicy? Tak?

279
00:20:18,780 --> 00:20:22,800
[Studentka] wziąć tablicę kwot

280
00:20:22,800 --> 00:20:25,430
w położeniu tuż przed nią, to 8

281
00:20:25,430 --> 00:20:32,170
a następnie dodać bieżący subproblem.

282
00:20:32,170 --> 00:20:36,460
[Yu] Więc jej sugestia jest patrzeć na tych dwóch liczb,

283
00:20:36,460 --> 00:20:40,090
ta liczba, a ich liczba.

284
00:20:40,090 --> 00:20:50,130
Więc to 8 odnosi się do odpowiedzi na subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
I nazwijmy mojej tablicy wejście A.

286
00:20:57,300 --> 00:21:01,470
W celu znalezienia maksymalny subarray, który kończy się w pozycji I,

287
00:21:01,470 --> 00:21:03,980
Mam dwie opcje: można albo kontynuować subarray

288
00:21:03,980 --> 00:21:09,790
, który zakończył się na poprzednim indeksu, lub rozpocząć nową tablicę.

289
00:21:09,790 --> 00:21:14,190
Jeśli miałbym kontynuować subarray które rozpoczęły się w poprzednim indeksie,

290
00:21:14,190 --> 00:21:19,260
to maksymalna suma mogę osiągnąć to odpowiedź na poprzednie subproblem

291
00:21:19,260 --> 00:21:24,120
oraz aktualna pozycja tablicy.

292
00:21:24,120 --> 00:21:27,550
Ale ja też mam wybór rozpoczęciem nowego subarray,

293
00:21:27,550 --> 00:21:30,830
w takim przypadku suma 0..

294
00:21:30,830 --> 00:21:42,860
Więc odpowiedź jest max 0, subproblem i - 1, plus bieżąca pozycja tablicy.

295
00:21:42,860 --> 00:21:46,150
Czy to nawrót sens?

296
00:21:46,150 --> 00:21:50,840
Nasza nawrót, jak to właśnie odkrył, jest subproblem i

297
00:21:50,840 --> 00:21:54,740
jest równa maksimum poprzedniej subproblem Plus mój bieżący wpis tablicy

298
00:21:54,740 --> 00:22:01,490
co oznacza kontynuować dotychczasową subarray,

299
00:22:01,490 --> 00:22:07,250
lub 0, rozpocząć nową subarray w moim obecnym indeksie.

300
00:22:07,250 --> 00:22:10,060
I raz zbudowaliśmy tę tabelę rozwiązań, nasza ostateczna odpowiedź,

301
00:22:10,060 --> 00:22:13,950
zrób liniowy zamiatać całej macierzy subproblem

302
00:22:13,950 --> 00:22:19,890
i wziąć maksymalną liczbę.

303
00:22:19,890 --> 00:22:23,330
To jest dokładna realizacja tego, co właśnie powiedział.

304
00:22:23,330 --> 00:22:27,320
Więc tworzymy nową tablicę subproblem, podzagadnień.

305
00:22:27,320 --> 00:22:32,330
Pierwsza pozycja to 0 albo pierwszy wpis, maksymalna z tych dwóch.

306
00:22:32,330 --> 00:22:35,670
I dla pozostałych podzagadnień

307
00:22:35,670 --> 00:22:39,810
używamy dokładnej powtórzeniu właśnie odkrył.

308
00:22:39,810 --> 00:22:49,960
Teraz możemy obliczyć maksimum naszej tablicy podzagadnień, i to jest nasza ostateczna odpowiedź.

309
00:22:49,960 --> 00:22:54,130
>> Więc ile miejsca mamy w tym przy użyciu algorytmu?

310
00:22:54,130 --> 00:23:01,470
Jeśli tylko podjąć CS50, to może nie omówiono przestrzeń bardzo.

311
00:23:01,470 --> 00:23:07,750
Cóż, jedna rzecz, należy stwierdzić, że zadzwoniłem malloc tutaj zn wielkości.

312
00:23:07,750 --> 00:23:13,590
Co to proponuję dla ciebie?

313
00:23:13,590 --> 00:23:17,450
Algorytm ten wykorzystuje przestrzeni liniowej.

314
00:23:17,450 --> 00:23:21,030
Możemy zrobić lepiej?

315
00:23:21,030 --> 00:23:30,780
Czy istnieje coś, co można zauważyć, że nie jest konieczne, aby obliczyć ostateczną odpowiedź?

316
00:23:30,780 --> 00:23:33,290
Chyba lepiej pytanie, jakie informacje

317
00:23:33,290 --> 00:23:40,680
nie musimy przeprowadzić przez całą drogę do końca?

318
00:23:40,680 --> 00:23:44,280
Teraz, jeśli spojrzymy na te dwie linie,

319
00:23:44,280 --> 00:23:47,720
interesują nas tylko poprzedniego subproblem,

320
00:23:47,720 --> 00:23:50,910
a my tylko dbamy o maksimum jakie widzieliśmy do tej pory.

321
00:23:50,910 --> 00:23:53,610
Aby obliczyć naszą ostateczną odpowiedź, że nie potrzebujemy całej tablicy.

322
00:23:53,610 --> 00:23:57,450
Musimy tylko ostatni numer, ostatnie dwie cyfry.

323
00:23:57,450 --> 00:24:02,630
Ostatni numer na tablicy subproblem i numer ostatniego dla maksimum.

324
00:24:02,630 --> 00:24:07,380
Tak więc, w rzeczywistości można razem łączą te pętle

325
00:24:07,380 --> 00:24:10,460
i przejść z przestrzeni liniowej do stałego miejsca.

326
00:24:10,460 --> 00:24:15,830
Ta suma dotychczas, tu zastępuje rolę subproblem, naszej tablicy subproblem.

327
00:24:15,830 --> 00:24:20,020
Więc prąd suma, jak dotąd, jest odpowiedzią na poprzedni subproblem.

328
00:24:20,020 --> 00:24:23,450
Oraz że suma, do tej pory, zajmuje miejsce naszego max.

329
00:24:23,450 --> 00:24:28,100
Obliczamy maksymalnie jak iść.

330
00:24:28,100 --> 00:24:30,890
I tak przechodzimy od przestrzeni liniowej do stałej przestrzeni,

331
00:24:30,890 --> 00:24:36,650
i mamy także liniową rozwiązanie naszego problemu subarray.

332
00:24:36,650 --> 00:24:40,740
>> Tego rodzaju pytania będzie można uzyskać podczas rozmowy kwalifikacyjnej.

333
00:24:40,740 --> 00:24:44,450
Co to jest złożoność, co to jest złożoność przestrzeń?

334
00:24:44,450 --> 00:24:50,600
Można to zrobić lepiej? Czy są rzeczy, które są potrzebne do utrzymania w pobliżu?

335
00:24:50,600 --> 00:24:55,270
Zrobiłem to, aby podświetlić analiz, które należy wykonać na własną rękę

336
00:24:55,270 --> 00:24:57,400
jak pracujesz przez te problemy.

337
00:24:57,400 --> 00:25:01,710
Zawsze się zastanawiasz: "Czy mogę to zrobić lepiej?"

338
00:25:01,710 --> 00:25:07,800
W rzeczywistości, można zrobić lepiej?

339
00:25:07,800 --> 00:25:10,730
Rodzaju podchwytliwe pytanie. Nie można, bo trzeba

340
00:25:10,730 --> 00:25:13,590
przeczytać przynajmniej wejście do problemu.

341
00:25:13,590 --> 00:25:15,570
Tak więc fakt, że należy przeczytać przynajmniej wejście problemu

342
00:25:15,570 --> 00:25:19,580
Oznacza to, że nie można zrobić lepiej niż czasu linearnego,

343
00:25:19,580 --> 00:25:22,870
i nie można zrobić lepiej niż stałego miejsca.

344
00:25:22,870 --> 00:25:27,060
Jest to więc w rzeczywistości, najlepszym rozwiązaniem tego problemu.

345
00:25:27,060 --> 00:25:33,040
Pytania? Okay.

346
00:25:33,040 --> 00:25:35,190
>> Problem giełdzie:

347
00:25:35,190 --> 00:25:38,350
"Biorąc pod uwagę wartości całkowitych n, dodatnie, zerowe lub ujemne,

348
00:25:38,350 --> 00:25:41,680
które reprezentują cenę zapasów na dzień n,

349
00:25:41,680 --> 00:25:44,080
napisać funkcję do obliczania maksymalnych zysków można dokonać

350
00:25:44,080 --> 00:25:49,350
zważywszy, że można kupić i sprzedać dokładnie 1 akcji w tych n dni. "

351
00:25:49,350 --> 00:25:51,690
Zasadniczo, chcemy kupić niskie, sprzedać drogo.

352
00:25:51,690 --> 00:25:58,580
I chcemy, aby dowiedzieć się najlepsze zysku możemy zrobić.

353
00:25:58,580 --> 00:26:11,500
Wracając do mojej końcówki, co jest od razu jasne, najprostsza odpowiedź, ale to jest wolny?

354
00:26:11,500 --> 00:26:17,690
Tak? (Student, niezrozumiały) >> Tak.

355
00:26:17,690 --> 00:26:21,470
>> Więc możesz sobie iść, choć i spojrzeć na ceny akcji

356
00:26:21,470 --> 00:26:30,550
na każdy punkt w czasie, (niezrozumiałe).

357
00:26:30,550 --> 00:26:33,990
[Yu] Okay, więc jej rozwiązanie - jej propozycja informatyki

358
00:26:33,990 --> 00:26:37,380
Najniższa i najwyższa obliczenia niekoniecznie pracować

359
00:26:37,380 --> 00:26:42,470
ponieważ może wystąpić przed najwyższy najniższy.

360
00:26:42,470 --> 00:26:47,340
Więc co to jest brute force rozwiązanie tego problemu?

361
00:26:47,340 --> 00:26:53,150
Jakie są dwie rzeczy, które trzeba jednoznacznie określić zysk daję? Racja.

362
00:26:53,150 --> 00:26:59,410
Brute force jest rozwiązanie - oh, tak, propozycja Jerzego jest musimy tylko dwa dni

363
00:26:59,410 --> 00:27:02,880
, aby jednoznacznie ustalić wynik tych dwóch dni.

364
00:27:02,880 --> 00:27:06,660
Więc obliczyć każdą parę, jak kupić / sprzedać,

365
00:27:06,660 --> 00:27:12,850
obliczyć zyski, które mogą być ujemne lub dodatnie lub zero.

366
00:27:12,850 --> 00:27:18,000
Oblicz maksymalny zysk, że robimy po iterowanie wszystkich par dni.

367
00:27:18,000 --> 00:27:20,330
To będzie nasza ostateczna odpowiedź.

368
00:27:20,330 --> 00:27:25,730
Oraz że rozwiązanie będzie O (n ^ 2), ponieważ nie jest n wybrać dwie pary -

369
00:27:25,730 --> 00:27:30,270
z dni, które można wybierać spośród dni końcowych.

370
00:27:30,270 --> 00:27:32,580
Ok, więc nie mam zamiaru iść na brutalnej siły rozwiązanie tutaj.

371
00:27:32,580 --> 00:27:37,420
I powiem ci, że istnieje n log n roztwór.

372
00:27:37,420 --> 00:27:45,550
Jaki algorytm masz obecnie wiadomo, że jest n log n?

373
00:27:45,550 --> 00:27:50,730
To nie jest podchwytliwe pytanie.

374
00:27:50,730 --> 00:27:54,790
>> Scalanie sortowania. Scalanie sortowania jest n log n,

375
00:27:54,790 --> 00:27:57,760
i faktycznie, jednym ze sposobów rozwiązania tego problemu jest użycie

376
00:27:57,760 --> 00:28:04,400
rodzaj sort merge idei nazywa, w ogóle, dziel i rządź.

377
00:28:04,400 --> 00:28:07,570
Pomysł i jest w następujący sposób.

378
00:28:07,570 --> 00:28:12,400
Chcesz obliczyć najlepszą kupić / sprzedać parę w lewej połowie.

379
00:28:12,400 --> 00:28:16,480
Znajdź najlepsze zyski można dokonać, tylko z pierwszym n ciągu dwóch dni.

380
00:28:16,480 --> 00:28:19,780
Potem chcesz oompute najlepsze kupić / sprzedać parę na prawej połowie,

381
00:28:19,780 --> 00:28:23,930
tak ostatnio n na dwa dni.

382
00:28:23,930 --> 00:28:32,400
I teraz pytanie, w jaki sposób połączyć te rozwiązania, wraz z powrotem?

383
00:28:32,400 --> 00:28:36,320
Tak? (Student, niezrozumiały)

384
00:28:36,320 --> 00:28:49,890
>> Okay. Więc pozwól mi narysować obrazek.

385
00:28:49,890 --> 00:29:03,870
Tak? (George, niezrozumiały)

386
00:29:03,870 --> 00:29:06,450
>> Dokładnie. Rozwiązanie Jerzego jest dokładnie prawo.

387
00:29:06,450 --> 00:29:10,040
Więc jego propozycja jest najpierw wylicza najlepszy kupić / sprzedać parę,

388
00:29:10,040 --> 00:29:16,050
i że występuje w lewej połowie, tak nazwijmy, że w lewo, w lewo.

389
00:29:16,050 --> 00:29:20,790
Najlepiej kupić / sprzedać parę, która występuje w prawej połowie.

390
00:29:20,790 --> 00:29:25,180
Ale jeśli tylko porównać te dwie liczby, brakuje nam sprawę

391
00:29:25,180 --> 00:29:30,460
gdzie tu kupić i sprzedać gdzieś w prawej połowie.

392
00:29:30,460 --> 00:29:33,810
Kupujemy w lewej połowie, sprzedawać w prawej połowie.

393
00:29:33,810 --> 00:29:38,490
A najlepszym sposobem, aby obliczyć najlepszą kupić / sprzedać parę, która obejmuje obie połówki

394
00:29:38,490 --> 00:29:43,480
jest obliczenie minimum tutaj i obliczyć maksymalną tutaj

395
00:29:43,480 --> 00:29:45,580
i biorą ich różnicę.

396
00:29:45,580 --> 00:29:50,850
Więc dwóch przypadkach, gdzie kupić / sprzedać parę występuje tylko tutaj,

397
00:29:50,850 --> 00:30:01,910
tylko tu, lub na obu połówkach jest określone przez te trzy numerów.

398
00:30:01,910 --> 00:30:06,450
Więc nasz algorytm scalić nasze rozwiązania wraz z powrotem,

399
00:30:06,450 --> 00:30:08,350
chcemy obliczyć najlepszą kupić / sprzedać parę

400
00:30:08,350 --> 00:30:13,120
gdzie kupić na lewym pół i sprzedać na prawej połowie.

401
00:30:13,120 --> 00:30:16,740
A najlepszym sposobem na to jest do obliczenia najniższą cenę w pierwszym półroczu,

402
00:30:16,740 --> 00:30:20,360
Najwyższa cena w prawej połowie, i wziąć ich różnicę.

403
00:30:20,360 --> 00:30:25,390
Powstały trzy zyski, te trzy numery, można podjąć maksymalnie trzech,

404
00:30:25,390 --> 00:30:32,720
i jest to najlepszy wynik można zrobić w ciągu tych pierwszych dni i koniec.

405
00:30:32,720 --> 00:30:36,940
Tutaj ważne linie są w kolorze czerwonym.

406
00:30:36,940 --> 00:30:41,160
Jest to wywołanie rekurencyjne obliczyć odpowiedź w lewej połowie.

407
00:30:41,160 --> 00:30:44,760
Jest to wywołanie rekurencyjne obliczyć odpowiedź w prawej połowie.

408
00:30:44,760 --> 00:30:50,720
Te dwie pętle obliczyć min i max na pół lewej i prawej.

409
00:30:50,720 --> 00:30:54,970
Teraz obliczyć zysk, który obejmuje obie połówki,

410
00:30:54,970 --> 00:31:00,530
i końcowy jest maksymalna odpowiedź z tych trzech.

411
00:31:00,530 --> 00:31:04,120
Okay.

412
00:31:04,120 --> 00:31:06,420
>> Tak, na pewno, mamy algorytm, ale większe pytanie,

413
00:31:06,420 --> 00:31:08,290
co to jest złożoność tego?

414
00:31:08,290 --> 00:31:16,190
I dlatego wspomniałem sortowanie korespondencji seryjnej, że ta forma dzielenia odpowiedź

415
00:31:16,190 --> 00:31:19,200
na dwie części, a następnie łączenia naszych rozwiązań wraz z powrotem

416
00:31:19,200 --> 00:31:23,580
jest dokładnie formą sortowania korespondencji seryjnej.

417
00:31:23,580 --> 00:31:33,360
Więc pozwól mi przejść przez okres.

418
00:31:33,360 --> 00:31:41,340
Jeżeli określony w funkcji n (t) jest liczba etapów

419
00:31:41,340 --> 00:31:50,010
na dzień n,

420
00:31:50,010 --> 00:31:54,350
nasze dwa połączenia rekurencyjne

421
00:31:54,350 --> 00:32:00,460
są każdy będzie kosztować T (n / 2),

422
00:32:00,460 --> 00:32:03,540
i nie dwa z tych połączeń.

423
00:32:03,540 --> 00:32:10,020
Teraz trzeba obliczyć minimum lewej części,

424
00:32:10,020 --> 00:32:17,050
co mogę zrobić w n / 2 godziny, plus maksymalnie prawej połowie.

425
00:32:17,050 --> 00:32:20,820
Więc jest to po prostu n.

426
00:32:20,820 --> 00:32:25,050
A następnie oraz pewnej stałej pracy.

427
00:32:25,050 --> 00:32:27,770
I to równanie nawrotu

428
00:32:27,770 --> 00:32:35,560
jest dokładnie równanie nawrotów sortowanie korespondencji seryjnej.

429
00:32:35,560 --> 00:32:39,170
A wszyscy wiemy, że sort merge log n n czas.

430
00:32:39,170 --> 00:32:46,880
Dlatego nasz algorytm jest również n log n godzinę.

431
00:32:46,880 --> 00:32:52,220
Czy to iteracja sens?

432
00:32:52,220 --> 00:32:55,780
Tylko krótkie podsumowanie tego:

433
00:32:55,780 --> 00:32:59,170
T (N) to ilość stopni w celu obliczenia maksymalnej zysk

434
00:32:59,170 --> 00:33:02,750
w ciągu dni, n.

435
00:33:02,750 --> 00:33:06,010
Sposób podzieliliśmy nasze rekurencyjnych wywołań

436
00:33:06,010 --> 00:33:11,980
jest wywołanie nasze rozwiązanie na pierwszych n / 2 dni,

437
00:33:11,980 --> 00:33:14,490
tak że jest jedno połączenie,

438
00:33:14,490 --> 00:33:16,940
a potem zadzwonić ponownie na drugiej połowie.

439
00:33:16,940 --> 00:33:20,440
Więc to dwa zaproszenia.

440
00:33:20,440 --> 00:33:25,310
I wtedy możemy znaleźć minimum na lewej połowie, co możemy zrobić w czasie liniowym,

441
00:33:25,310 --> 00:33:29,010
znaleźć maksymalnie prawej połowie, co możemy zrobić w czasie liniowym.

442
00:33:29,010 --> 00:33:31,570
Tak n / 2 + N / 2 jest tylko N.

443
00:33:31,570 --> 00:33:36,020
Następnie mamy jakąś stałą pracę, która jest jak arytmetyki.

444
00:33:36,020 --> 00:33:39,860
Równanie to nawrót jest dokładnie równanie nawrotów sortowanie korespondencji seryjnej.

445
00:33:39,860 --> 00:33:55,490
Stąd nasz algorytm shuffle jest także n log n.

446
00:33:55,490 --> 00:33:58,520
Więc ile miejsca mamy przy użyciu?

447
00:33:58,520 --> 00:34:04,910
Wróćmy do kodu.

448
00:34:04,910 --> 00:34:09,420
>> Lepsze pytanie, ile ramek stosu mamy kiedykolwiek w danym momencie?

449
00:34:09,420 --> 00:34:11,449
Ponieważ używamy rekurencji,

450
00:34:11,449 --> 00:34:23,530
liczba ramek stosu określa nasz wykorzystania przestrzeni.

451
00:34:23,530 --> 00:34:29,440
Rozważmy n = 8.

452
00:34:29,440 --> 00:34:36,889
Wzywamy shuffle 8,

453
00:34:36,889 --> 00:34:41,580
która wywoła shuffle pierwszych czterech wjazdów,

454
00:34:41,580 --> 00:34:46,250
które nazywamy shuffle pierwszych dwóch pozycji.

455
00:34:46,250 --> 00:34:51,550
Więc nasz stack jest - to jest nasz stos.

456
00:34:51,550 --> 00:34:54,980
I wtedy nazywamy shuffle, ponownie 1,

457
00:34:54,980 --> 00:34:58,070
i to, co w naszym przykładzie jest podstawa, więc natychmiast.

458
00:34:58,070 --> 00:35:04,700
Czy kiedykolwiek mieć więcej niż to wiele ramek stosu?

459
00:35:04,700 --> 00:35:08,880
Nie, ponieważ za każdym razem robimy inwokację,

460
00:35:08,880 --> 00:35:10,770
recursive inwokacja do shuffle

461
00:35:10,770 --> 00:35:13,950
dzielimy naszą wielkość w połowie.

462
00:35:13,950 --> 00:35:17,020
Tak więc maksymalną ilość klatek stosu kiedykolwiek mają w danym momencie

463
00:35:17,020 --> 00:35:28,460
jest na zlecenie dziennika n stos ramek.

464
00:35:28,460 --> 00:35:42,460
Każda ramka stosu ma stałą przestrzeń,

465
00:35:42,460 --> 00:35:44,410
a zatem całkowita ilość miejsca,

466
00:35:44,410 --> 00:35:49,240
maksymalną ilość miejsca, jakie kiedykolwiek użyć jest O (log n) przestrzeń

467
00:35:49,240 --> 00:36:03,040
w którym n oznacza liczbę dni.

468
00:36:03,040 --> 00:36:07,230
>> Teraz, zawsze należy zadać sobie pytanie: "Czy możemy zrobić lepiej?"

469
00:36:07,230 --> 00:36:12,390
A w szczególności, możemy zmniejszyć to na problem mamy już rozwiązany?

470
00:36:12,390 --> 00:36:20,040
Podpowiedź: tylko omówiła dwa inne problemy przed tym, i nie będzie to shuffle.

471
00:36:20,040 --> 00:36:26,200
Możemy przekształcić ten problem giełdowe do maksymalnej problemu subarray.

472
00:36:26,200 --> 00:36:40,100
W jaki sposób możemy to zrobić?

473
00:36:40,100 --> 00:36:42,570
Jeden z was? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, niezrozumiały)

475
00:36:47,680 --> 00:36:53,860
[Yu] Dokładnie.

476
00:36:53,860 --> 00:36:59,940
Więc maksymalnej problemu subarray,

477
00:36:59,940 --> 00:37:10,610
szukamy sumy w ciągłym subarray.

478
00:37:10,610 --> 00:37:16,230
Emmy i sugestia jest dla problemu zasobów,

479
00:37:16,230 --> 00:37:30,720
rozważyć zmiany, lub delty.

480
00:37:30,720 --> 00:37:37,440
I obraz jest - to jest cena akcji,

481
00:37:37,440 --> 00:37:42,610
ale jeśli wzięliśmy różnicę pomiędzy każdy kolejny dzień -

482
00:37:42,610 --> 00:37:45,200
Widzimy zatem, że maksymalna cena, maksymalny zysk moglibyśmy

483
00:37:45,200 --> 00:37:50,070
jest, jeśli kupimy tutaj i sprzedać tutaj.

484
00:37:50,070 --> 00:37:54,240
Ale spójrzmy na ciągły - spójrzmy na problem subarray.

485
00:37:54,240 --> 00:38:02,510
Więc tutaj, możemy - idąc stąd dotąd,

486
00:38:02,510 --> 00:38:08,410
mamy pozytywne zmiany, a następnie przechodząc stąd tutaj mamy negatywny zmianę.

487
00:38:08,410 --> 00:38:14,220
Ale potem się stąd tutaj mamy ogromne pozytywne zmiany.

488
00:38:14,220 --> 00:38:20,930
I są to zmiany, które chcemy zsumować, aby nasz ostateczny zysk.

489
00:38:20,930 --> 00:38:25,160
Wtedy mamy więcej negatywnych zmian tutaj.

490
00:38:25,160 --> 00:38:29,990
Kluczem do redukcji zapasów naszego problemu do naszej maksymalnej problemu subarray

491
00:38:29,990 --> 00:38:36,630
jest rozważenie delty między dzień.

492
00:38:36,630 --> 00:38:40,630
Więc tworzymy nową tablicę o nazwie delty,

493
00:38:40,630 --> 00:38:43,000
zainicjować pierwszy wpis do 0,

494
00:38:43,000 --> 00:38:46,380
, a następnie dla każdej delta (i), które pozwalają się różnica

495
00:38:46,380 --> 00:38:52,830
z moja tablica wejściowa (i), i tablicy (i - 1).

496
00:38:52,830 --> 00:38:55,530
Wtedy nazywamy naszą rutynową procedurę dla maksymalnej subarray

497
00:38:55,530 --> 00:39:01,500
przechodzącą w tablicy A Delta.

498
00:39:01,500 --> 00:39:06,440
A ponieważ ilość subarray jest liniowy czas,

499
00:39:06,440 --> 00:39:09,370
i zmniejszenie to ten proces tworzenia tego delta tablicę,

500
00:39:09,370 --> 00:39:11,780
jest również czas liniowy,

501
00:39:11,780 --> 00:39:19,060
następnie końcowy roztwór do zasobów jest O (n) oraz pracy O (n) pracy, jest nadal O (n) pracy.

502
00:39:19,060 --> 00:39:23,900
Mamy więc rozwiązanie liniowego czasu do naszego problemu.

503
00:39:23,900 --> 00:39:29,610
Czy wszyscy rozumieją tę transformację?

504
00:39:29,610 --> 00:39:32,140
>> W ogóle, to dobry pomysł, że zawsze należy mieć

505
00:39:32,140 --> 00:39:34,290
jest spróbować zmniejszyć nowy problem, który widzisz.

506
00:39:34,290 --> 00:39:37,700
Jeśli wygląda znajomo do starego problemu,

507
00:39:37,700 --> 00:39:39,590
spróbuj zmniejszyć go do starego problemu.

508
00:39:39,590 --> 00:39:41,950
I jeśli można użyć wszystkich narzędzi, które zostały zamieszczone na stary problem

509
00:39:41,950 --> 00:39:46,450
rozwiązać nowy problem.

510
00:39:46,450 --> 00:39:49,010
Tak, aby zakończyć, techniczne wywiady są wyzwaniem.

511
00:39:49,010 --> 00:39:52,280
Problemy te są prawdopodobnie niektóre problemy trudniejszych

512
00:39:52,280 --> 00:39:54,700
, które można zobaczyć w wywiadzie,

513
00:39:54,700 --> 00:39:57,690
więc jeśli nie rozumiesz wszystkich problemów, które po prostu uwzględnione, to w porządku.

514
00:39:57,690 --> 00:40:01,080
Są to niektóre z problemów, bardziej ambitnych.

515
00:40:01,080 --> 00:40:03,050
Praktyka, praktyka, praktyka.

516
00:40:03,050 --> 00:40:08,170
Dałem dużo problemów w materiałach informacyjnych, więc na pewno ci się sprawdzić.

517
00:40:08,170 --> 00:40:11,690
I powodzenia na swoich wywiadów. Wszystkie moje zasoby są wywieszone w ten link,

518
00:40:11,690 --> 00:40:15,220
i jeden z moich starszych przyjaciół zaproponował zrobić mock technicznych wywiadów,

519
00:40:15,220 --> 00:40:22,050
więc jeśli jesteś zainteresowany, e-mail będzie Yao w tym adresu e-mail.

520
00:40:22,050 --> 00:40:26,070
Jeżeli masz jakieś pytania, możesz mnie zapytać.

521
00:40:26,070 --> 00:40:28,780
Czy faceci mają konkretne pytania dotyczące technicznych wywiadów

522
00:40:28,780 --> 00:40:38,440
lub jakieś problemy, które widzieliśmy do tej pory?

523
00:40:38,440 --> 00:40:49,910
Okay. Powodzenia na swoich wywiadów.

524
00:40:49,910 --> 00:40:52,910
[CS50.TV]