9 байт Вотякова. Айти, прога

Рубрика "Алгоритминутка" Давайте на минутку погрузимся алгоритмы! Дан отсортированный список целых чисел nums и некоторое целое число target. Если target находится в списке nums, то нужно вернуть его индекс. Иначе вернуть индекс на котором стоял бы target в этом списке. 1) nums=[1,3,5,6], target=5 —> 2 2) nums=[1,3,5,6], target=2 —> 1 3) nums=[1,3,5,6], target=7 —> 4 Решение в "лоб" 0) Будем идти по списку пока target большего текущего индекса 1) Если в какой-то момент target будет равен элементу массива, то мы нашли такой индекс 2) Если в какой-то момент target будет меньше элемента массива, то нужно вернуть этот же индекс, потому что если бы target был бы в списке, то он стоял бы не этом месте

def solve(nums, target: int):
    i = 0
    while i < len(nums):
        if target == nums[i] or target < nums[i]:
            return i
        i += 1
    return i

Эффективное решение 0) Так как список отсортированный, то можем воспользоваться бинарным поиском: поставим два указателя на начало и конец списка и запустить цикл пока левая граница не превосходит правую. 1) На каждой итерации цикла будем искать середину между двумя указателями m и сравнивать значение массива в этом месте nums[m] с target. 2) Если nums[m] = target, то мы нашли такой индекс. 3) Если nums[m] > target, то нужно сдвинуть правую границу на m-1. 4) Если nums[m] < target, то нужно сдвинуть левую границу на m+1.

def solve(nums, target: int):
    left, right = 0, len(nums) - 1

    while left <= right:
        m = (left + right) // 2
        if nums[m] == target:
            return m
        elif nums[m] > target:
            right = m - 1
        else:
            left = m + 1
    return left

Если все просто, то решаем задачку от сюда и смотрим на более интересную: целочисленное вычисление квадратного корня на похожую идею! А теперь предлагаю вам самим посчитать асимптотику алгоритмов! #алгоритминутка

Библиотека seaborn Оторвемся на минутку от алгоритмов и поговорим об интересной библиотеке. seaborn — это Python-библиотека с открытым кодом для построения красивых графиков. В основе этой библиотеки лежит matplotlib (тоже библиотека для построения графиков), pandas (библиотека для обработки данных) и многие другие. Установка seaborn Пишем в консоль: pip install seaborn Данные для графика Чтобы не собирать данные, воспользуемся встроенными датасетами seaborn. Возьмем датасет tips. Это данные некоторого ресторана, которые отражают поведение клиентов, дающих чаевые. Вы можете посмотреть эти данные так (вместо n подставьте число строк, которые Вы хотите увидеть):

# Подключаем библиотеку seaborn, принятое сокращение sns
import seaborn as sns
# Подключаем датасет
tips = sns.load_dataset("tips")
# Смотрим данные
tips.head(n)
print(tips.head(n)) # Для PyCharm

total_bill: Общая сумма счета tip: Сумма чаевых sex: Пол клиента smoker: Является ли клиент курильщиком day: День недели time: Обед или ужин size: Количество человек в компании Пишем первую программу Если Вы используете Jupyter Notebook/Google Colab, то можете закомментировать вторую и последнюю строчки программы, у Вас графики будут отображаться и так. Эти строчки нужны, чтобы график отображался в PyCharm.

# Подключаем библиотеку seaborn, принятое сокращение sns
import seaborn as sns
# Для PyCharm
import matplotlib.pyplot as plt

# Устанавливаем тему по умолчанию
sns.set_theme()

# Подключаем датасет
tips = sns.load_dataset("tips")

# Строим график
sns.relplot(
    data=tips,
    x="total_bill", y="tip", col="time",
    hue="smoker", style="smoker", size="size",
)

# Для PyCharm
plt.show()

Этот график показывает взаимосвязь между пятью переменными в наборе данных tips с помощью одного вызова функции seaborn relplot(). Но это, конечно, не все возможности seaborn, продолжение читайте в документации

Рубрика "Алгоритминутка" Вот такая задача встретилась в этом году на отборочном этапе мегаолимпиады ИТМО. Дан список строк. Найти самый длинный общий префикс для всех строк в этом списке. Если такого префикса нет, то в ответ идет пустая строка. Примеры: 1) ["flower","flow","flight"] —> "fl" 2) ["dog","racecar","car"] —> "" Решение в "лоб" Решение которое напрашивается такое: 0) Если в списке только одно слово, то возвращаем это слово 1) Заводим список префиксов. Начинаем идти циклом по списку строк strs, начиная с первой i=0 2) Запускаем второй цикл со следующей строки, j=i+1 3) Находим наибольший общий префикс строк strs[i] и strs[j] и добавляем его в список префиксов 4) Из этого списка префиксов находим наименьший — это и будет ответом

def common_prefix(str1, str2) -> str:
    result = ""

    for i in range(min(len(str1), len(str2))):
        if str1[i] == str2[i]:
            result += str1[i]
        else:
            break

    return result


def solve(strs) -> str:
    if len(strs) == 1:
        return strs[0]

    prefixs = []
    for i in range(len(strs)):
        for j in range(i+1, len(strs)):
            prefixs.append(common_prefix(strs[i], strs[j]))

    return min(prefixs)

Асимптотика Понятно, что такое решение совсем неэффективное. Посчитаем его асимптотику. Пусть в списке n элементов. Два вложенных цикла работают за O(n^2) (даже не смотря на то, что во втором цикле мы идем от i+1) На каждой итерации вызывается функция common_prefix(), которая работает за O(m), где m — длина наименьшей строки из двух. В худшем случае все строки одинаковы, так что возьмем m за длину наибольшей строки в списке. Суммарное время работы алгоритма: O(m*n^2) Хорошее решение 0) Отсортируем исходный список строк в лексикографическом порядке 1) Чтобы найти общий префикс всех строк, достаточно посчитать его для первой и последней строк

def common_prefix(str1, str2):
    result = ""
    for i in range(min(len(str1), len(str2))):
        if str1[i] == str2[i]:
            result += str1[i]
        else:
            break

    return result


def solve(strs) -> str:
    strs.sort()
    return common_prefix(strs[0], strs[-1])

Асимптотика Сортировка в Python работает за O(nlogn), где n — длина списка. Сравнение строк работает за длину строки, в общем случае не больше чем за максимальную длину строки в списке m. После нее мы ищем общий префикс за O(m) (оцениваем сверху) Суммарное время работы алгоритма: O(m*nlogn) Эффективное решение 0) Если входной массив strs пустой, то возвращаем пустую строку 1) Заводим переменную prefix, равную первой строки в списке 2) Начинаем итерироваться по списку строк (начиная со второй строки) и сравниваем ее символы с символами префиксной строки. 3) Если при сравнении найдется несовпадение символов или если префикс окажется пустым, то возвращаем текущее значение префикса как ответ.

def solve(strs):
    if not strs:
        return ""
    prefix = strs[0]
    for string in strs[1:]:
        while string.find(prefix) != 0:
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

Асимптотика: O(n * m), где n - количество строк в массиве, а m - длина самой длинной строки. А теперь попробуйте сами написать эту задачу на LeetCode! #алгоритминутка

Баг в библиотеке numpy numpy — это Python библиотека с открытым кодом для сложных математических вычислений. Её очень часто используют при анализе данных. Она написана на C и на Fortran, поэтому работает довольно быстро. Функции round() и np.round() Функция round(x, ndigits) — это встроенная функция в Python, которая округляет число до ближайшего кратного 10^(-ndigits) числа. Параметр ndigits является необязательным, но он может быть как положительным, так и отрицательным. В случае ndigits>0 число ndigits отвечает за количество знаков после запятой. Рассмотрим примеры:

print(round(1.25))      # 1
print(round(5.5))       # 6
print(round(5.126, 2))  # 5.13
print(round(15.5, -1))  # 20.0

Если первые три примера интуитивно понятны, то четвертый нужно разобрать. В этом случае ndigits=-1, значит 10^(-ndigits)=10. Теперь Python рассчитывает к какому числу ближе 15.5 к 10 или 20: 10 + 5.5 = 15.5 20 - 4.5 = 15.5 Так и получается ответ. Функция np.round() работает схожим образом:

# Подключаем библиотеку numpy, np — принятое сокращение
import numpy as np
print(np.round(1.25))     # 1.0
print(np.round(5.5))      # 5.0
print(np.round(5.126, 2)) # 5.13
print(np.round(15.5, -1)) # 20.0

А теперь попробуем такой пример:

print(np.round(2**63-1, -1))  # -9223372036854775808
print(round(2**63-1, -1))     # 9223372036854775810

numpy выводит неправильный ответ. Эта проблема уже есть в issues к numpy. Так как numpy написан на C, то скорее всего эта проблема возникает из-за переполнения типа int. Давайте попробуем округлить не целое число, а дробное: 2**63-1 (int) —> 2**63-1.0 (float):

print(np.round(2**63-1.0, -1))  # 9223372036854775808

Результат лучше, но все равно отличается (различаются две последние цифры) 👆 Если знаете решение этой проблемы, то пишите в issues!

Рубрика "Алгоритминутка" Получилась задачка? Если нет, то ниже решение, а если еще не смотрели, то прочитайте сначала этот пост (ссылка на предыдущий пост)

def romanToInt(s: str) -> int:
    translator_roman_to_int = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000,
    }

    number = 0
    s = s.replace("IV", "IIII").replace("IX", "VIIII")
    s = s.replace("XL", "XXXX").replace("XC", "LXXXX")
    s = s.replace("CD", "CCCC").replace("CM", "DCCCC")

    for char in s:
        number += translator_roman_to_int[char]

    return number

Теперь давайте разберемся с обратной задачей: перевод числа в римскую систему счисления. Int —> Roman Дано целое число из диапазона [1, 3999]. Вывести соответствующее число из римской системы счисления. Если ничего не знаешь про римские цифры, то читай предыдущий пост! 1) 3 —> "III" 2) 58 —> "LVIII" 3) 1994 —> "MCMXCIV" Решение №1 1) Как и в предыдущей задачи заведем словарь. Только ключами уже будут не римские цифры, а арабские. В соответствие им ставим римские цифры. 2) Заводим пустую строку result, к которой будем добавлять римские цифры 3) Проходимся циклом по [1000, 500, 100, 50, 10, 5, 1] — ключи в словаре от большего к меньшему. Пусть за элемент на каждом шаге отвечает переменная n. 4) Если наше число больше, чем n, то к строке result добавляем это же римское число (легко делаем с помощью словаря), а из исходного числа вычитаем n. Затем выполняем п. 4 еще раз, пока наше число не станет меньше n 5) Строку result останется "причесать", то есть заменить длинные комбинации цифр на короткие: IIII —> IV и т.д. Важный момент: начинать нужно с больших разрядов. То есть первая замена будет такой: DCCCC —> CM

def intToRoman(num: int) -> str:
    translator_int_to_roman = {
        1: "I",
        5: "V",
        10: "X",
        50: "L",
        100: "C",
        500: "D",
        1000: "M",
    }

    result = ""

    for n in [1000, 500, 100, 50, 10, 5, 1]:
        while n <= num:
            result += translator_int_to_roman[n]
            num -= n                            

    result = result.replace("DCCCC", "CM").replace("CCCC", "CD")
    result = result.replace("LXXXX", "XC").replace("XXXX", "XL")
    result = result.replace("VIIII", "IX").replace("IIII", "IV")

    return result

Решение №2 Одно из самых изящных решений этой задачи выглядит так:

def intToRoman(num: int) -> str:
    M = ["", "M", "MM", "MMM"]
    C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
    X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
    I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
    return M[num // 1000] + C[(num % 1000) // 100] + X[(num % 100) // 10] + I[num % 10]

1) Под каждый разряд заводим отдельный список: под тысячи M, под сотни — C, под десятки — X, под единицы — I. Так как по условию число num <= 3999, то этого достаточно. 2) Затем берем число из соответствующего разряда. Например, num // 1000 — получаем тысячи, а (num % 100) // 10 — десятки. 3) Обращаемся к соответствующему списку по индексу и конкатенируем строки — это и есть ответ #алгоритминутка

Как вам рубрика, открываем на постоянной основе? Выкладывать решение к прошлой задаче?

Рубрика "Алгоритминутка" Сегодня поговорим о римских числах. Есть две интересные задачи, связанные с ними: это перевод из римской системы счисления в обычную (арабскую) и из обычной — в римскую. Римские цифры представлены семью различными символами: I, V, X, L, C, D и M. Например, 2 записывается как II в римских цифрах. Число 12 записывается как XII, то есть просто X + II. Число 27 записывается как XXVII, то есть XX + V + II. Римские цифры обычно пишутся слева направо от наибольшей к наименьшей. Однако цифра, обозначающая четыре, не является IIII. Вместо этого число четыре записывается как IV. Поскольку единица находится перед пятеркой, мы вычитаем ее, получая четыре. Тот же принцип применим к числу девять, которое записывается как IX. Есть шесть случаев, когда используется вычитание: a) I можно поставить перед V (5) и X (10), чтобы получить 4 и 9. b) X можно поставить перед L (50) и C (100), чтобы получить 40 и 90. c) C можно поставить перед D (500) и M (1000), чтобы получилось 400 и 900. Roman —> Int Дана строка s, состоящая из римских цифр (то есть содержит только такие символы: 'I', 'V', 'X', 'L', 'C', 'D', 'M'). Гарантируется, что s - действительное римское число в диапазоне [1, 3999]. Написать функцию, которая переводит это число в обычную систему. 1) "III" —> 3 2) "LVIII" —> 58 3) "MCMXCIV" —> 1994 Заметим, что римские числа очень удобно раскладываются по цифрам: 1) III = I + I + I = 3 2) LVIII = L + V + I + I + I = 50 + 5 + 1 + 1 + 1 = 58 3) MCMXCIV = M + CM + XC + IV = 1000 + 900 + 90 + 4 = 1994 Алгоритм решения 1) Заводим словарь из 7 римских цифр в соответствие им ставим числа 2) Заменяем в строке римские цифры, которые представлены из двух связанных цифр, по одной цифре. Например, IV = IIII, IX = VIIII и так далее. 3) Проходимся циклом по измененной строке. Переводим римские цифры в обычные с помощью словаря и суммируем их. Это и будет ответом. Пробуйте решить эту задачу на LeetCode! В следующем посте будет решение этой задачи и подсказка как решить обратную задачу: перевод числа в римскую систему счисления. Думаю, что словарь Вам пригодиться ;)

translator_roman_to_int = {
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000,
}

Скидывайте в комменты за сколько ms у вас зашла задача! #алгоритминутка

Не прошёл собеседование на стажировку в гугл. Мальчик: блин, жаль, пойду дальше курсы по проге проходить Мужчина:

Императивное VS Декларативное программирование Императивное программирование — это парадигма, основанная на составлении алгоритма действий (инструкций/команд), которые изменяют состояние (информацию/данные/память) программы. Первыми языками программирования, основанными на таком подходе, были машинные коды и ассемблеры. Фактически, программа на этих языках — это код, который выполняется компьютером сразу, без предварительной компиляции. Из языков высокого уровня, требующих компиляции исходного кода программы в машинный код (или интерпретации), к императивным можно отнести C, C++, Java. Декларативное программирование — это парадигма, при которой описывается желаемый результат, без составления детального алгоритма его получения. В пример можно привести HTML и SQL. При создании HTML мы с помощью тегов описываем, какую хотим получить страничку в браузере, а не то, как нарисовать на экране заголовок статьи, оглавление и текст. В SQL, если нам нужно посчитать количество сотрудников с фамилией «Сидоров», мы напишем SELECT count(*) FROM employee WHERE last_name = 'Сидоров';. Тут ничего не сказано про то, в каком файле или области памяти находятся данные по сотрудникам, как именно выбрать из них всех Сидоровых и нужно ли вообще это делать для подсчёта их количества. Рассмотрим ещё один пример. Допустим, мы хотим приготовить обед. В императивной парадигме это выглядит как-то так: купить мясо, огурцы, помидоры, соль; порезать мясо, посолить; поставить сковородку на плиту; … В декларативной: хочу на обед жареное мясо с овощами (неплохо звучит, правда? :)). Вроде бы различия очевидны. Однако, императивный язык не мешает обобщить и автоматизировать отдельные задачи. Можно реализовать некий «слой» кода, библиотеки, которые будут «уметь» выполнять отдельные этапы алгоритма: определять по рецепту, есть ли в наличии необходимые продукты, заказывать их доставку, пользоваться плитой и т.д. Получится, что программный код императивного языка программирования, использующий такие библиотеки, уже не будет по своей структуре так уж сильно отличаться от декларативного. На практике, при написании кода и выбора подхода, разработчик отталкивается не только от возможностей и ограничений языка программирования, но и удобства использования той или иной парадигмы в данном конкретном случае. Что из себя представляют императивное и декларативное программирование? Если кратко, то императивная программа содержит прямые указания, что должен сделать компьютер и в каком порядке должны выполняться инструкции. Примерами императивных языков являются Java, Python, JavaScript, C, C++. Декларативная же программа состоит из ограничений и правил, из которых компьютер генерирует способ получения результата. Пример декларативного языка: SQL.

Кто мне объяснит, почему в SQL, языке, в котором синтаксис и style guide явно продумывался чтобы его было легко и красиво читать непрограммистам (полные слова, грамматически корректные конструкции, всякие BETWEEN и т.д.), при сортировке ORDER BY ключевые слова для возрастания и убывания это ASC и DESC, а не ASCENDING и DESCENDING. Они что, после всего этого топорного синтаксиса, решили всё-таки буквы экономить?

Я: запариваюсь про лексически и грамматически корректные комментарии в коде на английском на курсе АИСД. Тем временем, сайты-тренажёры по проге:

Просто великолепная статья про хэши и взломы решений других участников контеста за счёт подгона правильных тестов, которые вызывают много коллизий в хэш-функциях. И про то, как писать "хорошие" кастомные хэш-функции, устойчивые от взломов. Перед чтением статьи рекомендую почитать, что такое хэш в принципе, если ты вдруг в танке. https://codeforces.com/blog/entry/62393

Смотрите какая странная штука Вроде бы два одинаковых куска кода, но во втором есть странный неадекватный warning. Вот вам код, чтобы скопипастить и самим поиграться:

a = [[], []]
x, y = 0, 1
a[x].append(7)

b = [[], []]
p, q = [0, 1]
a[p].append(7)

В продолжение есть задача: дана последовательность из n - 1 числа, известно что дубликатов нет, а все числа в диапазоне от 0 до n - 1 включительно, найти недостающее число, если можно использовать O(1) дополнительной памяти

Вот вам код. a выбирает случайное число из двух. Что вычисляет b? p.s. В комментариях ещё более эффективная версия того же трюка

upd к этой коллекции: Как по-вашему правильно читать слово schedule, если вы - программист? ЩЕДУЛЕ. Ударение на У.

Ссылка на пончик-код: https://www.a1k0n.net/2011/07/20/donut-math.html для совсем новичков: в коде с сайта не хватает инклюдов, не забудьте их вписать в начало кода, иначе gcc у вас printf не распознает

Готовлюсь к лайв-уроку на своём курсе по программированию, тема - терминал. Смотрю демонстрацию плагина fig, которую делает CEO продукта (крутой плагин!). Добавляет всякие autocomplete и кучу других классных фич для юзеров терминала. Комментарий к видео:

Git сложен: легко всё испортить, и нереально понять как исправить

https://dangitgit.com/ru Автор данного ресурса описал несколько ситуаций, из которых разработчикам часто приходится выбираться при работе с Git