首页 > 试题广场 >

DNA序列

[编程题]DNA序列
  • 热度指数：125232 时间限制：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。
算法知识视频讲解
添加回答
Javascript_V8
格陵兰小饼干头像 格陵兰小饼干
let strs = readline(),length = Number(readline()),result = []
for(let i=0;i<strs.length;i++){
    let end = i+length
    let str = strs.slice(i,end)
    if(str.length==length) result.push(str)
}
result = result.map((el,index)=>{
    return {key:el,value:compute_GCRatio(el),index:index}
})
result.sort((a,b)=>{return (b.value-a.value)!=0?b.value-a.value:a.index-b.index})
// print(result.map(el=>el.key+':'+el.value))
print(result[0].key)

function compute_GCRatio(DNA){
    return [...DNA].filter(el=>el=='G'||el=='C').length/DNA.length
}
发表于 2022-07-12 22:25:27 回复(0)
Javascript_V8
独孤剑走偏锋头像 独孤剑走偏锋 
const str = readline()
const N = +readline()
let gcRatio = 0
let res = ''
for (let i = 0; i < str.length - N + 1; i++) {
    const currStr = str.substring(i, i + N)
    const match = currStr.match(/(G|C)/g)
    let newGcRatio = match ? match.length / N : 0
    if (newGcRatio > gcRatio) {
        gcRatio = newGcRatio
        res = currStr
    }
}
print(res)

发表于 2022-07-11 00:44:50 回复(0)
Javascript_V8
牛客478514651号头像 牛客478514651号 
let dna = readline();
let n = parseInt(readline());
// let res = [];
let max = 0,str = "";
for (let i = 0; i < dna.length; i++) {
  if (i + n <= dna.length) {
      let k = dna.substring(i, i + n)
    let t = 0;
    for (j of k) {
      if (j == "C" || j == "G") {
        t++;
      }
    }
    let r = t / k.length;
//     res.push({ k: k, v: r });
    if (r > max) {
      max = r;
      str = k;
    }
  }
}
console.log(str);

发表于 2022-06-09 14:23:58 回复(0)
Javascript_V8
不系之舟1027头像 不系之舟1027
const str = readline()
const n = parseInt(readline())
let maxLen = 0
let res = ''
for(let i = 0;i<str.length+1-n;i++){
   let t = str.substr(i,n)
   let matchs = t.match(/[C|G]/g)
   if(matchs&&matchs.length>maxLen) {
       maxLen = matchs.length
       res = t
   }
}
console.log(res)
发表于 2022-03-15 16:54:26 回复(0)
Javascript_V8
Number_DDD头像 Number_DDD 
function calcGCRatio(dnaStr) {
  let countG = 0;
  let countC = 0;
  dnaStr.split("").forEach((char) => {
    if (char === "G") countG++;
    else if (char === "C") countC++;
  });
  return (countG + countC) / dnaStr.length;
}

function highGCRatioSubInDNA(dnaStr, subLen) {
  let arr = [];
  for (let i = 0; i <= dnaStr.length - subLen; i++) {
    let subDnaStr = dnaStr.slice(i, i + subLen);
    let ratio = calcGCRatio(subDnaStr);
    arr.push(ratio);
    // console.log(`${subDnaStr} : ${ratio}`);
  }
  let maxRatio = Math.max(...arr);
  // console.log(`max ratio : ${maxRatio}`);
  let maxRatioIndex = arr.findIndex((a) => a === maxRatio);
  // console.log(`max ratio index : ${maxRatioIndex}`);
  // console.log(dnaStr.slice(maxRatioIndex, maxRatioIndex + subLen));
  return dnaStr.slice(maxRatioIndex, maxRatioIndex + subLen)
}

let dnaStr;

while(dnaStr = readline()){
    let subLen = parseInt(readline())
    let result = highGCRatioSubInDNA(dnaStr, subLen);
    console.log(result)
}

发表于 2021-12-17 20:43:36 回复(0)
Javascript_V8
我走路带風头像 我走路带風 
var str = '';
var n = 0;
while (str = readline (), n = Number(readline())) {
        var str1=''
        var max= 0
       let start=0
        for (let i= 0;i<str.length-n;i++) {
            
            let str1=str.substr(i,n);
            let count =0;
            for (let j=0;j<str1.length;j++) {
            if (str1[j] =='C'||str1[j] =='G' ){
              count++
            }
        }
          if (count > max) {
            max = count;
            start = i;
          }
        }
        console.log(str.substr(start,n))
}

发表于 2021-11-21 21:18:25 回复(0)
Javascript_V8
Aifomy头像 Aifomy
let line
while(line = readline()) {
    let inputLen = readline()
    let scopeLen = Number(inputLen)
    let len = line.length
    let result = ''
    let ratio = 0
    for(let i=0; i<=len-scopeLen;i++) {
        let sp = line.substr(i, scopeLen)
        let temp = sp.match(/G|C/g)
        let tempRatio = temp ? (temp.length / len) : 0
//         console.log(sp, tempRatio)
        if(tempRatio > ratio) {
            ratio = tempRatio
            result = sp
        }
    }
    console.log(result)
}
发表于 2021-08-11 16:54:42 回复(0)
Javascript_V8
邓洲201731104108头像 邓洲201731104108
太简单了,就不做讨论了 
while(str= readline()){
    let num = readline();
    fun(str.split(""), parseInt(num))
}

function fun(str,num){
    let max=0;
    let maxSeg = [];
    for(let i=0;i<str.length-num+1;i++){
        let seg = str.slice(i,i+num);
        //数CG的数量
        let count = 0;
        for(let j=0;j<num;j++){
            if(seg[j]=="C" || seg[j]=="G"){
                count++
            }
        }
        let ratio = count/num;
        if(ratio>max){
            max=ratio;
            maxSeg = seg;
        }
    }
    //全检查完了
    console.log(maxSeg.join(""))
}


发表于 2021-07-26 05:09:27 回复(0)
Javascript_V8
牛客887360905号头像 牛客887360905号
var str;
while(str=readline()){
    var num=readline();//表示字符串的长度
    var map={
        key:"",
        ratio:0,
    };//用于存储符合条件的
    for(var i=0;i<str.length;i++){
        var newstr=str.substring(i,i+Number(num));
        var reg=/^ACGT|AC|CG|CGT\ig/;
        if(reg.test(newstr)){
            //满足条件 计算比例 和出现的
            var total=0;
            newstr.split("").forEach(function(i){
                if(i=="C"||i=="G"){
                    total+=1;
                }
            })
          var ratio=total/Number(num);
            if(map.key=="" ||map.ratio<ratio){
                map.key=newstr;
                map.ratio=ratio;
            }
        }
    }
    
    console.log(map.key)
}
每次在map里面存储满足条件的
发表于 2021-07-24 15:16:54 回复(0)
Javascript_V8
卫宫士郎头像 卫宫士郎
let str = readline()
let n = parseInt(readline())
let max = 0
let maxStr = ''
for(let i=0;i<=(str.length-n);i++){
    let subStr = str.slice(i,i+n)
    let filterStr = subStr.replace(/[^CG]/g,'')
    let ratio = filterStr.length/subStr.length
    if(ratio>max){
        max = ratio
        maxStr = subStr
    }
}
print(maxStr)

发表于 2021-07-16 00:03:30 回复(0)
提交观点

问题信息

字符串
难度：
13条回答 30622浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号