В этом посте мы найдем букву приоритета и их коэффициент в нескольких подпоследовательностях ДНК.
Описание задания
Последовательность ДНК может быть представлена в виде строки, состоящей из букв A, C, G и T, которые соответствуют типам последовательных нуклеотидов в последовательности. У каждого нуклеотида есть импакт-фактор, который представляет собой целое число. Нуклеотиды типов A, C, G и T имеют импакт-факторы 1, 2, 3 и 4 соответственно. Вам предстоит ответить на несколько вопросов вида: Каков минимальный импакт-фактор нуклеотидов, содержащихся в той или иной части заданной последовательности ДНК?
Последовательность ДНК задается в виде непустой строки S = S[0]S[1]…S[N-1], состоящей из N символов. Имеется M запросов, заданных в непустых массивах P и Q, каждый из которых состоит из M целых чисел. K-й запрос (0 ≤ K ‹ M) требует найти минимальный импакт-фактор нуклеотидов, содержащихся в последовательности ДНК между позициями P[K] и Q[K] (включительно).
Например, рассмотрим строку S = CAGCCTA и массивы P, Q такие, что:
P[0] = 2 Q[0] = 4
P[1] = 5 Q[1] = 5
P[2] = 0 Q[2] = 6
Ответы на эти M = 3 запросы следующие:
- Участок ДНК между позициями 2 и 4 содержит нуклеотиды G и C (дважды), импакт-факторы которых равны 3 и 2 соответственно, поэтому ответ равен 2.
- Часть между позициями 5 и 5 содержит один нуклеотид Т, импакт-фактор которого равен 4, поэтому ответ равен 4.
- Часть между позициями 0 и 6 (вся строка) содержит все нуклеотиды, в частности нуклеотид А, импакт-фактор которого равен 1, поэтому ответ равен 1.
Напишите функцию:
защитное решение (S, P, Q)
что для заданной непустой строки S, состоящей из N символов, и двух непустых массивов P и Q, состоящих из M целых чисел, возвращается массив, состоящий из M целых чисел, определяющих последовательные ответы на все запросы.
Массив результатов должен быть возвращен как массив целых чисел.
Например, для строки S = CAGCCTA и массивов P, Q таких, что:
P[0] = 2 Q[0] = 4
P[1] = 5 Q[1] = 5
P[2] = 0 Q[2] = 6
функция должна возвращать значения [2, 4, 1], как описано выше.
Напишите эффективный алгоритм для следующих предположений:
- N — целое число в диапазоне [1..100 000];
- M — целое число в диапазоне [1..50 000];
- каждый элемент массивов P, Q является целым числом в диапазоне [0..N − 1];
- P[K] ≤ Q[K], где 0 ≤ K ‹ M;
- строка S состоит только из заглавных английских букв A, C, G, T.
Авторские права, 2009–2020 гг., принадлежат Codility Limited. Все права защищены. Несанкционированное копирование, публикация или разглашение запрещено.
Ключевой момент
- Найдите точно приоритетную букву в каждой подпоследовательности по заданным индексам.
- Избегайте ситуаций тайм-аута. Например, метод линейного поиска требует гораздо больше времени, когда заданная последовательность ДНК длинная.
Решение (с использованием Python)
def solution(S, P, Q):
M, letters = [], {'A':1, 'C':2, 'G':3, 'T':4}
for idx in range(len(P)):
for key in list(letters.keys()):
if(key in S[P[idx]:Q[idx]+1]):
min_coeff = letters[key]
break
M.append(min_coeff)
return M
Используйте приведенное выше решение для справки.
Я рекомендую вам написать собственный исходный код.
