AtCoder Regular Contest B - DNA Sequence Difficulty: 410
Dieses Thema, kumulative Summe
Dies ist ein kumulatives Summenproblem, aber dieses Mal benötigen wir vier kumulative Summen von A``C``G``T
.
Ruby
ruby.rb
n, s = gets.chomp.split
n = n.to_i
a = [0]
c = [0]
g = [0]
t = [0]
n.times do |i|
a << a[-1]
c << c[-1]
g << g[-1]
t << t[-1]
if s[i] == 'A'
a[i + 1] += 1
elsif s[i] == 'C'
c[i + 1] += 1
elsif s[i] == 'G'
g[i + 1] += 1
elsif s[i] == 'T'
t[i + 1] += 1
end
end
cnt = 0
n.times do |i|
at = a[i] - t[i]
cg = c[i] - g[i]
(i.next).upto(n) do |j|
cnt += 1 if a[j] - t[j] == at && c[j] - g[j] == cg
end
end
puts cnt
Ich habe die Idee von @scivola im Kommentarbereich reflektiert.
ruiseki.rb
a << a[-1]
c << c[-1]
g << g[-1]
t << t[-1]
Beim Erstellen eines kumulativen Arrays können Sie auch zuerst die erforderliche Anzahl von Elementen vorbereiten. Dieses Mal habe ich das letzte Element mit "[-1]" aufgerufen und hinzugefügt.
hantei.rb
at = a[i] - t[i]
cg = c[i] - g[i]
(i.next).upto(n) do |j|
cnt += 1 if a[j] - t[j] == at && c[j] - g[j] == cg
end
Wenn die Anzahl der Elemente von "A" C "G" T "im Intervall gleich ist, kann dies als" komplementär "beurteilt werden. Python
pypy.py
from sys import stdin
def main():
input = stdin.readline
n, s = input().split()
n = int(n)
s = 'N' + s + 'N'
cnt = 0
for i in range(1, n + 2):
a = 0
c = 0
g = 0
t = 0
j = i + 1
while True:
if s[i] == 'A':
a += 1
elif s[i] == 'C':
c += 1
elif s[i] == 'G':
g += 1
elif s[i] == 'T':
t += 1
else:
break
if s[j] == 'A':
a += 1
elif s[j] == 'C':
c += 1
elif s[j] == 'G':
g += 1
elif s[j] == 'T':
t += 1
else:
break
if a == t and c == g:
cnt += 1
i -= 1
j += 1
print(cnt)
main()
"Pypy" ist eine andere Lösung. Mit dieser Lösung wird es zu "TLE" in "Python" und "Ruby".
banpei.py
s = 'N' + s + 'N'
Es gibt Wachen vor und nach der Schnur. Es wird für die Bedingung "Pause" mit "während" verwendet.
hiroge.py
i -= 1
j += 1
Wir überprüfen die Nummer, indem wir den Bereich an jeder Zeichenposition erweitern Java
java.java
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.next());
String s = "N" + sc.next() + "N";
sc.close();
int cnt = 0;
for (int k = 1; k < n+2; k++) {
int i = k;
int j = k + 1;
int gn = 0;
int cn = 0;
int tn = 0;
int an = 0;
while (true) {
if (s.charAt(i) == 'A') {
an++;
} else if (s.charAt(i) == 'C') {
cn++;
} else if (s.charAt(i) == 'G') {
gn++;
} else if (s.charAt(i) == 'T') {
tn++;
} else {
break;
}
if (s.charAt(j) == 'A') {
an++;
} else if (s.charAt(j) == 'C') {
cn++;
} else if (s.charAt(j) == 'G') {
gn++;
} else if (s.charAt(j) == 'T') {
tn++;
} else {
break;
}
if (an == tn && cn == gn) {
cnt++;
}
i--;
j++;
}
}
System.out.println(cnt);
}
}
"Java" ist die gleiche Lösung wie "Pypy". Ich habe die Idee von @ c-yan im Kommentarbereich reflektiert.
i.java
for (int k = 1; k < n+2; k++) {
int i = k;
Im Gegensatz zu "Python" und "Ruby" wirkt sich die Zuweisung zu einer Schleifenvariablen in einem Block auf die nächste Schleifenvariable aus, sodass Sie sie einer anderen Variablen zuweisen.
Ruby | Pypy | Java | |
---|---|---|---|
Codelänge(Byte) | 482 | 920 | 1436 |
Ausführungszeit(ms) | 1011 | 336 | 335 |
Erinnerung(KB) | 14676 | 69312 | 39456 |
Recommended Posts