[题目描述]

给定两段基因片段 Gene1 和 Gene2 ,基因片段中由数字和”ACGT”四种字符组成。

每一个字符前都会有相应的数字，这个数字是描述该字符连续出现的数量，例如：”1A2C2G1T” 表示 “ACCGGT”。

返回一个表示这两个基因片段的相似度的字符串，相似度字符串的定义是：”相同位置上的字符相同个数” + “/” + “总字符个数”。

• Gene1 和 Gene2 仅仅包含数字和[“A”, “C”, “G”, “T”]这四种字母
• Gene1 以及 Gene2 的长度范围是: [1, 100000] – 基因片段中字符数量的范围是: [1, 10000000]
• 保证扩充之后的 Gene1 以及 Gene2 的长度相同

在线评测地址: https://www.lintcode.com/problem/gene-similarity/?utm_source=sc-v2ex-fks

示例 1:

输入: Gene1: "2T3G" Gene2: "3T2G" 输出: "4/5" 解释: "TTTGG" 和 "TTGGG" 有 4 处位置上的基因片段相同，所以 "4/5" 

示例 2:

输入: Gene1 = "3T2G4A1C" Gene2 = "6T1A2C1G" 输出: "4/10" 解释："TTTGGAAAAC" 和 "TTTTTTACCG" 有 4 个位置具有相同的基因片段, 所以 "4/10" 

[题解]

将两个字符串当成两段大区间，每个大区间里面有很多个小区间。 每一个小区间主要有两个参数，长度以及字符种类。 利用双指针遍历这两段大区间，统计相同的字符数即可。

class Gene{     private int index;     public int cnt;     private char[] gene;     private char gene_base;           public Gene(){}     public Gene(String a){         cnt = 0;         index = 0;         gene = a.toCharArray();         gene_base = ' ';     }     public void updateGene(){         cnt = 0;         gene_base = ' ';         if(index >= gene.length){             return;         }          while(index < gene.length && gene_base == ' '){             if(gene[index] >= '0' && gene[index] <= '9'){                 cnt = cnt * 10 + (gene[index] - '0');             }              else{                 gene_base = gene[index];             }             index ++;         }     }     public char get_base(){         return gene_base;     } }   public class Solution {     /**      * @param Gene1: a string      * @param Gene2: a string      * @return: return the similarity of two gene fragments      */     public String GeneSimilarity(String Gene1, String Gene2) {         // write your code here         int same_time = 0, cnt_time = 0;          Gene g1 = new Gene(Gene1);         Gene g2 = new Gene(Gene2);          g1.updateGene();         g2.updateGene();          cnt_time += g1.cnt;         while(g1.get_base() != ' ' && g2.get_base() != ' '){             if(g1.get_base() == g2.get_base()){                 same_time += Math.min(g1.cnt, g2.cnt);             }              if(g1.cnt > g2.cnt){                 g1.cnt -= g2.cnt;                 g2.updateGene();             }             else if(g1.cnt < g2.cnt){                 g2.cnt -= g1.cnt;                 g1.updateGene();                 cnt_time += g1.cnt;             }             else{                 g1.updateGene();                 g2.updateGene();                 cnt_time += g1.cnt;             }         }         return String.valueOf(same_time) +  "/" + String.valueOf(cnt_time);     } } 

更多题解参见：https://www.jiuzhang.com/solution/gene-similarity/?utm_source=sc-v2ex-fks

大佬有話說 (0)