首页 > 试题广场 >

DNA序列

[编程题]DNA序列
  • 热度指数:140138 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

一个 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 等等

数据范围:字符串长度满足  ,输入的字符串只包含 A/C/G/T 字母

输入描述:

输入一个string型基因序列,和int型子串的长度



输出描述:

找出GC比例最高的子串,如果有多个则输出第一个的子串

示例1

输入

ACGT
2

输出

CG

说明

ACGT长度为2的子串有AC,CG,GT3个,其中AC和GT2个的GC-Ratio都为0.5,CG为1,故输出CG   
示例2

输入

AACTGTGCACGACCTGA
5

输出

GCACG

说明

虽然CGACC的GC-Ratio也是最高,但它是从左往右找到的GC-Ratio最高的第2个子串,所以只能输出GCACG。    
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            int n = in.nextInt();
            in.nextLine(); // 消耗掉nextInt()后的换行符
            int strLen = str.length();
            // 处理边界情况
            if (!isVaild(str, n)) {
                System.out.println("");
                continue;
            }
            int max = 0;
            String maxString = null;
            for (int i = 0 ; i <= strLen - n ; i++ ) {
                String temp = str.substring(i, i + n); //截取n位的字符串
                int count = 0;
                for (char c : temp.toCharArray()) {
                    if (c == 'G' || c == 'C') {
                        count++;
                    }
                }
                if (count > max) {
                    max = count;
                    maxString = temp;
                }
            }
            System.out.println(maxString);
        }
    }
    //验证字符串中是否只含有ACGT四种字母
    private static boolean isVaild(String str, int n) {
        if (str.length() < n || n <= 0 || n > 1000 || str.length() < 0) {
            return false;//字符串长度不合格或者n不合格
        }
        for (char c : str.toCharArray()) {
            if (c != 'A' && c != 'C' && c != 'G' && c != 'T') {
                return false;//不是只含有ACGT字母
            }
        }
        return true;//通过校验,返回true
    }
}

发表于 2025-07-01 15:47:25 回复(0)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            int b = in.nextInt();
            double gcRatio = 0;
            String maxStr = "";
            for (int i = 0; i <= a.length() - b; i++) {
                String s = a.substring(i, i + b);
                if (s.contains("ACG") || s.contains("CGT") || s.contains("CG")) {
                    char[] ss = s.toCharArray();
                    int count = 0;
                    for (int k = 0; k < ss.length; k++) {
                        if (ss[k] == 'G' || ss[k] == 'C') {
                            count++;
                        }
                    }
                    double rr = (double) count / b;
                    if (rr > gcRatio) {
                        gcRatio = rr;
                        maxStr = s;
                    }
                }
            }
            System.out.println(maxStr);
        }
    }
}

发表于 2025-05-18 22:57:10 回复(0)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s=in.nextLine();
        int n=in.nextInt();
        int max=0;
        String res="";
        if(s.length()<=n){
            res=s;
        }
        for(int i=0;i<s.length()-n;i++){
            String s1=s.substring(i,i+n);
            String s2=s1.replaceAll("[^CG]","");
            if(s2.length()>max){
                max=s2.length();
                res=s1;
            }
        }
        System.out.println(res);
    }
}

发表于 2025-04-08 19:39:45 回复(0)
//滑动窗口 get钩
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String dna = in.nextLine();
        //System.out.println(dna.length());
        int n = dna.length();
        int k = in.nextInt();
        //System.out.println(dna.substring(0,2));
        if (k >= n) {
            System.out.println(dna);
        } else {
            int a = 0;
            for (int i = 0; i < k; i++) {
                char p = dna.charAt(i);
                if (p == 'C' || p == 'G') {
                    a++;
                }
            }
            int b = 0;
            int c = k;
            int count = a;
            int max = a;
            for (int i = k; i < n;
                    i++) {
                if (dna.charAt(i - k) == 'C' || dna.charAt(i - k) == 'G') {
                    count--;
                }
                if (dna.charAt(i) == 'C' || dna.charAt(i) == 'G') {
                    count++;
                }
                if (count > max) {
                    b = i - k + 1;
                    c = b+k;
                    max = count;
                }
            }
            System.out.println(dna.substring(b, c));
        }
    }
}

发表于 2025-03-21 15:26:07 回复(0)

计算子串GC个数即可,因为n固定,个数最多的即比率最大的

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int n = in.nextInt();
        int max = 0, index = 0;
        for (int i = 0; i + n < s.length(); i++) {  // G、C个数最多的子串
            int cnt = n - s.substring(i, i + n).replaceAll("[GC]", "").length();
            if (cnt > max) {
                max = cnt;
                index = i;
            }
            if (cnt == n) break;
        }
        System.out.print(s.substring(index, index + n));
    }
}


发表于 2025-01-28 10:41:22 回复(0)
解题思路:
1. 统计子串中GC字母的数量,数量最大的那个符合要求
2.从左至右遍历字符,当前子串的GC数量可以简便计算:根据上一个子串的GC数量计算,仅仅需要处理上一个子串的头字符和当前子串的尾字符即可。
import java.util.*;
public class Main{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int n = Integer.parseInt(sc.nextLine());
        //记录最大比率子串的起点和GC的字母数
        int str_child_idx = 0;
        int str_child_GC = 0;
        //循环检索字符串
        int pre_substring_GC = 0;
        for(int i=0;i<str.length();i++)
        {
            char c = str.charAt(i);
            if(i<n)
            {
                //i<n,说明还在处理第一个子串
                //第一个串直接按默认最大GC串处理
                if(c=='G'||c=='C')
                {
                    str_child_GC++;
                }
                pre_substring_GC = str_child_GC;
            }else{
                //i>=n,说明第一个子串已经处理完毕
                //把i当做当前子串的末尾,则当前子串的起始点为i-n+1
                //当前子串的GC数量可以在前一个子串的数量基础上计算,去掉前一个子串头一个字符,加上当前字符
                int cur_substring_idx = i-n+1;
                int cur_substring_GC = pre_substring_GC;
                if(c=='G'||c=='C')
                {
                    cur_substring_GC++;
                }
                char c1 = str.charAt(i-n);
                if(c1=='G'||c1=='C')
                {
                    cur_substring_GC--;
                }
                //判断当前串的是否是已记录的最大串
                if(cur_substring_GC>str_child_GC)
                {
                    str_child_GC = cur_substring_GC;
                    str_child_idx = cur_substring_idx;
                }
                //当前串变为前一个子串,继续下一轮循环
                pre_substring_GC = cur_substring_GC;
            }
        }
        //最后输出
        System.out.println(str.substring(str_child_idx,str_child_idx+n));
    }
}

发表于 2024-11-28 10:27:44 回复(0)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = sc.nextInt();
        int max = 0;
        String rs = "";
        for (int i = 0; i < s.length() - n + 1; i++) {
            String temp = s.substring(i, i + n);
            int count = 0;
            for (char c : temp.toCharArray()) {
                if (c == 'G' || c == 'C') {
                    count++;
                }
            }
            if (count > max) {
                max = count;
                rs = temp;
            }
        }
        System.out.println(rs);
        sc.close();
    }
}

发表于 2024-11-12 00:39:20 回复(1)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String seq = in.next();
        int len = in.nextInt(), index = -1;
        double max = 0;
        for (int i = 0; i < seq.length() - len; i++) {
            if (max < getGCRatio(seq.substring(i, i + len))) {
                index = i;
                max = getGCRatio(seq.substring(i, i + len));
            }
        }
        if (index >= 0) {
            System.out.print(seq.substring(index, index + len));
        } else {
            System.out.print(seq);
        }
    }

    public static double getGCRatio(String seq) {
        double count = 0;
        for (char c : seq.toCharArray()) {
            if (c == 'C' || c == 'G') {
                count++;
            }
        }
        return count / seq.length();
    }
}
发表于 2024-10-01 16:54:50 回复(0)
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String input = in.nextLine();
        int k = in.nextInt();
        Deque<Integer> q = new LinkedList<Integer>();
        int res = 0;
        String output = new String();
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == 'C' || input.charAt(i) == 'G') q.add(i);
            if (i >= k) {
                //System.out.println( i + " qp: " + q.peekFirst());
                if (q.peekFirst() != null && q.peekFirst() < i - k + 1) q.removeFirst();
            }
            //System.out.println(i + " " + q.size());
            if (i == k - 1) {
                res = q.size();
                //System.out.println("st: " + i);
                output = input.substring(i - k + 1, i + 1);
            } else if (i >= k && res < q.size()) {
                res = q.size();
                //System.out.println("st: " + i);
                output = input.substring(i - k + 1, i + 1);
                //System.out.println(output);
            }
        }
        if (input.length() <= k) System.out.println(input);
        else System.out.println(output);
    }
}
发表于 2024-09-09 14:55:36 回复(0)
来个Java版的,时间复杂度O(n^2)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int n = in.nextInt();
        if (n > s.length()) {
            n = s.length();
        }
        int[][] gcCount = new int[n][s.length()];
        for (int j = 0; j < s.length(); j++) {
            gcCount[0][j] = (s.charAt(j) == 'G' || s.charAt(j) == 'C') ? 1 : 0;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < (s.length() - i); j++) {
                gcCount[i][j] = gcCount[i - 1][j];
                if (j + i < s.length()) {
                    gcCount[i][j] += gcCount[0][j + i];
                }
            }
        }
        // calculate gc ratio
        double[] gcRatio = new double[s.length() - n + 1];
            for (int j = 0; j < (s.length() - n + 1); j++) {
                gcRatio[j] = (double) gcCount[n - 1][j] / n;
            }
        // select first appearance of max gc ratio
        double maxRaito = 0;
        for (int j = 0; j < (s.length() - n + 1); j++) {
            if (gcRatio[j] > maxRaito) {
                maxRaito = gcRatio[j];
            }
        }

        for (int j = 0; j < (s.length() - n + 1); j++) {
            if (gcRatio[j] == maxRaito) {
                System.out.println(s.substring(j, j + n));
                return;
            }
        }

    }
}


发表于 2024-06-23 10:56:33 回复(0)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            String numStr = in.nextLine();
            int num = Integer.parseInt(numStr);
            int length = a.length();
            String findStr = "";
            for (int j = num; j > 0; j --) {
                boolean find = false;
                for (int i = 0; i <= length - num; i++) {
                    int lastIndex = i + num;
                    // if(lastIndex > length){
                    //     lastIndex = length;
                    // }
                    String subStr = a.substring(i, lastIndex);
                    if (islengthest(subStr, j)) {
                        findStr = subStr;
                        find = true;
                        break;
                    }
                }
                if(find){
                    break;
                }
            }
            System.out.println(findStr);
        }
    }

    private static boolean islengthest(String str, int num) {
        boolean f = false;
        int length = str.length();
        int total = 0;
        for (int i = 0; i < length; i ++) {
            char c = str.charAt(i);
            if (c == 'G' || c == 'C') {
                total ++;
            }
        }
        if (total == num) {
            f = true;
        }
        return f;
    }
}
发表于 2024-05-17 15:52:39 回复(0)
public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            int n = in.nextInt();
            int max = 0;
            String maxChild = "";
            for(int i=0;i+n<=str.length();i++){
                String child = str.substring(i,i+n);
                String temp = child.replaceAll("C","").replaceAll("G","");
                int len = child.length() - temp.length();
                if(max < len || "".equals(maxChild)){
                    max = len;
                    maxChild = child;
                }
            }

            System.out.println(maxChild);
        }
    }
发表于 2023-09-12 08:19:08 回复(0)
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();
    }
}

发表于 2023-08-11 10:15:19 回复(0)
咱比较菜啊,也就是按照给定的长度来不定的截取字符串,然后在截取到的字符串里计算GC-Ratio,把得到的GC-Ratio值存储在数组里,最后获取数组最大值索引,根据索引截取字符串输出就好。
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String dna = in.next();
            int n = in.nextInt();
            System.out.println(highRate(dna, n));
        }
    }
    public static String highRate(String s, int n) {
        int size = s.length();
        int[] count = new int[size - n + 1];
        for (int i = 0; i < size - n + 1; i++) {
            for (int j = i; j < n + i; j++) {
                if (s.charAt(j) == 'C' || s.charAt(j) == 'G') {
                    count[i]++;
                }
            }
        }
        int index = getMaxIndex(count);
        String res = s.substring(index, index + n);
        return res;
    }
    public static int getMaxIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }

        int maxIndex = 0;
        int maxValue = arr[0];

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxValue) {
                maxValue = arr[i];
                maxIndex = i;
            }
        }

        return maxIndex;
    }
}

发表于 2023-06-18 22:41:19 回复(0)
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));
    }
}

发表于 2023-06-04 18:32:35 回复(0)
//使用前缀和优化,时间复杂度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));

    }
}

发表于 2023-04-27 12:54:45 回复(0)
Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.next();
            int n = in.nextInt();
            int strLen = str.length();
            TreeMap<Integer,String> treeMap = new TreeMap<Integer,String>();
            for(int i=0;i<strLen;i++){
                for(int j=strLen;j>i;j--){
                    if(j-i==n){
                        String cutStr = str.substring(i,j);
                        if(!(cutStr.contains("CG") || cutStr.contains("GC"))){
                            continue;
                        }
                        int num=0;
                        for(int k=0;k<cutStr.length();k++){
                            if(cutStr.charAt(k)=='C' || cutStr.charAt(k)=='G'){
                                num++;
                            }
                        }
                        if(!treeMap.containsKey(num)){
                             treeMap.put(num,cutStr);
                        }
                    }
                }
            }
            System.out.println(treeMap.lastEntry().getValue());
        }
发表于 2023-04-16 19:45:54 回复(0)
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));
        }
    }
}

发表于 2023-04-06 15:50:20 回复(0)
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;
            }
        }
    }
}

发表于 2023-02-28 09:33:46 回复(0)