DNA序列

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int n = Integer.parseInt(br.readLine());

        // 业务场景为存取有序，所以使用linkedHashMap
        LinkedHashMap<String, Double> map = new LinkedHashMap<>();
        for (int i = 0; i <= line.length() - n; i++) {
            String sub = line.substring(i, i + n);
            map.put(sub, getGCRatio(sub));
        }

        // 计算最大值
        Collection<Double> values = map.values();
        double max = Collections.max(values);

        // 遍历找出第一个gc最大的字符串
        for (Map.Entry<String, Double> entry : map.entrySet()) {
            double value = entry.getValue();
            String key = entry.getKey();
            if (value == max) {
                System.out.println(key);
                break;
            }
        }
    }


    /**
     * 计算一个字符串GC的比例
     *
     * @param line
     * @return
     */
    private static double getGCRatio(String line) {
        int count = 0;
        for (int i = 0; i < line.length(); i++) {
            char c = line.charAt(i);
            if (c == 'C' || c == 'G') {
                count++;
            }
        }

        return count * 1.0 / line.length();
    }
}

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 str=in.nextLine();
        int num=in.nextInt();
        double maxRatio=0.0;
        //符合题目答案要求的开始索引
        int index=0;
        //计算答案
        for(int i=0;i<str.length()-num;i++){
            String strTmp=str.substring(i,i+num);
            //G,C出现的次数
            int sum=0;
            //求当前的GC-Ratio
            double ratio=0.0;
            for(int j=0;j<strTmp.length();j++){
                if(strTmp.charAt(j)=='G'){
                    sum++;
                }
                if(strTmp.charAt(j)=='C'){
                    sum++;
                }
            }
            //获取GC-Ratio
            ratio=Double.valueOf(sum)/Double.valueOf(num);
            //如果GC-Ratio大于最大GC-Ratio，就更新
            if(ratio>maxRatio){
                index=i;
                maxRatio=ratio;
            }
        }
        System.out.print(str.substring(index,index+num));
    }
}

//使用前缀和优化，时间复杂度O(N)


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 dna = in.next();
        int n = in.nextInt();
        int [] prefixSum = new int[dna.length()+1];
        for(int i=0; i<dna.length(); i++){
            if(dna.charAt(i) == 'G' || dna.charAt(i) == 'C'){
                prefixSum[i+1] = prefixSum[i] + 1;
            }else{
                prefixSum[i+1] = prefixSum[i];
            }
        }
        int maxStartIndex = 0, maxGCNum = 0;
        for(int i=0; i<=dna.length()-n; i++){
            if(prefixSum[i+n]-prefixSum[i] > maxGCNum){
                maxGCNum = prefixSum[i+n]-prefixSum[i];
                maxStartIndex = i;
            }
        }
        System.out.println(dna.substring(maxStartIndex,maxStartIndex+n));

    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = reader.readLine();
        int k = Integer.parseInt(reader.readLine());
        Main main = new Main();
        List<String> list = new ArrayList<>();
        main.getSubStr(s, list,k);
        int[] ratio = new int[list.size()];
        int max = 0;
        for (int i = 0; i < list.size(); i++) {
            int num = 0;
            String temp = list.get(i);
            for (int j = 0; j < temp.length(); j++) {
                if (temp.charAt(j) == 'G' || temp.charAt(j) == 'C') {
                    num++;
                }
            }

            max = Math.max(max, num);
            ratio[i] = num;
        }
        for (int i = 0; i < ratio.length; i++) {
            if (max == ratio[i]) {
                System.out.println(list.get(i));
                break;
            }
        }
    }

    public void getSubStr(String s, List<String> list, int k) {
        for (int i = 0; i <= s.length() - k; i++) {
            list.add(s.substring(i, i + k));
        }
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int n = sc.nextInt();
        // 注意：这里要用LinkedHashMap，HashMap是无序的
        Map<String, Double> map = new LinkedHashMap<>();
        for (int i = 0; i <= str.length() - n; i++) {
            String s = str.substring(i, i + n);
            // 被除数+0.0转为double
            map.put(s, (s.length() - s.replaceAll("[GC]", "").length() + 0.0) / n);
        }
        Double max = map.values().stream().sorted(Comparator.comparingDouble(Double::doubleValue).reversed()).findFirst().get();
        Set<Map.Entry<String, Double>> entries = map.entrySet();
        for (Map.Entry<String, Double> entry : entries) {
            if (max.compareTo(entry.getValue()) == 0) {
                System.out.println(entry.getKey());
                break;
            }
        }
    }
}

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int num = sc.nextInt();
        String result = "";
        int total = 0;
        for(int i = 0; i < str.length() - num + 1; i++){
            String temp = str.substring(i,i+num);
            int nn = 0;
            for(int j = 0; j < temp.length(); j++){
                if(temp.charAt(j) == 'C' || temp.charAt(j) == 'G'){
                    nn++;
                }
            }
            if(total < nn){
                total = nn;
                result = temp;
            }
        }
        System.out.println(result);
    }
}

标准的滑动窗口 ，Java实现
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String dna = sc.nextLine();
        int n = Integer.parseInt(sc.nextLine());


        List<Character> window = new ArrayList<>();
        //一个窗口内 gc的个数
        int currWindowGcCount = 0;
        int maxGcCount;
        String maxGcStr;

        //先把开始的 n个 加入到窗口中
        for (int i = 0; i < n ; i++) {
            if ('G' == dna.charAt(i) || 'C' == dna.charAt(i)) {
                currWindowGcCount++;
            }
            window.add(dna.charAt(i));
        }

        //当前第一个就是最大 gc
        maxGcCount = currWindowGcCount;
        maxGcStr = characterToString(window);

        //从第 n 个开始滚动窗口
        for (int i = n; i < dna.length(); i++) {
            // 往后滚动，如果是GC 则当前窗口GC数+1
            if ('G' == dna.charAt(i) || 'C' == dna.charAt(i)) {
                currWindowGcCount++;
            }
            window.add(dna.charAt(i));
            //第一个元素出队 ，如果是 GC，则窗口GC 数-1
            if ('G' == window.get(0) || 'C' == window.get(0)){
                currWindowGcCount--;
            }
            window.remove(0);
            if (currWindowGcCount >= maxGcCount){
                maxGcStr = characterToString(window);
                maxGcCount = currWindowGcCount;
            }
        }
        System.out.println(maxGcStr);
    }

    public static String characterToString(List<Character> characters){
        StringBuilder stringBuilder = new StringBuilder();
        characters.stream().forEach(stringBuilder::append);
        return stringBuilder.toString();
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        while ((str = br.readLine()) != null){
            // DNA长度
            int DNAlen = str.length();
            // 限定的子串长度 N
            Integer n = Integer.parseInt(br.readLine());
            // 限定的子串
            List<String> dnaChildStr = new ArrayList<>();
            // 子串切割
            int index = 0;
            while ((index+n) < DNAlen){
                dnaChildStr.add(str.substring(index,index+n));
                index++;
            }
            // 获取GC-Ratio最高且长度为N的第一个子串
            int rowIn = 0;
            // GC-Ratio最高且长度为N的第一个子串
            BigDecimal maxGcRatio= BigDecimal.ZERO;
            for (int i = 0; i < dnaChildStr.size(); i++) {
                char[] chars = dnaChildStr.get(i).toCharArray();
                int GC = 0;
                for (int j = 0; j < chars.length; j++) {
                    if (chars[j] == 'C' || chars[j] == 'G'){
                        GC++;
                    }
                }
                // DNA子串GC-Ratio
                BigDecimal GcRtaio =new BigDecimal(GC).divide(new BigDecimal(n),5,BigDecimal.ROUND_HALF_UP);
                if (maxGcRatio.compareTo(GcRtaio) == -1){
                    maxGcRatio = GcRtaio;
                    rowIn = i;
                }
            }
            // 打印GC-Ratio最高且长度为N的第一个子串
            String dnaStr = null;
            if (rowIn == 0 && DNAlen == n){
                dnaStr = str;
            }else {
                dnaStr = dnaChildStr.get(rowIn);
            }
            System.out.println(dnaStr);
        }
    }
}

import java.util.LinkedHashMap;
import java.util.Scanner;

/**
 * 题目:DNA序列
 * 一个 DNA 序列由 A/C/G/T 四个字母的排列组合组成。 G 和 C 的比例（定义为 GC-Ratio ）是序列中 G 和 C 两个字母的总的出现次数除以总的字母数目（也就是序列长度）。在基因工程中，这个比例非常重要。因为高的 GC-Ratio 可能是基因的起始点。
 *  给定一个很长的 DNA 序列，以及限定的子串长度 N ，请帮助研究人员在给出的 DNA 序列中从左往右找出 GC-Ratio 最高且长度为 N 的第一个子串。
 * DNA序列为 ACGT 的子串有: ACG , CG , CGT 等等，但是没有 AGT ， CT 等等
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        int n = scanner.nextInt();

        //找出子字符串中，CG个数最多的
        int maxCount = 0;
        String substring = "";
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();


        if(str.length() == n){
            System.out.println(str);
            return;
        }

        for (int i = 0; i < str.length()-n; i++) {
             substring = str.substring(i, i+n);
//             maxCount = Math.max(maxCount,getCount(substring));
            int count = getCount(substring);
            //不能=，不然会被替换掉
            if(count > maxCount){
                map.put(count,substring);
                maxCount = count;
            }
        }


        System.out.println(map.get(maxCount));



    }

    public static int getCount(String str){
        int count = 0;
        for (char c : str.toCharArray()) {
            if(c == 'C' || c == 'G'){
                count++;
            }
        }
        return count;
    }
}

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int n = sc.nextInt();
        
        ArrayList<String> list = new ArrayList<>();
        for(int i = 0 ; i < str.length() - n + 1 ; i ++){
            String temp = str.substring(i,i+n);
            list.add(temp);
        }
        
        ArrayList<Double> ratio = new ArrayList<>();
        for(int i = 0 ; i < str.length() - n + 1 ; i ++){
            double count = 0;
            String temp = list.get(i);
            for(int j = 0 ; j < n ; j ++){
                if(temp.charAt(j) == 'G' || temp.charAt(j) == 'C') count++;
            }
            double res = count / n;
            ratio.add(res);
        }
        
        int index = 0;
        double max = 0;
        for(int i = 0 ; i < str.length() - n + 1 ; i ++){
            if(ratio.get(i) > max){
                max = Math.max(max,ratio.get(i));
                index = i;
            }
        }
        
        System.out.print(list.get(index));
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String s = sc.nextLine();
            int n = sc.nextInt();
           //if (s.length()<n)   System.out.println(s);
            int lg = 0;
            int max = 0;
            int pos = 0; //右边界
            for (int i = 0; i<s.length(); i++) {
                char cur = s.charAt(i);
                if (cur=='C'||cur =='G') lg++;
                if (i >=n) {
                    char last = s.charAt(i-n);
                    if (last=='C'||last =='G') lg--;
                    
                }
                if (lg > max) {
                        max = lg;
                        pos = i+1;
                    }
               
            }
             if (pos <= n)  System.out.println(s.substring(0,n));
            else  System.out.println(s.substring(pos-n, pos));
           
        }
    }
}