Тренировки по алгоритмам от Яндекса. Лекция 4: «Словари и сортировка подсчётом»

keybyword('a1') == 'a111'
keybyword('a' * 111) == 'a111'

Данные строки не являются анаграммами, но только не для нашей функции подсчёта.

Михаил, а сколько у вас задачек на leetcode/topcoder решено? =)

О боже, Миша! Помню тебя еще по курсу по плюсам на Степике :) Спасибо тебе, с него начался мой путь в разработке :)

Может польза в этом и есть но глабально лекции этого пассажира это калл. Трижды переваренный калл
Проще почитать про это самому и быстрее будет

Можете опубиковать ссылку на задачу 4 на литкоде?

а в задаче с 2 числами и сортировкой подсчетом, скажите плиз, какое число элементов "небольшое" ? до какой степени можно использовать этот способ?

Супер!

я написал так решение первой задачки - сделал две мапы, перевел числа в массивы символов и прошелся одним циклом по массиву - за каждую итерацию добавлял в мапу через MERGE (пишу на джаве) цифру и количество ее повторений. Вернул результат equals по двум мапам. Работает. Сложность 0(n), некоторые накладные по памяти. Норм?)

В задаче #2 две ладьи не могут стоять в одной клетке? Не описали этот момент в условии. Просто, если 2 ладьи могут стоять в одной клетке, то алгоритм выдаст ответ: две пары, хотя по факту одна

А почему при упоминании про задачу о ферзях не разобрали backtracking (поиск с возвратом) алгоритм?

UPD: в следующей лекции объяснили.

задача 1 в JS:
function isEqualDigits(a,b) {
function countDigits(num) {
const digitCountArr = new Array(10).fill(0);
while (num > 0) {
const lastDigit = num % 10;
digitCountArr[lastDigit] += 1;
num = Math.floor(num / 10);
}
return digitCountArr
}

const digitsA = countDigits(a);
const digitsB = countDigits(b);
for (let i = 0; i < 10; i++) {
if (digitsA[i] !== digitsB[i]) return false;
}
return true;
}

Цитаты великих людей: "Не ошибаемся, только когда не думаем" XD

Было бы конечно гораздо понятнее если бы автор пользовался анотациями типов в примерах, особенно коггда приходят сложные структуры данных по-типу списка кортежей итд.

Про ладьи - можно создать два множества - для непустых строк и столбцов - и для каждой ладьи смотреть, есть ли ее координаты в множествах. Если нет - добавить, если есть - увеличить глобальный счетчик пар.

спасибо за лекцию! все понятно👍

Задача 3 в .Net core

public static void PrintSymbolLattices(string inputString)
{
var sortedList = inputString.GroupBy(c => c).Select(g => new
{
Symbol = g.Key,
Count = g.Count()
}).OrderBy(letter => (int)letter.Symbol).ToList();

for (var i = sortedList.Max(l => l.Count); i > 0; i--)
{
foreach (var symbolContainer in sortedList) Console.Write(symbolContainer.Count < i ? " " : "#");
Console.WriteLine();
}

sortedList.ForEach(s => Console.Write(s.Symbol));
}

Очень высокий уровень подачи, спасибо !

Блин, Питон - нечитаемый.

Первый дизлайк поставил, потому что сортировку подсчетом именно код вы объяснили плохо как мне кажется

Классный урок, не хватило шуток прикольных

А обязательно ли нам нужен цикл в 1 задаче, который проверяет все числа на их количество?
Мы не можем просто возвращать digitsx == digitsy?
И если не можем, интересно какие тестовые данные используются или почему не можем

UPD. Идея которая мне пришла в голову, сравнение в цикле при несовпадении элементов будет занимать меньше времени, если скажем кол-во единиц в двух числах не совпадает, т.е цикл сделает 2 действия при таком раскладе, а сравнение списков напрямую всегда будет занимать O(n).
Но в таком случае разница максимальна в 9 действий, и есть ли в таком случае жертвовать читабельностью с целью сэкономить максимум 9 действий.

groupwords будет работать неверно, если во входящей сироке будут цифры

Почему в последней задаче при сортировке подсчётом говорится, что сложность О(KLogK)? Мы ведь проходимся изначально по слову длинной N, чтобы собрать словарь. Тогда ведь получается сложность сортировки будет О(N*K*LogK)?

а что в задаче про группировку строк просто сначала в set не собрать (только плюсовый, сортированный), а потом не сделать из него строку-ключ? в задаче не сказано, не повторяются ли символы, а ну как повторяются, тем более если хакер вбил гигантскую строку. Ну n*logn, но зато ключ будет потенциально мелкий и не надо городить массив для сортировки подсчетом для (потенциально) utf8.

Сгруппировать слова - LeetCode 49. Group Anagrams. Помог подсчет, без сортировки. Решал на Го. В качестве ключей в мапе был как раз список частот длиной 26 (число букв в алфавите). На первый взгляд получилось O(n), n - число всех букв в словах. 
Значит можно и без сортировки?

Я нашел какая строка может сломать алгоритм, можно мне в Яндекс?
Так, стоп, а как давно была сделана запись? 🤔

Task #3. More short implimentation on Python:

s = 'Hello, world!'
s = ''.join(sorted(list(s)))
d, v_max = {}, 0
for ch in s:
d[ch] = d.get(ch, 0) + 1
if d[ch] > v_max:
v_max = d[ch]
l_t = zip(*[list(('#' * c).rjust(v_max, ' ')) for c in d.values()])
for el in l_t:
s1 = ''.join(el)
print(s1)
print(''.join(sorted(set(s))))

В первой задаче есть довольно легкое решение - принимать эти числа в качестве string, сортировать, на этапе сортировки число станет список, и просто сравнивать два отсортированных списка

C Python 3.7 словари типа dict поддерживают порядок добавления элементов.

Непонятно объяснил про ферзей и диагонали, представим такую расстановку 5 на 5

11 13 15
22 24
31 33 35
42 44
51 53 55

Легко заметить что координаты по диагонали взаимно изменяются на единицу, что дает нам равный результат при вычитании или сложении.
Так можно определить по какому ключу их хранить/суммировать:

11 22 33 44 55: c-r = 0, можно хранить по ключу 0
51 42 33 24 15: r+c = 6, можно хранить по ключу 6

т.е. встретив координаты
3,3: можно сделать инкремент по ключу 0(3-3) и 6(3+3) горизонтального словаря, т.е. этот ферзь бьет в 2 диагоналях с номерами 0 и 6
4,2: инкремент по ключу -2(2-4) и 6(4+2)
5,3: инкремент по ключу -2(3-5) и 8(5+3)
3,5: инкремент по ключу 2(5-3) и 8(3+5)
и т.д.

таким образом в -2-й диагонали мы нашли 2 ферзей, еще двух в 6-й и в 8-й

Код битвы ладей
def countbeatingrooks(rookcoords):
def addrook(roworcol, key):
if key not in roworcol:
roworcol[key] = 0
roworcol[key] += 1

def countpairs(roworcol):
pairs = 0
for key in roworcol:
pairs += roworcol[key] - 1
return pairs

rooksinrow = {} # словарь рядов
rooksincol = {} # словарь колонок
for row, col in rookcoords: # распаковка списка пар(кортежей)
addrook(rooksinrow, row) # добавление в ряд
addrook(rooksincol, col) # добавление в колонку
return countpairs(rooksinrow) + countpairs(rooksincol)

# 11 13 15
#
# 33
#
# 51 55
print(countbeatingrooks([(1,1),(1,3),(1,5),(3,3),(5,1),(5,5)]))

Большое Спасибо!