【华为OD题库-098】DNA序列-java

2023-12-19 21:39:07

题目

一个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等等
数据范围:字符串长度满足1≤n≤1000,输入的字符串只包含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.

思路

维护一个长度为N的滑动窗口,统计窗口内出现C或G的最大次数,返回此时的窗口即可

题解

package hwod;

import java.util.Scanner;

public class DNASeq {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String seq = sc.nextLine();
        int n = sc.nextInt();
        System.out.println(dNASeq(seq, n));
    }

    private static String dNASeq(String seq, int n) {
        int cnt = 0;
        for (int k = 0; k < n; k++) {
            if ("CG".contains(seq.substring(k, k + 1))) {
                cnt++;
            }
        }
        int i = 0, j = i + n - 1;
        int left = i, right = j;
        int maxNum = cnt;
        do {
            if ("CG".contains(seq.substring(++j, j + 1))) {
                cnt++;
            }
            if ("CG".contains(seq.substring(i++, i))) {
                cnt--;
            }
            if (cnt > maxNum) {
                maxNum = cnt;
                left = i;
                right = j;
            }
        } while (j < seq.length()-1);
        return seq.substring(left, right + 1);
    }
}

推荐

如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。

文章来源:https://blog.csdn.net/qq_31076523/article/details/135084132
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。