DNA序列

时间复杂度O(n)2都能通过啊……

while True:
    try:
        a, b = input(), int(input())
        maxStr, maxCnt = a[:b], a[:b].count("C") + a[:b].count("G")
        for i in range(0, len(a) - b):
            if a[i:i + b].count("C") + a[i:i + b].count("G") > maxCnt:
                maxCnt = a[i:i + b].count("C") + a[i:i + b].count("G")
                maxStr = a[i:i + b]
        print(maxStr)
    except:
        break

while True:
  try:
    a,b,c = input(),int(input()),[]
    for i in range(len(a)-b+1):
      if a[i] == "G"&nbs***bsp;"C":
        c.append([a[i:i+b],a[i:i+b].count("C")+a[i:i+b].count("G")])
    c.sort(key = lambda x: x[1], reverse = True)
    print(c[0][0])
  except:
    break

import java.util.*;
public class Main {
	public static int GCRatio(String str){
		int count = 0;
		for(int i=0;i<str.length();i++){
			if(str.charAt(i)=='G'||str.charAt(i)=='C'){
				count++;
			}
		}
		return count;
		
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			String str = scan.next();
			int n = scan.nextInt();
			String[] strs = new String[str.length()-n];
			LinkedHashMap<String,Integer> map = new LinkedHashMap<String,Integer>();
			//
			for(int i=0;i<str.length()-n;i++){
				strs[i]=str.substring(i, i+n);
				map.put(strs[i], GCRatio(strs[i]));
			}
			Collection<Integer> coll = map.values();
			int value = Collections.max(coll);
			Set<String> set = map.keySet();
			for(String s :set){
				if(map.get(s)==value){
					System.out.println(s);
					break;
				}
			}
		}
	}

} 

用的python3计算，思路及代码如下：

1. 根据需求，输出字符串长度已经规定了，如果要 GC-Ratio最高，那么则代表要求输出字符串中C和G的数量最多；
2. 因为是要在输入的字符串中找到一段长度为N的字符串，可以遍历所有的长度为N的字符串并存放进一个列表中，我定义为GC_list；
3. 对于GC_list列表中的每一个字符串目前都是满足长度为N的要求了，那么下一步就是选出列表中含有最多的C、G的字符串出来；
4. 再定义一个空列表num_list用于存放GC_list中各个字符串含有C、G的数量，即遍历GC_list中每一个字符串，判断是否含有C、G，含有则conunt+1，count追加进入num_list，则GC_list中字符串的下标与num_list中数字的下标一一对应；
5. 通过max取得num_list中的最大值，再通过index判断最大值的下标，这个下标在GC_list中对应的字符串即是我们需要的字符串，打印输出即可。

def func(s,n):
    GC_list=[]
    for i in range(len(s)-n+1): # 考虑输出字符串长度n,不能循环至末尾
        GC_str=s[i:i+n]
        GC_list.append(GC_str) # 遍历完所有长度为n的字符串，追加进入GC_list列表
        pass
    num=[]
    for j in range(len(GC_list)): # 遍历GC_list列表中每一个字符串
        count=0
        for a in GC_list[j]: # 对于每一个字符串而言，判断C、G是否存在，存在则+1
            if a=="C":
                count+=1
                pass
            elif a=="G":
                count+=1
                pass
            pass
        num.append(count) # 把每一个字符串中C、G的数量追加进num列表
        pass
    num_max=max(num) # 求num列表最大值
    res_num=num.index(num_max) # 求最大值对应的下标
    return GC_list[res_num] # GC_list中对应下标的字符串即是所需字符串
    pass
while True:
    try:
        s=str(input())
        n=int(input())
        print(func(s,n))
        pass
    except:
        break

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String DNA = sc.next();
            int N = sc.nextInt();
            double n = N;
            int index = -1;
            double max = 0;
            for(int i = 0; i < DNA.length() - N + 1; i++) {
                double num = ratio(DNA.substring(i, i + N)) / n;
                if(num > max) {
                    max = num;
                    index = i;
                }
            }
            System.out.println(DNA.substring(index, index + N));
        }
    }
    public static double ratio(String s) {
        s = s.replaceAll("[AT]","");
        return s.length();
    }
}

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
int main()
{
    string s;
    int x;
    while(cin>>s) {
        cin>>x;
        int index=-1;
        int max_count=0;
        int cur=0;
        int len=s.size();
        int i;
        for(i=0;i<x && i<len;++i) {
            if(s[i]=='G' || s[i]=='C') {
                ++cur;
            }
        }
        max_count=cur;
        index=0;
        while(i<len) {
            if(s[i-x]=='G' || s[i-x]=='C')
                --cur;
            if(s[i]=='G' || s[i]=='C')
                ++cur;
            if(cur>max_count) {
                max_count=cur;
                index=i-x+1;
            }
            ++i;
        }
        cout<<s.substr(index,x)<<endl;
    }
    return 0;
}

/**
 * 本人使用了比较直接的办法，就是挨个遍历，算出来每个子串的CG比例，
 * 然后找到第一个出现的比例最大的子串的位置。可能时间复杂度较大，
 * 希望网友提出改进意见。
 *
 */

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        while(s.hasNext()) {
            String str = s.next();
            int n=s.nextInt();
            int length=str.length();
            double[] ratio=new double[length-n+1];  //用数组来存储每个子串的CG比例
            for(int i=0;i<length-n+1;i++){
                ratio[i]=calculate(str.substring(i,i+n)); //计算每个子串的CG比例
            }
            double max=0;
            for(int i=0;i<length-n+1;i++){
                if(max<ratio[i]){
                    max=ratio[i];
                }
            }
            int flag=-1;
            for(int i=0;i<length-n+1;i++){
                if(max==ratio[i]){
                    flag=i;   //找到第一个比例最大的子串。
                    break;
                }
            }

            System.out.println(str.substring(flag,flag+n));
            }
        }


    private static double calculate(String str){
         char[] ch=str.toCharArray();
         double num=0;
         double d=str.length();
         for(int i=0;i<ch.length;i++){
             if(ch[i]=='G'||ch[i]=='C'){
                 num++;
             }
         }
      return  num/d;
    }
}

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            String input = scanner.next();
            int size = scanner.nextInt();
            System.out.println(findMaxGC(input,size));
        }
    }
    public static String findMaxGC(String input, int size){
        String potentialResult = "";
        int currentGCcount = 0;
        for (int i = 0; i <= input.length() - size; i++){
            List<String> sub = Arrays.asList(input.substring(i,i+size).split(""));
            int Gcount = Collections.frequency(sub,"G");
            int Ccount = Collections.frequency(sub,"C");
            if (Gcount == size/2 && Ccount == size/2){
                return String.join("",sub);
            }
            if (currentGCcount < Gcount+Ccount){
                currentGCcount = Gcount+Ccount;
                potentialResult = String.join("",sub);
            }
        }
        return potentialResult;
    }
}

while True:
    try:
        string, num = input().strip(), int(input().strip())
        C_and_G_counts = []
        for i in range(0, len(string)-num+1):
            sub_str = string[i:i+num]
            C_and_G_counts.append(sub_str.count('C') + sub_str.count('G'))
        index = C_and_G_counts.index(max(C_and_G_counts))
        print(string[index:index+num])
    except:
        break
        

while True:
    try:
        a = input()
        b = int(input())
        char = a[:b]
        ra = char.count('C')+char.count('G')
        for i in range(1,len(a)-b+1):
            if a[i:i+b].count('C')+a[i:i+b].count('G') > ra:
                char = a[i:i+b]
                ra = char.count('C')+char.count('G')
        print(char)
    except:
        break

while True:
    try:
        string,n=input(),int(input())
        tmp,cnt=[],[]
        for i in range(0,len(string)-4):
            tmp.append(string[i:i+n])
            cnt.append(tmp[i].count('G')+tmp[i].count('C'))
        print(tmp[cnt.index(max(cnt))])
    except:
        break