Я участвую в 30-дневном соревновании по программированию на Python, и в этой статье я попытаюсь решить проблему Steady Gene.
Гены можно представить в виде строки длины n (где n делится на 4), состоящей из букв A, C, T и G.
Он считается постоянным, если каждая из четырех букв встречается ровно n/4 раза.
Например, GACT и AATGCCT являются стабильными генами.
Проблема:
Решение:
def steadyGene(gene):
n = len(gene)
count = {'A': 0, 'C': 0, 'G': 0, 'T': 0}
# occurrences of each letter in the gene string
for letter in gene:
count[letter] += 1
# determine the excess count of each letter
excess = {letter: count[letter] - n//4 for letter in 'ACGT' if count[letter] > n//4}
# if the gene is already steady, return 0
if not excess:
return 0
min_len = float('inf')
left = 0
for right in range(n):
# move the right end of the window until we
# have a substring that contains all the excess letters
if gene[right] in excess:
excess[gene[right]] -= 1
# move the left end of the window until we
# no longer have a substring that contains all the excess letters
while all(val <= 0 for val in excess.values()):
min_len = min(min_len, right - left + 1)
if gene[left] in excess:
excess[gene[left]] += 1
left += 1
return min_len
if __name__ == '__main__':
gene=open("gene.txt")
gene = gene.read()
result = steadyGene(gene)
print(result)
Чтобы запустить код, сохраните это в том же каталоге и назовите его gene.txt .
Объяснение:
Чтобы решить эту проблему, нам сначала нужно определить вхождение каждой буквы в заданную строку генов.
Затем мы можем использовать подход со скользящим окном, чтобы найти самую короткую подстроку, которую нужно заменить.
Сначала мы перемещаем правый конец окна, пока не получим подстроку, содержащую все лишние буквы (т. е. буквы, встречающиеся в строке гена более n/4 раз).
Затем мы перемещаем левый конец окна до тех пор, пока у нас не останется подстрока, содержащая все лишние буквы.
На данный момент у нас есть самая короткая подстрока, которую нужно заменить.
Мы повторяем этот процесс для всех возможных лишних букв и отслеживаем минимальную длину замещающей подстроки.
Наконец, мы возвращаем эту минимальную длину.
Подход скользящего окна:
Это распространенный алгоритмический метод, используемый в информатике для решения задач, связанных с массивами или строками.
Это простой и эффективный способ перебора элементов массива или строки в окне фиксированного размера или подмассиве/подстроке и вычисления желаемого результата. значение на основе элементов в этом окне, перемещая его по большему массиву или строке.
На каждом шаге скользящего окна мы добавляем или удаляем элементы из окна по мере необходимости и обновляем выходное значение на основе новых элементов в окне.
Это позволяет нам перебирать весь массив или строку с временной сложностью O(n), где n — размер входных данных.
Подход со скользящим окном обычно используется в задачах, связанных с поиском максимального или минимального значения в подмассиве или подстроке, подсчетом количества различных элементов в подмассиве или подстроке или поиском подмассива или подстроки, которые удовлетворяют определенному условию (например, содержащему все элементы заданного множества).
def sliding_window(s, window_size):
# Initialize variables
window_start = 0
window_end = 0
current_sum = 0
# Loop through the string
while window_end < len(s):
# Expand the window to the right
current_sum += s[window_end]
window_end += 1
# Shrink the window from the left
while current_sum > target:
current_sum -= s[window_start]
window_start += 1
# Check if we have found a valid subarray
if current_sum == target:
return [window_start, window_end - 1]
# Return None if no valid subarray found
return None
Спасибо за чтение и за вашу поддержку.
Пока!
