首页 > 代码库 > hihoCoder 1052 基因工程 最详细的解题报告
hihoCoder 1052 基因工程 最详细的解题报告
题目来源：基因工程
解题思路：假设基因序列长度为N，则需要计算基因序列前K个和后K个相同所需要的最少改变次数sum。
假设基因序列为 ATACGTCT （即M=8），K=6；interval=M-K=2；
0 1 2 3 4 5 6 7
sq1 A T A C G T C T
sq2 A C G T C T
从上图可以看出，标有相同彩色的字符相同，sq1的下标为0的字符与sq2的下标为0的字符相同，即 sq1[0]==sq1[2]，由此可以得出sq1[i]==sq1[i+interval],其中0<=i<=interval，因此此题可以转化为求要想使字符 sq1[i],sq1[i+interval],sq1[i+interval*2],... 全部变成相同字符，需要改变多少次。解决这个问题就很简单了，只需要分别统计所有字符出现的次数，然后用总数total减去字符出现最多的次数max，即temp=total-max；最后将所有的temp求和。
具体算法（Java版，直接AC）
1 import java.util.Scanner; 2 3 public class Main { 4 5 public static void main(String[] args) { 6 Scanner scanner = new Scanner(System.in); 7 int T = scanner.nextInt(); 8 while (T > 0) { 9 String gene = scanner.next();10 int K = scanner.nextInt();11 int interval = gene.length() - K;12 int sum = 0;13 for (int i = 0; i < interval; i++) {14 int[] count = new int[4];//用来统计出现的次数15 for (int j = i; j < gene.length(); j += interval) {16 if (gene.charAt(j) == ‘A‘) {17 count[0]++;18 } else if (gene.charAt(j) == ‘T‘) {19 count[1]++;20 } else if (gene.charAt(j) == ‘C‘) {21 count[2]++;22 } else if (gene.charAt(j) == ‘G‘) {23 count[3]++;24 }25 }26 int total = 0, max = 0;27 for (int j = 0; j < 4; j++) {28 total += count[j];29 max = max > count[j] ? max : count[j];30 }31 sum += total - max;32 }33 System.out.println(sum);34 T--;35 }36 }37 }
hihoCoder 1052 基因工程 最详细的解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。