Тренировки по алгоритмам от Яндекса. Лекция 2: «Линейный поиск»
Вставка
- Опубліковано 3 чер 2021
- Расписание тренировок доступно по ссылке: yandex.ru/yaintern/algorithm-...
Чат в Телеграме для общения и вопросов о тренировках: t.me/joinchat/Ve7wRegrZtI0NjIy
У человека талант педагога) очень приятно смотреть и слушать мастера своего дела, ОЧЕНЬ ОЧЕНЬ! Надеюсь в будущем еще увижу его в роли педагога!!! Благодарю за ваш труд
Ну не зря наверно студенты ВШЭ по 500 к в год платят
Спасибо огромное за информативную и полезную лекцию !!!
08.07.2021 Прекрасные видео, спасибо лектору. Очень круто обьясняет.
Задача 1: зачем продолжать поиск, после того как найден ответ (первое вхождение!)?
Вариант решения без лишних переменной, проверки и итераций
def findx(seq, x):
for i in range(len(seq)):
if seq[i] == x:
return i
return -1
тот же вопрос возник
Поддержу. Зачем весь список пробегать, если результат уже найден. Это как минимум не эффективно.
как зачем, чтобы рассказать как эффективно использовать -1.😜
Может чтобы решение обеих задач было как-то консистентно. Но там не обработано условие с положительными числами.
походу ошибка в условии, нужно не крайнее левое вхождение, а крайнее правое, потому что тот код, что приводит ведущий не выводит крайнее левое, а находит и выводит крайнее правое.
круто, курс который я всегда мечтал пройти. было бы здорово если бы Вы объедили эти видео в один плейлист.
Курс объединён в плейлист ua-cam.com/play/PL6Wui14DvQPySdPv5NUqV3i8sDbHkCKC5.html
0:32 О чем лекция. План.
1:00 Классические задачи линейного поиска.
1:04 Что такое Линейный поиск.
1:43 Задача 1. Найти первое вхождение.
5:48 Задача 2. Найти последнее вхождение.
7:51 Задача 3. Найти максимальное число.
12:50 Задача 3. Пояснение сложности сравнения. Лексикографический порядок.
15:44 Задача 3. Зачем сохранять индексы. Сложность копирования.
18:48 Задача 4. Два максимума.
26:17 Задача 5. Минимальное четное.
30:44 Двухпроходные алгоритмы.
30:48 Задача 6. Вывести самые короткие слова
35:28 Задача 7. Сколько блоков воды.
44:00 Задача с собеседования. RLE
51:22 Ответы на вопросы.
В задаче 4. Обязательно писать range(2, len(seq)). Иначе в последовательности [5,9,7,8,1,7,4,1,7] вернет (9, 9) вместо (9, 8) потому что алгоритм с самого начала проходит последовательность, и elif seq[i] > max2 встречает 9ку, макс2 записывает 9ку вместо 5ки.
Вы не совсем правы. В этом алгоритме гораздо больше ошибок, чем вы указали. И ваша правка не спасет ситуацию. [5,9,7, 9,1,7,4,1,7] при ваших правках тоже вернет (9, 9). А еще [9,9,7,4,1,7,4,1,7] тоже вернет (9,9). В программе не верна и логика выбора начальных значений и алгоритм замены. Вот так будет работать:
def foo(lst):
if len(lst) < 2:
return 'error'
max1 = max2 = min(lst)
for i in lst:
if i > max2:
if i > max1:
max2, max1 = max1, i
elif i < max1:
max2 = i
return max1, max2
ответ (9, 9) правильный, поскольку нам нужно найти не второе по величине число, а максимум из последовательности если из неё вычеркнуть первый максимум
@@Zaqer84 Согласен с предыдущим оратором. При обсуждении задачи (19:38) чётко обсуждался этот момент.
Да, он это упоминает во время вопросов (1:03:56)
Вот такая же программа на Паскале
program max;
uses crt;
label l;
var
arr: array of integer;
i, len, max1, max2: integer;
begin
l:
writeln('Input the array length: ');
readln(len);
if len < 2 then goto l;
setlength(arr, len);
writeln('Input the array: ');
for i := 1 to len do read(arr[i]);
if arr[0] > arr[1] then
begin
max1 := 0;
max2 := 1;
end
else
begin
max1 := 1;
max2 := 0;
end;
for i := 0 to length(arr) do
begin
if arr[i] > arr[max1] then
begin
max2 := max1;
max1 := i;
end;
if (arr[i] = arr[max1]) and (i max1) then max2 := max1;
if (arr[i] < arr[max1]) and (arr[i] > arr[max2]) then max2 := i;
end;
writeln('Max 1 is: ', arr[max1], ' Max 2 is: ', arr[max2]);
readkey;
end.
Спасибо ❤
Крутое объяснение! Спасибо! Но информации очень много, не каждый воспримет
findmax2 - если в нее передать следующую последовательность {-2,-4,-6} и начать проход по всей последовательности, то что мы получаем, в первый if не заходим, а во втором max2 становится равным -2 и функция вернет {-2, -2}
Задача №6
Написано :
if len(word)
Возьмите работать в Яндекс
@@user-hv9rc7bm2f ахахаа красава
@@user-hv9rc7bm2fпреподавать в ВШЭ*
У вас в задаче на вывод слов с минимальной длиной опечатка: вы присваиваете счётчику минимальной длины размер заданного массива, а не длину слова
55:34 Категорически не согласен с тем, что continue и break затрудняют понимание. continue уменьшает вложенность, что как раз значительно облегчает понимание и немного ускоряет выполнение, а break значительно ускоряет и также облегчает понимание. Хотя, это у кого как. Разумеется, необходимо во второй задаче идти справа налево и делать break, либо заранее разворачивать список. Нелюбовь к этим конструкциям будет заставлять делать процессор тупую работу, когда можно было бы её не делать. Например, как в ещё одной приведённой задаче, искать минимальную длину слова до конца массива, когда она уже == 1. И функция для осмысливания не на экран должна помещаться, а в голову. Успехов.
насчет continue и break поддерживаю на все 100
Спасибо
В python минус бесконечность можно задать как -float('inf')
В задаче на собеседование можно счётчик добавить, и если встретили новый символ,добавить цифру в выходную строку, а счётчик обнулить?
Знаю, что пишу уже поздно, но может кто нибудь ответит. Хорошо ли решать эту задачу с собеседования используя словарь, в котором ключ это индекс строки, а значение сколько раз она встретилась. А в конце собрать строку обращаясь к исходной через индекс из словаря и количество из значения? Я предполагаю, что по памяти возможно будет хуже, чем предложенное решение, но всё же.
def update_str(string: str) -> str:
def pack(s, count):
if count > 1:
s += str(count)
return s
if string == '':
return string
current_index = 0
count_chars = {0: 1}
for i in range(1, len(string)):
if string[i] != string[current_index]:
count_chars[i] = 1
current_index = i
elif string[i] == string[current_index]:
count_chars[current_index] = count_chars[current_index] + 1
return ''.join([pack(string[key], value) for key, value in count_chars.items()])
Идеально на 1.5х смотреть. Как и все остальные.
2x норм. Жаль, нет 3x
@@i17talk8 давненько добавил себе ссылочку в браузере для 3x :D
URL должен быть чем-то вроде: javascript:document.querySelector('video').playbackRate = 3;
Это если лень открывать консоль каждый раз.
@@deniskhakimov Спасибо, сработало. В FF только через консоль получилось. Закладка меняет весь body на "3"
@@deniskhakimov в video speed controller - можно более гибко скорость менять, всё-таки у всех разная дикция и скорость речи.
А мне кажется, или в 6 задаче в 5 строке решения должно быть len(word) вместо len(words)?
Не кажется
Да, тоже бросилось в глаза и думал показалось ))) Начал искать ответ, чтоб не на плодить еще одного замечания про это
Привет! Я чего-то не понимаю, но зачем в задаче 1 перебирать массив дальше, если первое вхождение числа было найдено? Ведь можно сразу вернуть искомое и не нужны будут заморочки с -1-кой и дополнительной переменной?
Понятно что скорость алгоритма останется O(n) для наихудшего случая, и по памяти почти нет выигрыша но..... алгоритм станет проще на мой взгляд....
Небольшая помарка по 6 задаче. В условии сказано, что слова нужно вывести через пробел, если запустим финальное решение на список слов, слова будут просто выведены через пробел. Чтобы исправить это, можно добавить запятую в кавычки join, т.е ' '.join(ans) -> ', '.join(ans)
Имена переменных вызывают вопросы, конечно. В python snake case принято использовать.
В задаче 8 - обязательно нужно начинать итерацию с 0 элемента, иначе не обработаем ситуацию когда строка в 1 символ, например text = "A"
Нет, тогда работает append после цикла и ответ всё равно будет 'A'
Задача 3 "Зачем сохранять индексы. Сложность копирования."
18:17
Мне кажется, для корректной работы строку
if seq[i] > seq[ans]:
нужно заменить на
if seq[i] > seq[0]:
Тогда у тебя будет происходить сравнение остальных элементов только с первым, и программа будет выдавать последнее число из последовательности, которое больше первого
5 задача не решается при всех чётных отрицательных числах, исправить можно убрав из условия вторую часть после and и записать ещё один вложенный
if ans == -1 :
ans=seq[i]
elif ans
задача 7 требует дополнительного описания, так как не рассмотрен случай, когда "график" имеет несколько максимумов (несколько паттернов подъема и спуска "ступенек")
В задаче ищется первый максимум. Все другие максимумы будут справа. Последний максимум в ходе цикла станет nowm.
Про числовое значение h[maxpos] по факту можно забыть после первого цикла - теперь это чисто элемент-ограничитель для воды, гарантирующий, что она не перельется.
Попробуйте запустить код в песочнице с тестовыми примерами, он верный.
Добрый день. А если в задаче с островом несколько одинаково больших вершин? Тогда как?
в задаче с двумя проходами первый вариант добавинт пробел в конце строки, поэтому решение не прошло бы тест
Задача 7. Имеем последовательность с локальными минимумами. Оцениваем каждый элемент как минимальную разницу между соседями
У тебя в задаче явно указан случай (справа), где емкость в ширину может быть два и больше
Задача про RLE решена неверно: в исходной формулировке просят генерировать ошибку, если приходит невалидная строка, а в реализации проверки, что s[i] >='A' && s[i]
Попробуй использовать vector (динамический массив, к нему нужно дополнительно подключать библиотеку #include , чтобы узнать как с ним работать рекомендую погуглить). Но, если я ничего не путаю, строка в плюсах работает не так как в питоне. В плюсах это динамический массив чаров и в большинстве случаев добавление происходит за константу, а log н раз копирование. Если интересно что у это структуры ,,под капотом,, рекомендую почитать про Array List. Удачи в изучении)
Задачу номер 6 можно решить за один проход. Просто добавлять все слова в мапу => 1: ['a', 'b'], 2: ['ab', 'ba'], ... , после вернуть минимальный ключ
чтобы вернуть минимальный ключ, надо пройтись циклом по ключам или я не прав?
@@user-xf5ry2ig3h В переменной
@Мария Кузнецова
Если именно для Python, то можно за один цикл:
dct = {}
for word in words:
dct.setdefault(len(word), []).append(word)
Все еще проще:
seq = ['aa', 'b', 'cc', 'd']
def shortwords(words):
minlen = len(words[0])
ans = []
for word in words:
if len(word) < minlen:
minlen = len(word)
ans = []
ans.append(word)
elif len(word) == minlen:
ans.append(word)
return " ".join(ans)
print(shortwords(seq)) # b d - Решение через 1 прохода
@@justyar5781 Проблема в сложности алгоритма) В вашем решении много раз происходит операция добавления в массив (тк будут записываться слова разной длины) и операции удаления массива. А сложность при 1 проходе массива или 2 проходах примерно одинаковая = O(n). Так что решение с 2 проходами будет быстрее (тк нет удаления и меньше добавления в массив)
50:10 15FullHD или 24-4k ? :)
Михаил очень приятно смотреть твои видео!!! Я про задачу на собеседование сделл в один проход все С++
std::string st = "AAAABBBCCXYZDDDDEEEFFFAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBB";
if (!st.empty()) {
char last = st[0];
int count = 0;
for (auto i : st) {
if (i == last) {
count += 1;
}
else {
std::cout 1)std::cout
Что это за чудо-лампа?
задача 7 - это литкод 42, если кому-то нужно
Зачем в первой задаче проходить полностью по всей последовательности чисел, если можно вернуть найденную позицию сразу как только она будет найдена?
Он в конце видео ответил
@@FeelUs нет, не ответил
@@jimmycaldwell2012 52:16
@@FeelUs спасибо
7 задача это просто эталон задач с отбора на всякие компании, нифига с условия непонятно, входных данных нет, как реализовать тоже, сиди 5 часов и думай, что от тебя автор хотел.
я потратил кучу времени, чтобы понять, что в качестве аргумента приходит ландшафт без воды. И что вообще является входным аргументом(думал что двумерный массив)
@@user-gu5pz8xf3u та же ситуация, хотел решить задачу до разбора, поставил видео на паузу и пошел решать. Из контекста думал что ландшафт представлен двумерным массивом и решал задачу соответственно. Потом начал смотреть разбор и понял, что приходит массив из высот столбцов, и все гораздо проще)
В Java первую задачу начинаем итерацию с начала массива и сразу, как только нашли элемент с нужным значением, возвращаем его индекс и из цикла выходим. Чтобы найти последнее вхождение, надо итерацию начать с конца массива и также вернуть индекс первого встречного элемента с нужным значением, выйти из цикла. Зачем целиком массив перебирать? Лишняя работа. Если переберём весь массив, а элемента с нужным значением не найдём, тогда вернём -1.
Я не знаю, конечно, как там в Python с этим дела обстоят, но мне кажется, тоже должны быть такие возможности. Или нет?
Если я на позицию Java-разработчика начну минус один городить, меня спросят: "А нафига ты такой фигнёй занимаешься? Это все избыточно". И джуном то даже не возьмут. Скажут, что нифига не понимаю.))
Можно было также как вы говорите решить и в питоне, и было бы чуть быстрее. Но что в питоне круто, если с джавой сравнивать - можно было вообще это решение в одну строку уместить.
rle на js, мое решение:
function rle(str) {
let ans = '';
let curLetter = str[0];
let count = 1;
for(let i = 1; i < (str+'_').length; i++) {
if (str[i] === curLetter) {
count++;
} else {
ans += curLetter+(count > 1 ? count : '');
count = 1;
curLetter = str[i];
}
}
return ans;
}
офигенно!
1) >>>> ans += curLetter+(count > 1 ? count : '');
Привет, O(n^2) по памяти
2) в condition-части цикла вместо _i < (str+'_').length;_ лучше написать _i
В задаче 8 забыли, что строка может быть пустая
Первая задача: А что, брейкнуть нельзя цикл без проверки на -1?
Можешь выйти из цикла, а можешь продолжить. Сложность так и останется O(n)
Вот именно. Нафига каждый раз проверять на -1? Кошмарно, если так в яндексе учат и пишут. Академики. Есть ли смысл дальше смотреть? Не научусь ли я у них субоптимальности (тупизне) кода?
@@i17talk8 Не учить вовсе очень плохо
@@rusfungame не учить надо, а понять. Есть же нормальные книги (мануалы, видео), так зачем учиться по плохим? Никто не говорит, что если ты не пользуешься корявыми источниками, то ты не учишься вовсе.
@@i17talk8 если нашёл скинь пожалуйста
странное решение первой и второй задачи, в первой после нахождения первого вхождения надо прервать цикл, и сравнивать на -1 не придется, во второй итерацию начинаем с конца списка в обратном направление, и так же выходим из итерации после нахождения. хотя может в петухоне нет операторов прерывания цикла и итерации с конца, не знаком с ним
есть и то, и другое
55:50 - тут я выпал с окна 10 этажа
В решении задачи 6 ошибка (в одной букве)
minlen = len(word) должно быть
"Решение работать будет, но будет работать медленно" - не будет, слона то и не заметили :)
Задача с собеса. Куча вопросов. Что с памятью, что со временем. Надо ли запоминать получившуюся строку или просто вывести в консоль?..
1:08:50 Разрешено более одного максимума. Для этого алгоритма мы получим такой результат.
O O
OWOWO
OWOWO
OOOO0O
Почему?
5:40, а почему не сделать принудительный выход из цикла, если левое значение найдено? зачем дальнейший перебор?
52:20 ответ
почему в первой просто не брейкнуть как только нашли нужное число?
тоже подумал об этом, а еще лучше бы сразу вернуть число, тем самым также завершив цикл
00:20:58
ну чел, если есть проблемы с break и continue, даж хз что сказать. кмк это близко к топ 5 вредных советов. цикл мог выйти на 1 итерации, но ок, изза трудностей восприятия мы конечно будем крутиться все 10000 раз 😂
очень тихо(
Отлично! на выходные задачек будет) Чувствую буду после курса таким же крутым! ua-cam.com/video/g5OCi20yIyc/v-deo.html
Из-за Вашего комментария начал смотреть этот сериал :)
@@Sancho_Merka Отлично) тебе понравится! в переводе кубик в кубе обязательно
@@Sancho_Merka только наши ролики не смотри. лучше сначала сам сериал)
где домашка то?
//Задача 4 - Java script
const arr = [ 5, 9, 7, 9, 1, 7, 4, 1, 7 ]
let numbers = [ 0, 0 ]
for (let i = 0; i < arr.length; i++) {
if (numbers[1] < arr[i]) {
numbers[1] = arr[i]
}
if (numbers[0] < arr[i] && arr[i] < numbers[1]) {
numbers[0] = arr[i]
}
}
console.log(numbers)
Зачем так усложнять 4 задачу? Это ведь та же первая, только предыдущее значение перед ответом мы должны запомнить, и еще дополнение: если два одинаковых числа встречаются, то нужно обработать оба, поэтому в ифе больше либо равно вместо строгого равенства
def find2max(seq):
ans1 = seq[0]
for i in range(len(seq)):
if seq[i] >= ans1:
ans2 = ans1
ans1 = seq[i]
return ans1, ans2
Ваше решение сломается на тестах [5, 4, 3, 2] или [5, 5, 7, 6]
@@mberdyshev Спасибо, видимо, все-таки без мин макс или сортировки не обойтись)
Мда, разжёвываем, разжёвываем простое...
Потом сложное - "ну здесь всё понятно, пропускаем" 🤦🤦
4 задача решена не верно. Не верно выбираются начальные значения и не верно заменяются значения при переборе.
Верный вариант если можно использовать min и max:
def foo(lst):
if len(lst) < 2:
return 'error'
max1 = max(lst)
max2 = min(lst)
for i in lst:
if max1 > i > max2:
max2 = i
return max1, max2
Верный вариант если можно использовать сортировку:
def foo(lst):
if len(lst) < 2:
return 'error'
max1, *max2 = sorted(set(lst))[:-3:-1]
return max1, max2[0] if max2 else max1
Слишком длинные видео.
Поэтому люди будут перелистывать.
И 90% времени на экране текст задачи или решение какой-то задачи. Контекст совершенно непонятен.
Добавляйте заголовки что за тема задачи и зачем её разбирать. У вас всё равно во многих сценах 50% свободного места на экране
перед решением одной задачи, решил свое решение писать и сравнивать с тем что получилось. Это задача в 2 прохода, где нужно найти короткие слова. C 1 циклом получилось и как оказалось быстрее
import timeit
import copy
some_words = 'adasawsd aa asdadsadb csdcc dasaads dd'.split(' ')
def short_words_1(words):
words = copy.deepcopy(words)
count = len(words[0])
ans = []
for w in words:
if len(w) > count:
continue
if len(w) < count:
ans.clear()
count = len(w)
ans.append(w)
return ' '.join(ans)
def short_words_2(words):
words = copy.deepcopy(words)
min_len = len(words[0])
for word in words:
if len(word) < min_len:
min_len = len(word)
ans = []
for word in words:
if len(word) == min_len:
ans.append(word)
return ' '.join(ans)
ans_1 = short_words_1(some_words)
ans_1_time = timeit.timeit(lambda: short_words_1(some_words), number=10000000)
ans_2 = short_words_2(some_words)
ans_2_time = timeit.timeit(lambda: short_words_2(some_words), number=10000000)
print(f'{ans_1}: {ans_1_time}') # aa dd: 29.5462521
print(f'{ans_2}: {ans_2_time}') # aa dd: 29.923632399999995
Вот вам один проход, не тупите. скинет все слова с минимальной длиной за один проход.
function linearSearch(strings) {
let minLen = strings[0].length;
let arr = [];
for (const word of strings) {
if (word.length < minLen) {
minLen = word.length;
arr = [word];
} else if (word.length === minLen) {
arr.push(word);
}
}
return arr.join(' ');
}
Спасибо
В задаче на собеседование можно счётчик добавить, и если встретили новый символ,добавить цифру в выходную строку, а счётчик обнулить?
В задаче на собеседование можно счётчик добавить, и если встретили новый символ,добавить цифру в выходную строку, а счётчик обнулить?