题解 | #DNA序列#
DNA序列
https://www.nowcoder.com/practice/e8480ed7501640709354db1cc4ffd42a
题解：第一种方法是 找出符合长度的子序列，然后一个一个的统计里面包含的CG字符，最后将包含CG最多的字符串的下标保存起来
第二种是采用滑动窗口，通过统计窗口内CG字符的个数来找出包含CG最多的子序列，也是保存下标
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Scanner scanner = new Scanner(br);
String str = scanner.nextLine();
int length = scanner.nextInt();
String result = getSubstringWithTheHighestGCRatio2(str,length);
System.out.println(result);
}
/**
* 滑动窗口求解
*/
private static String getSubstringWithTheHighestGCRatio2(String str, int length) {
if (str == null || str.length()==0 || length <= 0) return null;
int left, right,max,count = 0,result = 0;
// 创建窗口
for (int i = 0; i < length; i++) {
if (str.charAt(i) == 'C' || str.charAt(i) == 'G')
count++;
}
max = count;
left = 1;
right = length;
// 窗口的维护
while (right < str.length()){
if (str.charAt(left-1) == 'C' || str.charAt(left-1) == 'G')
count--;
if (str.charAt(right) == 'C' || str.charAt(right) == 'G')
count++;
if (count > max){
max = count;
result = left;
}
left++;right++;
}
return str.substring(result,result+length);
}
/**
* 遍历求解
*/
private static String getSubstringWithTheHighestGCRatio1(String str, int length) {
if (str == null || str.length()==0 || length <= 0) return null;
int max = 0;
int result = 0;
for (int i = 0; i < str.length()-length; i++) {
int count = 0;
String s = str.substring(i,i+length);
for (int j = 0; j < s.length(); j++) {
if (s.charAt(j) == 'C' || s.charAt(j) == 'G')
count++;
}
if (max < count){
max = count ;
result = i;
}
}
return str.substring(result,result+length);
}
}
