Задать вопрос

o5a

Ответы пользователя по тегу Алгоритмы

  • Как вывести самую длинную цепочку из символов в алфавитном порядке?

    @o5a
    Проблема из-за условия проверки
    if ord(text[i + j]) - ord(elems[-1][-1]) < 2
    в условии последовательности требуется, чтобы последующая буква была не меньше предыдущей, не понятно, с чего Вы вдруг такое условие написали.

    Вообще нет надобности сохранять куда-то сами последовательности, тем более, что требуется только первую из самых длинных. Как можно это сделать:
    Проходим по символам последовательности и проверяем, стал ли ord() текущего символа меньше предыдущего. Если стал, то последовательность закончилась. Проверяем, не стала ли эта последовательность больше предыдущей. Если да, обновляем данные максимальной последовательности (стартовую позицию и длину).
    В противном случае переходим к следующему.
    Примерно так:
    spoiler
    text = ...
text_len = len(text)
max_len = 0
max_idx = 0
seq_idx = 0
prev = 0

for i, x in enumerate(text):
    if ord(x) < prev:
        seq_len = i-seq_idx
        if seq_len > max_len:
            max_len = seq_len
            max_idx = seq_idx
        seq_idx = i
    elif i==text_len-1:
        seq_len = i-seq_idx+1
        if seq_len > max_len:
            max_len = seq_len
            max_idx = seq_idx
    prev = ord(x)
print(max_len, text[max_idx:max_idx+max_len])
    Ответ написан
    Комментировать
    Комментировать

  • Как рассчитать "похожесть" двух словарей?

    @o5a
    Если значения ключей не важны для сравнения, то достаточно использовать keys()
    d1 = {'Апельсин': 1,
'Яблоко': 2,
'Банан': 3
}

d2 = {'Апельсин': 2,
'Яблоко': 2,
'Инжир': 1
}

print(d1.keys())
# общие ключи
print(d1.keys()&d2.keys())

    Судя по ссылке, этого достаточно для расчета Вашего коэффициента.
    Ответ написан
    4 комментария
    4 комментария

  • Где ошибка в алгоритме пермутаций?

    @o5a
    Алгоритм должен быть такой: с конца ищем первый символ, такой, что a[i] < a[i+1], так мы определяем наименьший разряд, который сделает число больше предыдущего. Затем нам нужно минимизировать "хвост", чтобы получилось число, ближайшее к исходному (чем меньше хвост, тем оно ближе к исходному). Для этого мы хвост сортируем по возрастанию и переставляем наше число наименьшего разряда с первым числом из хвоста, большим его.

    В примере с 1234567890.

    1. Ищем цифру наименьшего разряда, когда a[i] < a[i+1]. Это 8, хвост [9, 0].
    2. Сортируем хвост [0, 9] и идем по нему в поисках первой цифры, большей нашей 8. Это 9.
    3. Переставляем их и возвращаем результат
    1234567809 => 1234567908
    Ответ написан
    3 комментария
    3 комментария