В рамках моей попытки принять участие в конкурсе Python 30 Days of Coding Challenge я буду учиться писать код для расчета состояния ДНК в этой статье.

В этом задании вам дается набор генов и соответствующие им значения для здоровья, а также набор нитей ДНК. Для каждой цепи ДНК вам необходимо рассчитать значение ее здоровья, подсчитавсколько раз каждый ген встречается в цепи, и умножив это число на значение здоровья гена. Итоговое значение Значение здоровья цепи ДНК представляет собой сумму значений здоровья всех генов, которые появляются в цепи.

Для большого количества нитей ДНК и генов задача требует эффективного алгоритма для выполнения этих вычислений. Один из методов состоит в том, чтобы сохранить гены и их значения для здоровья в структуре данных Trie, а затем просмотреть Trie для каждой цепи ДНК, чтобы определить ее значение для здоровья.

Предварительные требования

Что такое Трие?

Эффективным способом хранения и поиска строк является использование дерева, представляющего собой древовидную структуру данных. Поскольку каждый узел в дереве представляет собой префикс одной или нескольких строк, его также называют деревом префиксов.

Каждый дочерний узел в дереве представляет собой символ, который можно добавить к префиксу, представленному его родительским узлом, а корень дерева представляет собой пустую строку. Узлы, представляющие полные строки, обозначаются как «терминальные» узлы. Ребра в дереве, которые соединяют родительские узлы с дочерними, представляют символы.

Возможность быстрого поиска и поиска строк является одним из основных преимуществ использования дерева. Это связано с тем, что для поиска строки в дереве требуется перемещение по дереву по одному символу за раз до тех пор, пока строка не будет обнаружена или не будет определено, что строки нет в дереве.

Текстовые редакторы, программы для проверки орфографии и программы для секвенирования ДНК — вот лишь несколько примеров программ, которые часто используют попытки при поиске строк. Алгоритм сопоставления строк Ахо-Корасика и алгоритм кодирования Хаффмана — два других алгоритма, которые их используют.



Trie — Википедия
В компьютерных науках trie, также называемое цифровым деревом или префиксным деревом, представляет собой тип k-арного дерева поиска, дерева данных…ru.wikipedia.org



Алгоритм KMP (Кнут-Моррис-Пратт)?

К счастью, у меня уже есть статья о поиске строк с использованием алгоритма KMP.

Согласно Википедии: алгоритм поиска строк ​​Кнута-Морриса-Пратта (или алгоритм KMP) ищет вхождения слова W в основной 'текстовая строка' S, используя наблюдение, что, когда происходит несоответствие, само слово содержит достаточную информацию, чтобы определить, где может начаться следующее совпадение, минуя таким образом повторную проверку ранее сопоставленных символов.



Алгоритм поиска строки (Кнут–Моррис–Пратт) | в Python
Алгоритм поиска строк Кнута-Морриса-Пратта (или алгоритм KMP) ищет вхождения «слова W в…medium.com»



Алгоритм Ахо-Корасик?

В информатике алгоритм Ахо-Корасика — это алгоритм поиска строк, изобретенный Альфредом В. Ахо и Маргарет Дж. Корасик в 1975 году. Это своего рода словарь. -сопоставление алгоритм, который находит элементы конечного набора строк (словарь) во входном тексте. Соответствует всем строкам одновременно. Сложность алгоритма линейна в зависимости от длины строк плюс длина искомого текста плюс количество совпадений на выходе.

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



Алгоритм Ахо-Корасика — Википедия
Поиск строк в классе, сопоставление строк Структура данных Конечный автомат строк В информатике…en.wikipedia.org



Алгоритм бинарного поиска?

Согласно Википедии: бинарный поиск, также известный как полуинтервальный поиск, [1], логарифмический поиск, [2] или бинарная отбивка, [3] — это алгоритм поиска, который находит положение целевого значения в отсортированном массиве. [4][5] Двоичный поиск сравнивает целевое значение в средний элемент массива. Если они не равны, половина, в которой не может лежать цель, исключается, и поиск продолжается в оставшейся половине, снова беря средний элемент для сравнения с целевым значением и повторяя это до тех пор, пока целевое значение не будет найдено. Если поиск заканчивается тем, что оставшаяся половина пуста, цель отсутствует в массиве.

Бинарный поиск выполняется за логарифмическое время в худшем случае.

Двоичный поиск быстрее, чем линейный поиск, за исключением небольших массивов. Однако массив должен быть сначала отсортирован, чтобы можно было применить бинарный поиск.



Алгоритм бинарного поиска — Википедия
В компьютерных науках бинарный поиск, также известный как полуинтервальный поиск, логарифмический поиск или двоичный поиск, — это поиск… en.wikipedia.org



Теперь я уверен, что вы спрашиваете себя, с какой стати Богдан перечисляет все эти алгоритмы?

По правде говоря, для решения проблемы (как вы увидите) вы просто не можете использовать то или иное решение, так как оно не решит все дела за требуемое время, оно просто истечет по таймауту.

Теперь давайте углубимся в проблему!

Проблема:



Определение здоровья ДНК | HackerRank
ДНК — это нуклеиновая кислота, присутствующая в телах живых существ. Каждая часть ДНК содержит ряд генов, некоторые из…www.hackerrank.com



Решение:

Использование Trie | Успех: 25/33

from collections import defaultdict

# TrieNode class with children as defaultdict and gene_indices as a list
class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.gene_indices = []

# Trie class with insert and search functions
class Trie:
    def __init__(self):
        self.root = TrieNode()

    # Function to insert a gene with its index and health into the Trie
    def insert(self, gene, index):
        node = self.root
        for char in gene:
            node = node.children[char]
        node.gene_indices.append(index)

    # Function to search for a DNA substring in the Trie and calculate health
    def search(self, dna, start, end):
        health = 0
        node = self.root
        for char in dna:
            node = node.children.get(char)
            if node is None:
                break
            health += sum(h for i, h in node.gene_indices if start <= i <= end)
        return health

# Read input
n = int(input().strip())
genes = input().rstrip().split()
health = list(map(int, input().rstrip().split()))
s = int(input().strip())

# Create a Trie and insert genes with their index and health
trie = Trie()
for i, gene in enumerate(genes):
    trie.insert(gene, (i, health[i]))

# Initialize min_health and max_health
min_health, max_health = float('inf'), float('-inf')

# Process each DNA strand
for _ in range(s):
    start, end, dna = input().rstrip().split()
    start, end = int(start), int(end)

    # Calculate health for the current DNA strand
    health = 0
    for i in range(len(dna)):
        health += trie.search(dna[i:], start, end)
    
    # Update min_health and max_health
    min_health, max_health = min(min_health, health), max(max_health, health)

# Print the min_health and max_health
print(min_health, max_health)

Пояснение:

Это решение использует структуру данных Trie для эффективного хранения и поиска генов в цепях ДНК. Давайте подробно проанализируем решение:

  1. TrieNode: это класс, представляющий один узел в Trie. У каждого TrieNode есть словарь с именем children, который сопоставляет символы с соответствующими дочерними TrieNode. Кроме того, каждый TrieNode содержит список gene_indices для хранения индекса гена и его связанного значения работоспособности для гена, заканчивающегося в этом узле.
  2. Trie: этот класс представляет структуру данных Trie. Он содержит root TrieNode и имеет методы для вставки генов в Trie и поиска генов в цепях ДНК.
  • insert: Этот метод вставляет ген в Trie вместе с его индексом. Он начинается с корня TrieNode и пересекает Trie в соответствии с символами в гене. Как только он достигает TrieNode, соответствующего концу гена, он добавляет индекс гена и его значение работоспособности в список gene_indices этого TrieNode.
  • search: Этот метод ищет гены в цепи ДНК, начиная с определенной позиции. Он начинается с корня TrieNode и пересекает Trie на основе символов в цепи ДНК. Для каждого посещаемого TrieNode он суммирует значения работоспособности индексов генов, которые попадают в указанный диапазон (от начала до конца), и возвращает общее состояние работоспособности.

3. Основная программа: основная часть кода считывает входные данные, создает экземпляр класса Trie и вставляет гены в Trie. Затем он перебирает нити ДНК и вычисляет здоровье каждой нити с помощью Trie. Он отслеживает минимальные и максимальные значения здоровья и печатает их в конце.

Преимущества:

Использование Trie для решения этой задачи — хорошая идея, поскольку она позволяет эффективно хранить и искать гены. Структура Trie позволяет быстро искать гены в цепях ДНК, используя символы ДНК для обхода узлов Trie. Это устраняет необходимость в избыточных сравнениях или поиске, значительно снижая общую временную сложность.

Кроме того, Tries может эффективно обрабатывать перекрывающиеся гены в цепях ДНК, поскольку поиск продолжается вниз по узлам Trie даже после обнаружения гена, что позволяет обнаруживать перекрывающиеся гены. Эта функция особенно полезна для этой проблемы, когда гены могут появляться несколько раз в виде подстрок в ДНК.

Использование КМП | Успех: 8/33

def compute_prefix_function(pattern):
    # Initialize the prefix function array
    pi = [0] * len(pattern)
    j = 0

    # Compute the prefix function values for each character in the pattern
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]

        if pattern[i] == pattern[j]:
            j += 1

        pi[i] = j

    return pi


def kmp(text, pattern):
    # Initialize the count of occurrences and the prefix function
    occurrences = 0
    pi = compute_prefix_function(pattern)
    j = 0

    # Iterate through the characters in the text
    for i in range(len(text)):
        # Adjust j based on the prefix function to avoid unnecessary comparisons
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]

        # If the characters match, increment j
        if text[i] == pattern[j]:
            j += 1

        # If the pattern is fully matched, increment occurrences and update j
        if j == len(pattern):
            occurrences += 1
            j = pi[j - 1]

    return occurrences


if __name__ == '__main__':
    n = int(input().strip())
    genes = input().rstrip().split()
    health = list(map(int, input().rstrip().split()))
    s = int(input().strip())

    min_health = float('inf')
    max_health = float('-inf')

    for s_itr in range(s):
        first_multiple_input = input().rstrip().split()
        start = int(first_multiple_input[0])
        end = int(first_multiple_input[1])
        dna = first_multiple_input[2]

        current_health = 0

        # Iterate through the genes in the specified range and search for occurrences in the DNA strand
        for i in range(start, end + 1):
            # Call the kmp function to find occurrences of the gene in the DNA strand
            occurrences = kmp(dna, genes[i])

            # Multiply occurrences by the corresponding health value and add to the total health
            current_health += occurrences * health[i]

        min_health = min(min_health, current_health)
        max_health = max(max_health, current_health)

    print(min_health, max_health)

Пояснение:

Предоставленное решение использует алгоритм Кнута-Морриса-Пратта (KMP) для эффективного поиска генов в цепях ДНК. Давайте подробно проанализируем решение:

  1. compute_prefix_function: это вспомогательная функция, которая вычисляет функцию префикса для заданного шаблона (гена). Префиксная функция, обозначенная как pi, представляет собой массив той же длины, что и шаблон. Значение pi[i] представляет собой длину самого длинного правильного префикса шаблона, который также является суффиксом шаблона [0..i]. Эта функция имеет решающее значение для алгоритма KMP, поскольку помогает избежать ненужных сравнений в процессе поиска.
  2. kmp: эта функция реализует алгоритм KMP, который ищет вхождения шаблона (гена) в тексте (цепочке ДНК).
  • Во-первых, он вызывает compute_prefix_function для вычисления функции префикса для данного шаблона.
  • Затем он перебирает символы в тексте, сохраняя переменную j, которая представляет текущую позицию в шаблоне.
  • Для каждого символа в тексте функция проверяет, соответствует ли он соответствующему символу в шаблоне. Если они совпадают, увеличивается j. Если они не совпадают и j больше 0, он обновляет j на основе функции префикса, чтобы избежать ненужных сравнений.
  • Когда j достигает длины шаблона, это означает, что шаблон был найден в тексте, поэтому функция увеличивает счетчик occurrences и обновляет j на основе функции префикса, чтобы продолжить поиск.

3. Основная программа. Основная часть кода считывает входные данные и вычисляет состояние каждой цепи ДНК с помощью алгоритма KMP. Для каждой нити он перебирает гены в указанном диапазоне и вызывает функцию kmp, чтобы найти вхождения каждого гена в нити. Затем количество вхождений умножается на соответствующее значение работоспособности и добавляется к общему состоянию цепочки. Программа отслеживает минимальные и максимальные значения здоровья и распечатывает их в конце.

Преимущества:

Использование алгоритма KMP для этой задачи — хорошая идея, поскольку он позволяет эффективно искать гены в цепях ДНК. KMP может значительно сократить количество сравнений в процессе поиска, используя функцию префикса. Это помогает избежать квадратичной временной сложности наивного подхода к сопоставлению строк.

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

Однако важно отметить, что, хотя алгоритм KMP более эффективен, чем подход наивного сопоставления строк, он может быть не таким эффективным, как Trie или Aho-Corasick при поиске нескольких генов в цепях ДНК. Эти структуры данных позволяют осуществлять одновременный поиск нескольких генов, что еще больше повышает производительность.

Использование Aho-Corasick | Успех: 15/33

class TrieNode:
    def __init__(self):
        self.children = {}  # Dictionary to store child TrieNodes
        self.indices = []  # List to store indices of genes at this TrieNode
        self.fail = None  # Fail link, used for Aho-Corasick algorithm

def insert(root, gene, index):
    node = root
    for char in gene:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.indices.append(index)  # Add gene index to the TrieNode

def build_fail_links(root, genes, health):
    queue = []
    for child in root.children.values():
        child.fail = root  # Set fail link of root's children to root
        queue.append(child)

    while queue:
        current = queue.pop(0)
        for char, child in current.children.items():
            queue.append(child)
            fail_node = current.fail
            while fail_node is not None and char not in fail_node.children:
                fail_node = fail_node.fail
            child.fail = fail_node.children[char] if fail_node else root  # Set child's fail link

def search(root, dna, first, last, health):
    node = root
    total_health = 0
    for char in dna:
        # Traverse fail links until finding a matching character or reaching the root
        while node is not None and char not in node.children:
            node = node.fail
        if node is None:
            node = root
        else:
            node = node.children[char]
            current = node
            # Traverse fail links, adding health for each gene index in the range [first, last]
            while current:
                total_health += sum(health[i] for i in current.indices if first <= i <= last)
                current = current.fail
    return total_health

def main():
    n = int(input().strip())  # Read the number of genes
    genes = input().rstrip().split()  # Read the genes as a list of strings
    health = list(map(int, input().rstrip().split()))  # Read the health values as a list of integers
    s = int(input().strip())  # Read the number of DNA strands

    root = TrieNode()  # Create the root TrieNode
    for index, gene in enumerate(genes):
        insert(root, gene, index)  # Insert each gene into the trie

    build_fail_links(root, genes, health)  # Build the fail links for the Aho-Corasick algorithm

    min_health, max_health = float('inf'), float('-inf')  # Initialize minimum and maximum health values
    for _ in range(s):
        first, last, dna = input().rstrip().split()  # Read the start, end, and DNA strand
        first, last = int(first), int(last)

        health_sum = search(root, dna, first, last, health)  # Calculate the current DNA strand's health
        min_health, max_health = min(min_health, health_sum), max(max_health, health_sum)  # Update the minimum and maximum health values

    print(min_health, max_health)  # Print the minimum and maximum health values

if __name__ == "__main__":
    main()

Пояснение:

Этот код реализует решение проблемы здоровья генов с использованием алгоритма Ахо-Корасика. Он состоит из класса TrieNode, трех основных функций (вставка, build_fail_links и поиск) и основной функции.

  1. TrieNode класс: класс TrieNode является основным строительным блоком для дерева. Каждый узел имеет три атрибута: children (словарь для хранения дочерних TrieNodes), indices (список для хранения индексов генов в этом TrieNode) и fail (неудачная ссылка, используемая для алгоритма Ахо-Корасика).
  2. Функция insert: функция вставки принимает корневой TrieNode, ген и его индекс. Он добавляет ген в дерево, создавая TrieNodes для каждого символа в гене, если они еще не существуют. Индекс гена добавляется к окончательному TrieNode.
  3. Функция build_fail_links: Функция build_fail_links создает ссылки сбоя для алгоритма Ахо-Корасика. В качестве входных данных он принимает корневой TrieNode, гены и значения здоровья. Он устанавливает неудачные ссылки каждого TrieNode, проходя по дереву в порядке ширины, гарантируя, что каждый TrieNode указывает на правильную ошибочную ссылку.
  4. Функция search: функция поиска использует в качестве входных данных корневой TrieNode, цепь ДНК, индексы первого и последнего гена и значения здоровья. Он ищет гены в цепочке ДНК и вычисляет общее состояние здоровья, проходя по трем и неудачным ссылкам. Он возвращает общее количество здоровья для данной цепи ДНК.
  5. Функция main: основная функция считывает ввод, создает корневой TrieNode и вставляет гены в trie. Он создает ссылки сбоя для алгоритма Ахо-Корасика и инициализирует минимальное и максимальное значения работоспособности. Для каждой цепи ДНК он вычисляет здоровье текущей цепи ДНК и обновляет минимальное и максимальное значения здоровья. Наконец, он печатает минимальное и максимальное значения здоровья.

Trie (дерево префиксов) — это фундаментальная структура данных, используемая в алгоритме Ахо-Корасика. Trie используется для эффективного хранения и поиска шаблонов (в данном случае генов) в заданном тексте (цепочке ДНК). Trie позволяет нам искать несколько шаблонов одновременно за линейное время, что делает алгоритм Ахо-Корасика более эффективным, чем другие алгоритмы поиска строк, такие как Naive или Knuth-Morris-Pratt (KMP), когда задействовано несколько шаблонов.

В алгоритме Ахо-Корасика Trie строится на основе шаблонов, которые мы хотим найти, и каждый узел в Trie представляет символ в шаблоне. TrieNode в алгоритме Ахо-Корасика содержит не только дочерние элементы и индексы, но и ссылку с ошибкой. Неудачная ссылка — важнейший элемент алгоритма Ахо-Корасика, поскольку она помогает нам более эффективно перемещаться по Trie, пропуская недопустимые символы и сокращая время поиска.

Таким образом, использование TrieNode в алгоритме Aho-Corasick важно, потому что оно позволяет нам хранить шаблоны таким образом, чтобы обеспечить эффективный поиск и сопоставление в тексте, используя преимущества свойств Trie и Aho -Конкретные неудачные ссылки алгоритма Corasick.

Преимущества:

Использование алгоритма Ахо-Корасика в сочетании с trie является хорошей идеей для этой задачи по следующим причинам:

  1. Эффективный поиск: алгоритм Ахо-Корасика позволяет одновременно искать несколько паттернов (генов) в заданном тексте (цепочке ДНК) с линейной временной сложностью, O(m + n + z), где m — длина текста, n — общая длина всех шаблонов, а z — общее количество вхождений шаблонов в тексте. Эта эффективность имеет решающее значение при поиске нескольких генов в длинных последовательностях ДНК.
  2. Оптимизация пространства. Использование структуры данных trie помогает оптимизировать пространство, необходимое для хранения паттернов (генов), за счет совместного использования общих префиксов. Такая оптимизация пространства особенно полезна при работе с большим количеством генов.
  3. Предварительная обработка: Алгоритм Ахо-Корасика требует однократного этапа предварительной обработки для построения ссылок на три и отказ, что может быть выполнено за время O (n), где n — общая длина всех шаблонов. После выполнения этого шага поиск нескольких шаблонов в нескольких текстах может быть выполнен эффективно.
  4. Обработка перекрывающихся паттернов: алгоритм Ахо-Корасика может эффективно обрабатывать перекрывающиеся паттерны (гены), что важно в этой проблеме, поскольку ген может появляться несколько раз в одной и той же цепи ДНК или перекрываться с другими генами.

Подводя итог, можно сказать, что использование алгоритма Ахо-Корасика для решения этой задачи является хорошей идеей благодаря его эффективным возможностям поиска, оптимизации пространства и способности обрабатывать перекрывающиеся шаблоны. Он предлагает более эффективное решение по сравнению с альтернативными подходами, такими как наивное сопоставление строк или даже алгоритм KMP, особенно при поиске большого количества генов в длинных последовательностях ДНК.

Хеширование + Попытки + Двоичный поиск | Успех: 33/33

from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

# function to calculate health of a strand
def getHealth(seq, first, last, largest):
    h, ls = 0, len(seq) # initialize health to 0 and get length of sequence
    for f in range(ls): # iterate over all possible substrings of the strand
        for j in range(1, largest+1):
            if f+j > ls: break # if the substring is out of range, break
            sub = seq[f:f+j] # get the substring
            if sub not in subs: break # if substring not in set of valid substrings, break
            if sub not in gMap: continue # if substring not in gene map, continue
            ids, hs = gMap[sub] # get the list of ids and healths for the gene
            h += hs[bRight(ids, last)]-hs[bLeft(ids, first)] # add the health of the gene for the given range
    return h

# get number of genes and list of genes
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))

# get number of strands and build gene map and set of valid substrings
howStrands = int(input())
gMap = defaultdict(lambda: [[], [0]])
subs = set()
for id, gene in enumerate(genes):
    gMap[gene][0].append(id) # add the id of the gene to the gene map
    for j in range(1, min(len(gene), 500)+1):
        subs.add(gene[:j]) # add all valid substrings to the set
for v in gMap.values():
    for i, ix in enumerate(v[0]):
        v[1].append(v[1][i]+healths[ix]) # add up the healths of the gene

# get the largest gene length
largest = max(list(map(len, genes)))

# initialize minimum and maximum health values to infinity and 0 respectively
hMin, hMax = inf, 0

# for each strand, calculate the health and update minimum and maximum values if necessary
for _ in range(howStrands):
    firstLastd = input().split()
    first = int(firstLastd[0])
    last = int(firstLastd[1])
    strand = firstLastd[2]
    h = getHealth(strand, first, last, largest)
    hMin, hMax = min(hMin, h), max(hMax, h)

# print the minimum and maximum health values
print(hMin, hMax)

Объяснение:

В этом решении используется комбинация нескольких методов для оптимизации проблемы, в результате чего получается очень эффективное решение, прошедшее все тесты.

Алгоритм использует комбинацию хеширования, префиксных деревьев (попыток) и бинарного поиска. Вот пошаговое объяснение кода:

  1. Код считывает ввод из стандартного ввода и сохраняет гены и соответствующие им значения здоровья в списках. Он также считывает количество нитей ДНК, которые необходимо обработать.
  2. Код создает список списков по умолчанию, называемый gMap, который будет использоваться для хранения индексов и значений здоровья для каждого гена. Он также создает набор под названием subs, который будет использоваться для хранения всех возможных подстрок генов.
  3. Затем код перебирает каждый ген, добавляя индекс гена и значение здоровья в словарь gMap. Он также добавляет каждую подстроку гена (до максимальной длины 500) в набор подстроек.
  4. Затем для каждого гена в gMap предварительно вычисляются значения работоспособности для всех индексов гена и сохраняются эти значения в списке. Этот предварительный расчет ускорит поиск индексов генов.
  5. Затем код определяет длину самого длинного гена в списке генов. Это будет использоваться позже для определения максимальной длины искомых подстрок.
  6. Для каждой цепи ДНК код считывает начальный и конечный индексы и саму цепь. Затем он вызывает функцию getHealth для вычисления значения здоровья для данной нити ДНК и добавляет его к промежуточному итогу.
  7. Функция getHealth принимает в качестве входных данных цепь ДНК, начальный и конечный индексы, а также длину самого длинного гена. Затем он перебирает все подстроки цепи ДНК (вплоть до длины самого длинного гена) и проверяет, входит ли подстрока в набор подстрок. Если это не так, он выходит из цикла. Если это так, он проверяет, находится ли подстрока в словаре gMap. Если это не так, он переходит к следующей подстроке. Если это так, он извлекает индексы и предварительно вычисленные значения здоровья для гена из словаря gMap и использует двоичный поиск, чтобы найти индексы, попадающие в заданный диапазон. Затем он суммирует соответствующие значения здоровья и возвращает общее состояние здоровья цепи ДНК.
  8. Наконец, код выводит минимальные и максимальные значения здоровья для всех нитей ДНК.

Преимущества:

Это решение высоко оптимизировано, поскольку оно предварительно вычисляет значения здоровья для каждого гена и использует бинарный поиск для быстрого нахождения индексов генов в заданном диапазоне. Он также использует набор для хранения всех возможных подстрок генов, что обеспечивает эффективную проверку подстрок. Кроме того, он использует список списков по умолчанию для хранения индексов генов и значений здоровья, что позволяет эффективно извлекать эти значения. Наконец, он использует быстрый механизм ввода/вывода для эффективной обработки больших объемов данных. В целом, этот алгоритм обеспечивает оптимальное решение задачи.

Богдан Тудораче | Основатель @ berrynews.org

Если вам понравилась статья и вы хотите меня поддержать, сделайте следующее:

  • 👏 Аплодируйте истории (50 хлопков), чтобы эта статья попала в топ
  • 🔔 Подпишитесь на меня в Среднем
  • 📰 Дополнительные материалы по кодированию на Coding Challenge
  • 🔔 Подключиться со мной: LinkedIn| Реддит