题解 | #DNA序列#
DNA序列
https://www.nowcoder.com/practice/e8480ed7501640709354db1cc4ffd42a
滑动窗口法
长度为n的窗口,在char数组上滑动,记录每次包含的GC数量。
每次滑动时,左边丢了一个,右边加入一个。
可以利用这个特点,用窗口上次位置的GC数量就能计算出,此时GC数量。
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 String s = in.nextLine(); char[] chs = s.toCharArray(); int len = chs.length; int l = in.nextInt(); int[] num = new int[len - l + 1]; int max = 0; int i = 0; int j = l - 1; int k = 0; while (k <= j) { if (chs[k] == 'G' || chs[k] == 'C') { max ++; } k ++; } num[0] = max; //初始化完成 i++; j++; while (j < len) { int tmp = 0; //如果丢掉的那个字符属于GC if (chs[i - 1] == 'G' || chs[i - 1] == 'C') { tmp --; } //如果新加的那个字符属于GC if (chs[j] == 'G' || chs[j] == 'C') { tmp ++; } num[i] = num[i - 1] + tmp; max = max > num[i] ? max : num[i]; i ++; j ++; } for(int a = 0; a < num.length; a ++){ if(num[a] == max){ System.out.println(s.substring(a, a + l)); break; } } } }