华为笔试在线训练-DNA序列问题
题目描述
一个DNA序列由A/C/G/T四个字母的排列组合组成。G和C的比例（定义为GC-Ratio）是序列中G和C两个字母的总的出现次数除以总的字母数目（也就是序列长度）。在基因工程中，这个比例非常重要。因为高的GC-Ratio可能是基因的起始点。
给定一个很长的DNA序列，以及要求的最小子序列长度，研究人员经常会需要在其中找出GC-Ratio最高的子序列。
牛客网链接
https://www.nowcoder.com/practice/e8480ed7501640709354db1cc4ffd42a?tpId=37&tqId=21286&rp=0&ru=/ta/huawei&qru=/ta/huawei/question-ranking
前言
本题中绝大部分的解决方法都是时间复杂度O(m*n),本文提供一种时间复杂度O(m) 空间复杂度为O(n)的方法。（其中m表示DNA序列的长度，n表示子序列的长度），算法思想受左程云《程序员代码面试指南》-“生成窗口最大值数组”和“最大值减去最小值小于或等于num的子数组数量”启发，向牛客网左程云老师表示感谢，跟着老师学了很久，终于感受到了算法构想的进步。
符号说明：
m：序列的总长度；
n: 子序列长度；
first：队列头部元素值（注意是下标不是真实的数值）；
size：滑动窗口中元素的个数，其实就是滑动窗口内G和C的总数；
start：最长子序列的第一个元素下标
max：最长子序列的长度
算法流程
建立滑动窗口（双端队列） 滑动窗口大小为n；
遍历DNA序列，窗口向前滑动，当遍历到的元素为'G'||'C'的时候，元素下标从队列尾部进入队列；
当first=i-w的时候，双端队列首部元素出队列；
更新start和max的值；
最后利用substring()进行子序列截取，打印；
当输入为如下序列的时候
TTTTCTGTTAGCGGTCCATCCTACCCCCTAAGAGTATCAGCGCATTAACTGTTGGGTAGACCTATACCGAAC
42
正确输出：TTTCTGTTAGCGGTCCATCCTACCCCCTAAGAGTATCAGCGC
但是截止到目前的算法思路输出：CTGTTAGCGGTCCATCCTACCCCCTAAGAGTATCAGCGCATT
所以要多考虑边界条件
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String str;
int start=0;
int max=-1;
while((str=reader.readLine())!=null) {
int w=Integer.valueOf(reader.readLine());
LinkedList<Integer> list=new LinkedList<>();
char temp;
if(w<1||str.length()<w){
continue;
}
for(int i=0;i<str.length();i++){
temp=str.charAt(i);
if(temp=='G'||temp=='C'){
list.offerLast(i);
}
if((list.size()!=0)&&(i-w==list.peekFirst())){
list.pollFirst();
}
// if(i>=w-1){
if(list.size()!=0){
start=list.size()>max?list.peekFirst():start;
max=Math.max(max,list.size());
}
// }
}
int lastIndex=0;
for(int j=start+w-1;j>=start;j--){
if(str.charAt(j)=='G'||str.charAt(j)=='C'){
break;
}else{
lastIndex++;
}
}
if((start-lastIndex)<0){
System.out.println(str.substring(0,w));
continue;
}
System.out.println(str.substring(start-lastIndex,start-lastIndex+w));
}
}
}
