基因相关性

题意

两条等长 DNA 序列中，相同位置碱基对的比例不低于阈值时输出 yes。

思路

zip(first, second) 配对相同位置字符，累加相等判断，除以序列长度得到比例。

代码

Python代码

python

1
2
3
4
5threshold = float(input())
first = input().strip()
second = input().strip()
same_count = sum(left == right for left, right in zip(first, second))
print("yes" if same_count / len(first) >= threshold else "no")

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#include <cstdio>
#include <cstring>

double rate;
char str1[505];
char str2[505];

int main(){
    scanf("%lf",&rate);
    scanf("%s",str1+1);
    scanf("%s",str2+1);
    int i,cnt=0;
    int len = strlen(str1+1);
    for (i=1;i<=len;i++){
        if( str1[i] ==  str2[i]){
            cnt++;
        }
    }
    if( cnt*1.0 / len >= rate )
        printf("yes");
    else
        printf("no");
    return 0;
}

复杂度

时间复杂度为 $O(n)$ ，除输入字符串外额外空间复杂度为 $O(1)$ 。

总结

等长序列的逐位置比较可直接用 zip 表达。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结