Задача ШАДа
Дается строка s и число k. Найти длину максимального подотрезка на котором не более k различных букв.
Решение
Задача решается за O(n) с помощью двух указателей.
Давайте будем перебирать правый край отрезка, а левый будет сдвигаться до тех пор пока в подотрезке больше k различных символов. Чтобы хранить количество различных символов используем словарь. Ключем в словаре будет буква, а значение то сколько раз встречалась буква на этом подотрезки.
Таким образом получим, второй указатель двигается слева направо, а первый его догоняет. Таким образом мы рассмотрели каждую позицию не более 2 раз, соответственно асимптотика O(n)
Псевдокод в комментариях:
Дается строка s и число k. Найти длину максимального подотрезка на котором не более k различных букв.
Решение
Давайте будем перебирать правый край отрезка, а левый будет сдвигаться до тех пор пока в подотрезке больше k различных символов. Чтобы хранить количество различных символов используем словарь. Ключем в словаре будет буква, а значение то сколько раз встречалась буква на этом подотрезки.
Таким образом получим, второй указатель двигается слева направо, а первый его догоняет. Таким образом мы рассмотрели каждую позицию не более 2 раз, соответственно асимптотика O(n)
🔥16👍4🐳3⚡1❤1👏1🎉1
Задача с собеседования в Яндекс
Дается строка s. Найти максимальную по длине подстроку, которая является палиндромом.
Например abccbd ответом будет bccb
Решение:
Разберем решение за O(N^2)
Пусть dp[l][r] = 1 если подстрока [l, r] является палиндромом и 0 иначе. База дп будет dp[i][i] = 1 для всех i, а также dp[i][i + 1] = 1, если s[i] = s[i + 1].
Давайте научимся пересчитывать состояние dp, для этого переберем отрезки начиная с меньших длин. Пусть сейчас хотим узнать является ли палиндромом подстрока [l, r]. Замечу, что для подстроки [l + 1, r - 1] мы уже знаем является ли подстрока палиндромом или нет (потому что начинали перебирать подотрезки по возрастанию длин), очевидно если s[l] = s[r] и dp[l + 1][r - 1] = 1 то подстрока [l, r] будет палиндромом! В таком случае делаем dp[l][r] = 1.
Чтобы вывести саму подстроку мы перебираем подотрезки и обновляем ответ если подстрока палиндром, то есть dp[l][r] = 1 и длина подстроки наибольшая.
Решение за O(N) использовать алгоритм Манакера, который умеет находить все палиндромы в строке за O(N).
Псевдокод в комментариях:
Дается строка s. Найти максимальную по длине подстроку, которая является палиндромом.
Например abccbd ответом будет bccb
Решение:
Пусть dp[l][r] = 1 если подстрока [l, r] является палиндромом и 0 иначе. База дп будет dp[i][i] = 1 для всех i, а также dp[i][i + 1] = 1, если s[i] = s[i + 1].
Давайте научимся пересчитывать состояние dp, для этого переберем отрезки начиная с меньших длин. Пусть сейчас хотим узнать является ли палиндромом подстрока [l, r]. Замечу, что для подстроки [l + 1, r - 1] мы уже знаем является ли подстрока палиндромом или нет (потому что начинали перебирать подотрезки по возрастанию длин), очевидно если s[l] = s[r] и dp[l + 1][r - 1] = 1 то подстрока [l, r] будет палиндромом! В таком случае делаем dp[l][r] = 1.
Чтобы вывести саму подстроку мы перебираем подотрезки и обновляем ответ если подстрока палиндром, то есть dp[l][r] = 1 и длина подстроки наибольшая.
Решение за O(N) использовать алгоритм Манакера, который умеет находить все палиндромы в строке за O(N).
🔥14❤1⚡1👍1👏1
Задача с собеседования в Яндекс
Дается массив целых чисел a1, a2, a3, ..., an.
Отрезок назовем хорошим, если сумма чисел в ней равно нулю. Найдите максимальную по длине хороший подотрезок.
Например 1 2 -1 1 -1 -1
ответ 5.
Решение:
Давайте заведем префиксную сумму, то есть p[0] = 0, p[1] = a1, p[2] = a1 + a2, ...., p[n] = a1 + a2 + ... an. Ясно, что теперь сумму на подотрезке [l, r] мы можем узнавать через p[r] - p[l - 1]. Нас интересуют хорошие подотрезки, тогда разность должна быть равно нулю, то есть p[r] - p[l - 1] = 0, а именно p[r] = p[l - 1].
Давайте идти слева направо по префиксной сумме, пусть мы зафиксировали r, наша задача найти минимально возможную l, что p[r] = p[l]. Чтобы находить позицию l давайте во время прохода будем запоминать позиции первых вхождений для каждой суммы.
Работает за O(N) времени и O(N) памяти.
Псевдокод в комментариях:
Дается массив целых чисел a1, a2, a3, ..., an.
Отрезок назовем хорошим, если сумма чисел в ней равно нулю. Найдите максимальную по длине хороший подотрезок.
Например 1 2 -1 1 -1 -1
ответ 5.
Решение:
Давайте идти слева направо по префиксной сумме, пусть мы зафиксировали r, наша задача найти минимально возможную l, что p[r] = p[l]. Чтобы находить позицию l давайте во время прохода будем запоминать позиции первых вхождений для каждой суммы.
Работает за O(N) времени и O(N) памяти.
🔥18👍4👏1
Задача ШАДа
Даются два натуральных числа k, n (1 <= k <= n <= 500000). Вычислить значения фукнции Эйлера от биномиального коэффициента С(n, k).
Ответ вывести по модулю 1e9 + 7.
Пример k = 1, n = 5, ответ 4.
Ссылка на задачу.
Решение:
Для начало нужно понять, что такое функция Эйлера и как ее находить. Почитать можно по ссылке .
Давайте заранее почитаем все простые числа на отрезке [1, 5e5] это можно сделать с помощью алгоритма Решето Эратосфена за O(n * logn)
Функция Эйлера от числа n будет равен f(n) = n * ( (1-p1)/p1) * ( (1-p2)/p2) * .... * ( (1-pk)/pk)
В нашей задачи вместо n должны подставить C(n, k), давайте для каждого простого числа p узнаем делится ли число C(n, k) на p.
С(n, k) = n!/k!/(n-k)!
пусть
(n!) % (p^cnt1) == 0
(k!) % (p^cnt2) == 0
(n-k)! % (p^cnt3) == 0
Где cnt1, cnt2, cnt3 максимальные целые числа, тогда C(n, k)%p ==0, если cnt1 - cnt2 - cnt3 > 0.
Чтобы найти в какой степени входит простое число в разложение n! применим формулу
cnt1 = n/p + n/(p^2) + ..... + n/(p^t).
Таким образом мы сможем найти все простые делители числа C(n, k), соответственно сможем посчитать f(C(n, k)).
Замечу, что ответ нужно выводить по простому модулю, а значит написать просто ans *= (1-p)/p не получится, так как делить нельзя, но по малой теореме ферма 1/p = p^(1e9 + 7 - 2) mod (1e9 + 7), что соответственно и применим.
Работает за N * log(N), где N = 5e5
Псевдокод в комментариях:
Даются два натуральных числа k, n (1 <= k <= n <= 500000). Вычислить значения фукнции Эйлера от биномиального коэффициента С(n, k).
Ответ вывести по модулю 1e9 + 7.
Пример k = 1, n = 5, ответ 4.
Ссылка на задачу.
Решение:
Давайте заранее почитаем все простые числа на отрезке [1, 5e5] это можно сделать с помощью алгоритма
Функция Эйлера от числа n будет равен f(n) = n * ( (1-p1)/p1) * ( (1-p2)/p2) * .... * ( (1-pk)/pk)
В нашей задачи вместо n должны подставить C(n, k), давайте для каждого простого числа p узнаем делится ли число C(n, k) на p.
С(n, k) = n!/k!/(n-k)!
пусть
(n!) % (p^cnt1) == 0
(k!) % (p^cnt2) == 0
(n-k)! % (p^cnt3) == 0
Где cnt1, cnt2, cnt3 максимальные целые числа, тогда C(n, k)%p ==0, если cnt1 - cnt2 - cnt3 > 0.
Чтобы найти в какой степени входит простое число в разложение n! применим формулу
cnt1 = n/p + n/(p^2) + ..... + n/(p^t).
Таким образом мы сможем найти все простые делители числа C(n, k), соответственно сможем посчитать f(C(n, k)).
Замечу, что ответ нужно выводить по простому модулю, а значит написать просто ans *= (1-p)/p не получится, так как делить нельзя, но по малой теореме ферма 1/p = p^(1e9 + 7 - 2) mod (1e9 + 7), что соответственно и применим.
Работает за N * log(N), где N = 5e5
🔥13🤷♂1❤1👏1
Задача с собеседования в Яндекс
Даются n строк. Гарантируется, что строки состоят из латинских букв в нижнем регистре.
Две строки равны между собой, если можно так переставить буквы в них, чтобы они стали равны. Ваша задача найти количество пар (i, j), что строки s[i] и s[j] равны.
Решение:
Очевидно, две строки s и t раны, тогда и только тогда, когда sort(s) = sort(t), но если будем сортировать все слова и дальше записывать в словарь количество вхождений это займет больше чем линейное время, засчет сортировки строк.
Давайте для каждой строки s[i] мы заведем вектор vec[i] = [] который будет хранить 26 чисел, где vec[i][j] = количеству вхождений в строке i буквы j.
Тогда очевидно строки s[i] = s[j] если vec[i] = vec[j].
Каждый такой вектор мы запишем в словарь и зная количество вхождений определенного вектора мы сможем узнавать количество пар.
Время работы O(M + N), где M суммарная длина строк.
Псевдокод в комментариях:
Даются n строк. Гарантируется, что строки состоят из латинских букв в нижнем регистре.
Две строки равны между собой, если можно так переставить буквы в них, чтобы они стали равны. Ваша задача найти количество пар (i, j), что строки s[i] и s[j] равны.
Решение:
Давайте для каждой строки s[i] мы заведем вектор vec[i] = [] который будет хранить 26 чисел, где vec[i][j] = количеству вхождений в строке i буквы j.
Тогда очевидно строки s[i] = s[j] если vec[i] = vec[j].
Каждый такой вектор мы запишем в словарь и зная количество вхождений определенного вектора мы сможем узнавать количество пар.
Время работы O(M + N), где M суммарная длина строк.
🔥26👍2❤1👏1
Задача с собеседования в Яндекс
Дается бинарное дерево. Проверьте является бинарное дерево сбалансированным.
Определение: В сбалансированном дереве высота левого и правого поддерева отличается не более чем на 1.
Решение:
Давайте добавим параметр h в структуре вершины. Которая будет равна глубине вершины относительно корня. Глубину для каждой вершины мы сможем посчитать во время обхода в глубину, просто передавая число которая будет отвечать за глубину и увеличивая ее во время запуска dfs от детей.
Также создадим еще один параметр в структуре вершины, которую назовем maxDeapth, которая будет отвечать за максимальную глубину от левого поддерева и от правого поддерева. Чтобы пересчитать maxDeapth мы первоначально для вершины присваиваем maxDeapth = h, а после берем максимум maxDeapth от детей.
Таким образом мы должны для каждой вершины 'v' проверить неравенство |v.left.maxDeapth - v.right.maxDeapth| <= 1.
Алгоритм работает за O(N)
Псевдокод в комментариях:
Дается бинарное дерево. Проверьте является бинарное дерево сбалансированным.
Определение: В сбалансированном дереве высота левого и правого поддерева отличается не более чем на 1.
Решение:
Также создадим еще один параметр в структуре вершины, которую назовем maxDeapth, которая будет отвечать за максимальную глубину от левого поддерева и от правого поддерева. Чтобы пересчитать maxDeapth мы первоначально для вершины присваиваем maxDeapth = h, а после берем максимум maxDeapth от детей.
Таким образом мы должны для каждой вершины 'v' проверить неравенство |v.left.maxDeapth - v.right.maxDeapth| <= 1.
Алгоритм работает за O(N)
🔥11❤1🤷♂1👏1
Задача ШАДа
Дается массив строк. Найдите такое минимальное число mn, что если мы оставим в каждой строке первые mn букв то все строки будут различными.
(если длина строки меньше чем mn, мы берем всю строку)
Решение:
Заметим, что чем больше mn тем больше вероятность того, что строки будут различные!
Присутствует монотонность. Таким образом ответ можно забинарить.
Остается научиться проверять правда ли если мы в каждой строке оставим can букв то они все станут различные.
Для этого мы в каждой строке s[i] выделим min(can, len(s[i]) букв, запишем в словарь в качестве ключа, если какой-то ключ встретится более одного раза вернем False и сдвинем левую границу бинарного поиска, иначе правую.
Время работы алгоритма O(E * log(M)) Где E = суммарная длина строк, а M = max(len(s[i]))
Псевдокод в комментариях:
Дается массив строк. Найдите такое минимальное число mn, что если мы оставим в каждой строке первые mn букв то все строки будут различными.
(если длина строки меньше чем mn, мы берем всю строку)
Решение:
Присутствует монотонность. Таким образом ответ можно забинарить.
Остается научиться проверять правда ли если мы в каждой строке оставим can букв то они все станут различные.
Для этого мы в каждой строке s[i] выделим min(can, len(s[i]) букв, запишем в словарь в качестве ключа, если какой-то ключ встретится более одного раза вернем False и сдвинем левую границу бинарного поиска, иначе правую.
Время работы алгоритма O(E * log(M)) Где E = суммарная длина строк, а M = max(len(s[i]))
🔥13❤1👍1👏1
Задача с собеседования в Яндекс
Дан массив целых чисел длины N. Массив упорядочен по возрастанию. Написать функцию, которая из этого массива получает массив квадратов чисел, упорядоченный по возрастанию
Пример:
a = [-4, -3, -2, 0, 0, 2, 3, 5] -> [0, 0, 4, 4, 9, 9, 16, 25]
Решение:
Пусть l = максимальной позиции где находится отрицательное число, если такой позиции нет то присвоим -1
Пусть r = минимальной позиции где находится положительное число, если такой позиции нет то присвоим -1
Пусть cntZero = количество нулей в массиве.
Очевидно у нас в ответе будет cntZero нулей. Давайте их сразу выпишем в ответ.
Теперь нам нужно вывести len(a) - cntZero чисел. Если l = -1 мы выводим a[r] * a[r] и увеличиваем указатель r. Если же r = -1 то мы выводим a[l] * a[l] и уменьшаем счетчик, иначе очевидно мы должны возвести в квадрат то число, которое наименьшее из |a[l]|, |a[r]|. Не забываем изменять счетчик и будьте осторожны с выходом заграницы массивы при изменения счетчика.
Время работы алгоритма O(n)
Псевдокод в комментариях:
Дан массив целых чисел длины N. Массив упорядочен по возрастанию. Написать функцию, которая из этого массива получает массив квадратов чисел, упорядоченный по возрастанию
Пример:
a = [-4, -3, -2, 0, 0, 2, 3, 5] -> [0, 0, 4, 4, 9, 9, 16, 25]
Решение:
Пусть r = минимальной позиции где находится положительное число, если такой позиции нет то присвоим -1
Пусть cntZero = количество нулей в массиве.
Очевидно у нас в ответе будет cntZero нулей. Давайте их сразу выпишем в ответ.
Теперь нам нужно вывести len(a) - cntZero чисел. Если l = -1 мы выводим a[r] * a[r] и увеличиваем указатель r. Если же r = -1 то мы выводим a[l] * a[l] и уменьшаем счетчик, иначе очевидно мы должны возвести в квадрат то число, которое наименьшее из |a[l]|, |a[r]|. Не забываем изменять счетчик и будьте осторожны с выходом заграницы массивы при изменения счетчика.
Время работы алгоритма O(n)
🔥18👍1👏1