[leetcode/lintcode 题解] 谷歌面试题：基因相

【题目描述】

给定两段基因片段 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-js-mh0610

示例 1:

输入:
Gene1: "2T3G"
Gene2: "3T2G"
输出: "4/5"

解释: "TTTGG" 和 "TTGGG" 有 4 处位置上的基因片段相同，所以 "4/5"

示例 2:

输入:
Gene1 = "3T2G4A1C"
Gene2 = "6T1A2C1G"
输出: "4/10"

解释："TTTGGAAAAC" 和 "TTTTTTACCG" 有 4 个位置具有相同的基因片段, 所以 "4/10"

【题解】

将两个字符串当成两段大区间，每个大区间里面有很多个小区间。

每一个小区间主要有两个参数，长度以及字符种类。

利用双指针遍历这两段大区间，统计相同的字符数即可。

    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;
    }
}

class Solution 
public {
    /**
     * @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-js-mh0610